首师大附中集训第六天专题测试

专题测试

      第一题：大家都知道田忌赛马的故事，田忌和齐王又要赛马了，他们将各派出 N 匹马，每场比赛输 的一方需要给赢的一方 200 两黄金，平局的话双方都不比出钱，已知所有马的速度，且齐王 的出马顺序永远固定，求田忌的最大收益。

      有一个很显然的贪心算法，就是将它们两个序列从大到小排序，比较当前齐王最大的和田忌最大的。如果田忌的比齐王的大，那么就拿出来比。如果田忌最小的比齐王最小的大，那么直接比。否则田忌最小的就没有用了，而且没有一匹马可以打败齐王的第一匹马。就直接那田忌最小的马去拼。还是很简单的。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int T;
int n;
int a[1010],b[1010];bool cmp(int x,int y){return x>y;
}int main(){freopen("horse.in","r",stdin);freopen("horse.out","w",stdout);scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) scanf("%d",&b[i]);sort(a+1,a+1+n,cmp);sort(b+1,b+1+n,cmp);for(int i=1;i<=n;i++) printf("%d ",a[i]);printf("\n");for(int i=1;i<=n;i++) printf("%d ",b[i]);printf("\n");int tot=0,l1,l2,r1,r2;l1=l2=1,r1=r2=n;for(int i=1;i<=n;i++){if(a[l1]>b[l2]) tot++,l1++,l2++;else if(a[r1]>b[r2]) tot++,r1--,r2--;else{if(a[r1]<b[l2]) tot--;r1--;l2++;}}printf("%d\n",tot*200);}
}

      第二题：给出一个长度为 2N 的数字串，这个数字串中的每一位都是 0-9 的整数，其中，有一 些位置上的数是我们已知的，还有一些位置上的数未知，当且仅当这个数字串满足：前 N 个数码的乘积等于后 N 个数码的乘积的时候，我们称这个数字串是一个好的数字串，给出 一个有若干个位置未知的数字串，请你求出在未知处填上数码之后，使得这个串是一个好 的串的方案数。1≤n≤18

      想到问号并没有那么多（因为只会打暴力），所以就直接暴力枚举这个位置选什么值。然后就完了。

      把左边可能的值插进map里面，然后右边在做的时候进去查就可以了。

      为了优化时间复杂度，我们可以让两边平均，把一边的某些数移到另一边去，变成除法，至于最后答案可能很大，不会超过。直接把它拆成两个long long即可。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;int n,tot1,tot2,data;
char s[40];
long long f1,f2;
long long ans1=0,ans2=0;
long long ci[20],f[20][20],c[20];
const long long block=1e18,b=1e9;
map<long long,int> mp;void times(long long x,long long y){long long x1=x/b,y1=x%b,x2=y/b,y2=y%b;ans1+=x1*x2;ans2+=y1*y2;if(x1*y2>=b) ans1+=x1*y2/b,ans2+=x1*y2%b*b;else ans2+=x1*y2*b;if(x2*y1>=b) ans1+=x2*y1/b,ans2+=x2*y1%b*b;else ans2+=x2*y1*b;ans1+=ans2/block;ans2%=block;
}void dfs_1(int x,long long coef){if(x==data+1){mp[coef]++;return ;}for(int i=1;i<=9;i++){if(x>tot1){if(coef%i!=0) continue;dfs_1(x+1,coef/i);}else dfs_1(x+1,coef*i);}
}void dfs_2(int x,long long coef){if(x==data+1){if(mp[coef]) ans2+=mp[coef];if(ans2>=block) ans1+=ans2/block,ans2%=block;return ;}for(int i=1;i<=9;i++){if(x>tot2){if(coef%i!=0) continue;dfs_2(x+1,coef/i);}else dfs_2(x+1,coef*i);}
}void calc(){ci[0]=1;for(int i=1;i<=n;i++) ci[i]=ci[i-1]*9;c[0]=1;for(int i=1;i<=n;i++) c[i]=c[i-1]*10;f[0][0]=1;for(int i=1;i<=n;i++){f[i][0]=f[i][i]=1;for(int j=1;j<i;j++) f[i][j]=f[i-1][j-1]+f[i-1][j];}long long t1=0,t2=0;if(f1==0) t1=c[tot1];else for(int i=1;i<=tot1;i++) t1+=f[tot1][i]*ci[tot1-i];if(f2==0) t2=c[tot2];else for(int i=1;i<=tot2;i++) t2+=f[tot2][i]*ci[tot2-i];times(t1,t2);
}int main(){
//	freopen("string.in","r",stdin);
//	freopen("string.out","w",stdout);scanf("%d",&n);scanf("%s",s+1);f1=f2=1;for(int i=1;i<=n;i++) if(s[i]!='?') f1*=s[i]-'0';else tot1++;for(int i=2*n;i>=n+1;i--) if(s[i]!='?') f2*=s[i]-'0';else tot2++;if(f1 && f2){data=(tot1+tot2)/2;dfs_1(1,f1);data=tot1+tot2-(tot1+tot2)/2;dfs_2(1,f2);}calc();if(ans1) printf("%lld%lld",ans1,ans2);else printf("%lld",ans2);
}

      然后就过了90。没过的那一组是因为太多问号。

      还是要讲讲正解，其实一开始差不多想出来了，但认为那个递推不能简单转移，所以就丢了。

      考虑最后相同的乘积的质因子只可能有。而且2出现的次数不超过54次，3出现的次数不超过36次，5和7出现的次数不超过18次。那么直接记为把这个数填进i个空格的方案数。转移十分简单，直接枚举下一个数是什么就可以了。

      那么答案就是。

      其中tot1,tot2分别是左右两边的问号数量，a1b1c1d1是左边的已知乘积的质因数拆分，a2b2c2d2同理。

      代码补得有点恶心。（同时注意没有问号的情况）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;int n,tot1,tot2;
