Codeforces Round #368 (Div. 2)

　　A题，水题。

　　B题，一开始看题目觉得蛮复杂的，其实很简单。存好图后找可以储存的点，再遍历这些点附近可以开店的点，维护一下答案的最小值即可。

　　C题，推不出公式= =。见代码好了：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <iostream>
 5 #include <vector>
 6 using namespace std;
 7 const int N = 100000 + 5;
 8 typedef long long ll;
 9 
10 ll n;
11 
12 int main()
13 {
14     cin >> n;
15     if(n <= 2) cout << "-1" << endl;
16     else
17     {
18         if(n % 2 == 0) printf("%I64d %I64d
",n/2*n/2-1,n/2*n/2+1);
19         else printf("%I64d %I64d
",(n*n)/2,(n*n)/2+1);
20     }
21     return 0;
22 }

　　D题，以前用dfs+离线写过。看别人写的可持久化。内存消耗蛮大的= =。我不是很清楚节点的内存到底要开多大。。下面是铭神的代码：

 1 #include <bits/stdc++.h>
 2 
 3 struct Node
 4 {
 5     int lc, rc;
 6     bool flag;
 7     int val;
 8 };
 9 
10 Node node[100000 * 10 * 5];
11 
12 const int kQ = 100000 + 1;
13 const int kN = 1000 + 1;
14 
15 int shelves[kQ][kN];
16 
17 int n, m, nq;
18 
19 int tot;
20 
21 int query(int o, int p, int l, int r) 
22 {
23     if (o == 0)
24         return 0;
25     if (l == r)
26         return node[o].val;
27     int mid = l + r >> 1;
28     if (p <= mid)
29         return query(node[o].lc, p, l, mid);
30     else
31         return query(node[o].rc, p, mid + 1, r);
32 }
33 
34 int modify(int o, int p, int l, int r) 
35 {
36     int w = tot ++;
37     node[w] = node[o];
38 
39     if (l == r) {
40         node[w].val ^= 1;
41         return w;
42     }
43     int mid = l + r >> 1;
44     if (p <= mid)
45         node[w].lc = modify(node[o].lc, p, l, mid);
46     else
47         node[w].rc = modify(node[o].rc, p, mid + 1, r);
48     node[w].val = node[node[w].lc].val + node[node[w].rc].val;
49     return w;
50 }
51 
52 int main()
53 {
54     tot = 1;
55     std::ios::sync_with_stdio(false);
56     std::cin >> n >> m >> nq;
57     for (int i = 1; i <= nq; ++ i) {
58         int op;
59         std::cin >> op;
60         if (op == 4) {
61             int k;
62             std::cin >> k;
63             for (int j = 1; j <= n; ++ j) {
64                 shelves[i][j] = shelves[k][j];
65             }
66         } else {
67             for (int j = 1; j <= n; ++ j) {
68                 shelves[i][j] = shelves[i - 1][j];
69             }
70             if (op == 3) {
71                 int x;
72                 std::cin >> x;
73                 int w = tot ++;
74                 node[w] = node[shelves[i][x]];
75                 node[w].flag ^= 1;
76                 shelves[i][x] = w;
77             } else {
78                 int x, y;
79                 std::cin >> x >> y;
80                 bool aim = (op == 1) ^ node[shelves[i][x]].flag;
81                 if (query(shelves[i][x], y, 1, m) != aim) {
82                     shelves[i][x] = modify(shelves[i][x], y, 1, m);
83                 }
84             }
85         }
86         int answer = 0;
87         for (int x = 1; x <= n; ++ x) {
88             int tmp = node[shelves[i][x]].val;
89             if (node[shelves[i][x]].flag == false)
90                 answer += tmp;
91             else
92                 answer += m - tmp;
93         }
94         printf("%d
", answer);
95     }
96 }