Codeforces Round 455(Div.2)题解(909A~909E)

2018-01-12jzqjzq?

传送门:CF Round455
我这么菜,显然是………………
打的vp啊……

A

题意:给你两个串,取前一个串的任意前缀和后一个串的任意前缀拼接,求字典序最小的串
直接暴力贪心即可

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
char s[2][10010],ans[100010];
int main()
{
scanf("%s%s",s[0]+1,s[1]+1);
ans[1]=s[0][1];int l=strlen(s[0]+1);
int cnt=1;
for(int i=2;i<=l;i++)if(s[0][i]<s[1][1])ans[++cnt]=s[0][i];else break;
ans[++cnt]=s[1][1];
printf("%s",ans+1);
}

B

题意:看样例解释吧……
答案是$(n+1)/2*((n+2)/2)$
代码不贴了

C

题意:python是靠换行和缩进来识别代码的。给你一段未缩进的代码,求出可能的程序种数
DP,设f[i][j]表示前i个语句,第i个语句前有j个缩进(Tab)的种数
转移:f[i][j]=f[i-1][j-1](前面是for)/f[i-1][j]+……+f[i-1][n](前面是正常语句)
做个前缀和就可以在O(n^2)时间转移

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
#define int long long
using namespace std;
const int MOD=1e9+7;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
int n,s[100010],ans,top,f[5010][5010];
signed main()
{
n=read();
for(int i=1;i<=n;i++){
char c[5];scanf("%s",c);
s[i]=1;
if(c[0]=='f')s[i]=0;
}
for(int i=1;i<=n+1;i++)f[0][i]=1;s[0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=i+1;j++){
if(s[i-1])f[i][j]=(f[i-1][n]-f[i-1][j-1]+MOD)%MOD;
else if(j>1)f[i][j]=(f[i-1][j-1]-f[i-1][j-2]+MOD)%MOD;
}
for(int j=1;j<=n+1;j++)f[i][j]=(f[i][j]+f[i][j-1])%MOD;
}
writeln(f[n][n+1]);
return 0;
}

D

题意:给你一个串,对于每一次操作,如果任意一个位置上字符与左右两边不一样的话就会和左右两边一起被删除,问最多会进行多少次操作
分组直接后暴力模拟即可,因为每个字符最多会被删除一次,所以可证复杂度为$O(length)$的

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
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
char s[1000010],c[1000010];
int a[1000010],cnt=0;
int main()
{
scanf("%s",s+1);int l=strlen(s+1);
for(int i=1;i<=l;i++)if(s[i]!=s[i-1]){
c[++cnt]=s[i];a[cnt]=1;
}else a[cnt]++;
int ans=0;
while(cnt>1){
ans++;
for(int i=2;i<cnt;i++)a[i]-=2;
a[1]--;a[cnt]--;
int K=cnt;cnt=0;
for(int i=1;i<=K;i++)if(a[i]>0){
if(c[i]==c[cnt])a[cnt]+=a[i];
else c[++cnt]=c[i],a[cnt]=a[i];
}
}
writeln(ans);
}

E

题意:给你n个点和m条有向边,每个点要被访问到必须先访问到连到这个点的所有点(使其入度为0)。如果这个点权值是1,则需要在副处理器上访问,每次副处理器可以访问所有入度为0的点,求使用副处理器的最少次数使得可以访问所有点
拓扑排序+贪心即可
首先我们把可以用主处理器处理的都处理掉,然后再处理1的点,这样往复做显然是最优的

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <ctime>
#include <map>
#include <queue>
#include <cstdlib>
#include <string>
#include <climits>
#include <set>
#include <vector>
using namespace std;
inline int read(){
int k=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
return k*f;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);putchar(x%10+'0');
}
inline void writeln(int x){
write(x);puts("");
}
int nedge=0,p[200010],nex[200010],head[200010];
int a[100010],n,m,f[100010],rd[100010];
queue<int>q1,q2;
inline void addedge(int a,int b){
p[++nedge]=b;nex[nedge]=head[a];head[a]=nedge;
}
inline void work(){
while(!q2.empty()){
int now=q2.front();q2.pop();
for(int k=head[now];k;k=nex[k]){
rd[p[k]]--;if(rd[p[k]])continue;
if(a[p[k]])q1.push(p[k]);
else q2.push(p[k]);
}
}
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++){
int x=read()+1,y=read()+1;
addedge(y,x);rd[x]++;
}
for(int i=1;i<=n;i++)if(!rd[i]){
if(a[i])q1.push(i);
else q2.push(i);
}
work();int ans=0;
while(!q1.empty()){
ans++;
while(!q1.empty()){
int now=q1.front();q1.pop();
for(int k=head[now];k;k=nex[k]){
rd[p[k]]--;if(rd[p[k]])continue;
if(a[p[k]])q1.push(p[k]);
else q2.push(p[k]);
}
}
work();
}
writeln(ans);
return 0;
}

F

留坑待填……