| Solved | A | B | C | D |
|---|---|---|---|---|
| 4/4 | O | O | O | O |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
突然看到有套在线$DP$比赛，就顺便打了一下，还挺有趣的。
A
题目描述
给一个$1/2$序列，可以取某一段区间进行翻转操作（该区间所有元素$1$-$2$，$2$-$1$）求一种操作使得最终非严格递增序列最长并求出最大值。
解题思路
枚举待操作区间中的一点$i$。
枚举区间左端点$j$，统计从$[1,j]$中$1$的总个数与$[j+1,i]$中$2$的总个数和的最大值$l$。
枚举区间右端点$j$，统计从$[i,j]$中$1$的总个数与$[j+1,n]$中$2$的总个数和的最大值$r$。
则$l+r$即为最大值。用前缀和计算上述问题。AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
int n,a[N],p[N],q[N],ans;
int main(){
int i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++)p[i]=p[i-1]+(a[i]==1);
for(i=n;i;i--)q[i]=q[i+1]+(a[i]==2);
for(i=1;i<=n;i++){
int r=0,l=0;
for(j=1;j<=i+1;j++)l=max(l,p[j-1]+q[j]-q[i+1]);
for(j=i;j<=n;j++)r=max(r,q[j+1]+p[j]-p[i]);
ans=max(ans,l+r);
}
printf("%d",ans);
return 0;
}
B
题目描述
题干极长，英语阅读能力差，看了好吓人。题目中给的图$AB$之间还有空缺，理解了半天，原来是图错了。
简单概括为一句话：给定先序遍历的路径，求树的形态种数。
解题思路
我们假设$dp[i][j]$是第$i$个字符和第$j$个字符之间的串可能构成的子树形态种数，则答案即为$dp[0][l-1]$。
对于$a[i]==a[j]$，我们先假设这两个点代表同一个节点$a$：
- $dp[i][j]+=dp[i+1][j-1]$，这时$a$只有一个孩子；
- $dp[i][j]+=\sum_{k=i+2}^{j-2}dp[i][k]*dp[k+1][j-1] (a[i]==a[k])$，这时$a$有一个右孩子$[k+1,j-1]$，至少一个左孩子$[i,k]$，这个可以继续当做树根。
其实，在递推的时候保证了这是一个子树节点也就是这两个点代表同一个节点。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
char a[N];
long long dp[N][N];
long long dfs(int l,int r){
if(~dp[l][r])return dp[l][r];
if(l>=r)return 1;
int i;
long long ans=0;
if(a[l]==a[r]&&r>l+1){
ans=dfs(l+1,r-1);
for(i=l+2;i<r-1;i++)if(a[i]==a[l])(ans+=dfs(l,i)*dfs(i+1,r-1))%=w;
}
return dp[l][r]=ans%w;
}
int main(){
int i;
while(~scanf("%s",a)){
memset(dp,-1,sizeof(dp));
printf("%lld\n",dfs(0,strlen(a)-1));
}
return 0;
}
C
题目描述
给定一段序列，让选一个点$x$，每次选定包含$x$这个元素的包含两种相邻颜色的区域，把他们染成任意一种颜色。求最少多少步能够把所有的点染成一个颜色。
解题思路
设$dp[0][l][r]$表示把$[l,r]$区间内的元素染成$color[l]$所需最少步数，
设$dp[1][l][r]$表示把$[l,r]$区间内的元素染成$color[r]$所需最少步数。然后递推就可以了。
AC代码
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using namespace std;
int n,cnt,a[N],dp[2][N][N];
int main(){
int i,j,x;
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&x);
if(!i||x!=a[cnt-1])a[cnt++]=x;
}
n=cnt;
memset(dp,0x3f,sizeof(dp));
for(i=0;i<n;i++)dp[0][i][i]=dp[1][i][i]=0;
for(i=0;i<n;i++){
for(j=i;j>=0;j--){
if(j)dp[0][j-1][i]=min(dp[0][j-1][i],min(dp[0][j][i]+(a[j-1]!=a[j]),dp[1][j][i]+(a[j-1]!=a[i])));
if(i<n-1)dp[1][j][i+1]=min(dp[1][j][i+1],min(dp[0][j][i]+(a[i+1]!=a[j]),dp[1][j][i]+(a[i+1]!=a[i])));
}
}
printf("%d",min(dp[0][0][n-1],dp[1][0][n-1]));
return 0;
}
D
题目描述
用$1$到$4$位二进制数表示$26$个英文字母，其中$0011,0101,1110,1111$没有对应的英文字母。
给定一个$01$串，求每一个前缀包含的所有本质不同的字母串个数。
解题思路
这个题是最有意思的一道题，
刚开始没想过来差点没有AK显然需要离线处理枚举前缀的结尾。
第一思路是，从前缀的结尾$i$往前递推，$num$记录最多能向后延伸几位，$dp[j]$表示$j$之后的字母串种类个数。
那么有$dp[j]=\sum_{k=1}^{num}{dp[j+k]}$，
也就是$[j,j+k-1]$表示的一个字母和$[j+k,i]$表示的一段字母串连成一个更大的字母串。但是要处理本质不同这个问题，有点麻烦。
本来是想用后缀自动机解决，发现没有必要，可以用倒序的字典树直接判重解决。稍微有点细节，直接上代码。
AC代码
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
int trie[2][N*N/2],tot;
int n,a[N],f[N];
int main(){
int i,j,k,num,now,ans=0;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0;i<n;i++){
f[i+1]=1;
now=0;
for(j=i;j>=0;j--){
num=std::min(4,i-j+1);
f[j]=0;
if(num==4&&(rep==3||rep==5||rep==14||rep==15))num--;
for(k=1;k<=num;k++)(f[j]+=f[j+k])%=w;
if(!trie[a[j]][now])(ans+=f[j])%=w,trie[a[j]][now]=++tot;
now=trie[a[j]][now];
}
printf("%d\n",ans);
}
return 0;
}