2018—08—21

竟然没有暴零

110/300

第一题：

poker(题目见个人题库)

心路历程：

先二话不说打了一遍模拟，发现模拟也不怎么好判断；

怀疑是数论....

想不出来，于是逆着模拟——二分答案

反过来check答案

Code：

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int n,b1,a[10000010];bool check(int mid){    int ans=0;    //代表取走的特殊牌的数量     for(int i=1;i<=n;i++)    {        if(a[i]
        
         b1) return 0;        //如果需要取走的特殊牌数量超过了我们有的     }    return 1;}int main(){    scanf("%d%d",&n,&b1);    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);    }    sort(a+1,a+1+n);    //排序一波，满足二分答案的单调性     int l=0,r=1000000000;    //二分模板 的一种     while(r-l>1)    {        int mid=(r+l)/2;        if(check(mid)) l=mid;        //考虑到可能存在更大的答案        //所以在r到mid中间寻找         else r=mid;    }    cout<
         
          <

第二题：

集合

心路历程：

看完题目就知道是并查集...

思路大致是先暴力处理出它是哪个质数的倍数，然后合并

然而我不知道怎么处理他们集合的代表元素（emmmm内牛满面）

于是直接暴力模拟

rt 暴零狗的日常

正解是并查集，处理代表元素就用它的质因子

Code：

#include
    
     #include
     
      using namespace std;int f[1000010],pri[1000010],ans=0;long long a,b,p;int find(int x){    return f[x]==x?x:f[x]=find(f[x]);}int main(){    scanf("%d%d%d",&a,&b,&p);    ans=b-a+1;    //极限情况         for(int i=a;i<=b;i++)    {        f[i]=i;        //并查集初始化     }        //筛选质数     for(int i=2;i<=b;i++)    {        if(pri[i]==0)        //如果是质数         {            if(i>=p)            //当该质数大于p的时候才能合并             {                for(int j=i*2;j<=b;j+=i)                {                    pri[j]=1;                    //标记不是质数                     if(j-i>=a&&find(j)!=find(j-i))                    //如果在范围内且两个集合不同                     {                        f[find(j)]=find(j-i);                        //合并                         ans--;                    }                }            }            else            {                for(int j=i*2;j<=b;j+=i)                {                    pri[j]=1;                }            }        }    }    cout<

燃鹅这并不是AC代码

病狂的模拟赛出题人又加强了数据

正解Code：

//之前的程序是预处理出ans，然后合并集合的时候再减一//现在先预处理出所有数属于的集合，然后ans从0开始累加//同时处理素数的时候，直接将它的区间拿出来计算 #include
    
     #include
     
      using namespace std;int ans=0,f[1000100],pri[1000100];long long a,b,p,leng,lang,hhh;int find(int x){    return f[x]==x?x:f[x]=find(f[x]);}int main(){    scanf("%lld%lld%lld",&a,&b,&p);    leng=b-a+1;    //区间长度         for(int i=1;i<=leng;i++)    {        f[i]=i;    }        pri[1]=1;    //优化素数筛选     for(int i=2;i<=leng-1;i++)    {        if(pri[i]==0)        {            for(int j=2;j<=leng/i;j++)            {                pri[i*j]=1;            }            if(i>=p)            {                if(a%i==0) lang=a;                else lang=a-a%i+i;                hhh=lang-a+1;                hhh=find(hhh);                for(long long j=lang/i+1;j<=b/i;j++)                {                    f[find(i*j-a+1)]=hhh;                }            }        }    }    for(int i=1;i<=leng;i++)    {        if(f[i]==i)        {            ans++;        }    }    cout<

第三题：

卡片游戏

心路历程就不用说了吧，不会就暴力模拟......

正解竟然也是爆搜.........

Code：

#include
    
     #include
     
      #include
      
       using namespace std;int n,m,a[1005];bool flag=0;bool vis[1005];void dfs(int x,int y,int ans)//x代表第几个人取卡片,y代表取到第几张卡片,ans代表分数 {    if(flag) return;    //如果所有人都取完了     if(x==n+1)    {        flag=1;        return;    }    //如果取到了顺序上的最后一张    if(y==m+1)    {        if(ans!=1) return;        //返回此时ans还不为1，就不成立，直接返回         dfs(x+1,1,a[x+1]);        //换下一个人取         return;    }    if(vis[y]==0&&ans%y==0)    //如果还没被取过，而且符合条件     {        vis[y]=1;        dfs(x,y+1,ans/y);        //该名玩家继续取下一张牌 ，同时更新分数         vis[y]=0;    }    dfs(x,y+1,ans);    //取不到这张牌，就往下取，分数不改变 }void solve(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);    }    flag=0;    memset(vis,0,sizeof(vis));    dfs(1,1,a[1]);    if(flag) puts("No");    else puts("Yes");}int main(){    int t;    scanf("%d",&t);    while(t--)    {        solve();    }    return 0;}