这三个题写了一天半，第一个题写了大概一整天。出题人劝我从后往前写，我不听，结果T1想了+调了一天QWQWQ

Task 1：序列

【问题描述】

 定义一个“好的序列”为一个长度为M的不下降序列，且序列中的元素均为1-N的正整数。现在我们随机生成一个“好的序列”，每个不同的“好的序列”出现的概率相同，求这个序列中众数的出现次数的期望。

【输入】

 输入文件含有多组数据

 每组数据读入一行两个整数M、N。

【输出】

 对于每组测试数据，输出一行一个实数表示答案，精确到小数点后4位。

【输入输出样例】

 1 5

 2 9

 3 3

 1.0000

 1.2000

 2.2000

【样例解释】

 令x表示序列中众数的出现次数。

 当M = 3，N = 3时可能的序列有：

• 1 1 1(x=3) 1 1 2(x=2) 1 1 3(x=2)

• 1 2 2(x=2) 1 2 3(x=1) 1 3 3(x=2)

• 2 2 2(x=3) 2 2 3(x=2) 2 3 3(x=2)

• 3 3 3(x=3)

 因此x的期望为2.2。

【数据范围】

 1 ≤ M≤ 250，1 ≤ N ≤ 10^9

 每个点的总数据组数不会超过15组。

【提示】

• 题目难度与题目顺序无关。

• 请注意精度问题。 

 关键难点在于如何构建状态。

 这里我们设sum[ k ][ i ][ j ]为众数个数为[ 1 , k ]，数列长度为i，选用元素为j的情况数量之和。

 这样设定的好处，看下面很快就会明白：

• 对于数列本身，我们有这样的划分：
  • 对于某个特定长度的数列，我们考虑把它离散化处理。
    成多块，每块由相同元素组成，一共ki[ 1 , m ]块。
    • 在n个元素中选出k个填入这些块中，离散化的结果和数列本身效果一致，根据乘法原理，直接把可以选的个数C（n,k）与最终答案对应相乘即可。
      • 为了处理答案，我们维护一个前缀和：众数个数<=k的情况下序列总个数的和 
      • 为什么维护前缀和而不是单独求本身某一个？因为求和制约条件更宽松，容易推导和判断。 

​

更新时，累加前面两种情况：

• 上一个选择的元素是最新的元素

• 上一个选择的元素不是最新元素

需要判重的情况：

• 众数个数超过k个的话。

• 如果同一个元素在这里累积了k+1次，就应该去掉。

 所以转移方程就可以得到了：

