首页 > 代码库 > 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 }
View Code

  第二题,并查集,详见食物链。

 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 }
View Code

  第三题,调和级数是收敛的(笑)。标程是数据分治。。哎。我错的很离谱。

 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 }
View Code