注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【事后】【CF Round #235 div2】  

2014-03-11 11:40:58|  分类: 某z的日常 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
      这次不是当场做的而是第二天做的。感觉上也没有太大压力吧...div 2前几题挺适合练习C++的...

    A:题目大意:给你一堆数,先求和,然后要你用绝对值不超过X的数加进和里面去,直到变成0,问最少要加几个数。
    直接贪心就可以了嘛...然后傻×的地方在于咱判0的时候用的是 = 而不是 == 然后调试了半天才发现...

#include <cstdio>
using namespace std;

int n,limit,sum=0,tag;

int main()
{
int i,j;
scanf("%d%d",&n,&limit);
for (i=1;i<=n;i++) scanf("%d",&j),sum+=j;
if (sum<0) sum=-sum;
tag=sum%limit==0?0:1;
if (sum==0) printf("%d",sum); {这里写成sum=0了...}
else sum=sum/limit+tag,printf("%d",sum);
scanf("%d",&sum);
return 0;
}


B:题目大意,一个人去打CF的比赛,然后他当前打的比赛是ROUND X,然后给出之前这个人打的k场比赛的ROUND数,这几场比赛中有 DIV 1 和DIV 2 合在一起的,其中DIV 2如果是ROUND X的话 DIV 1就是 ROUND X+1,然后第二种就是只有DIV2,问这个人没有参加的DIV2 最多有多少场,最少有多少场。
也是直接贪心....先考虑在没出现的ROUND全部为DIV2,然后考虑两个插入的,贪心的插就可以了。而且k<=4000,x<=4000,各种都可以过。

#include <cstdio>
#include <cstring>
using namespace std;
int x,k,max,min,sum;
bool join[4010];

int dfs(int u)

    join[u]=true;
    int sum=1;
    if (u<x-1&&!join[u+1]) sum+=dfs(u+1);
    if (u>1&&!join[u-1]) sum+=dfs(u-1);
    return sum;
}

int main()
{
    int i,j,u,v;
    scanf("%d%d",&x,&k);
    memset(join,0,sizeof(join));
    max=x-1;min=0;
    for (i=1;i<=k;i++)
     {
         scanf("%d",&j);
         if (j==1) scanf("%d%d",&u,&v),join[u]=join[v]=true,max-=2;
              else scanf("%d",&u),join[u]=true,max--;
     }
    for (i=1;i<x;i++)
     if (!join[i]) sum=dfs(i),min+=(sum+1)/2;
    printf("%d %d",min,max);
    //scanf("%d",&min);
    return 0;
}


C:题目大意:一群人在摆01的卡片,要求不能有连续两个0和连续三个1,给出0的个数1的个数(10^6)。求一种摆法或者输出无解。(这题有些纠结的是这个答案不一定唯一的话怎么破?)
   构造... 首先,在0的后面加数字必然只能加1,在1的后面加数字得考虑1前面的数。咱们不妨先构造这样一个数列:
   010101010101010101...0101
   显然这个是符合规定的,且1的数目=0的数目,假设1的数目<0的数目-1,显然无解(除了末尾1个0,每个0后面对应一个1)
   那么多出来的1呢?插进去呗...显然每一个1后面可以插1个1,然后开头可以插2个1,这题就这样构造出来了,最多可以插 0的数目+2 个1进去,也就是说 1的数目>0的数目*2+2的话也是没有解的,剩余的情况这样子随便挑个地方插入即可。
   另外看起来此题的确是随便构造好像就可以了....Spcial Judge 的一道题。

#include <cstdio>
#include <cstdlib>
using namespace std;

int n,m;

int main()
{
  scanf("%d%d",&n,&m);
  if (m<n-1||m>n*2+2) {printf("%d",-1);/*system("pause");*/return 0;}
  if (m==n*2+2) printf("%d%d",1,1),m-=2;
  if (m==n*2+1) printf("%d",1),m--;
  while (m)
   {
        if (m>n) printf("%d%d%d",0,1,1),m-=2,n--;
            else printf("%d%d",0,1),m--,n--;
   }
  if (n) printf("%d",0);
  //system("pause");
  return 0;
}


