topcoder srm 701 div1 -3-白红宇

topcoder srm 701 div1 -3

阅读量：6546 次

发布时间：2019-06-24

本文共 2207 字，大约阅读时间需要 7 分钟。

1、一堆石子有$n$个，Alice，Bob轮流拿，给定每个人每次可以拿的石子的数目的集合。谁先不能拿谁输。问谁能赢？

思路：对于先手来说，输赢的局面一定是从某个数字开始呈循环状态。所以找到这个循环开始的位置和循环的长度就能判断$n$是不是赢的局面。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           using namespace std;const int N=666;int f[N],g[N];vector
            
              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[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[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

a,vector

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

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 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           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
            
             =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

转载于:https://www.cnblogs.com/jianglangcaijin/p/6853382.html

你可能感兴趣的文章