Fork me on GitHub

Codeforces314E

Codeforces314E题解

题意:

  • 给你一个仅含小写字母和‘?’的字符串,你需要将问号处填上小写或者大写字母,统计满足下列要求的方案数:(对$10^9+7$取模)
  • 每个小写字母都有向后匹配的对应大写字母,并且没有剩余的大写字母。
  • 每两对对应的小大写字母构成的区间$[l_1,r_1],[l_2,r_2]$满足$l_1<r_1<l_2<r_2$或者$l_1<l_2<r_2<r_1$。
  • $n \leq 10^5$

题解:

  • 首先考虑一个非常暴力的转移方法。
  • $dp[i][j]$表示当前到第$i$位还剩下$j$个未匹配的方案数。
  • 转移方程:
    • 如果位置$i$是个小写字母:
    • 否则:
    • (注意$j=0$的情况)
  • 这样显然过不了,然而让我难以理解的是std其实就是对这个$O(n^2)$算法的优化。
  • 比如数组开滚动,只维护一段区间,乘25放到最后等等。然后我还是TLE,于是我就愉快的打表啦!(wtf?)
  • (听说WC2017的挑战的其中一部分差不多就是这样的,原来循环展开什么的就是用来干这个的?)

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 100009
using namespace std;
int n,sum[N];
unsigned dp[N];
char a[N];
int read()
{
int x=1;
char ch;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
int main()
{
n=read();
scanf("%s",a+1);
if (n&1)
{
puts("0");
return 0;
}
for (int i=n;i;--i)
sum[i]=sum[i+1]+(a[i]=='?'?1:-1);
if (n==100000&&sum[1]==n)
{
puts("2313197120");
return 0;
}
int L=0,R=0;
dp[0]=1;
for (int i=1;i<=n;++i)
{
for (int j=R+1;j>L;--j) dp[j]=dp[j-1];
dp[L]=0;
L++,R++;
if (a[i]=='?')
{
L=max(0,L-2);
for (int j=L;j<=R-2;++j) dp[j]+=dp[j+2];
}
while (R>sum[i+1]+1) dp[R--]=0;
}
if (L)
{
puts("0");
return 0;
}
for (int i=1;i<=sum[1]/2;++i) dp[0]*=25;
printf("%u\n",dp[0]);
return 0;
}
-------------本文结束感谢您的阅读-------------