Sereja and Squares

博主： admin
发布时间：2021 年 02 月 23 日
601次浏览
3 条评论
2469字数
分类：蓝桥杯

# Sereja and Squares

## 题目

资源限制

时间限制：4.0s  内存限制：256.0MB

问题描述

Sereja在平面上画了n个点，点i在坐标(i,0)。然后，Sereja给每个点标上了一个小写或大写英文字母。Sereja不喜欢字母"x"，所以他不用它标记点。Sereja认为这些点是漂亮的，当且仅当：
　　·所有的点可以被分成若干对，使得每个点恰好属于一一对之中。
　　·在每对点中，横坐标较小的会被标上小写字母，较大的会被标上对应的大写字母。
　　·如果我们在每对点上画一个正方形，其中已知的一对点会作为正方形的相对的顶点，它们间的线段会成为正方形的对角线，那么在所有画出的正方形中不会有相交或触碰的情况。
　　小Petya擦掉了一些小写字母和所有大写字母，现在Sereja想知道有多少种方法来还原每个点上的字母，使得还原后这些点是漂亮的。

输入格式

第一行是一个整数n，表示点的个数。
　　第二行是一个长度为n的字符串，包含小写字母和问号"?"，是按照横坐标递增的顺序的每个点的描述。问号表示这个点的字母被Petya擦掉了。保证输入串不含字母"x"。

输出格式

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

样例输入

4
a???

样例输出

样例输入

4
abc?

样例输出

样例输入

6
abc???

样例输出

数据规模和约定

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

## 题目分析

* 可以将本题理解为括号匹配问题，只不过括号有25种罢了
* 可以先将本题看成只有一种括号，最后再乘上$25^m$(m是括号对数)即可
* 括号匹配问题使用动态规划，设$f(i,j)$为到第$i$个位置为止($i$从0开始)，有$j$个右括号。若当前位置是`?`，那么有两种选择：一种是填左括号,那么$f(i,j)=f(i-1,j)$;另一种是填右括号，那么$f(i,j)=f(i-1,j-1)$。综上$f(i,j)=f(i-1,j)+f(i-1,j-1)$
* 另外计算$f(i,j)$时，$j$只需要算到$\lfloor\frac {i+1} 2\rfloor$即可，后续都为0，因为到第$i$个位置的$i+1$个括号中,左括号的个数一定大于右括号的个数，具体计算过程如下：
  $$
  f(*,0)=1

$$
  f(1,1)=f(0,1)+f(0,0)=1

$$
  f(2,1)=f(1,1)+f(1,0)=2

$$
  f(3,1)=f(2,1)+f(2,0)=3

$$
  f(3,2)=f(2,2)+f(2,1)=2

$$
  f(4,1)=f(3,1)+f(3,0)=4

$$
  f(4,2)=f(3,2)+f(3,1)=5

$$
* 实际上计算$f(i,*)$时只需要$f(i-1,*)$的数据，因此可以只使用一个一维数组来保存上一轮次的$f$，依次遍历输入的字符，若当前字符为`?`那么更新这个数组，这时$f(i,j)$变成了$f(j)$，$i$其实就是遍历的字符位置，起初$f(0)$为1，其余位置为0。需要注意的是$j$要从大到小遍历，否则会覆盖要使用的数据。例如$f(5)=f(5)+f(4)$如果先更新了$f(4)$那么$f(4)$就不是$i-1$轮次的数据了

## 代码

### C++

```cpp
#include<iostream>
using namespace std;

int n;
int m; //左括号数目
int n2;
unsigned int f[50004];
char s[100004];

int minimal; //到当前位置至少有几个右括号

unsigned int solve() {
	cin >> n;
	cin >> s;
	if (n % 2)
		return 0;
	f[0] = 1;
	n2 = n / 2;
	for (int i = 0; i < n; ++i) {
		if (s[i] == '?') {
			minimal = i + 1 - n2;
			for (int j = (i + 1) / 2; j >= minimal && j >= 1; --j)
				f[j] += f[j - 1];
		}
		else
			++m;
	
	}
	if (n2 < m) {
		return 0;
	}

for (int i = n2 - m; i > 0; --i)
		f[n2] *= 25;
	return f[n2];
}

int main() {
	cout<<solve();
	return 0;
}
```

