2021-02-20-2月20日题解
问题E¶
题目链接¶
http://icpc.upc.edu.cn/problem.php?cid=2723&pid=4
类似问题：https://www.luogu.com.cn/problem/P2145
题目描述¶
Playing games is fun. For programmers, however, playing games with programs is even more fun. Consider a simple single-user tabletop game as follows. Given a row of sticks, each of which is in one of the seven colors, red (R), green (G), blue (B), cyan (C), magenta (M), yellow (Y), and key (K), the goal of the game is to eliminate all the sticks by repeating the following rules. • Consecutive sticks with the same color can be eliminated if the size of them is not less than m . • The remaining sticks will move closer together. For the case where the row is BBBRRRRRRGGGB and m is 3, all the sticks can be successfully eliminated as the following steps:
- BBBRRRRRRGGGB
- BBBGGGB (By eliminating all red sticks)
- BBBB (By eliminating all green sticks)
- (By eliminating all blue sticks) For the same row of sticks with m = 4, however, it is no way to eliminate all the sticks. Given a row of n sticks and the value of m , your task is to determine if it is possible to eliminate all the sticks.
输入¶
Each test case is given as a string that is the row of sticks and an integer m .
输出¶
Output Yes if it is possible to eliminate all the sticks. Otherwise, output No.
样例输入¶
样例输出¶
提示¶
• 0 <n,m ≤ 500
题解¶
题意：给定7种字符 每有一段连续的长度大于m的相同字符就能消去 问最终整段字符串能否消去
dp[i][j][k] 代表 i到j区间 种类为k的数最大连续子串的长度
dp[i][j][k]全部初始化为-1e9，代表没有任何连续子串。
那么每次区间合并的时候 dp[i][j][k]=max(dp[i][l][k]+dp[l+1][j][k],dp[i][j][k])
如果当前的区间段有能够删除的段，那么其他的字符串的当前区间段的数的非法状态就可以置为0，保证能把断开的字符串接起来。（代表消除相同的元素，该串长度为0）
经过删除合并最后如果剩余一个长度大于m的子串则输出yes，反之输出no
代码¶
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[600][600][8]={0}; ///dp[i][j][k] 代表从i到j值为k的连续个数
map<char,int>mp;
char c[600]={0};
int main()
{
int n,m;
scanf("%s%d",c+1,&m);
n=strlen(c+1);
if(m==1)
{
printf("Yes\n");
return 0;
}
mp['R']=1;
mp['G']=2;
mp['B']=3;
mp['C']=4;
mp['M']=5;
mp['Y']=6;
mp['K']=7;
for(int i=0;i<n+10;i++)
for(int j=0;j<n+10;j++)
for(int k=0;k<8;k++)
dp[i][j][k]=-1e9;
for(int i=1;c[i];i++)
dp[i][i][mp[c[i]]]=1;
for(int len=2;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
int flag=0;
for(int l=i;l<j;l++)
{
for(int k=1;k<=7;k++)
{
dp[i][j][k]=max(dp[i][j][k],dp[i][l][k]+dp[l+1][j][k]);
if(dp[i][j][k]>=m)
flag=1;
}
}
if(flag)
{
for(int k=1;k<=7;k++)
{
if(dp[i][j][k]<0)
dp[i][j][k]=0;
}
}
}
}
for(int k=1;k<=7;k++)
{
if(dp[1][n][k]>=m)
{
printf("Yes\n");
return 0;
}
}
printf("No\n");
return 0;
}
问题 F¶
问题链接¶
http://icpc.upc.edu.cn/problem.php?cid=2723&pid=5
题目描述¶
A company ICPC (International Cable Protection Company) produces a cable protection tool that can be installed in a network switch to monitor whether all cable links connected to it are working properly. Because the protection tool would cause transmission delay, it is not suitable for installation on every switch. Usually network topology consists of two parts: a backbone and several subnets. The switches on the backbone are linked as a ring structure and each backbone switch is treated as a root of a subnet in which the switches are linked as a tree structure. We call such topology as unicyclic topology. Figure 2 shows an example of a unicyclic topology.
Suppose there are n backbone switches and m subnet switches. The switches are numbered by integers from 0 to m + n − 1. Backbone switches are numbered from 0 to n − 1 in clockwise order and the subnet switches are numbered from n to n + m − 1 where the index of each subnet switch is larger than the index of its parent in the rooted tree structure of the subnet it belongs. Figure 3 shows an example of switch numbering.
Please write a program for ICPC to decide the minimum number of switches selected for installing cable protection tools that can monitor all the cable links. Figure 4 shows an optimum solution (circled by ellipses) for the given network.
输入¶
The first line of the input file contains two integers n and m , separated by a space, indicating the numbers of backbone switches and subnet switches respectively. Each of the next n+m lines consists of two integers, separated by a space, indicating the indices of the two end switches of a link.
输出¶
Output the minimum number of switches selected for installing cable protection tools that can monitor all the cable links.
样例输入¶
【样例1】
3 2
0 1
1 2
0 2
1 3
2 4
【样例2】
4 11
0 1
0 3
0 4
0 5
1 2
1 6
2 3
2 9
3 12
6 7
6 8
9 10
10 11
12 13
12 14
样例输出¶
提示¶
• 3 ≤ n ≤ 100000 • 1 ≤ m ≤ 100000
题解¶
树上DP，由于中心处为一个环，可以去除一条边使其变为一棵树，然后通过DP来进行求解答案。
由于去掉了一条边，如果是这条边（假设该边两端点为x和y）能够被覆盖，则分为两种情况，x点被选择和y点被选择，两种情况取最小即为答案。
dp[i][0]代表该点被选择，dp[i][i]代表该点不被选择，则有如下的递推公式
dp[i][0]=min(dp[i][0],dp[i][1])+1,dp[i][1]=dp[i][0]+1
代码¶
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
int to,next;
};
node edge[400500]={0};
int head[400500]={0};
int flag=0,x,y,sum=0;
int dp[400500][2]={0}; ///树上DP，dp[i][0]代表该点被选择，dp[i][1]代表该点没有被选择
void add(int from ,int to)
{
edge[++sum].next=head[from];
edge[sum].to=to;
head[from]=sum;
}
void dfs(int now,int fa)
{
dp[now][0]=dp[now][1]=0;
for(int i=head[now];i;i=edge[i].next)
{
if(edge[i].to!=fa)
{
dfs(edge[i].to,now);
dp[now][0]+=min(dp[edge[i].to][0],dp[edge[i].to][1]);
dp[now][1]+=dp[edge[i].to][0];
}
}
dp[now][0]++;
if(now==y&&flag==2)
dp[now][1]++;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n+m;i++)
{
int s,e;
scanf("%d%d",&s,&e);
if(!flag&&s<n&&e<n) ///在中心环上，选取一条边将其断掉，使其变为一棵树
{
x=s,y=e,flag=1;
continue;
}
add(s,e);
add(e,s);
}
int ans=999999999;
dfs(x,-1); ///代表x点被标记，那么x到y这条边一定满足条件
ans=min(ans,dp[x][0]);
flag=2;
dfs(x,-1); ///代表y点被标记，那么x到y这条边一定满足条件
ans=min(ans,min(dp[x][0],dp[x][1]));
printf("%d\n",ans);
}