D:题目大意,给出一个不超过10^18的数n,每一次都可以重新排列各个位得到一个新的数(要求首位不是0),求所有可能的数中模m(m<=100)等于0的数的个数。比如 n=104 m=2 那么可行的方案有 104,410 ,140 三种。答案为3.

   一开始的想法是只枚举一半位数,用HASH表存着答案再枚举所有一半位数(挂链表),算出另一半应该的模数,然后去HASH表找答案即可,可观的复杂度就是C(18,9)=40000多,但是这样子的最坏复杂度依旧有些高,因为另一半除了模数相同之外还必须与之配对才行。所以查找的时候实际上还需要特判,这在m很小n很大的情况下就会TLE了。

   然后去找了一下,貌似还有其他的方法,
    http://www.cnblogs.com/acvc/p/3593467.html
    一个就是状压DP(抱歉咱DP非常烂...)(实际上上面的这个HASH表的思想就有些无后效性的感觉)咱们设 f[i][j]表示 余数为 j 状态为i,凑出的方案总数(这里的状态用二进制表示,最多18位,0表示该位的数字没有被用过,1表示该位的数字被用上去了)然后 f[i+1<<j][(a[j]+w*10)%m][k+1]+=f[i][w],(从顶向下刷表即可),然后最后的答案就是 f[1<<n的位数-1][0]。转移的时候枚举一下哪一位没有被选过即可(即哪一位不是1)
   但是这里可能会有算重复的方案,所以用组合计数把它剔除就可以了。
   另外咱DP实在是比较差(魔兽地图的dp各种纠结...)...所以此题还是有co代码的嫌疑的...(感觉还是用p过一遍把)

#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

long long n,p,d,f[1<<18][105],b[19];
int m,a[18],c[10];

int main()
{
    int i,j,k,len;
    scanf("%I64d %d",&n,&m);
    memset(f,0,sizeof(f));
    memset(c,0,sizeof(c));
    memset(b,0,sizeof(b));
    f[0][0]=1;
    len=0;p=n;b[0]=1;d=1;
    while (p) a[len++]=p%10,p=p/10;
    for (i=1;i<=len;i++) b[i]=b[i-1]*i;
    for (i=0;i<len;i++) c[a[i]]++;
    for (i=0;i<10;i++) d*=b[c[i]];{这里的d是重复的情况}
    for (k=0;k<1<<len;k++)
     for (j=0;j<len;j++)
       if (!(k&1<<j))
         for (i=0;i<m;i++)
          if (!(k==0&&a[j]==0))
           f[k|1<<j][(i*10+a[j])%m]+=f[k][i];
    printf("%I64d",f[(1<<len)-1][0]/d);
    //system("pause");
    return 0;
}         


