[雅礼NOIP2018集训 day4]

感觉状态极差啊，今天居然爆零了

主要是以下原因：

1.又是T1看错题肝了两个小时，发现题意理解错误瞬间心态爆炸

2.T2交错了文件名

3.T3暴力子任务和正解（假的）混在一起，输出了两个答案

都想为自己刷个赞，调不出代码是水平不够，但是这样真的让人无话可说，幸好这只是模拟赛

T1：

题意：给出一个集合，要求把这个集合分成两部分，使得一个集合中的任意一个元素都与对面集合的全部元素都互质

我不知道我为什么会写炸这样的傻X题。。。

显然暴力就是$O(n^2)$枚举，暴力判断gcd是否为1，如果不为1说明要放在一个集合里，并查集维护一下联通块的个数就好，答案就是$s^{联通块的个数}-2$（-2是因为不能出现空集）

考虑优化这个过程

我们枚举质因数，用类似邻接链表的方法把它的倍数连在一起，这样就形成了若干联通块，dfs计算联通块的个数统计答案就好了

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+,maxa=1e6+,mod=1e9+;

int t,n,last[maxa],ans;

bool vis[maxn];

vector<int> g[maxn];

int pcnt,prime[maxa],minp[maxa];

bool prm[maxa];

inline void init(){

    for(int i=;i<maxa;++i){

        if(!prm[i]){

            prime[++pcnt]=i;

            minp[i]=i;

        }

        for(int j=;j<=pcnt&&i*prime[j]<maxa;++j){

            prm[i*prime[j]]=true;

            minp[i*prime[j]]=prime[j];

            if(i%prime[j]==)

                break;

        }

    }

}

void dfs(int pos){

    vis[pos]=true;

    for(int i=;i<g[pos].size();++i)

        if(!vis[g[pos][i]])

            dfs(g[pos][i]);

}

int main(){

//    freopen("x.in","r",stdin);

//    freopen("x.out","w",stdout);

    init();

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        for(int i=;i<=pcnt;++i)

            last[prime[i]]=;

        for(int i=,x;i<=n;++i){

            vis[i]=false;

            g[i].clear();

            scanf("%d",&x);

            while(x>){

                int fac=minp[x];

                while(x%fac==)

                    x/=fac;

                if(last[fac]){

                    g[i].push_back(last[fac]);

                    g[last[fac]].push_back(i);

                }

                last[fac]=i;

            }

        }

        ans=;

        for(int i=;i<=n;++i)

            if(!vis[i])

                ans=ans*%mod,dfs(i);

        printf("%d\n",(ans+mod-)%mod);

    }

    return ;

}

T2：

老实说现在让我再写一次我不会写，因为是看标程才勉强理解的（神奇的bitset啊）

据出题人大大说，暴力是这么写的，dp[i][j][bit]表示从i到j是否存在一条表示可以表示为bit的边。（注意到前导0，办法和昨天那题是一样的，或上1<<len就好，len是路径的长度）

然后我们要优化这个暴力，出题人大大还说了，meet in the middle，我们长度为d的路径拆分成d2=d/2,d1=d-d2两段，注意到d1>=d2

然后我们用bitset搞一波就好

具体看代码注释吧

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<iostream>

#include<bitset>

using namespace std;

const int N=+;

const int maxn=<</+;

int n,m,d;

bitset <N> g0[N],g1[N],dp[maxn],f[maxn];

inline int read()

{

    char ch=getchar();

    int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

int main()

{

//    freopen("y.in","r",stdin);

//    freopen("y.out","w",stdout);

    n=read();m=read();d=read();

    for (int i=,u,v,c;i<=m;i++)

    {

        u=read();v=read();c=read();

        if (c) {g1[u][v]=g1[v][u]=true;}

        else {g0[u][v]=g0[v][u]=true;}

    }

    int d2=d/,d1=d-d2;

    for (int u=n;u>=;u--)

    {

        for (int i=;i<maxn;i++) dp[i].reset();

        dp[][u]=true;//以u为结尾状态是否存在，最开始的1是为了避免前导0

        for (int x=;x<<<d1;x++)

            for (int y=;y<=n;y++)

                if (dp[x][y])

                {

                    dp[x<<]|=g0[y];

                    dp[x<<|]|=g1[y];

                }

        for (int x=;x<<<d1;x++)//一个由u拓展的状态以任何一个结尾都说明以u开头的这个状态是存在的

            f[x][u]=dp[<<d1|x].any();//f数组是以u为开头的状态是否存在

    }

    int ans=;

    for (int i=;i<<<d1;i++)

        for (int j=;j<<<d2;j++)//最后的dp数组状态都是由1为开头拓展而来的

            if ((dp[<<d2|j]&f[i]).any()) ans++;//有任意一个接上就可以累计答案

    printf("%d\n",ans);

    return ;

}

T3：

待填

巴特西

[雅礼NOIP2018集训 day4]

T1：

T2：

T3：

最新文章

热门文章