char s[45];
long long f1,f2,mmax=1;
long long c[20],ci[20],C[20][20];
long long g[55][37][19][19],h[55][37][19][19];
int t[2][4];
int p[10][4];
long long f[2][55][37][19][19];
long long ans1,ans2;
const long long block=1e18,b=1e9;void times(long long x,long long y){long long x1=x/b,y1=x%b,x2=y/b,y2=y%b;ans1+=x1*x2;ans2+=y1*y2;if(x1*y2>=b) ans1+=x1*y2/b,ans2+=x1*y2%b*b;else ans2+=x1*y2*b;if(x2*y1>=b) ans1+=x2*y1/b,ans2+=x2*y1%b*b;else ans2+=x2*y1*b;ans1+=ans2/block;ans2%=block;
}void prepare(){f[0][0][0][0][0]=1;g[0][0][0][0]=1;h[0][0][0][0]=1;long long coef=1,t1,t2,t3;for(int i=1;i<=max(tot1,tot2);i++){int now=(i&1)^1;coef=1;memset(f[now^1],0,sizeof(f[now^1]));for(int a=0;a<55;a++){if(a) coef*=2;t1=coef;for(int b=0;b<37;b++){if(b) coef*=3;if(coef>mmax) break;t2=coef;for(int c=0;c<19;c++){if(c) coef*=5;if(coef>mmax) break;t3=coef;for(int d=0;d<19;d++){if(d) coef*=7;if(coef>mmax) break;for(int k=1;k<=9;k++) if(p[k][0]<=a && p[k][1]<=b && p[k][2]<=c && p[k][3]<=d)f[now^1][a][b][c][d]+=f[now][a-p[k][0]][b-p[k][1]][c-p[k][2]][d-p[k][3]];}coef=t3;}coef=t2;}coef=t1;}if(i==tot1) for(int a=0;a<55;a++)for(int b=0;b<37;b++)for(int c=0;c<19;c++)for(int d=0;d<19;d++)g[a][b][c][d]=f[now^1][a][b][c][d];if(i==tot2) for(int a=0;a<55;a++)for(int b=0;b<37;b++)for(int c=0;c<19;c++)for(int d=0;d<19;d++)h[a][b][c][d]=f[now^1][a][b][c][d];}while(f1%2==0) f1/=2,t[0][0]++;while(f1%3==0) f1/=3,t[0][1]++;while(f1%5==0) f1/=5,t[0][2]++;while(f1%7==0) f1/=7,t[0][3]++;while(f2%2==0) f2/=2,t[1][0]++;while(f2%3==0) f2/=3,t[1][1]++;while(f2%5==0) f2/=5,t[1][2]++;while(f2%7==0) f2/=7,t[1][3]++;
}void solve(){long long coef=1,t1,t2,t3;for(int a=0;a<55;a++){if(a) coef*=2;t1=coef;for(int b=0;b<37;b++){if(b) coef*=3;if(coef>mmax) break;t2=coef;for(int c=0;c<19;c++){if(c) coef*=5;if(coef>mmax) break;t3=coef;for(int d=0;d<19;d++){if(d) coef*=7;if(coef>mmax) break;if(a>=t[0][0] && b>=t[0][1] && c>=t[0][2] && d>=t[0][3]&& a>=t[1][0] && b>=t[1][1] && c>=t[1][2] && d>=t[1][3])times(g[a-t[0][0]][b-t[0][1]][c-t[0][2]][d-t[0][3]],h[a-t[1][0]][b-t[1][1]][c-t[1][2]][d-t[1][3]]); 	 }coef=t3;}coef=t2;}coef=t1;}
}void calc(){ci[0]=1;for(int i=1;i<=n;i++) ci[i]=ci[i-1]*9;c[0]=1;for(int i=1;i<=n;i++) c[i]=c[i-1]*10;C[0][0]=1;for(int i=1;i<=n;i++){C[i][0]=C[i][i]=1;for(int j=1;j<i;j++) C[i][j]=C[i-1][j-1]+C[i-1][j];}long long t1=0,t2=0;if(f1==0) t1=c[tot1];else for(int i=1;i<=tot1;i++) t1+=C[tot1][i]*ci[tot1-i];if(f2==0) t2=c[tot2];else for(int i=1;i<=tot2;i++) t2+=C[tot2][i]*ci[tot2-i];times(t1,t2);
}int main(){scanf("%d",&n);scanf("%s",s+1);f1=f2=1;for(int i=1;i<=n;i++) if(s[i]=='?') tot1++;else f1*=s[i]-'0';for(int i=n+1;i<=2*n;i++) if(s[i]=='?') tot2++;else f2*=s[i]-'0';for(int i=1;i<=n;i++) mmax*=9;for(int i=1;i<=9;i++){int temp=i;while(temp%2==0) temp/=2,p[i][0]++;while(temp%3==0) temp/=3,p[i][1]++;while(temp%5==0) temp/=5,p[i][2]++;while(temp%7==0) temp/=7,p[i][3]++;}if(f1 && f2){prepare();solve();}calc();if(ans1) printf("%lld%lld",ans1,ans2);else printf("%lld",ans2);
}

      第三题：[NOI2006]网络收费

      题面太长。可以想到把一个配对的收益拆成两个点分别的收益之和。

      那么如果我们知道了这个点到根这条链的状态，我们就可以知道这个点分别取0/1的贡献，直接暴力枚举！

      用记录这个点所管辖的叶子结点取j个B的方案数。dfs时先钦定这个点一个状态，然后再向下dfs，那么到叶子结点的时候就知道一条链的状态，然后就可以得到当前叶子结点分别取0/1的收益，然后向上的时候直接合并就可以了。

      比赛时想到了这个状态，也想到了把收益拆开。但是没有想到怎么转移。我还是太菜了，这种题还是第一次见。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define ls (x<<1)
