http://codeforces.com/contest/1248
A. Integer Points
做法：
统计两条垂直线的截距的奇偶性就行了
#include "bits/stdc++.h" using namespace std; typedef long long ll; const int maxn = 100000 + 10; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T, p, n; cin >> T; while (T--) { int odd = 0, eve = 0; cin >> n; for (int i = 1; i <= n; i++) { cin >> p; if (p & 1) odd++; else eve++; } cin >> n; ll ans = 0; for (int i = 1; i <= n; i++) { cin >> p; if (p & 1) ans += odd; else ans += eve; } cout << ans << endl; } return 0; }B. Grow The Tree
做法：排一个序，然后取前一半小的做一个方向的就可以了。
#include "bits/stdc++.h" using namespace std; typedef long long ll; const int maxn = 100000 + 10; int a[maxn], n, x; //priority_queue<int, vector<int>, less<int> > qu; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; ll l = 0, r = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; l += a[i]; } sort(a + 1, a + n + 1); for (int i = 1; i <= n / 2; i++) { r += a[i]; } l -= r; cout << l * l + r * r << endl; return 0; }C. Ivan the Fool and the Probability Theory
做法：我当时首先想到了只有一列的时候，我知道那个超级楼梯那道题，方案数就是斐波那契数列，因为有两种颜色因此要乘以2，然后，假设增加列数，然后我们通过观察发现也和斐波那契数列数列有关，猜一波结论，推几个样例没错。
#include "bits/stdc++.h" using namespace std; typedef long long ll; const int maxn = 100000 + 10; const ll mod = 1000000000 + 7; int n, m; ll f[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; f[0] = 1, f[1] = 1; for (int i = 2; i < maxn; i++) { f[i] = (f[i - 2] + f[i - 1]) % mod; } cout << 2 * (f[m] + f[n] - 1) % mod << endl; return 0; }D. The World Is Just a Programming Task
做法：简单版直接爆了枚举位置就可以了。
困难版，好像是关于括号的加减，然关于这个的一个折线图，要求循环序列一定是零最多的。所以扩展这个字符串到2n找到一个最少值开始，匹配括号，这里需要明白交换括号一定相邻的不同方向的括号，具体细节看看代码吧，建议查看官方题解，这道题应该是整个div2中最难的。
#include "bits/stdc++.h" using namespace std; typedef long long ll; #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define pii pair<int,int> const int maxn = 300000 + 10; const ll mod = 1000000000 + 7; int n, m, now[maxn << 1], pre[maxn << 1]; char s[maxn << 1]; int sum[maxn << 1], sta[maxn << 1], lef[maxn << 1]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> (s + 1); for (int i = 1; i <= n; i++) s[i + n] = s[i]; int cnt = 0, mn = 0, id = 0; for (int i = 1; i <= n; i++) { if (s[i] == '(') cnt++; else cnt--; if (cnt < mn) mn = cnt, id = i; } if (cnt != 0) { cout << "0\n1 1\n"; return 0; } int top = 0, ans = 0; for (int i = id + 1; i <= id + n; i++) { if (s[i] == '(') sta[++top] = i; else { sum[i] = now[top]; now[top] = 0; lef[i] = sta[top--]; pre[i] = top; now[top]++; } if (top == 0) ans++; } int tmp = ans, x = 1, y = 1; for (int i = id + 2; i <= id + n; i++) { if (s[i] == ')') { if (pre[i] == 0 && sum[i] + 1 > ans) ans = sum[i] + 1, x = lef[i], y = i; if (pre[i] == 1 && sum[i] + tmp + 1 > ans) ans = sum[i] + tmp + 1, x = lef[i], y = i; } } cout << ans << endl; cout << (x - 1) % n + 1 << " " << (y - 1) % n + 1 << endl; return 0; }E. Queue in the Train
做法：抽象一下这个问题，假设一个队列，定义三个属性，a,b,c分别表示，a表示时间，b表示出入队列，c表示id
优先度也是按照abc，因此需要set或者堆进行维护。如果会一些技巧可以优化一维。
建议查看官方题解，讲得很好。
#include "bits/stdc++.h" using namespace std; typedef long long ll; #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define pii pair<int,int> #define pll pair<ll,ll> const int maxn = 100000 + 10; const ll mod = 1000000000 + 7; int n; ll ans[maxn], p; struct node { ll x, f, id; bool operator<(const node &a) const { if (x == a.x) { if (f == a.f) return id > a.id; return f > a.f; } return x > a.x; } } a[maxn]; priority_queue<node> q1; priority_queue<ll, vector<ll>, greater<ll> > q2; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> p; ll cnt = 0, count = 0; for (int i = 1; i <= n; i++) { cin >> a[i].x; a[i].id = i; a[i].f = 0; q1.push(a[i]); } ll tmp = n + 1; while (!q1.empty()) { node now = q1.top(); q1.pop(); cnt = max(cnt, now.x); if (now.f == 0) { now.f = 1; if (now.id < tmp) { tmp = now.id, count++; now.x = cnt + p; cnt = max(cnt, now.x); q1.push(now); } else { q2.push(now.id); } } else { ans[now.id] = now.x; count--; if (count == 0) { if (!q2.empty()) { count++; q1.push({cnt += p, 1, q2.top()}); tmp = q2.top(); q2.pop(); } // else tmp = n + 1; } } } for (int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl; return 0; }F. Catowice City
做法：题我也没怎么读懂，然后觉得是一个强联通，然后看见很多人过了，然后。裸了一发tarjan过了。
#include "bits/stdc++.h" using namespace std; typedef long long ll; #define lson o<<1,l,mid #define rson o<<1|1,mid+1,r #define pii pair<int,int> #define pll pair<ll,ll> const int maxn = 1000000 + 10; const ll mod = 1000000000 + 7; int n, m, colnum, cnt, dfsnum, top; int vis[maxn], low[maxn], dfn[maxn]; int sta[maxn], col[maxn], dis[maxn]; vector<int> g[maxn]; void tarjan(int u) { low[u] = dfn[u] = ++dfsnum; sta[++top] = u; vis[u] = 1; for (auto v:g[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else { if (vis[v]) low[u] = min(low[u], low[v]); } } if (low[u] == dfn[u]) { vis[u] = 0; col[u] = ++colnum; while (sta[top] != u) { vis[sta[top]] = 0; col[sta[top--]] = colnum; } top--; } } void init(int n) { colnum = top = dfsnum = 0; for (int i = 0; i <= n; i++) { vis[i] = low[i] = dfn[i] = 0; sta[i] = col[i] = 0; g[i].clear(); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T, u, v; cin >> T; while (T--) { cin >> n >> m; init(n); for (int i = 1; i <= m; i++) { cin >> u >> v; if (u == v) continue; g[u].push_back(v); // g[v].push_back(u); } for (int i = 1; i <= n; i++) { if (!dfn[i]) tarjan(i); } if (colnum == 1) cout << "No" << endl; else { cout << "Yes" << endl; int cnt = 0; for (int i = 1; i <= n; i++) if (col[i] == 1) cnt++; cout << cnt << " " << n - cnt << endl; for (int i = 1; i <= n; i++) if (col[i] == 1) cout << i << " "; cout << endl; for (int i = 1; i <= n; i++) if (col[i] != 1) cout << i << " "; cout << endl; } } return 0; }
