好久没有做CF了手生的很。。。

 

　　【A.Beautiful Year】

　　

　　题目大意：四位数都不同的年份被称为“Beautiful Year”，问一个给定年份之后最近的“Beautiful Year”

　　模拟就可以了。。。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 int n; 8 bool vis[10]; 9 10 bool check(int x){11     memset(vis,false,sizeof(vis));12     while(x){13         int tmp=x%10;14         x/=10;15         if(vis[tmp]) return false;16         vis[tmp]=true;17     }18     return true;19 }20 21 int main(){22     cin>>n;23     n++;24     while(!check(++n))25     cout<
          
           <
          
         
        
       
      

 

　　【B.Prime Matrix】

　　

　　题目大意：n×m的格子，每次操作可以将一个格子中的数字加1，问最少操作次数使得存在一行或一列全为质数。

　　预处理出每个格子需要多少次操作成为质数，然后求最小行、列和即可。素数筛表即可，注意多筛一些。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 template
          
           inline void gmin(T &a,T b){
    if(a>b)a=b;} 7  8 int n,m,a[1010][1010],prime[101000],tot,ans=2147483647,sum[1010][1010]; 9 bool vis[200010];10 11 int check(int x,int y){12     int t=a[x][y];13     int low=1,high=tot,mid;14     while(low
           
            >1;16 if(prime[mid]
            
             >n>>m;24 for(int i=1;i<=n;i++)25 for(int j=1;j<=m;j++)26 cin>>a[i][j];27 for(int i=2;i<=200010;i++)28 if(!vis[i]){29 for(int j=2;j*i<=200000;j++)30 vis[j*i]=true;31 }32 for(int i=2;i<=200000;i++)33 if(!vis[i]) prime[++tot]=i;34 35 for(int i=1;i<=n;i++)36 for(int j=1;j<=m;j++)37 check(i,j);38 for(int i=1;i<=n;i++){39 int tmp=0;40 for(int j=1;j<=m;j++)41 tmp+=sum[i][j];42 gmin(ans,tmp);43 }44 for(int i=1;i<=m;i++){45 int tmp=0;46 for(int j=1;j<=n;j++)47 tmp+=sum[j][i];48 gmin(ans,tmp);49 }50 cout<
             
              <
             
            
           
          
         
        
       
      

　　【C.Secret】

　　

　　题目大意：n个物品分给k个人，使得每件物品所属的人的编号都不组成等差数列，找出可行方案。

　　这题做法有很多，随便构造一下就可以了。首先如果k*3<=n的话一定是无解的，因为这样肯定存在一个人拥有少于三个物品，那么必然构成等差数列。

　　满足之后就构造。可以1...k 1...k k...1，也可以112233...kk 1..k，and so on

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 int n,m; 8  9 int main(){10     cin>>n>>m;11     if(m*3>n){12         cout<<-1<
         
        
       
      

 

　　【D.Good Substrings】

　　

　　题目大意：存在不多于k个"坏"字母的字符串叫做“Good Substring”，问字符串s中有多少个不同子串是"Good Substring"。

　　复杂度不高，可以预处理前缀和（坏字母个数），然后枚举左右端点，哈希判重，这里直接用map了。。。

1 #include 
      
        2 #include 
       
         3 #include 
        
       
      

 

　　【E.Three Horses】

　　

　　题目大意：有三种转换（具体看题），问有多少种(x,y)，x<=y<=m能通过转换得到所有二元组(1,an)

　　思路来自cxlove blog:

　　从二元组(x,y)的差d=y-x来考虑。

　　对于第一个操作(x,y)->(x+y)，(x,y)->(y,2y-x)->(x,2y-x)->(2x-2,2y-2)->(x-1,y-1)，由此可知一个差为d的二元组(x,y)可以推出所有差为d的二元组(x',y')。

　　对于第二个操作，(x,x+d)->(x/2,x/2+d/2)，d'=d/2，差减半，由此可知一个差为d的二元组可以退出所有差为d^(2k)的所有二元组(x',y')。

　　对于第三个操作，(x,x+d1)&(x+d1,x+d1+d2)->(x,x+d1+d2)，差为两个二元组差的和，由此可知由一个差为d的二元组(x,y)可以推出所有差为kd的二元组(x',y')。

　　综上，我们可以找出所有可以推出目标二元组的可能的“差”，如果差为d，且x<=y<=m,则差为d的可能的初始二元组有m-d个。

1 #include 
      
        2 using namespace std; 3  4 int n,m,a,gcd; 5 long long ans; 6  7 int GCD(int a,int b){ 8     return b==0?a:GCD(b,a%b); 9 }10 11 int main(){12     cin>>n>>m;13     for(int i=0;i
       
        >a;15         gcd=GCD(gcd,a-1);16     }17     while(!(gcd&1)) gcd>>=1;18     for(int i=1;i*i<=gcd;i++)19         if(!(gcd%i)){20             for(int j=i;j
        
         <<=1) ans+=m-j;21             if(i*i