20191003 「HZOJ NOIP2019 Round #8」20191003模拟

综述

试题为常州集训2019SCDay2

得分\(100+30(0)+28\)

时之终结

问题描述

HZOJ1310

题解

构造题。

发现部分分有一档是 \(Y\) 是 \(2^x\) ，于是自然想到很多个三角形连到一起。

然后正解就是在这个基础上删边。

\(\mathrm{Code}\)

#include<bits/stdc++.h>
using namespace std;

#define int long long

template <typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),fh=-1;
    else fh=1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    x*=fh;
}

int y,opt=2;
bool eps[1007];

bool deal(){
    int bf=y,cnt=0;
    while(1){
        if(bf&1) return (bf==1);
        ++cnt;bf>>=1;++opt;
    }
    return 0;
}

namespace Subtask_2{
    void solve(){
        printf("%lld %lld\n",opt,opt*(opt-1)/2);
        for(int i=1;i<opt;i++){
            for(int j=i+1;j<=opt;j++) printf("%lld %lld\n",i,j);
        }
    }
}

namespace Subtask_3{
    void solve(){
        int bf=y;opt=2;int tmp=1;
        while(bf){
            eps[opt]=(bf&1);bf>>=1;
            tmp+=(eps[opt]==0);++opt;
        }
        printf("%lld %lld\n",opt,opt*(opt-1)/2-tmp);
        for(int i=1;i<opt;i++){
            for(int j=i+1;j<=opt;j++){
                if(j==opt&&!eps[i]) continue;
                printf("%lld %lld\n",i,j);
            }
        }
    }
}

signed main(){
    freopen("review.in","r",stdin);freopen("review.out","w",stdout);
    read(y);
    if(y==1){
        puts("2 1");puts("1 2");
        fclose(stdin);fclose(stdout);
        return 0;
    }
    if(y==2){
        puts("3 3");puts("1 2");puts("2 3");puts("1 3");
        fclose(stdin);fclose(stdout);
        return 0;
//      3 3 1 2 2 3 1 3
    }
    if(deal()) Subtask_2::solve();
    else Subtask_3::solve();
    return 0;
}

博士之时

问题描述

HZOJ1311

题解

~~想象它是肽链和肽环~~

正难则反

链只能倒过来，环随便转

注意长度相同的链、长度相同的环可以互换。

\(\mathrm{Code}\)

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e5+10;
const int M=5e5+10;
const int mod=1e9+7;
int Num,n,m1,m2,A,B,head[N],cnt,n0,n1,n2,n3,f[N][2],opt,g[N],fac[N],ans,num,tot,bin[N];bool d[N],w[N],vis[N],pd;//f链，g环 
bool cc[20][20],dd[20][20];
struct edge{int nxt,to;}ed[M<<1];
inline void addedge(int x,int y){
    ed[++cnt].to=y;ed[cnt].nxt=head[x];head[x]=cnt;
    ed[++cnt].to=x;ed[cnt].nxt=head[y];head[y]=cnt;}
inline void Add(int &x,int y){x+=y;x-=x>=mod? mod:0;}
inline int MOD(int x){x-=x>=mod? mod:0;return x;}
inline int Minus(int x){x+=x<0? mod:0;return x;}
inline int fas(int x,int p){int res=1;while(p){if(p&1)res=1ll*res*x%mod;p>>=1;x=1ll*x*x%mod;}return res;}
inline void DFS(int u){
    vis[u]=true;num++;int record=0;
    for(register int i=head[u];i;i=ed[i].nxt){
        int v=ed[i].to;if(vis[v]){record++;continue;}
        DFS(v);
    }
    if(!ed[head[u]].nxt)opt=w[u];
    if(record==2)pd=true;
}
int main(){
    freopen("refrain.in","r",stdin);
    freopen("refrain.out","w",stdout);
    scanf("%d",&Num);
    scanf("%d%d%d",&n,&m1,&m2);
    for(register int i=1;i<=m1;i++){
        scanf("%d%d",&A,&B);
        d[A]=true;d[B]=true;addedge(A,B);
    }
    for(register int i=1;i<=m2;i++){
        scanf("%d%d",&A,&B);
        w[A]=true;w[B]=true;addedge(A,B);
    }
    fac[0]=1;for(register int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    bin[0]=1;for(register int i=1;i<=n;i++)bin[i]=2ll*bin[i-1]%mod;
    ans=fac[n];
    for(register int i=1;i<=n;i++)
        if(!vis[i]){
            num=0;pd=false;DFS(i);
            if(num==1)n0++;
            else if(num==2){if(d[i]&&w[i])n3++;else if(d[i])n1++;else n2++;}
            else if(pd)g[num]++;else f[num][opt]++;
        }
    tot=fac[n0];
    tot=1ll*tot*fac[n1]%mod*bin[n1]%mod;
    tot=1ll*tot*fac[n2]%mod*bin[n2]%mod;
    tot=1ll*tot*fac[n3]%mod*bin[n3]%mod;
    for(register int i=3;i<=n;i++)
        if(i&1)tot=1ll*tot*fac[f[i][0]+f[i][1]]%mod;
        else tot=1ll*tot*fac[f[i][0]]%mod*bin[f[i][0]]%mod*fac[f[i][1]]%mod*bin[f[i][1]]%mod;
    for(register int i=4;i<=n;i+=2)
        tot=1ll*tot*fac[g[i]]%mod*fas(i,g[i])%mod;
    ans=Minus(ans-tot);
    printf("%d\n",ans);
    return 0;
}