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

　　在开头问自己一句，题解还能坚持多少场呢？不管那样，能坚持就继续坚持下去，就算我不喜欢打字。

　　好了，然后下面要正文了。7月18号，第二场个人赛。今天的比赛是另外一位10的大神yys出的，总体评价一下今天的题，虽然题目难度不算打，但是思维要求还是蛮高的，虽然有一道最小费用流的接近于模板题的题。然后，个人感觉，最近英语阅读水平降到不是路了，居然有一道大水题题意看了一场比赛都没看懂。_(:з」∠)_

下面是题目来源，因为UESTC在比赛的过程中挂掉了，所以临时将DE两题改成SGU的两题了：

	ID	Origin	Title
30 / 100	Problem A	CodeForces 48D	A
2 / 20	Problem B	UVALive 3222	B
2 / 43	Problem C	CodeForces 121E	C
	Problem D	UESTC 1817	D
0 / 4	Problem E	UESTC 1806	E
4 / 21	Problem F	POJ 3680	F

		ID	Origin	Title
		Problem A	SGU 236	A
	4 / 59	Problem B	SGU 186	B

　　今天因为卡了一道KMP的水题，所以我的开始时间又迟了。囧rz。

　　14点开始的比赛，我迟到了20分钟，去到那里，还是没有台式机给我用。_(:з」∠)_于是就只好布置我的电脑了。布置好以后，开始上去看题。21min，小马哥（一中大到华农的研究生大神，挺猛的）瞬秒了A（表一的A），于是我就去看A的题意~额。。比较蛋疼，表示自己英语真的不太好，开始担心起自己的四级过不过了。看了几分钟题目，有个叫做shuffle的单词一直没记住是什么意思，于是就拿起字典来查了。其实明白题意，这题超水，其实就是几个排列，把它们混在一起打乱了，把打乱了的结果给你，要求你把几个排列分离出来。排个序，然后从1开始堆上去，如果堆的过程中，其中一列断开了就不用继续了，否则继续堆，堆完以后对每一列编号就好了。然后就是十来分钟的敲代码时间了。1y是必然的~

　　之后，我看了一下我隔壁的另一个大神hq，他做F了。题意是，给出若干带权重的线段，要求重叠的位置不超过k层，求最大的权重和。想了下，瞬间知道最小费用最大流不解释。可是，我。。额。。能说我没学网络流吗？然而我又不想抄模板过这题，于是就放弃这题了（回到宿舍以后抄了下模板就过了），转去做36min被人过了的B（表一的B）。我看了下题目，好熟悉的感觉，好像什么时候做过！嗯。。应该是2012的网络赛中的一题了！不过那时好像是用贪心，而且不用输出满足的情况，于是我就做这题去了。做这题用了整整2个钟，中间限时想到相同的区间要进行合并，然后再像活动安排那样贪心，然后又想到好像不能贪心，要dp，然后还要特判那些必然矛盾的情况。对了，说一下题意。B的题意是，有一些龟，告诉你他的前面和后面各有多少龟，那些龟有些是抱团的，抱团的一堆龟在同一个坐标位置上，要一起算。其实龟们不知道自己有没有说谎的，所以就要问你，他们说的话最少有多少句是假话。这题的做法是，先处理出区间(a + 1, n - b)（这个的意思是，这只龟跟一些其他龟同时在这个区间里），然后统计各个区间的出现的次数。当然，这个次数不能超过区间的大小！然后根据区间右端点对区间进行排序。对这些区间进行一个dp，如果区间 i 的右端点比 j 的左端点小(i < j)，那么 j 这个区间就可以接在 i 的后面了，这时dp值为dp[i] + cnt[j]，然后取最大的dp[i]即可。最后回溯一下，扫一遍输出即可。各种小错误，wa了8次才过。

　　这时只剩1个多小时了，于是我就去看我比较有把握的C题。C的意思是，给出一串数，对它们的操作可以是对区间中的数增加同一个数，或者就是询问一个区间中只含数字4和7的数有多少个了。比赛的过程中，有两个12的师弟用暴力修改，树状数组查询的方法水过了，可是我居然没有那么无赖的去水。 - -||然而这题的正解是用线段树或者勉强能用块状数组（复杂度恰好允许）来做。http://codeforces.com/blog/entry/2956 不想写解释了，这里有C题的题解，请移步。

