CCPC 2016 杭州站

发表于 |

CCPC2016杭州赛区推出了大中学生对抗赛，于是全场比赛主要看点一是clj封榜前能不能AK，另一个就是看清华学长PK清华学弟。

1001 ArcSoft’s Office Rearrangement

题意

给定a[1..N]，可以合并相邻两项或者将一项拆开成两项，问是否能够得到b[1..K]且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
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream> 
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <algorithm>
#include <stack>
#include <functional>
#include "stdlib.h" 
#include "time.h"
#include <set>
#include <map>
#include <queue>
#include <string.h>
#include <numeric>
#include <set>


#define INF 0x3f3f3f3f
#define MAXN 10010
using namespace std;
#define LL long long

#define SC1(X) scanf("%d", &X)
#define SC2(X, Y) scanf("%d %d", &X, &Y)

int a[100100];

//fail at
//100
//25 25
//6 9 155 6 28 8 19 6 3 6 30 32 18 20 13 75 41 33 26 30 64 17 43 29 33
//Case #1: 34

int main() {
#ifdef __ACM
	//ifstream fin("1.txt");	streambuf *cinbackup;  	cinbackup = cin.rdbuf(fin.rdbuf());
	//freopen("ccpc2016hangzhou.1001.test.dat", "r", stdin);
	//freopen("ccpc2016hangzhou.1001.me.out", "w+", stdout);
#endif
	int T, cas = 0;
	SC1(T);
	while (T--) {
		cas++;
		int n, k;
		SC2(n, k);
		LL s = 0;
		memset(a, 0, sizeof a);
		for (int i = 1; i <= n; i++)
		{
			SC1(a[i]);
			s += 1ll * a[i];
		}
		// 操作次数
		int xx = 0;
		if (s % k == 0) {
			int av = s / k; // 平均
			for (int i = 1; i <= n; i++) {
				if (a[i] < av) {
					int rs = av - a[i]; // 还需要多少人
					for (int j = i + 1; j <= n; j++) {
						xx++; // 合并需要一次操作
						rs -= a[j];
						if (rs < 0) {
							// 人超
							xx ++; // 切掉多的，作为新的a[i]
							// xx ++; // 
							i = j + 1;
							a[i] += -rs; // 多的加到后面
							break;
						}
						else if (rs == 0) {
							// 人数正好
							i = j + 1;
							break;
						}
					}
				}
				else if (a[i] > av) {
					// 人数超了
					// 先切掉够平均数的
					while (a[i] > av) {
						xx++;
						a[i] -= av;
					}
					// 如果多余加到后面
					if (a[i] < av) {
						xx++;
						a[i + 1] += a[i];
					}
				}
			}
			// 如果最后还有没切完的
			if (av != 0) {
				xx += (a[n + 1] / av > 1 ? a[n + 1] / av - 1 : 0);
			}
			printf("Case #%d: %d\n", cas, xx);
		}
		else {
			printf("Case #%d: -1\n", cas);
		}
	}
#ifdef __ACM
	//int iwannastop;
	//scanf("%d", &iwannastop);
	//system("pause");
#endif
}

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N=1e5+5;
int a[N];

int main()
{
	int T;
	scanf("%d",&T);
	for (int t=1;t<=T;t++) {
		int n,k;
		scanf("%d%d",&n,&k);
		ll sum=0;
		for (int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
			sum+=1LL*a[i];
		}
		if (sum%k) {
			printf("Case #%d: -1\n",t);
			continue;
		}
		ll avg=sum/k;
		sum=0;int pre=0,ans=0;
		for (int i=1;i<=n;i++) {
			sum+=a[i];
			if (sum%avg==0) {
				ans+=(i-pre-1)+(sum/avg-1);
				sum=0;pre=i;
			}
		}
		printf("Case #%d: %d\n",t,ans);
	}
	return 0;
}

1002 Bomb

题意

平面上给了n个炸弹，引爆其中的炸弹i需要代价ci，一个炸弹爆炸会使得它半径ri内的炸弹爆炸，以此类推。求使得所有炸弹爆炸需要的最小代价。

思路

强连通缩点，然后找入度为0的所有的联通块，然后在联通块内找一个花费最小的即可。
找联通快和寻找花费最小代价的点可以在tarjan的弹栈操作完成。
特别地，寻找入度为0的所有连通块是通过遍历所有的边然后比较(u,v)是否属于同一联通块实现的实现的。
此外注意引爆具有有向性。
代码

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N=1010,INF=1<<30;
struct Bomb {
	int x,y,r,c;
} a[N];
struct Edge {
	int go,st,next;
} eg[N*N];
int Low[N],DFN[N],Stack[N],Belong[N],val[N];
int Index,top,scc;
int head[N],tot,in[N];
bool Instack[N],vis[N];

void adde(int x,int y)
{
	eg[++tot].go=y;
	eg[tot].st=x;
	eg[tot].next=head[x];
	head[x]=tot;
}

