2013暑假集训第一场个人赛总结

　　暑假的第一场个人赛今天开始了，题目是10的Troy神出的，总体感觉层次性不强。一共6题，有4题简单题，然后两题中等偏难的题吧，自己做不出那两题，不过也不像是难题。

　　题目来源如下表格。

	ID	Origin	Title
6 / 71	Problem A	SGU 174	A
0 / 3	Problem B	UVALive 6039	B
32 / 141	Problem C	SGU 180	C
5 / 54	Problem D	URAL 1468	D
4 / 24	Problem E	UVALive 5066	E
0 / 1	Problem F	URAL 1529	F

　　开场的时候，机房的机不够，我就被迫回去宿舍开始，于是开始的时间就比别人晚了大概25分钟左右。

　　那时已经有两个人过了C了，我用了大概半分钟吧，就看懂了是一个求逆序数的大水题。一共65537个数，很快就留意到这里有个小坑，65536*65537/2是爆int的，于是稳阵起见，果断用long long来做这题。开场35min，1y了这题，也就是说这题用了10分钟，手速还是有点慢。

　　然后我就去看A了。A那是什么神题，题意看半天不懂，于是就果断的跑去找另外一题，例如D。D是有点恶心的模拟，不过不难。D题意是，求A/B在N进制底下的表示，循环部分用括号括起来。先是处理整数部分，然后就计算纯小数。建立一个数组，因为知道B的范围不大，所以就可以直接用数组来记录余数出现位置的情况。为了不会有严重的错误，敲慢了点（其实是在跟人上q聊天_(:з」∠)_），第70min的时候过了这题。因为交错pascal编译器，WA了一次TAT。

　　然后去看A了。看了老半天，以为看懂了，然后觉得答案是不唯一的，于是就去问Troy大神，是不是有特判。结果告诉我的是“有唯一解的啊”。。囧。好吧，然后我再认真理解一下题意。。擦！！！原来是水并查集。。囧rz。题意是，按顺序给出线段，问到那条线段的时候已经有一些围成一个封闭区域的线段了。做法是对线段两个端点hash或者map，然后用并查集合并，直到找到两个端点在同一个集合就停止。好吧，用了20min敲出代码，瞬间过了sample。（不对，不是20min那么久的，中间肯定做其他事了。印象中这个东西只用了8min而已的。= =）然后。。这就是这次个人赛最搓的时刻了。提交，Runtime Error on test 4，以为是爆栈啦，改了再交，还是Runtime Error on test 4，再以为是有重合的点啦，再改，还是Runtime Error on test 4，原来题目也说了不会重合，崩溃。好吧，我发现问题了。20W的线段，原来是可以有40W个点的。于是我就把并查集的点开大一倍！以为这次妥了，自信满满的交上去，WA！_(:з」∠)_然后再发现改错位置了。改了存储大小，忘记改初始化的大小了。TAT啊啊啊！改了吧，再交PE都出来了。。。这次是忘记关freopen。最后WA6之后就过了。水题WA6次，蛋疼啊！

　　然后就是E，开始的时候是嫌这题题目太长了，其实这题题意很简单。有一个游戏，里面有L层楼，每层楼都是一个H*W的区域，每一层都有一些障碍或者上下楼的楼梯。玩家需要救出一些给定位置的。。volunteer，志愿者？应该是一些伤员吧。如果不运伤员，一个单位时间可以上下左右运动到一格非障碍区域，上下的情况需要有U或者D这些楼梯，运伤员的时候时间翻倍。另外，一旦运伤员，就得马上运到出口。然后就是给出一些伤员的位置以及价值，求出给定时间内能获得的最大价值。一个伤员只能救一次。显然，这题就是一个bfs然后一个01背包。先bfs，求出从入口到每一个位置至少需要多少时间，然后就是代价为这个时间3倍的一个简单背包了。我的写法需要在query的时候判断一下，结果第一次交的时候忘记了，WA了一次。改过来就AC了！

　　然后B好像说是贪心，我大概能想到的是先找最大边权的边延伸出最长路径，不停重复，直到所有边次数都覆盖。不知道对不对，但是这个的优化方法我都没想到，我还是好水。_(:з」∠)_ F是博弈，更加不会所以最后剩下一个钟，跟人吹一下水想一下B题然后就去吃饭了~

　　今天题目水题比较水，难题比较难，登了下顶，估计下次就没那么幸运的了，所以还是好好继续练习！~

贴一下代码。

A题代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <map>
 4 #include <iostream>
 5 #include <algorithm>
 6 #include <stack>
 7 
 8 using namespace std;
 9 
