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 collection
for 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;
}
};