E题:题目大意,给你二维坐标轴的第一象限的一个矩阵,矩阵的左下角为(0,0),右上角为(N,M),然后每一对点能相互看到当且仅当它们的欧几里得距离大于等于L小于等于R,且它们之间的连线没有其他的点,求能互相看到的点对的个数模P后的答案。n<=10^5,m<=10^5,1<=l<=r<=150000。

   首先由于对称性,咱们可以对于每一个点只统计其右上角的点对个数,然后答案乘以2再看情况加上竖直方向的和水平方向的即可(咱们统计右上角的点对,对于所有这种情况的点对,显然都可以在其中一个点统计得到,然后翻转一下这个矩阵,就可以对应所有左上角的点对),然后又由于对称性,咱们可以从上到下来统计。但是这样还是会超时。

   首先来看看怎样两点间不会有点。假设一个点 (x,y),一个点(z,w),它们之间向量为(z-x,w-y)(不妨设z>x,w>y)(咱们只统计右上角的),显然得有gcd(z-x,w-y)=1才行,不然的话可以找到一个更小的向量使得x,y加上这个向量得到一个共线的点,但是它相比(z,w)更小。所以咱们的问题转化成求出本质不同的向量,向量的两个数互质,然后这个向量可以套上的点可以O(1)算出。然后关键是怎么求所有的这个向量。即求10^5以内互质的数对 (x,y),为了方便咱们不妨假设 x<y,这样只需要求一半即可。另一半直接交换下即可,但是这样子依旧还是挺多的.....,然后咱们发现,首先要有l^2<x^2+y^2<r^2,不过这个条件倒没什么,因为数据一暴力就没了。(单单考虑100内的偶数,它们可以和所有的奇数配对,然后枚举下来就10^7了...)(实际上这个就是枚举每一个质因子的1在这个数对的哪一边,2^1000次方左右伤不起TAT)
  
  首先对于向量(x,y),其贡献量为 (n-x+1)*(m-y+1),假设咱们枚举 x,那么 (n-x+1) 已经 固定了,但是感觉y的贡献量还是不能求....但是咱可以发现咱们可以不枚举所有的y,只要求出y的和和y的个数即可。但是这个还是不会....
  于是咱就无耻地去看别人的标程和官方题解了....
  然后咱已经想到最后了.关键在于所有的y怎么求,l*l<=y<=r*r,咱们可以用容斥原理求,咱们分解x的质因数,然后计算L到R中至少包含x的质因数一个的数,求出和,那么剩余的y的就好求了...然后这个量就计算出来了。
    容斥原理还真是神奇咩...

program e; const maxp=10000; maxn=100010; eps=1e-8; var p:array[0..maxp]of longint; v:array[0..maxn]of boolean; pr,st:array[0..maxn]of longint; modd:longint; ans,num,sum,l,r,ll,rr,n,m:int64; function calc(w,l,r:int64):int64; begin l:=l div w; r:=r div w; exit(r-l); end; function calc2(w,l,r:int64):int64; var ll,rr,sum:int64; begin ll:=(l div w+1)*w; rr:=(r div w)*w; sum:=(rr+ll)*((rr-ll)div w+1)shr 1; exit(sum); end; procedure prepare; var i,j:longint; begin fillchar(v,sizeof(v),true); fillchar(pr,sizeof(pr),0); fillchar(p,sizeof(p),0); for i:=2 to n do begin if v[i] then begin inc(p[0]); p[p[0]]:=i; pr[i]:=i; end; for j:=1 to p[0] do begin if i*p[j]<=n then begin v[i*p[j]]:=false;pr[i*p[j]]:=p[j];end; if (i*p[j]>n)or(i mod p[j]=0) then break; end; end; end; procedure init; var j,k,u,v,w:longint; i:int64; fl:double; flag:boolean; begin read(n,m,l,r,modd); prepare; ans:=0; if l=1 then ans:=(ans+(n+1)*m+(m+1)*n)mod modd; ans:=ans mod modd; i:=1; ll:=l; while i<=n do begin if (i*i>=r*r)then break; if (l*l<=i*i) then ll:=1 else ll:=trunc(sqrt(l*l-i*i)); if ll*ll<l*l-i*i then inc(ll); rr:=trunc(sqrt(r*r-i*i)); if rr>m then rr:=m; if ll>rr then begin inc(i);continue;end; fillchar(st,sizeof(st),0); u:=i; while u<>1 do begin flag:=true; for j:=1 to st[0] do if st[j]=pr[u] then flag:=false; if flag then begin inc(st[0]); st[st[0]]:=pr[u]; end; u:=u div pr[u]; end; num:=0;sum:=0; for w:=0 to 1<<st[0]-1 do begin u:=w;j:=1;k:=0;v:=1; while u<>0 do begin if u and 1=1 then begin j:=j*st[v];inc(k);end; inc(v); u:=u shr 1; end; if k and 1=1 then begin num:=num-calc(j,ll-1,rr); sum:=sum-calc2(j,ll-1,rr); end else begin num:=num+calc(j,ll-1,rr); sum:=sum+calc2(j,ll-1,rr); end; end; ans:=(ans+2*(n-i+1)*((num*(m+1)-sum)mod modd))mod modd; inc(i); end; write(ans); end; begin init; end.

  评论这张
 
阅读(29)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017