Reku
0%

Codeforces Round #407 (Div. 2)

Posted on Edited on In Views: Valine:

感觉这场题目出的很不错

A. Anastasia and pebbles 边界情况没考虑好，WA了一次，感觉算是"比较难"的一个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
#include<bits/stdc++.h>
using namespace std;
int n,k;
int w[100010];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		w[i]=max(w[i],0);
		if(w[i]>=2*k)
		{
			ans+=w[i]/(2*k);
			w[i]%=2*k;
		}
		if(w[i]>k)
		{
			ans++;
			w[i]=0;
		}
		else if(w[i]!=0)
		{
			ans++;
			w[i+1]-=k;
		}
	}
	cout<<ans<<endl;
	return 0;
}

B. Masha and geometric depression 这个B真的恶心...WA了大概四五次才过...下次应该把这种边界条件都列在纸上，防止写一写把之前想到的忘了

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
79
80
#include<bits/stdc++.h>
using namespace std;
long long b1,q,l,m;
long long a[100010];
map<long long,int> ha;
int main()
{
	scanf("%lld%lld%lld%lld",&b1,&q,&l,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld",&a[i]);
		ha[a[i]]=1;
	}
	if(abs(b1)>l)
	{
		printf("0\n");
		return 0;
	}
	if(q==0)
	{
		int ans=0;
		if(ha.find(0)==ha.end())
		{
			printf("inf\n");
			return 0;
		}
		else
		{
			if(ha.find(b1)==ha.end()&&abs(b1)<=l) ans++;
			printf("%d\n",ans);
			return 0;
		}
	}
	if(b1==0)
	{
		if(ha.find(0)==ha.end())
		{
			printf("inf\n");
			return 0;
		}
		else
		{
			printf("0\n");
			return 0;
		}
	}
	if(abs(q)==1)
	{
		int ans=0;
		if(ha.find(b1)==ha.end()&&q==1)
		{
			printf("inf\n");
		}
		else if(ha.find(-b1)==ha.end()&&q==-1)
		{
			printf("inf\n");
		}
		else if(ha.find(b1)==ha.end()&&q==-1)
		{
			printf("inf\n");
		}
		else printf("%d\n",ans);
		return 0;
	}
	int ans=0;
	while(1)
	{
		if(abs(b1)>l)
		{
			printf("%d\n",ans);
			return 0;
		}
		if(ha.find(b1)==ha.end())
		{
			ans++;
		}
		b1*=q;
	}
	return 0;
}

C. Functions again 稍微处理一下，就是一个最大子段和的问题，基础dp，但是这个问题是子段和问题的变种，需要处理一下开端点的奇偶性。

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
#include<bits/stdc++.h>
using namespace std;
long long a[110000];
long long b[110000];
long long c[110000];
long long ans1[110000];
long long ans2[110000];
long long ans;
int n;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	ans=-1e18;
	for(int i=1;i<n;i++)
	{
		ans=max(abs(a[i]-a[i+1]),ans);
		if(i%2)
		{
			b[i]=abs(a[i]-a[i+1]);
			c[i]=-b[i];
		}
		else
		{
			c[i]=abs(a[i]-a[i+1]);
			b[i]=-c[i];
		}
	}
	int a1=0;
	int a2=0;
	for(int i=1;i<n;i++)
	{
		if(i%2)
		{
			ans1[i]=max(ans1[i-1]+b[i],b[i]);
			if(i!=1) ans2[i]=ans2[i-1]+c[i];
		}
		else
		{
			ans2[i]=max(ans2[i-1]+c[i],c[i]);
			ans1[i]=ans1[i-1]+b[i];
		}
		ans=max(ans,max(ans1[i],ans2[i]));
	}
	cout<<ans<<endl;
	return 0;
}

D. Weird journey 出的很好的一道题。

给定一个无向图，问有多少种走法，使得所有边都经过，且只有两条边经过一次，其余每条边都经过两次。两种走法不同当且仅当经过一次的两条边的边集不同，无重边，有自环

因为是无向图，我们访问任意一个子图，使得这个子图的每条边都被访问两次，那这个访问的起点和终点一定重合（可以把无向边拆成两条有向边，然后就是个欧拉回路）。知道了这个之后，如果这个图没有自环的话，那么这两个只访问一次的边，一定相邻。 然后自环其实跟在这个点停留是一样的，那么自环可以和任意一条边（包括自环）进行组合就好了。 这个题的坑点是可以有散点存在，只要边联通就好了，比赛的时候就是因为这个，一直WA18

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
#include<bits/stdc++.h>
#define N 1000101  
using namespace std;
long long du[N];
int fa[N];
int h[N];
int ff(int x)
{
	if(fa[x]==x) return x;
	fa[x]=ff(fa[x]);
	return fa[x];
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	long long t=0;
	long long o=0;
	int e;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(x==y) h[x]++,o++;
		else du[x]++,du[y]++,t++;
		e=x;
		if(ff(x)!=ff(y))
		{
			fa[ff(x)]=ff(y);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(ff(i)!=ff(e)&&(ff(i)!=i||h[i]==1))
		{
			cout<<0<<endl;
			return 0;
		}
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=du[i]*(du[i]-1)/2;
	}
	ans+=o*t;
	ans+=o*(o-1)/2;
	cout<<ans<<endl;
	return 0;
}

E. The Great Mixing 本质上，就是取一些数字（取过的数字可以重复取），然后使他们的和等于\(0\) 就是假设取了\(s_1,s_2,....,s_m\)然后就是让\((s_1-n)+(s_2-n)+...+(s_m-n)=0\) 这样的话，就有两种做法： 第一种是正常的dp,就是\(dp[i][j]\)表示取\(i\)个可乐，能不能凑出结果\(j\)，可以用位运算进行优化，时间复杂度是\(O(N^3/32)\)

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
#include<bits/stdc++.h>
using namespace std;
bitset<2001> dp[2];
bool a[1100]={};
int n,k;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
	{
		int t;
		scanf("%d",&t);
		a[t]=1;
	}
	dp[0][1000]=1;
	int no,la;
	no=0;
	la=1;
	int re;
	for(re=1;re<=1000;re++)
	{
		swap(no,la);
		dp[no].reset();
		for(int i=0;i<=1000;i++)
		{
			if(a[i]) dp[no]|=(dp[la]<<i)>>n;
		}
		if(dp[no][1000]==1)
		{
			printf("%d\n",re);
			return 0;
		}
	}
	puts("-1");
	return 0;
}

第二种是每个可能的结果作为一个点，然后转移就是选择哪种可乐，在不同的点上转移，然后找到这个图上最小的环，用BFS就行。复杂度\(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
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
bool a[1100];
int n,k;
int d[3100];
bool v[3100];
vector<int> u;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
	{
		int t;
		scanf("%d",&t);
		if(a[t]==0)
		{
			u.pb(t-n);
			a[t]=1;
		}			
	}
	queue<int> q;
	q.push(1000);
	v[1000]=1;
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		for(auto &i:u)
		{	
			if(t+i<0||t+i>2000) continue;
			if(t+i==1000)
			{
				printf("%d\n",d[t]+1);
				return 0;
			}
			if(v[t+i]==0)
			{
				d[t+i]=d[t]+1;
				v[t+i]=1;
				q.push(t+i);
			}
		}
	}
	puts("-1");
	return 0;
}

实际写了一下，二者时间差距其实不大