10 typedef pair<int, int> PII;
11 map<PII, int> id;
12 stack<int> tmp;
13 
14 const int N = 444444;
15 struct MFS {
16     int fa[N];
17     void init() { for (int i = 0; i < N; i++) fa[i] = i;}
18     int find(int x) {
19         while (!tmp.empty()) tmp.pop();
20         while (fa[x] != x) {
21             tmp.push(x);
22             x = fa[x];
23         }
24         while (!tmp.empty()) {
25             fa[tmp.top()] = x;
26             tmp.pop();
27         }
28         return x;
29     }
30     bool merge(int x, int y) {
31         int fx = find(x), fy = find(y);
32         if (fx == fy) return false;
33         fa[fx] = fy;
34         return true;
35     }
36 } mfs;
37 
38 int main() {
39 //    freopen("in", "r", stdin);
40     int n, a, b, x, y;
41     while (~scanf("%d", &n)) {
42         mfs.init();
43         id.clear();
44         int mk = 0;
45         for (int i = 1; i <= n; i++) {
46             scanf("%d%d%d%d", &a, &b, &x, &y);
47             if (mk) continue;
48             if (id.find(PII(a, b)) == id.end()) id[PII(a, b)] = id.size();
49             if (id.find(PII(x, y)) == id.end()) id[PII(x, y)] = id.size();
50             if (!mfs.merge(id[PII(a, b)], id[PII(x, y)])) mk = i;
51         }
52         printf("%d
", mk);
53     }
54     return 0;
55 }

View Code

C题代码：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <map>
 5 #include <cstring>
 6 
 7 using namespace std;
 8 
 9 const int N = 66666;
10 map<int, int> id;
11 int x[N], rec[N];
12 
13 inline int lowbit(int x) { return (-x) & x;}
14 struct BIT {
15     int a[N];
16     void init() { memset(a, 0, sizeof(a));}
17     void add(int x) {
18         x += 10;
19         while (x < N) {
20             a[x]++;
21             x += lowbit(x);
22         }
23     }
24     int sum(int x) {
25         int ret = 0;
26         x += 10;
27         while (x > 0) {
28             ret += a[x];
29             x -= lowbit(x);
30         }
31         return ret;
32     }
33 } bit;
34 
35 int main() {
36     int n;
37     while (~scanf("%d", &n)) {
38         bit.init();
39         id.clear();
40         for (int i = 0; i < n; i++) {
41             scanf("%d", &rec[i]);
42             x[i] = rec[i];
43         }
44         sort(x, x + n);
45         int m = unique(x, x + n) - x;
46         for (int i = 0; i < m; i++) id[x[i]] = i;
47         long long ans = 0;
48         for (int i = 0; i < n; i++) {
49             ans += i - bit.sum(id[rec[i]]);
50             bit.add(id[rec[i]]);
51         }
52         cout << ans << endl;
53     }
54     return 0;
55 }

View Code

D题代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <stack>
 6 
 7 using namespace std;
 8 
 9 const int N = 11111;
10 int rec[N], id[N];
11 
12 int main() {
13 //    freopen("in", "r", stdin);
14     int a, b, n;
15     while (cin >> a >> b && (a || b)) {
16         cin >> n;
17         int I = a / b, D = a % b;
18         stack<int> s;
19         while (!s.empty()) s.pop();
20         do {
21             s.push(I % n);
22             I /= n;
23         } while (I > 0);
24         memset(id, 0, sizeof(id));
25         rec[0] = 0;
26         while (true) {
27             if (D == 0) break;
28             if (id[D]) break;
29             id[D] = ++rec[0];
30             D *= n;
31             rec[rec[0]] = D / b;
32 //            cout << "~~ " << rec[rec[0]] << endl;
33             D %= b;
34         }
35 //        cout << id[D] << ' ' << rec[0] << endl;
36         while (!s.empty()) { putchar(s.top() < 10 ? '0' + s.top() : 'A' + s.top() - 10); s.pop();}
37         if (rec[0]) {
38             putchar('.');
39             for (int i = 1; i <= (D ? id[D] - 1: rec[0]); i++) putchar(rec[i] < 10 ? '0' + rec[i] : 'A' + rec[i] - 10);
40             if (id[D]) {
41                 putchar('(');
42                 for (int i = id[D]; i <= rec[0]; i++) putchar(rec[i] < 10 ? '0' + rec[i] : 'A' + rec[i] - 10);
43                 putchar(')');
44             }
45         }
46         puts("");
47     }
48     return 0;
49 }

View Code

E题代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <queue>
 6 
 7 using namespace std;
 8 
 9 const int N = 111;
10 char mat[N][N][N];
11 int tm[N][N][N];
12 int l, h, w;
13 
14 inline bool inmat(int x, int y) { return 0 <= x && x < h && 0 <= y && y < w;}
15 
16 struct Node {
17     int a, b, c;
18     Node() {}
19     Node(int a, int b, int c) : a(a), b(b), c(c) {}
20 } ;
21 queue<Node> q;
22 const int dx[4] = { 0, -1, 0, 1};
23 const int dy[4] = { 1, 0, -1, 0};
24 
25 void preMat() {
26     memset(tm, -1, sizeof(tm));
27     while (!q.empty()) q.pop();
28     for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) if (mat[0][i][j] == 'S') { q.push(Node(0, i, j)); tm[0][i][j] = 0;}
29     Node cur;
30     int nl, nh, nw;
31     while (!q.empty()) {
32         cur = q.front();
33         q.pop();
34         for (int i = 0; i < 4; i++) {
35             nl = cur.a, nh = cur.b + dx[i], nw = cur.c + dy[i];
36             if (!inmat(nh, nw)) continue;
37             if (mat[nl][nh][nw] == 'X') continue;
38             if (~tm[nl][nh][nw]) continue;
39             tm[nl][nh][nw] = tm[cur.a][cur.b][cur.c] + 1;
40             q.push(Node(nl, nh, nw));
41         }
42         if (mat[cur.a][cur.b][cur.c] == 'U') {
43             nl = cur.a + 1, nh = cur.b, nw = cur.c;
44             if (~tm[nl][nh][nw]) continue;
45             tm[nl][nh][nw] = tm[cur.a][cur.b][cur.c] + 1;
46             q.push(Node(nl, nh, nw));
47         }
48         if (mat[cur.a][cur.b][cur.c] == 'D') {
49             nl = cur.a - 1, nh = cur.b, nw = cur.c;
50             if (~tm[nl][nh][nw]) continue;
51             tm[nl][nh][nw] = tm[cur.a][cur.b][cur.c] + 1;
52             q.push(Node(nl, nh, nw));
53         }
54     }
55 //    for (int i = 0; i < l; i++) {
56 //        for (int j = 0; j < h; j++) {
57 //            for (int k = 0; k < w; k++) cout << tm[i][j][k] << ' '; cout << endl;
58 //        }
59 //    }
60 }
61 
62 int dp[11111];
63 
64 int main() {
65 //    freopen("in", "r", stdin);
66     int T, n, s;
67     scanf("%d", &T);
68     while (T--) {
69         scanf("%d%d%d%d%d", &l, &h, &w, &n, &s);
70         for (int i = 0; i < l; i++) {
71             for (int j = 0; j < h; j++) {
72                 scanf("%s", mat[i][j]);
73             }
74         }
75         preMat();
76         memset(dp, 0, sizeof(dp));
77         int a, b, c, d;
78         for (int i = 0; i < n; i++) {
79             scanf("%d%d%d%d", &a, &b, &c, &d);
80             a--, b--, c--;
81             if (~tm[a][b][c])
82             for (int i = s, e = tm[a][b][c] * 3; i >= e; i--) {
83                 dp[i] = max(dp[i], dp[i - e] + d);
84             }
85         }
86         printf("%d
", dp[s]);
87     }
88     return 0;
89 }

View Code

　　今天的问题主要暴露在思维不够严谨，手速跟不少脑速，停停打打的。其实开始的时候想到的是应该先写下来吧？下次要试试这样，免得无端端的错那么几次，好不值。

B题代码，做法是贪心：

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 
 6 using namespace std;
 7 
 8 const int N = 111111;
 9 int mx[N], sum[N], ttsum;
10 
11 int main() {
12     int T, n;
13     scanf("%d", &T);
14     for (int cas = 1; cas <= T; cas++) {
15         scanf("%d", &n);
16         int x, y, c;
17         memset(mx, 0, sizeof(mx));
18         memset(sum, 0, sizeof(sum));
19         ttsum = 0;
20         for (int i = 1; i < n; i++) {
21             scanf("%d%d%d", &x, &y, &c);
22             mx[x] = max(mx[x], c);
23             mx[y] = max(mx[y], c);
24             sum[x] += c;
25             sum[y] += c;
26             ttsum += c;
27         }
28         int ans = 0;
29         for (int i = 1; i <= n; i++) ans += max(sum[i] + 1 >> 1, mx[i]);
30         printf("Case #%d: %d
", cas, ans - ttsum);
31     }
32     return 0;
33 }

View Code

——written by Lyon

2013暑假集训 第一场个人赛总结

2013暑假集训第一场个人赛总结