中国(北方)大学生程序设计训练赛(第二周) (A B D G)

比赛链接

A题是KMP，先把A拼接到B的后面，然后利用next数组的意义（包括其具体含义，以及失配时的应用），得到ans

 #include<bits/stdc++.h>
 using namespace std;

 char T[],S[];
 int tlen,slen;
 int Next[];

 void getNext()
 {
     int j=,k=-;
     Next[]=-;
     while(j<tlen)
         if(k==-||T[j]==T[k])
             Next[++j]=++k;
         else
             k=Next[k];
 }

 int cal(int x)
 {
     int ret=;
     while(Next[x]!=-)
     {
         x=Next[x];
         ret++;
     }
     return ret;
 }

 int main()
 {
     //freopen("test.txt","r",stdin);
     int TT;scanf("%d",&TT);
     while(TT--)
     {
         scanf("%s%s",S,T);
         int x=min(strlen(S),strlen(T));
         strcat(T,S);
         tlen=strlen(T);
         getNext();
         int len=min(Next[tlen],x);
         int t=cal(len);
         printf("%d\n",t);

     }
 }

A

B算是数学题吧，对于同一个数，如果是整数，怎样操作都不会对difference有影响，而取ceil和取floor则恰好使difference差1，想明白这点就好了

代码自己没写，贴个链接。。 http://blog.****.net/mz839555819/article/details/47844275

D是DP，转移方程见代码

假设：当i'<i时，dp[i']都是确定好的最小的消耗值
.当i为偶数时，dp[i]可能来自三个方向：i-,i+,i/。若来自i+,则i+1必然来自i+，下面比较来自i+2和来自i/2的两种情况。
    dp[i]<-dp[i+]+2x<-dp[(i+)/]+y+2x<-(dp[i/]-x,dp[i/]+x)+y+2x ;
    dp[i]<-dp[i/]+y
显然后者得到的dp[i]更小，故i为偶数情况下，只可能从两个方向转移过来
.当i为奇数时，dp[i]可能来自两个个方向：i-,i+。而i-,i+1都是偶数，这样借用上面的偶数情况下的结论就可以了，即dp[i+]只能由自己或是dp[(i+)/]转移过来。其中由dp[i]转移的情况推给dp[i-]就好了

转移方程如下
　　if(i&1)  dp[i]=min(dp[i-1]+x,dp[(i+1)/2]+x+y)
　　else     dp[i]=min(dp[i-1]+x,dp[i/2]+y)

//最后，哪里有问题的话，欢迎提出来~

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long LL;

 LL n,x,y,ans;
 LL dp[];

 int main()
 {
     //freopen("test.txt","r",stdin);
     while(cin>>n>>x>>y)
     {
         memset(dp,0x3f3f3f3f,sizeof(dp));
         ans=;
         dp[]=x;dp[]=;
         for(int i=;i<=n+;i++)
         {
             if(i&)
                 dp[i]=min(dp[i-]+x,dp[(i+)/]+x+y);
             else
                 dp[i]=min(dp[i-]+x,dp[i/]+y);
         }
         cout<<dp[n]<<endl;
     }
 }

D

G题并查集，不同节点构成连通分量数 在这里等于 不同质因子的构成连通分量数。

具体一些细节： 1是特例； 只有质因子存在于图中时才要考虑该质因子

p.s. 分解质因数，素数筛 心里存个固定的板子真心好~

 #include<bits/stdc++.h>
 using namespace std;
 typedef long long LL;

 const int N=1e6+;
 int not_prime[N+];
 vector<int> prime;
 bool vis[N+];        //图中存在label，使i是label的质因数
 bool done[N+];        //这一连通分量是否已被计数
 int p[N+];
 int T,kase;

 int Find(int x)
 {
     return x==p[x]? x:p[x]=Find(p[x]);
 }
 void Union(int x,int y)
 {
     x=Find(x),y=Find(y);
     p[x]=y;
 }

 void init()
 {
     for(int i=;i<=N;i++)
     {
         if(!not_prime[i])
         {
             //printf("%d=====\n",i);
             prime.push_back(i);
             for(LL j=(LL)i*i;j<=N;j+=i)
                 not_prime[j]=true;
         }
     }
 }
 int init1()
 {
     for(int i=;i<=N;i++)
         p[i]=i;
     memset(vis,false,sizeof(vis));
     memset(done,false,sizeof(done));
 }

 void getFactors(int x)
 {
     vector<int> a;
     for(int i=;prime[i]*prime[i]<=x;i++)
     {
         if(x%prime[i]==)
         {
             a.push_back(prime[i]),vis[prime[i]]=true;
             while(x%prime[i]==) x/=prime[i];
         }
     }
     if(x>) a.push_back(x),vis[x]=true;
     for(int i=;i<a.size();i++)
         Union(a[],a[i]);
 }

 int solve()
 {
     int ret=;
     for(int i=;i<prime.size();i++)
     {
         if(vis[prime[i]])
         {
             int t=Find(prime[i]);
             if(!done[t])
             {
                 ret++;
                 //printf("===%d====",t);
                 done[t]=true;
             }
         }
     }
     return ret;
 }

 int main()
 {
     init();
     //freopen("test.txt","r",stdin);
     scanf("%d",&T);
     while(T--)
     {
         init1();
         int ans=;
         int n;
         scanf("%d",&n);
         for(int i=;i<n;i++)
         {
             int t;
             scanf("%d",&t);
             if(t==)
             {
                 ans++;
                 continue;
             }
             getFactors(t);
         }
         ans+=solve();
         printf("Case %d: %d\n",++kase,ans);
     }
 }

G