　　结束战斗的时候只有两题，排大概第8的位置。只有两个3题的，还要都是我的队友。_(:з」∠)_最后10min实现逆袭，过掉了B（表二）好厉害。。。

　　果然跟我说的一样，每次集训都是个好头可是就越打越差了。结束以后，把C、F和B（表二）都做了一下。C用了两种方法做，始终是线段树比较有优势。

贴代码时间：

A题代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 const int N = 111111;
 9 int rec[N];
10 typedef pair<int, int> PII;
11 PII arr[N], id[N];
12 
13 int main() {
14     int n;
15     while (cin >> n) {
16         memset(arr, 0, sizeof(arr));
17         for (int i = 0; i < n; i++) { scanf("%d", &arr[i].first); arr[i].second = i;}
18         sort(arr, arr + n);
19         memset(rec, 0, sizeof(rec));
20         bool ok = true;
21         int mx = 0;
22         for (int i = 0, g = 1; i < n; i++) {
23             id[i].first = arr[i].second;
24             if (rec[g] != arr[i].first - 1) {
25                 ok = false;
26                 break;
27             }
28             rec[g]++;
29             mx = max(g, mx);
30             id[i].second = g++;
31             if (arr[i].first != arr[i + 1].first) g = 1;
32         }
33         sort(id, id + n);
34         if (ok) {
35             printf("%d
", mx);
36             for (int i = 0; i < n; i++) {
37                 if (i) putchar(' ');
38                 printf("%d", id[i].second);
39             }
40             puts("");
41         } else puts("-1");
42     }
43     return 0;
44 }

View Code

B题代码（有点乱）：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <map>
 6 
 7 using namespace std;
 8 
 9 typedef pair<int, int> PII;
10 
11 const int N = 1111;
12 PII rec[N], tmp[N];
13 bool vis[N], mk[N];
14 map<PII, int> cnt_inv, ans;
15 int dp[N];
16 
17 bool cmp(PII a, PII b) { return a.second < b.second;}
18 
19 int main() {
20 //    freopen("in", "r", stdin);
21     int n, x, y, t;
22     while (cin >> n) {
23         t = 0;
24         memset(mk, 0, sizeof(mk));
25         for (int i = 1; i <= n; i++) {
26             cin >> x >> y;
27             if (x + y >= n) continue;
28             mk[i] = true;
29             tmp[t++] = rec[i] = PII(x + 1, n - y);
30         }
31         sort(tmp, tmp + t);
32         cnt_inv.clear();
33         for (int i = 0; i < t; i++)    {
34             if (cnt_inv.find(tmp[i]) == cnt_inv.end()) cnt_inv[tmp[i]] = 0;
35             cnt_inv[tmp[i]] = min(cnt_inv[tmp[i]] + 1, tmp[i].second - tmp[i].first + 1);
36         }
37         int m = unique(tmp, tmp + t) - tmp;
38         sort(tmp, tmp + m, cmp);
39         memset(dp, 0, sizeof(dp));
40         for (int i = 0; i < m; i++) {
41             int mx = 0;
42             for (int j = 0; j < i; j++) {
43                 if (tmp[j].second < tmp[i].first) mx = max(mx, dp[j]);
44             }
45             dp[i] = mx + cnt_inv[tmp[i]];
46         }
47         int mxid = 0;
48         for (int i = 1; i < m; i++) {
49             if (dp[mxid] < dp[i]) mxid = i;
50         }
51         ans.clear();
52         while (true) {
53             if (dp[mxid] == cnt_inv[tmp[mxid]]) {
54                 ans[tmp[mxid]] = cnt_inv[tmp[mxid]];
55                 break;
56             }
57             for (int i = mxid - 1; i >= 0; i--) {
58                 if (dp[mxid] - dp[i] == cnt_inv[tmp[mxid]] && tmp[i].second < tmp[mxid].first) {
59                     ans[tmp[mxid]] = cnt_inv[tmp[mxid]];
60                     mxid = i;
61                     break;
62                 }
63             }
64         }
65         memset(vis, 0, sizeof(vis));
66         int cntans = n;
67         for (int i = 1; i <= n; i++) {
68             if (mk[i] && ans.find(rec[i]) != ans.end()) {
69                 if (ans[rec[i]] > 0) {
70                     vis[i] = true;
71                     ans[rec[i]]--;
72                     cntans--;
73                 }
74             }
75         }
76         cout << cntans;
77         for (int i = 1; i <= n; i++) if (!vis[i]) cout << ' ' << i;
78         cout << endl;
79 
80     }
81     return 0;
82 }

View Code

C题代码（块状数组）：

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <algorithm>
  4 #include <cstring>
  5 #include <cmath>
  6 #include <vector>
  7 
  8 using namespace std;
  9 
 10 const int M = 11111;
 11 const int N = 111111;
 12 const int R = 333;
 13 
 14 vector<int> lucky;
 15 bool lc[M];
 16 
 17 bool test(int x) {
 18     while (x > 0) {
 19         if (x % 10 != 4 && x % 10 != 7) return false;
 20         x /= 10;
 21     }
 22     return true;
 23 }
 24 
 25 void PRE() {
 26     lucky.clear();
 27     for (int i = 1; i < M; i++)
 28         if (lc[i] = test(i)) lucky.push_back(i);
 29 }
 30 
 31 int cnt[R][M], late[R], rec[N];
 32 int n, m, r;
 33 
 34 void update(int L, int R, int d) {
 35     L--, R--;
 36     int a = L / r + 1, b = R / r;
 37     for (int i = a; i < b; i++) late[i] += d;
 38     if (a == b + 1) {
 39         for (int i = L; i <= R; i++) {
 40             cnt[b][rec[i]]--;
 41             rec[i] += d;
 42             cnt[b][rec[i]]++;
 43         }
 44     } else {
 45         for (int i = L, t = a * r; i < t; i++) {
 46             cnt[a - 1][rec[i]]--;
 47             rec[i] += d;
 48             cnt[a - 1][rec[i]]++;
 49         }
 50         for (int i = b * r; i <= R; i++) {
 51             cnt[b][rec[i]]--;
 52             rec[i] += d;
 53             cnt[b][rec[i]]++;
 54         }
 55     }
 56 //    for (int i = 0; i < n; i++) cout << rec[i] << ' '; cout << endl;
 57 //    for (int i = 0; i < r; i++) cout << late[i] << ' '; cout << endl;
 58 }
 59 
 60 int query(int L, int R) {
 61     L--, R--;
 62     int a = L / r + 1, b = R / r, ret = 0;
 63     vector<int>::iterator vi;
 64     for (int i = a; i < b; i++) {
 65         for (vi = lucky.begin(); vi != lucky.end(); vi++) {
 66             if (*vi - late[i] >= 0) ret += cnt[i][*vi - late[i]];
 67         }
 68     }
 69     if (a == b + 1) {
 70         for (int i = L; i <= R; i++) {
 71             if (lc[rec[i] + late[b]]) ret++;
 72         }
 73     } else {
 74         for (int i = L, t = a * r; i < t; i++) {
 75             if (lc[rec[i] + late[a - 1]]) ret++;
 76         }
 77         for (int i = b * r; i <= R; i++) {
 78             if (lc[rec[i] + late[b]]) ret++;
 79         }
 80     }
 81     return ret;
 82 }
 83 int main() {
 84 //    freopen("in", "r", stdin);
 85     PRE();
 86     while (~scanf("%d%d", &n, &m)) {
 87         memset(cnt, 0, sizeof(cnt));
 88         memset(late, 0, sizeof(late));
 89         r = (int) sqrt((double) n - 1) + 1;
 90         for (int i = 0; i < n; i++) {
 91             scanf("%d", &rec[i]);
 92             cnt[i / r][rec[i]]++;
 93         }
 94         char op[10];
 95         int L, R, d;
 96         while (m--) {
 97             scanf("%s", op);
 98             if (!strcmp(op, "count")) {
 99                 scanf("%d%d", &L, &R);
100                 printf("%d
", query(L, R));
101             }
102             if (!strcmp(op, "add")) {
103                 scanf("%d%d%d", &L, &R, &d);
104                 update(L, R, d);
105             }
106         }
107     }
108     return 0;
109 }

View Code

C题代码（线段树）：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <vector>
  6 
  7 using namespace std;
  8 
  9 #define lson l, m, rt << 1
 10 #define rson m + 1, r, rt << 1 | 1
 11 #define root 1, n, 1
 12 
 13 const int N = 111111;
 14 const int M = 11111;
 15 const int INF = 0x55555555;
 16 int lucky[33], mn[N << 2], lf[N << 2], late[N << 2], cnt[N << 2], rec[N << 2];
 17 
 18 bool test(int x) {
 19     while (x > 0) {
 20         if (x % 10 != 4 && x % 10 != 7) return false;
 21         x /= 10;
 22     }
 23     return true;
 24 }
 25 
 26 void PRE() {
 27     lucky[0] = 0;
 28     for (int i = 1; i < M; i++) if (test(i)) lucky[++lucky[0]] = i;
 29     lucky[++lucky[0]] = INF;
 30 //    for (int i = 1; i <= lucky[0]; i++) cout << lucky[i] << endl;
 31 }
 32 
 33 void up(int rt) {
 34     int ls = rt << 1, rs = rt << 1 | 1;
 35     if (mn[ls] <= mn[rs]) {
 36         lf[rt] = lf[ls];
 37         mn[rt] = mn[ls];
 38         cnt[rt] = cnt[ls];
 39         if (mn[ls] == mn[rs]) cnt[rt] += cnt[rs];
 40     } else {
 41         lf[rt] = lf[rs];
 42         mn[rt] = mn[rs];
 43         cnt[rt] = cnt[rs];
 44     }
 45 }
 46 
 47 void down(int rt) {
 48     if (late[rt]) {
 49         int ls = rt << 1, rs = rt << 1 | 1;
 50         mn[ls] -= late[rt];
 51         mn[rs] -= late[rt];
 52         late[ls] += late[rt];
 53         late[rs] += late[rt];
 54         rec[ls] += late[rt];
 55         rec[rs] += late[rt];
 56         late[rt] = 0;
 57     }
 58 }
 59 
 60 void fix1(int x) {
 61     if (x <= 1) return ;
 62     fix1(x >> 1);
 63     down(x >> 1);
 64 }
 65 
 66 void fix2(int x) {
 67     if (x <= 1) return ;
 68     up(x >> 1);
 69     fix2(x >> 1);
 70 }
 71 
 72 void update(int rt) {
 73     fix1(rt);
 74     int i = 1;
 75     while (lucky[i] < rec[rt]) i++;
 76     mn[rt] = lucky[i] - rec[rt];
 77 //    cout <<rec[rt] << ' ' << mn[rt] << endl;
 78     fix2(rt);
 79 }
 80 
 81 void build(int l, int r, int rt) {
 82     late[rt] = 0;
 83     if (l >= r) {
 84         scanf("%d", &rec[rt]);
 85         int i = 1;
 86         while (lucky[i] < rec[rt]) i++;
 87         mn[rt] = lucky[i] - rec[rt];
 88         cnt[rt] = 1;
 89         lf[rt] = rt;
 90         return ;
 91     }
 92     int m = l + r >> 1;
 93     build(lson);
 94     build(rson);
 95     up(rt);
 96 }
 97 
 98 void update(int L, int R, int d, int l, int r, int rt) {
 99     if (L <= l && r <= R) {
100         mn[rt] -= d;
101         late[rt] += d;
102         rec[rt] += d;
103         return ;
104     }
105     int m = l + r >> 1;
106     down(rt);
107     if (L <= m) update(L, R, d, lson);
108     if (m < R) update(L, R, d, rson);
109     up(rt);
110 }
111 
112 int query(int L, int R, int l, int r, int rt) {
113     if (L <= l && r <= R) return mn[rt] ? 0 : cnt[rt];
114     int ret = 0, m = l + r >> 1;
115     down(rt);
116     if (L <= m && mn[rt << 1] == 0) ret = query(L, R, lson);
117     if (m < R && mn[rt << 1 | 1] == 0) ret += query(L, R, rson);
118     up(rt);
119     return ret;
120 }
121 
122 int query(int L, int R, int n) {
123     while (mn[1] < 0) update(lf[1]);
124     return query(L, R, root);
125 }
126 
127 int main() {
128 //    freopen("in", "r", stdin);
129 //    freopen("out", "w", stdout);
130     int n, m;
131     PRE();
132     while (~scanf("%d%d", &n, &m)) {
133         build(root);
134 //        cout << "built" << endl;
135         char op[11];
136         int l, r, x;
137         while (m--) {
138             scanf("%s", op);
139             if (!strcmp(op, "count")) {
140                 scanf("%d%d", &l, &r);
141                 printf("%d
", query(l, r, n));
142             }
143             if (!strcmp(op, "add")) {
144                 scanf("%d%d%d", &l, &r, &x);
145                 update(l, r, x, root);
146             }
147 //            for (int i = 1; i <= 7; i++)cout << mn[i] << ' ' << lf[i] << ' ' << cnt[i] << endl;
148         }
149     }
150     return 0;
151 }

View Code

F题（最小费用流）代码：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <vector>
 6 #include <queue>
 7 
 8 using namespace std;
 9 
10 const int INF = 0x55555555;
11 struct Edge {
12     int s, t, cp, fl, co;
13 } ;
14 
15 const int N = 888;
16 struct MCMF {
17     int n, m, s, t;
18     vector<Edge> edges;
19     vector<int> G[N];
20     int inq[N], d[N], p[N], a[N];
21 
22     void init(int n) {
23         this->n = n;
24         for (int i = 0; i < n; i++) G[i].clear();
25         edges.clear();
26     }
27     void AddEdge(int s, int t, int cp, int co) {
28 //        cout << s << ' ' << t << ' ' << cp << ' ' << co << endl;
29         edges.push_back((Edge) { s, t, cp, 0, co});
30         edges.push_back((Edge) { t, s, 0, 0, -co});
31         m = edges.size();
32         G[s].push_back(m - 2);
33         G[t].push_back(m - 1);
34     }
35     bool BF(int s, int t, int &fl, int &co) {
36         for (int i = 0; i < n; i++) d[i] = INF;
37         memset(inq, 0, sizeof(inq));
38         d[s] = 0, inq[s] = 1, p[s] = 0, a[s] = INF;
39         queue<int> Q;
40         Q.push(s);
41         while (!Q.empty()) {
42             int u = Q.front();
43 //            cout << u << endl;
44             Q.pop();
45             inq[u] = 0;
46             for (int i = 0; i < G[u].size(); i++) {
47                 Edge &e = edges[G[u][i]];
48                 if (e.cp > e.fl && d[e.t] > d[u] + e.co) {
49                     d[e.t] = d[u] + e.co;
50                     p[e.t] = G[u][i];
51                     a[e.t] = min(a[u], e.cp - e.fl);
52                     if (!inq[e.t]) { Q.push(e.t); inq[e.t] = 1;}
53                 }
54             }
55         }
56         if (d[t] == INF) return false;
57         fl += a[t];
58         co += d[t] * a[t];
59         int u = t;
60         while (u != s) {
61             edges[p[u]].fl += a[t];
62             edges[p[u] ^ 1].fl -= a[t];
63             u = edges[p[u]].s;
64         }
65         return true;
66     }
67     int MC(int s, int t) {
68         int fl = 0, co = 0;
69         while (BF(s, t, fl, co)) ;
70         return co;
71     }
72 } mc;
73 
74 int main() {
75 //    freopen("in", "r", stdin);
76 //    freopen("out", "w", stdout);
77     int T, n, k, a[N], b[N], w[N];
78     cin >> T;
79     while (T-- && cin >> n >> k) {
80         mc.init(n + 5 << 1);
81         for (int i = 0; i < n; i++) cin >> a[i] >> b[i] >> w[i];
82         for (int i = 0; i < n; i++) {
83             mc.AddEdge(0, i + 1, 1, 0);
84             mc.AddEdge(i + 1, i + n + 1, 1, -w[i]);
85             for (int j = 0; j < n; j++) if (i != j && b[i] <= a[j]) mc.AddEdge(i + n + 1, j + 1, 1, 0);
86             mc.AddEdge(i + n + 1, n << 1 | 1, 1, 0);
87         }
88         mc.AddEdge(n << 1 | 1, n + 1 << 1, k, 0);
89 //        cout << "built" << endl;
90         cout << -mc.MC(0, n + 1 << 1) << endl;
91     }
92     return 0;
93 }

View Code

B题（表二，贪心）代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <iostream>
 5 
 6 using namespace std;
 7 
 8 bool cmp(int a, int b) { return a > b;}
 9 
10 int main() {
11     int rec[111], n;
12     while (cin >> n) {
13         for (int i = 0; i < n; i++) cin >> rec[i];
14         sort(rec, rec + n, cmp);
15         int t = 0, ans = 0;
16         while (t < n - 1) {
17             t++;
18             rec[t] = 100;
19             ans++;
20             if (rec[n - 1] == 1) n--;
21             else rec[n - 1]--;
22         }
23         cout << ans + max(0, n - t - 1) << endl;
24     }
25     return 0;
26 }

View Code

——written by Lyon

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

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