sum[ k ][ i ][ j ]=sum[ k ][ i - 1 ][ j - 1 ]+sum[ k ][ i - 1 ][ j ]; if( k < i )sum[ k ][ i ][ j ]-=sum[ k ][ i - k - 1 ][ j - 1 ];

 为了保证答案精度，这里使用long double。

 组合数的计算：这里我选择线性递推法.

 由于数据有15组之多，我们选择先进行不同长度情况的预处理，对于不同的可选元素个数只需要搞个组合数上去就可以了。

 复杂度：O（n^3）

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int T,m,n;long double C[255],sum[255][255][255],f[255][255][255],g[255];int main(){    freopen("sequence.in","r",stdin);    freopen("sequence.out","w",stdout);    C[0]=true;    for(register int k=1;k<=251;++k){        sum[k][0][0]=1;        for(register int i=1;i<=251;++i){            for(register int j=1;j<=i;++j){                //i->序列长度 j->总共使用的元素个数 k->众数的个数                //sum存储的就是在当前的众数个数的情况下，可以构造出来的序列个数。                //由于是一步一步递推得到，可以直接适用于所有m∈[1,251]的情况。                 sum[k][i][j]=sum[k][i-1][j-1]+sum[k][i-1][j];                //这里维护的是一个前缀和：求的是众数个数为k情况下序列总个数的和                 //更新时，累加前面两种情况：                     //->上一个选择的元素是最新的元素                    //->上一个选择的元素不是最新元素                 if(k
         
          如果同一个元素在这里累积了k+1次，就应该去掉。 } } } } while(cin>>m>>n){ memset(g,0,sizeof(g)); for(register int i=1;i<=m;++i){ C[i]=C[i-1]*(n-i+1)/i; }//O(m)递推求组合数 for(register int k=1;k<=m;++k){ for(register int j=1;j<=m;++j){ g[k]+=sum[k][m][j]*C[j]; }//计数求和。 } long double ans=0; //g表示的是总共可能出现的情况种类数，是累加 for(register int k=1;k<=m;++k){ ans+=k*(g[k]-g[k-1])/g[m]; } //给出答案 printf("%.4Lf\n",(double)ans); } return 0;}
         
        
       
      
     
    

 T1相当有难度，但T2T3都是大水题。

---

Task 2：游戏

【问题描述】

 小H喜欢玩游戏。她会首先选择一个数?0>2，并在每一轮游戏中修改它。在第i轮游戏中，小H会选择一个质数p<??−1，并令??为最小的p的倍数且大于等于??−1。

 现在已知?2，求最小的可能的?0。

【输入】

 一行一个整数表示?2。

【输出】

 一行一个整数表示答案。

【输入输出样例】

in： 20

out：15

【数据范围】

• 4 ≤ ?2 ≤ 10^6

• 对于100%的数据：保证?2不是质数。

 题面有点绕，其他都还好。

 直接模拟：

• 对H2分解质因数
• 求这个质因数P2和H2对应范围内的合数H1（线性筛预处理）
• 对每个H1找到它的最大质因数，直奔最优解（稍做优化复杂度O（√n））
• 没了，用queue可以简化代码

#include
    
     #include
     
      #include
      
       #include
       
        #define MAXN 1000010using namespace std;int H_2,cnt,ans=MAXN,prime[MAXN];bool vis[MAXN];void Get_Prime(int n){    vis[1]=true;    for(int i=2;i<=n;++i){        if(!vis[i]){            prime[++cnt]=i;        }        for(int j=1;j<=cnt&&i*prime[j]<=n;++j){            vis[i*prime[j]]=true;            if(i%prime[j]==0)break;        }    }}int main(){    freopen("game.in","r",stdin);    freopen("game.out","w",stdout);    scanf("%d",&H_2);    Get_Prime(H_2);    //Get Prime List    queue
        
         Prime2;    int tmp_H2=H_2;    for(int i=1;i<=cnt;++i){        if(tmp_H2==1)break;        if(tmp_H2%prime[i]==0){            while(tmp_H2%prime[i]==0){                  tmp_H2/=prime[i];            }            Prime2.push(prime[i]);        }    }    queue
         
          HH1; while(!Prime2.empty()){ int tmp=Prime2.front(); Prime2.pop(); for(int i=H_2-tmp+1;i<=H_2;++i){ if(vis[i]){ HH1.push(i); } } } while(!HH1.empty()){ int tmp=HH1.front(); HH1.pop(); int tt=tmp; for(int i=1;i<=cnt;++i){ while(tt%prime[i]==0){ tt/=prime[i]; } if(tt==1){//tt除完了 ans=min(ans,tmp-prime[i]+1); break; } if(!vis[tt]){//tt已经是素数 ans=min(ans,tmp-tt+1); break; } } } printf("%d",ans); return 0;}
         
        
       
      
     
    

---

Task 3：棋盘

【问题描述】

 小H和小C在一张n*m的黑白棋盘上下棋。他们轮流进行操作。小H先手。每一次可以选择一个黑色的格子，以这个格子为右下角，棋盘左上角为左上角，将这个矩阵的所有格子的颜色由黑变成白，由白变成黑。找不到一个黑色的格子的人输。不同寻常的是，由于小H和小C是很好的朋友，小H想尽可能的让小C取胜。而小C是个好胜的人，他想尽可能的让自己取胜。那么在此基础上，小H先手，谁能赢呢。

【输入】

 第一行一个整数T，表示有T组数据。

 每组数据第一行两个整数n、m，表示棋盘的大小。接下来n行每行m个字符B（黑色）或者W（白色）表示每个格子的颜色。

【输出】

 对于每组的每个询问，输出一行，“H”或者“C”(不含引号)。表示他会赢。

【输入输出样例】

chess.in：

​ 3 2 2

​ BW

​ WW

​ 2 2

​ WW

​ WW

​ 2 2

​ WB

​ BW

chess.out：

​ H

​ C

​ C

【数据范围】

• 1 ≤ n，m ≤ 100

• 对于100%的数据：1 ≤ T ≤ 100。

 结论题。

• 小H只要不想赢他就不会赢（每次都不选必胜情况）
• 但是存在这样一种情况，小C会绝对赢不了的状态：
  • 对于左上角的棋子，它每次都会被选中。
  • 如果它是B，那么不管变多少次小C都无法掌控它，因为小C无法通过它结束游戏。

 只要小C绝对赢不了那就是小H必胜了。

#include
    
     #include
     
      char ch[110][110];int main(){    freopen("chess.in","r",stdin);    freopen("chess.out","w",stdout);    int T,n,m;    scanf("%d",&T);    while(T--){//      memset(ch,0,sizeof(ch));        scanf("%d%d",&n,&m);        for(register int i=1;i<=n;++i){            for(register int j=1;j<=m;++j){                do{                    ch[i][j]=getchar();                }while(ch[i][j]==' '||ch[i][j]=='\n');                            }        }         if(ch[1][1]=='B'){            puts("H");        }else{            puts("C");        }    }    return 0;}