#define rs (x<<1|1)
using namespace std;int n,m;
int d[1025][11];
int type[1025],c[1025][2],ch[11];
int f[2048][1025];void dfs(int x,int l,int r,int dep){if(dep==n){f[x][0]=c[x-m+1][0];f[x][1]=c[x-m+1][1];for(int i=0;i<n;i++) f[x][ch[i]^1]+=d[x-m+1][i];return ;}int mid=(l+r)/2,mm=(r-l+1)/2;ch[dep]=0;dfs(ls,l,mid,dep+1);dfs(rs,mid+1,r,dep+1);for(int i=0;i<=mm;i++) {f[x][i]=2e9;for(int j=0;j<=i;j++)f[x][i]=min(f[x][i],f[ls][j]+f[rs][i-j]);}ch[dep]=1;dfs(ls,l,mid,dep+1);dfs(rs,mid+1,r,dep+1);for(int i=mm+1;i<=r-l+1;i++){f[x][i]=2e9;for(int j=max(i-mm,0);j<=mm;j++)f[x][i]=min(f[x][i],f[ls][j]+f[rs][i-j]);}
}int LCA(int x,int y){int t=n;while((x>>t) == (y>>t)) t--;return n-t-1;
}int main(){scanf("%d",&n);m=1<<n;for(int i=1;i<=m;i++) scanf("%d",&type[i]);for(int i=1;i<=m;i++) c[i][type[i]]=0,scanf("%d",&c[i][type[i]^1]);int x;for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++){scanf("%d",&x);	int lca=LCA(i+m-1,j+m-1);d[i][lca]+=x;d[j][lca]+=x;}dfs(1,1,m,0);int ans=2e9;for(int i=0;i<=m;i++) ans=min(ans,f[1][i]);printf("%d\n",ans);
}