ll sqr(ll x)
{
	return x*x;
}

/*判断 b 炸弹能否被 a 炸弹引爆 
*/
bool bina(const Bomb &a,const Bomb &b)
{
	return sqr(b.x-a.x)+sqr(b.y-a.y)<=sqr(a.r);
}

/* Tarjan 模板,求强连通分量 
*/
void Tarjan(int u)
{
	int v;
	Low[u] = DFN[u] = ++Index;
	Stack[top++] = u;
	Instack[u] = true;
	for(int i = head[u]; i; i = eg[i].next) {
		v = eg[i].go;
		if( !DFN[v] ) {
			Tarjan(v);
			if( Low[u] > Low[v] )Low[u] = Low[v];
		} else if(Instack[v] && Low[u] > DFN[v])
			Low[u] = DFN[v];
	}
	if(Low[u] == DFN[u]) {
		scc++;
		//对该连通分量的权值赋初值 
		val[scc]=INF;
		do {
			v = Stack[--top];
			Instack[v] = false;
			Belong[v] = scc;
			//连通分量的权值为最小的点权 
			val[scc]=min(val[scc],a[v].c);
		} while (v!=u);
	}
}

int main()
{
	int T;
	scanf("%d",&T);
	for (int t=1;t<=T;t++) {
		int n;
		scanf("%d",&n);
		tot=scc=Index=top=0;
		memset(in,0,sizeof(in));
		memset(head,0,sizeof(head));
		for (int i=1;i<=n;i++) {
			scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].r,&a[i].c);
		}
		//对于能被 i 引爆的所有 j , 加有向边 <i,j> 
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=n;j++) {
				if (i!=j) {
					if (bina(a[i],a[j])) {
						adde(i,j);
					}
				}
			}
		}
		memset(DFN,0,sizeof(DFN));
		memset(Instack,0,sizeof(Instack));
		for(int i=1;i<=n;i++) {
			if(!DFN[i]) {
				Tarjan(i);
			}
		}
		//对每个连通分量统计入度 
		for (int i=1;i<=tot;i++) {
			//如果第 i 条边的两端不属于同一个连通分量 
			if (Belong[eg[i].st]!=Belong[eg[i].go]) {
				//则对终点所在的连通分量增加入度
				//因为最后只判断入度是否为 0 , 入度的具体度数没有明确含义 
				in[Belong[eg[i].go]]++;
			}
		}
		int ans=0;
		for (int i=1;i<=scc;i++) {
			if (in[i]==0) {
				ans+=val[i];
			}
		}
		printf("Case #%d: %d\n",t,ans);
	}
}

1003 Car

题意

一辆车保持不减速运动（速度为实数），时间从0开始，在某些整数时刻记录下车的位置（整数递增），求最少需要多长时间达到最后一个记录点

思路

这道题目的坑主要是卡精度，求ceil得时候要减去eps=1e-7。或者直接用分数类也能过。
代码

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 <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const double eps=1e-7;
int a[100010];

int main()
{
	int T,n;
	scanf("%d",&T);
	for (int cas=1;cas<=T;cas++) {
		scanf("%d",&n);
		for (int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
		}
		a[0]=0;
		int t=1,ans=0;
		long double lastv=1e30;
		for (int i=n-1;i>=0;i--) {
			t=ceil((a[i+1]-a[i]-eps)/lastv);
			lastv=1.0*(a[i+1]-a[i])/t;
			ans+=t;
		}
		printf("Case #%d: %d\n",cas,ans);
	}
	return 0;
}

1006 Four Operations

题意

在一个最多20位的整数里面按顺序插入+、-、*、/（整除）四个运算符，要求结果最大。

思路

要注意整数有20位，使用long long。
代码

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 <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const ll INF=1LL<<60;
char s[50];

int main()
{
	int T;
	scanf("%d",&T);
	for (int t=1;t<=T;t++) {
		scanf("%s",s);
		int n=strlen(s);
		ll ans=-INF;
		//枚举除号的位置 
		for (int i=n-1;i>=4;i--) {
			int j=i;
			ll x=0;
			for (int k=i;k<n;k++) {
				x=x*10+s[k]-'0';
			}
			//乘号两边必然是个位数 
			x=(s[j-1]-'0')*(s[j-2]-'0')/x;
//			printf("X: %lld\n",x);
			//加号必然在 abcd+e 或者 a+bcde 
			ll y=0;
			for (int k=1;k<j-2;k++) {
				y=y*10+s[k]-'0';
			}
			ll ss=s[0]-'0'+y;
			y=0;
			for (int k=0;k<j-3;k++) {
				y=y*10+s[k]-'0';
			}
			ss=max(ss,y+s[j-3]-'0');
//			printf("SS: %lld\n",ss);
			ans=max(ans,ss-x);
		}
		printf("Case #%d: %lld\n",t,ans);
	}
}