【蓝桥杯2020】 Sereja and Squares

问题描述

Sereja在平面上画了n个点，点i在坐标(i,0)。然后，Sereja给每个点标上了一个小写或大写英文字母。Sereja不喜欢字母"x"，所以他不用它标记点。Sereja认为这些点是漂亮的，当且仅当：
　　·所有的点可以被分成若干对，使得每个点恰好属于一一对之中。
　　·在每对点中，横坐标较小的会被标上小写字母，较大的会被标上对应的大写字母。
　　·如果我们在每对点上画一个正方形，其中已知的一对点会作为正方形的相对的顶点，它们间的线段会成为正方形的对角线，那么在所有画出的正方形中不会有相交或触碰的情况。
　　小Petya擦掉了一些小写字母和所有大写字母，现在Sereja想知道有多少种方法来还原每个点上的字母，使得还原后这些点是漂亮的。
输入格式
　　第一行是一个整数n，表示点的个数。
　　第二行是一个长度为n的字符串，包含小写字母和问号"?"，是按照横坐标递增的顺序的每个点的描述。问号表示这个点的字母被Petya擦掉了。保证输入串不含字母"x"。

输出格式

输出答案对4294967296取模的值。如果没有可行的方案，输出0。

样例输入

4
a???

样例输出

50

样例输入

4
abc?

样例输出

0

样例输入

6
abc???
样例输出
1

数据规模和约定

20个测试点的n分别为：
5,10,20,50,100,
200,500,1000,2000,5000,
10000,20000,30000,40000,50000,
60000,70000,80000,90000,100000.

代码如下

#include <iostream>
#include<algorithm>
#include<cstring>
//这题的重点还在于“输出答案对4294967296取模的值”
//所以用unsigned int
#define LL unsigned int
using namespace std;

//这道题是我最开始想得复杂了
//又或是说没有看清楚题目，罪过罪过
//我们只需要算出需要填小写字母的问号位置和需要填大写字母的问号位置就可以了
//设小写字母问号位置有p个
//大写字母问好位置有q个
//最后就有25*p+q种

int n,p;//p是用来记录小写字母的个数
char c[200010];
LL f[200010]={1};
LL sum=1;

int main()
{
    cin>>n;
    cin>>c+1;
    if(n&1)
        cout<<"0"<<endl;
    else{
        int m=n>>1;//除以2
        for(int i=1;i<=n;i++){
            if(c[i]=='?'){
                //这里最后要用到的是f[m]
                //因为最后累计到了中间的数
                for(int j=i>>1;j>=i-m&&j;j--){
                    f[j]+=f[j-1];
                }
            }else{
                p++;//这是已经存在的小写字母
            }
        }
        //计算问号的小写字母
        for(int i=1;i<=m-p;i++)
            sum*=25;
        sum*=f[m];
        cout<<(LL)sum<<endl;
    }

    return 0;
}