莫名每道题文件忘记加.in  .out???

修正之后分数：10+100+0=110（太菜了...）

 

T1序列分解

 

题目描述：

老胡有一个长度为n（n为偶数）的序列a，现在他要把这个序列分解成两个长度为n/2的子序列，并满足如下要求：

1.两个子序列中的数在原序列中不能重叠。（即每个数要么在第一个子序列中，要么在第二个子序列中。）

2.两个子序列要完全一样。

然而这个问题对于老胡来说太简单了，所以他想请你来帮忙。

输入：

第一行给出一个T，表示T组数据。

对于每组数据，输入共2行。

第一行包含一个整数n。

第二行给出n个整数表示老胡的序列。

输出：

如果你完成了老胡的任务，他会说"Good job!!" (不包含引号)，否则他会说"What a pity!" (不包含引号)。

样例输入：

2

4

1 1 2 2

6

1 2 3 4 5 6

样例输出：

Good job!!

What a pity!

数据规模：

50%: n<=20

100%: 1<=T<=5，2<=n<=40，-1,000,000,000<=a[i]<=1,000,000,000

考试的时候根本没看到子序列，应该是按顺序而不一定连续的...然后开了一个map开心的过了样例......（竟然还有分...）

　　正解：

　　　　n很小，考虑搜索。

　　　　按顺序搜，考虑第stp个数属于第1个数列还是第2个数列。复杂度O（2^n）,爆炸

　　　　考虑剪枝

　　　　　　1、每个数列的数小于等于总长度一半（睿（ruo）智的剪枝）

　　　　　　2、如果第一个数列有l1个数，第二个数列有l2个数，若l1<l2且a[stp]==a2[l2]则必填入第一个，反之第二个同理

 

则代码如下：

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
        
       
      
     

 

 

T2:010串

题目描述：

如果一个01字符串满足不存在010这样的子串，那么称它为非010串。

求长度为n的非010串的个数。(对1e9+7取模)

输入：

一个数n，表示长度。

输出：

长度为n的非010串的个数。(对1e9+7取模)。

样例输入：

3

样例输出：

7

（解释）:

000

001

011

100

101

110

111

数据规模：

60%: n<=1e7

100%: n<=1e15。

　　考试的时候：这种题肯定找规律啊，想递推式.......10min，放弃，打了个爆搜，弄出了前33个数的规律，然后做差，再做差，再做差……不知怎的就出来一个规律：

f[n]=f[n-1]+f[n-2]+f[n-4]

考完后正确的思路：

　　

　　虽然两个递推式不一样，但是：把f[n-1]用 2f[n-2]-f[n-3]+f[n-4]代入，发现两式一样,嘿嘿

　　然后要一个矩阵加速，不过当时果断先拿了60分，看了一会儿T3，算了我还是先回来做T2吧...

　　然后打矩阵乘法......半天没过...忘记memset初始化矩阵,然而查了好久好久(半途打不出来还先去暴力了一下T3)然后好不容易所有数据都对上了一个矩乘打+查错用了一个小时...还是太弱了...矩乘不熟啊...不过最后还是A掉了

