   我航2016ACM/ICPC校赛的题解 - Dosk技术站

我航2016ACM/ICPC校赛的题解

Dec 21 2016

我航2016ACM/ICPC校赛的题解

比赛重现在我开发的oj上了，比赛的时候也是用的这个oj，支持几百人比赛没啥问题的稳定性很好0.0，一共五个学校参赛

我的oj传送门^_^

A 说反话，赤裸裸的水题，坑在于空格可能是多个

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include

int reverse() {
char ch = getchar();
int rs;

if (ch == ‘ ‘)
return 1;
if (ch == EOF)
return 0;

rs = reverse();
putchar(ch);
return rs;
}

int main() {
while (reverse() != 0) {
putchar(‘ ‘);
}
return 0;
}

B 优雅的阶乘，这不用说了吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include

using namespace std;

int main()
{
int n;
while (cin » n)
{
int ret = 1, jie = 1;
for (int i=2;i<=n;++i)
ret += jie *= i;
cout « ret « endl;
}
return 0;
}

C 不优雅的阶乘，可以用Java做偷懒–

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

#include #include

void mul(int *n, int m)
{
for(int i = 1; i <= n[0]; i++)
n[i] *= m;
for(int i = 1; i < n[0]; i++) {
if(n[i] >= 10000) {
n[i + 1] += n[i] / 10000;
n[i] %= 10000;
}
}
if(n[n[0]] >= 10000) {
n[n[0] + 1] = n[n[0]] / 10000;
n[n[0]++] %= 10000;
}
}

void add(int *n, int *m)
{
for(int i = 1; i <= m[0]; i++) {
if(i <= n[0]) n[i] += m[i];
else n[i] = m[i];
}
if(n[0] < m[0]) n[0] = m[0];
for(int i = 1; i < n[0]; i++) {
if(n[i] >= 10000) {
n[i + 1] += n[i] / 10000;
n[i] -= 10000;
}
}
if(n[n[0]] >= 10000) {
n[n[0] + 1] += n[n[0]] / 10000;
n[n[0]++] -= 10000;
}
}

void print(int *n)
{
printf(“%d”, n[n[0]]);
for(int i = n[0] - 1; i > 0; i–)
printf(“%04d”, n[i]);
}

int sum[1111][1024], fac[1024];

int main()
{
int n;
fac[0] = fac[1] = 1;
sum[0][0] = 1; sum[0][1] = 0;
for(int i = 1; i < 1111; i++) {
sum[i][0] = 1; sum[i][1] = 0;
mul(fac, i);
add(sum[i], sum[i - 1]);
add(sum[i], fac);
}
while(~scanf(“%d”, &n)) {
print(sum[n]);
putchar(‘\n’);
}

return 0;
}

D 阿甘再一次想知道线段的总长，这个题在比赛的时候数据范围给错了23333，用纯暴力的话也可以刚好过

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 #include

const int maxn = 2525;
int num[5050], N;
typedef long long ll;

int main()
{
int n;

memset(num, 0, sizeof(num));
scanf(“%d”, &N);
for(int i = 0; i < N; i++) {
scanf(“%d”, &n);
num[n + maxn]++;
}
ll ans = 0;
int s = 0;
for(int i = 0; i < 5050; i++) {
if(num[i]) {
ans += ((ll)s * 2 + num[i] - N) * num[i] * (i - maxn);
s += num[i];
}
}
printf(“%lld\n”, ans * 2);

return 0;
}

E 报名身高差，也是水的0.0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include

int main()
{
int N, n, ma, ans;
scanf(“%d%d%d”, &N, &ma, &n);
ans = ma - n;
for(int i = 2; i < N; i++) {
if(n > ma) ma = n;
scanf(“%d”, &n);
if(ma - n > ans)
ans = ma - n;
}
printf(“%d\n”, ans);

return 0;
}

F 我让你不刷题，动态规划，每秒有2或3个位置被打中，f[i][j] = max{f[i+1][j-1],f[i+1][j],f[i+1][j+1]}+f[i][j]，倒叙查找到f[0][0]，f[i][j]表示第 i 秒在 j 位置的最大值

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

#include #include

int main()
{
int dp[2][110], ball, N, M;
scanf(“%d%d”, &N, &M);
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= N; i++) {
int k = i & 1;
scanf(“%d”, &ball);
for(int j = 1; j <= i && j < M; j++) {
dp[k][j] = dp[k ^ 1][j - 1];
if(dp[k ^ 1][j] > dp[k][j])
dp[k][j] = dp[k ^ 1][j];
if(dp[k ^ 1][j + 1] > dp[k][j])
dp[k][j] = dp[k ^ 1][j + 1];
int dis = ball - j;
if(dis >= -1 && dis <= 1)
dp[k][j]++;
}
}

int ans = 0;
for(int i = 1; i < M; i++)
if(dp[N & 1][i] > ans)
ans = dp[N & 1][i];
printf(“%d\n”, ans);

return 0;
}

G 我让你不戴帽子，并查集

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

#include #include #include

const int MOD = 1000000007;
const int maxn = 100010;
int pa[maxn], val[maxn], dis[maxn], N, M;

