首页 > 代码库 > 20140711总结
20140711总结
第一题,傻逼题。但是忘判平方了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 int xx[4000001]; 6 inline void work(int n) 7 { 8 for(int i=1;i*i<=n;i++) 9 {10 if(n%i==0)11 {12 if(i*i==n) xx[n/i]++;13 xx[i]++;14 }15 }16 17 }18 char k;19 inline int getint()20 {21 int ans=0;22 k=getchar();23 while(k==‘\n‘||k==‘ ‘)24 k=getchar();25 while(k!=‘\n‘&&k!=‘ ‘)26 {27 ans=ans*10+(int)k-(int)‘0‘;28 k=getchar();29 }30 return ans;31 }32 int ans=0;33 int main()34 {35 freopen("set.in","r",stdin);36 freopen("set.out","w",stdout);37 int N=getint();38 for(int i=1;i<=N;i++)39 {40 k=getchar();41 getchar();42 if(k&1)43 {44 int t=getint();45 work(t);46 }47 else48 {49 int t=getint();50 ans^=xx[t];51 }52 53 54 }55 printf("%d\n",ans);56 }
第二题,并查集,详见食物链。
1 #include<cstdio> 2 #include<string> 3 #include<cstring> 4 using namespace std; 5 long long father[3000030]; 6 long long Find(long long x) 7 { 8 if(father[x]==x) 9 return x;10 return father[x]=Find(father[x]);11 }12 bool Same(long long L,long long R)13 {14 if(Find(L)==Find(R))15 return true;16 return false;17 }18 void Union(long long L,long long R)19 {20 long long fL,fR;21 fL=Find(L);22 fR=Find(R);23 if(fL==fR)24 return;25 father[fL]=fR;26 }27 int main()28 {29 long long n,k,ans=0;30 scanf("%I64d%I64d",&n,&k);31 for (int i=1;i<=n*3;i++) //扩大为三个节点32 father[i]=i;33 for (int i=1;i<=k;i++)34 {35 long long d,x,y;36 scanf("%I64d%I64d%I64d",&d,&x,&y);37 if (x>n||y>n) ans++;38 else if (d!=1&&d!=2) ans++;39 else if (d==2&&x==y) ans++;40 else if (d==1) //x,y 同类时41 {42 if (Same(x,y+n)) ans++; //x吃y43 else if (Same(x+n,y)) ans++; //y吃x44 else //合并操作45 {46 Union(x,y);47 Union(x+n,y+n);48 Union(x+n+n,y+n+n);49 }50 }51 else //x吃y时52 {53 if (Same(x,y)) ans++; //x,y同类54 else if (Same(x+n,y)) ans++; //y吃x55 else56 {57 Union(x,y+n);58 Union(x+n,y+n+n);59 Union(x+n+n,y);60 }61 }62 }63 printf("%I64d\n",k-ans);64 return 0;65 }
第三题,调和级数是收敛的(笑)。标程是数据分治。。哎。我错的很离谱。
1 #include<cmath> 2 #include<cstdio> 3 using namespace std; 4 long long n; 5 int m; 6 int main() 7 { 8 scanf("%I64d%d",&n,&m); 9 if(n<5000000)10 {11 double ans=0.0;12 for(int i=1;i<=n;i++)13 ans+=1.0/i;14 printf("%d\n",(int)floor(ans*m - (1e-7)));15 }16 else17 {18 printf("%d\n",(int)floor((log(n)+0.57721566490)*m - (1e-7)));19 }20 return 0;21 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。