首页 > 代码库 > topcoder srm 701 div1 -3
topcoder srm 701 div1 -3
1、一堆石子有$n$个，Alice，Bob轮流拿，给定每个人每次可以拿的石子的数目的集合。谁先不能拿谁输。问谁能赢？
思路：对于先手来说，输赢的局面一定是从某个数字开始呈循环状态。所以找到这个循环开始的位置和循环的长度就能判断$n$是不是赢的局面。
#include <string.h>#include <stdio.h>#include <vector>#include <string>#include <set>#include <algorithm>#include <map>using namespace std;const int N=666;int f[N],g[N];vector<int> A,B;int dfs1(int x);int dfs2(int x);int dfs2(int x) { if(g[x]!=-1) return g[x]; if(B.size()==0||x<B[0]) return g[x]=0; for(int i=0;i<(int)B.size();++i) { if(x>=B[i]&&!dfs1(x-B[i])) { return g[x]=1; } } return g[x]=0;}int dfs1(int x) { if(f[x]!=-1) return f[x]; if(A.size()==0||x<A[0]) return 0; for(int i=0;i<(int)A.size();++i) { if(x>=A[i]&&!dfs2(x-A[i])) { return f[x]=1; } } return f[x]=0;}int check(int L,int s) { int s1=s; int s2=s+L; int s3=s+L*2; for(int i=0;i<L;++i) { if(f[s1+i]!=f[s2+i]||f[s1+i]!=f[s3+i]) return 0; } return 1;}class PartisanGame {public: string getWinner(int n,vector<int> a,vector<int> b) { memset(f,-1,sizeof(f)); memset(g,-1,sizeof(g)); A=a; B=b; sort(A.begin(),A.end()); sort(B.begin(),B.end()); for(int i=0;i<N;++i) { f[i]=dfs1(i); } if(n<N) { if(f[n]) return "Alice"; return "Bob"; } for(int L=50;L<N/3;++L) { for(int i=1;i+L+L+L<N;++i) { if(check(L,i)) { if(f[i+(n-i)%L]) return "Alice"; return "Bob"; } } } }};
2、给定一个长度为$m$的字符串$s$，按照如下的算法产生一个包含$2^{m}$个串的集合$collection$。将这个集合的字符串排序。输出第$k$个字符串。
start with an empty collectionfor each subset X of the set {1,2,...,m}: take a new string t and initialize it to the given string s for i = 1,2,...,m: if X contains i: reverse the last i characters of t add the string t to the collection思路：对于一个最终的串$result[0~m-1]$来说，$s$的每个字符要么放在当前$result$的开头，要么放在结尾。即令$L=0,R=m-1$，那么:
for each c from s[0] to s[m-1],1 result[L++]=c;2 result[R--]=c
只能二选一。这种构造等同于上面反转最后若干字符的构造方法。设$s$=‘123456‘，1在前，2在后，3在前，4在后，5在前，6在前，那么最后的串为‘135642‘,这对应上面的 $X$集合为${2,3,4,5}$。这样可以用$n^{2}$的方法判断最后的答案有前缀$p$的方案数。$f[i][j]$表示处理完了$s$的前$i$个字符其中$j$个选择了操作1，即放在前面的方案数。
#include <string.h>#include <stdio.h>#include <vector>#include <string>#include <set>#include <algorithm>#include <map>using namespace std;const int N=55;long long f[N][N];long long cal(string s,string p) { memset(f,0,sizeof(f)); f[0][0]=1; int n=(int)s.size(); int m=(int)p.size(); for(int i=0;i<n;++i) { for(int j=0;j<=i;++j) { if(j>=m||s[i]==p[j]) f[i+1][j+1]+=f[i][j]; int r=n-1-(i-j); if(r>=m||s[i]==p[r]) f[i+1][j]+=f[i][j]; } } long long ans=0; for(int i=0;i<=n;++i) ans+=f[n][i]; return ans;}class KthStringAgain {public: string getKth(string s,long long k) { int n=(int)s.size(); string ans=""; for(int i=0;i<n;++i) { for(char c=‘a‘;c<=‘z‘;++c) { long long tmp=cal(s,ans+c); if(tmp<k) { k-=tmp; } else { ans+=c; break; } } } return ans; }};
topcoder srm 701 div1 -3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。