Codeforces Round 374

发表于 | 更新于

这是第二场codeforces。第一场codeforces因为在做CPU监控，拖了半个小时才开始做题。上次的BC，过了三道题的PT然后全都FST。每次的线上赛都惨不忍睹，不知道这次会怎么样。

A

打开题目吓了一跳，什么鬼？看不懂？然后在我仔细理解题意的时候已经有好多人A了。我吓到了，直接看样例，发现似乎是个编程入门题。

CODE

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define red(x) scanf("%d",&x)
const int MAXN=100+2;
char s[MAXN];
int c[MAXN];
int main()
{
	//freopen("input.txt","r",stdin);
	int n;red(n);
	scanf("%s",s+1);
	int bc=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='B')
			c[s[i]==s[i-1]?bc:++bc]++;
	}
	printf("%d\n",bc);
	if(bc)
	{
		for(int i=1;i<bc;i++)
			printf("%d ",c[i]);
		printf("%d\n",c[bc]);
	}

	return 0;
}

B

题意好理解，公式随便一写。 

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define red(x) scanf("%d",&x)
const int MAXN=100+2;
char s[MAXN];
int cnt[MAXN];
int main()
{
//	freopen("input.txt","r",stdin);
	int n,k;red(n),red(k);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		cnt[strlen(s+1)]++;
	}
	scanf("%s",s+1);
	int ans=strlen(s+1);
	int x=0;
	int sum=0;
	for(int i=1;i<ans;i++)
		sum+=cnt[i];
	x=sum+(sum/k)*5;
	printf("%d ",x+1);
	sum+=cnt[ans];
	x=sum+((sum-1)/k)*5;
	printf("%d\n",x);
	return 0;
}

C

限时+经过城市最多，我一眼就看着像网络流。于是就死磕网络流，怎么都建不出图。于是比赛结束了。看了看大神的代码。什么！直接O(n2)O(n^2)DP？直接SPFA？直接拓扑序？凌乱。。

教训

  • 永远不要质疑CF评测机的速度
  • 在DAG上DP是很正常的思路

CODE

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
72
73
74
75
76
77
78
#include<cstdio>
#include<cstring>
#include<algorithm>
#include <queue>
#define red(x) scanf("%d",&x)
using std::queue;

const int MAXN=5000+10;
struct Edge
{
	int to,v;	
}e[MAXN];int pre[MAXN],id[MAXN],ec=0;
int f[MAXN][MAXN],pr[MAXN][MAXN];
int n,T;
void adde(int _f,int _t,int _v)
{
	e[++ec].to=_t;e[ec].v=_v;pre[ec]=id[_f];id[_f]=ec;
}
int ind[MAXN];
void BFS()
{
	queue<int> Q;
	memset(f,127,sizeof(f));
	f[1][1]=0;
	for(int i=1;i<=n;i++)
		if(!ind[i])
			Q.push(i);
	while(!Q.empty())
	{
		int pres=Q.front();Q.pop();
		for(int i=id[pres],u;i;i=pre[i])
		{
			u=e[i].to;
			if(!--ind[u])
				Q.push(u);
			for(int j=2;j<=n;j++)
				if(f[pres][j-1]<=T)
				{
					if(f[pres][j-1]+e[i].v<f[u][j])
						f[u][j]=f[pres][j-1]+e[i].v,
						pr[u][j]=pres;
				}
		}
	}
}
void print(int pos,int c)
{
	if(!pos)
		return;
	print(pr[pos][c],c-1);
	printf("%d ",pos);
}
int main()
{
	//freopen("input.txt","r",stdin);
	int m;
	red(n),red(m),red(T);
	for(int i=1,t1,t2,t3;i<=m;i++)
	{
		red(t1),red(t2),red(t3);
		adde(t1,t2,t3);ind[t2]++;
	}
	BFS();
	int ans=-1;
	for(int i=n;i;i--)
		if(f[n][i]<=T)
		{
			ans=i;
			break;
		}
	if(ans!=-1)
	{
		printf("%d\n",ans);
		print(pr[n][ans],ans-1);
		printf("%d\n",n);
	}
	return 0;
}