int findp(int x)
{
if(pa[x] != x) {
int p = findp(pa[x]);
dis[x] += dis[pa[x]];
if(dis[x] > MOD)
dis[x] %= MOD;
return pa[x] = p;
}
return x;
}

int main()
{
char o;
int a, b;
scanf(“%d%d”, &N, &M);
memset(dis, 0, sizeof(dis));
for(int i = 1; i <= N; i++) {
scanf(“%d”, &val[i]);
pa[i] = i;
}
for(int i = 0; i < M; i++) {
getchar();
scanf(“%c %d”, &o, &a);
if(o == ‘A’) {
scanf(“%d”, &b);
pa[b] = a;
dis[b] = abs(val[a] - val[b]);
} else {
findp(a);
printf(“%d\n”, dis[a]);
}
}

return 0;
}

H 帝国扩张，水题，找到最大矩形后，测试四个边各向里去掉一个的情况，注意特判下特殊情况就好

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

#include

const int maxn = 50050;
int x[maxn], y[maxn];

int main()
{
int N, x1, x2, x3, x4, y1, y2, y3, y4;

scanf(“%d”, &N);
for(int i = 0; i < N; i++)
scanf(“%d%d”, &x[i], &y[i]);
x1 = x2 = y1 = y2 = 0x3f3f3f3f;
x3 = x4 = y3 = y4 = 0;
for(int i = 0; i < N; i++) {
if(x[i] < x1) { x2 = x1; x1 = x[i]; }
else if(x[i] < x2) { x2 = x[i]; }
if(x[i] > x4) { x3 = x4; x4 = x[i]; }
else if(x[i] > x3) { x3 = x[i]; }
if(y[i] < y1) { y2 = y1; y1 = y[i]; }
else if(y[i] < y2) { y2 = y[i]; }
if(y[i] > y4) { y3 = y4; y4 = y[i]; }
else if(y[i] > y3) { y3 = y[i]; }
}
int ans = (x4 - x1) * (y4 - y1);
for(int i = 0; i < N; i++) {
int minx = x1;
if(x[i] == minx) minx = x2;
int maxx = x4;
if(x[i] == maxx) maxx = x3;
int miny = y1;
if(y[i] == miny) miny = y2;
int maxy = y4;
if(y[i] == maxy) maxy = y3;
int area = (maxx - minx) * (maxy - miny);
if(area < ans) ans = area;
}
printf(“%d\n”, ans);

return 0;
}

I 超级寻宝，原题，网上有答案

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

#include #include #include #include #include #include

using namespace std;

#define MAXN 1010

int Q[MAXN];
int DP[MAXN];
int D[MAXN];
vector E\[MAXN\];

int cmp(int x, int y)
{
return Q[x] < Q[y];
}

int main() {

int N, ECST;
cin » N » ECST;
for (int i = 0; i < N; i++) {
int D;
cin » Q[i] » D;
for (int j = 0; j < D; j++) {
int v;
cin » v;
E[i].push_back(v - 1);
}
}

vector PI; for (int i = 0; i < N; i++) { PI.push\_back(i); } sort(PI.begin(), PI.end(), cmp);

int result = 0;
for (int i = N - 1; i >= 0; i–) {
int u = PI[i];

queue q; memset(D, -1, sizeof(D)); q.push(u); D\[u\] = 0; while (!q.empty()) { int v = q.front(); q.pop(); for (int i = 0; i < E\[v\].size(); i++) { int nv = E\[v\]\[i\]; if (D\[nv\] == -1) { D\[nv\] = D\[v\] + 1; q.push(nv); } } }

int res = Q[u];
for (int j = 0; j < N; j++) {
if (D[j] != -1) {
res = max(res, Q[u] + DP[j] - ECST * D[j]);
}
}
DP[u] = res;
result = max(result, res);
}

cout « result « endl;
return 0;
}

J 我帮你表白？，改编的题，poj原题，输入格式变化了。

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

#include #include #include #include

using namespace std;

struct Edge {
int to, dis, cost;
};

vector G\[110\]; int dp\[110\]\[10010\]; int used\[110\]; int K, N, R, ans;

int dfs(int s, int cost, int dis)
{
if(cost>K) return 0;
if(dis>ans) return 0;
if(dis>dp[s][cost]) return 0;
if(s==N) {
ans = min(ans, dis);
return 0;
}
dp[s][cost] = dis;
for(int i=0; i<G[s].size(); i++) {
if(used[G[s][i].to]) continue;
used[G[s][i].to] = 1;
dfs(G[s][i].to, cost+G[s][i].cost, dis+G[s][i].dis);
used[G[s][i].to] = 0;
}

}

int main()
{
int s, t, l, c;

scanf(“%d%d%d”, &N, &K, &R);
for(int i=0; i<R; i++) {
scanf(“%d%d%d%d”, &s, &t, &l, &c);
if(s!=t)
G[s].push_back((Edge){t, l, c});
}
memset(used, 0, sizeof(used));
for(int i=0; i<110; i++)
for(int j=0; j<10010; j++)
dp[i][j] = 1«30;
used[1] = 1;
ans = 1«30;
dfs(1, 0, 0);
if(ans<(1«30))
printf(“%d\n”, ans);
else printf(“-1\n”);

return 0;
}