莫名每道题文件忘记加.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<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<map> 6 using namespace std; 7 int T,n,a[455],flag; 8 inline int read(){ 9 int ans=0,f=1;char chr=getchar(); 10 while(!isdigit(chr)){if(chr=='-')f=-1;chr=getchar();} 11 while(isdigit(chr)) {ans=(ans<<1)+(ans<<3)+chr-48;chr=getchar();} 12 return ans*f; 13 } 14 inline void kai(){ 15 freopen("split.in","r",stdin); 16 freopen("split.out","w",stdout); 17 } 18 int s1[54],s2[54],l1,l2; 19 bool dfs(int stp){ 20 if(stp>n) return 1; 21 if(l1<=(n>>1)&&(l1<l2&&a[stp]==s2[l1]||l1>=l2)){ 22 s1[l1++]=a[stp]; if(dfs(stp+1)) return 1; --l1; 23 } 24 if(l2<=(n>>1)&&(l1>l2&&a[stp]==s1[l2]||l2>=l1)){ 25 s2[l2++]=a[stp]; if(dfs(stp+1)) return 1; --l2; 26 }return 0; 27 } 28 int main(){ 29 // kai(); 30 T=read(); 31 while(T--){ 32 n=read(); 33 for(int i=1;i<=n;i++) a[i]=read(); 34 l1=l2=1; 35 if(dfs(1)) puts("Good job!!");else puts("What a pity!"); 36 } 37 return 0; 38 }
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<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 #include<cstring> 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<<s; 60 } 61 return 0; 62 }
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<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 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){//插入Trie 21 int x=1,t;//x->jump 22 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])<<depth[x]; 31 int f=0; 32 for(int k=0;k<2;k++){ 33 for(int t=0;t<2;t++) 34 if (nxt[x][t]>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<minn)minn=dif,situ=0; 38 if (dif==minn)situ=(1LL*tot[x]*tot[y]+situ)%MOD; 39 }int solve(int x){ 40 if(x==0)return 0; 41 int s=solve(nxt[x][0])+solve(nxt[x][1]); 42 if(s==0&&tot[x]>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<<ans1<<endl<<ans2<<endl; 53 return 0; 54 }
京公网安备 11010502036488号