　　代码

　　

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define int long long 7 #define ll long long 8 using namespace std; 9 const ll MOD=1e9+7;10 inline int read(){11     int ans=0,f=1;char chr=getchar();12     while(!isdigit(chr)){
   if(chr=='-')f=-1;chr=getchar();}13     while(isdigit(chr)) {ans=(ans<<1)+(ans<<3)+chr-48;chr=getchar();}14     return ans*f;15 }16 inline void kai(){17     freopen("string.in","r",stdin);18     freopen("string.out","w",stdout);19 }20 struct P{
   int m[10][10];}aa,b,p;21 inline void First(){memset(aa.m,0,sizeof(aa.m));aa.m[0][0]=1;aa.m[0][2]=1;aa.m[1][0]=1;aa.m[1][2]=1;aa.m[2][3]=1;aa.m[3][1]=1;aa.m[3][3]=1;}22 P E(){P e;for(int i=0;i<4;i++){
   for(int j=0;j<4;j++){
   if(i==j)e.m[i][j]=1;else e.m[i][j]=0;}}return e;}23 P ksm(P x,int m){24     P c=E();25     while(m){26         if(m&1){27             P dp;28             memset(dp.m,0,sizeof(dp.m));29             for(int i=0;i<4;i++)30                 for(int j=0;j<4;j++)31                     for(int k=0;k<4;k++)32                         dp.m[i][j]=dp.m[i][j]+x.m[i][k]*c.m[k][j]%MOD,dp.m[i][j]%=MOD;33             c=dp;34         }35         P aa;36         memset(aa.m,0,sizeof(aa.m));37         for(int i=0;i<4;i++)38             for(int j=0;j<4;j++)39                 for(int k=0;k<4;k++)40                     aa.m[i][j]=aa.m[i][j]+x.m[i][k]*x.m[k][j]%MOD,aa.m[i][j]%=MOD;41         x=aa;42         m>>=1;43     }44     return c;45 }46 signed main(){47     kai();48     int n=read();49     if(n==1) cout<<2;50     else if(n==2) cout<<4;51     else{52         n-=2;53         First();54         P aaa=ksm(aa,n);55         int s=0;56         for(int i=0;i<4;i++)57             for(int j=0;j<4;j++)58                 s+=aaa.m[i][j],s%=MOD;59         cout<
         
        
       
      
     

 

 

 

 

 T3：最小生成树

 题目描述：

给定一个长度为n的数组a[1..n]，有一幅完全图，满足(u,v)的边权为a[u] xor a[v]。

求边权和最小的生成树，你需要输出边权和还有方案数对1e9+7取模的值。（注意边权和是不需要取模的）

输入：

第一行一个正整数n。

第二行n个整数表示a[1..n]。

输出：

第一行输出边权和。

第二行输出方案数。

样例输入：

5

2 2 3 4 5

样例输出：

8

6

数据规模：

50%: n<=1000

100%: 1<=n<=10^5，0<=a[i]<2^30。

 思路：Kruskal的思想，江边从小到大插入，但是直接裸的话,就炸了

　　考虑优化：异或很有意思，考虑分每一位考虑，要是异或值最小，相同的位越多越好，考虑Trie字典树，相同部分越多，异或值越小，可以递归处理，直到接下来集合相同，然后用某个叫Pruffer的东西:某个完全图（n个节点）的生成树个数：n^(n-2).也就是说到集合相同之后（异或值肯定都是0）直接知道答案--->推出相同树的个数。代码有点难实现，涉及到多个算法的叠加...

代码如下：

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define int long long 6 using namespace std; 7 inline int read(){ 8     char chr=getchar();    int f=1,ans=0; 9     while(!isdigit(chr)) {
   if(chr=='-') f=-1;chr=getchar();}10     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}11     return ans*f;12 }void write(int x){13     if(x<0) putchar('-'),x=-x;14     if(x>9) write(x/10);15     putchar(x%10+'0');16 }const int M = 1e5+5,MOD=1e9+7;17 int n,a[M],ans1,ans2;18 int ksm(int x,int y){
   int ans=1;for(;y;y>>=1,x=1LL*x*x%MOD)if(y&1)ans=1LL*ans*x%MOD;return ans;}//快速幂19 int nxt[M*30][2],tot[M*30],depth[M*30],flag[M*30],cnt=1;20 inline void Insert(int v){
   //插入Trie21     int x=1,t;//x->jump22     for (int i=29;i>=0;i--){23         t=(v>>i)&1;//取第i位（从高位开始取） 24         if(!nxt[x][t])nxt[x][t]=++cnt;25         x=nxt[x][t];26         depth[x]=i,flag[x]=t;27     }tot[x]++;28 }int minn,situ;//最小差值 29 void Min_Cost_Merge(int x,int y,int dif){30     dif|=(flag[x]^flag[y])<
         
          0&&nxt[y][t^k]>0)    Min_Cost_Merge(nxt[x][t],nxt[y][t^k],dif),f=1;35         if(f)return;36     }37     if (dif
          
           1)ans2=1LL*ans2*ksm(tot[x],tot[x]-2)%MOD;//如果全是0，pruffer-->ans=n^(n-2); 43 if(s==2){44 minn=1<<30,situ=1;45 Min_Cost_Merge(nxt[x][0],nxt[x][1],0);//Merge; 46 ans1+=minn,ans2=1LL*ans2*situ%MOD;47 }return 1;48 }49 signed main(){50 n=read();ans2=1;51 for(int i=1;i<=n;i++) a[i]=read(),Insert(a[i]);52 solve(1);cout<
           
            <
            
             <
             
              <