### Python

```python
def solve():
    n = int(input())
    s = list(input())
    f = [0] * n
    f[0] = 1
    m = 0
    if n % 2 != 0:
        return 0
    n2 = n // 2

for i in range(n):
        if s[i] == '?':
            j = (i + 1) // 2
            minimal = i + 1 - n2
            if i == n-1:
                f[j]=f[j-1]
                break
            while j >= max(1, minimal):
                f[j] += f[j-1]
                f[j]= f[j] % 4294967296
                j -= 1
        else:
            m += 1

if (n2 < m):
        return 0
    i =  n2 - m
    while i > 0:
        f[n2] *= 25
        f[n2]= f[n2] % 4294967296
        i -= 1
    return f[n2]

print(solve())
```

同样的代码,C++100分而Python只有50分

![](https://blog.super0.xyz/usr/uploads/2021/02/226385959.png)

最后修改：2021 年 02 月 28 日 11 : 17 PM

如果觉得我的文章对你有用，请随意赞赏

3 条评论

noeqnsfyes
December 1st, 2024 at 04:26 am

《三屈式》剧情片高清在线免费观看：https://www.jgz518.com/xingkong/60842.html

回复
zzk
February 24th, 2021 at 11:10 am

你sixxxxx

回复
1. admin
  February 24th, 2021 at 12:38 pm
  
  @zzk
  
  daydaylaughme啊
  
  回复

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Linux 的两种系统调用
评论数： 4
Git 提交代码基础方法
评论数： 4
Sereja and Squares
评论数： 3
非递归下降的预测分析
评论数： 3
原根
评论数： 2

alevykchhj
《豆腐西施杨七巧》国产剧高清在线免费观看：https://ww...
najvtmqvbt
《三屈式》剧情片高清在线免费观看：https://www.jg...
teiqtkzxvy
《豆腐西施杨七巧》国产剧高清在线免费观看：https://ww...
hmdhzzqcuz
《女优粤语》剧情片高清在线免费观看：https://www.j...
svvxjwiglm
《酷儿们》欧美剧高清在线免费观看：https://www.jg...

校园断线重连脚本
评论数： 2
Sticks
评论数： 0
Frist 与 Follow 集合
评论数： 0
全排列
评论数： 0
原根
评论数： 2

Sereja and Squares

admin • 2021 年 02 月 23 日

# Sereja and Squares

## 题目

资源限制

时间限制：4.0s  内存限制：256.0MB

问题描述

输入格式

输出格式

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

样例输入

4
a???

样例输出

样例输入

4
abc?

样例输出

样例输入

6
abc???

样例输出

数据规模和约定

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

## 题目分析

$$
  f(1,1)=f(0,1)+f(0,0)=1

$$
  f(2,1)=f(1,1)+f(1,0)=2

$$
  f(3,1)=f(2,1)+f(2,0)=3

$$
  f(3,2)=f(2,2)+f(2,1)=2

$$
  f(4,1)=f(3,1)+f(3,0)=4

$$
  f(4,2)=f(3,2)+f(3,1)=5

## 代码

### C++

```cpp
#include<iostream>
using namespace std;

int n;
int m; //左括号数目
int n2;
unsigned int f[50004];
char s[100004];

int minimal; //到当前位置至少有几个右括号

for (int i = n2 - m; i > 0; --i)
		f[n2] *= 25;
	return f[n2];
}

int main() {
	cout<<solve();
	return 0;
}
```

### Python

```python
def solve():
    n = int(input())
    s = list(input())
    f = [0] * n
    f[0] = 1
    m = 0
    if n % 2 != 0:
        return 0
    n2 = n // 2

if (n2 < m):
        return 0
    i =  n2 - m
    while i > 0:
        f[n2] *= 25
        f[n2]= f[n2] % 4294967296
        i -= 1
    return f[n2]

print(solve())
```

同样的代码,C++100分而Python只有50分

![](https://blog.super0.xyz/usr/uploads/2021/02/226385959.png)

3 条评论

发表评论 取消回复

Sereja and Squares

发表评论取消回复