wtclwtcl！！ T3的简单式子我推了半个小时才推正确额额额，导致没时间做T2 。
T1：NKOJ4312 飞行管制
题目大意：给定若干架飞机的原定起飞时间和延误单位时间的代价，先要求在第k + 1分钟才能开始发机，求最小代价。
题解：应该是一道老题了，我感觉我见过的。反正话不多说，这个题直接维护一个最小代价的小根堆，然后每次直接取出堆顶计算代价即可。
#include<bits/stdc++.h> using namespace std; #define ll long long const ll maxn = 600005; struct node{ ll m, id; bool operator> (node x) const { return m == x.m ? id < x.id : m < x.m; } }a[maxn]; priority_queue<node, vector <node>, greater <node> > q; ll ans[maxn]; main() { ll n, k; scanf("%lld%lld", &n, &k); for (ll i = 1; i <= n; i++) { scanf("%lld", &a[i].m); a[i].id = i; } for(ll i = 1; i <= k + 1; i++) { q.push(a[i]); } ll hd = k + 1, tl = k + 2, sum = 0; ans[q.top().id] = hd; sum += (hd - q.top().id) * q.top().m; q.pop(); for (ll i = 2; i <= n; i++) { if (tl <= n) { q.push(a[tl]); } if (tl <= n) { tl++; }hd++; sum += (hd - q.top().id) * q.top().m; ans[q.top().id] = hd; q.pop(); } printf("%lld\n", sum); }
T2（订正） NKOJ7842 疫情防控
这个题连向神都没有做出来。。我以为它很难。。。
题目大意：有n座城市和m条双向道连接各个城市，先要求将双行道改为单行道，使任两座都只有一种走法，判断是否有解。
题解：我一拿到这个题就傻了，还想着去跑dfs或者搞一搞强联通分量之类的东西。。
然鹅事实上这个题只需要判断1至n是否有环，有则有解，否则无解，于是直接用并查集维护点是否已经联通即可。
#include <bits/stdc++.h> using namespace std; bool mark[100005]; int fa[100005]; int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);} int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) fa[i] = i; while (m--) { int x, y; scanf("%d%d", &x, &y); int fx = find(x), fy = find(y); if (fx != fy) { fa[fx] = fy, mark[fy] = (mark[fx] | mark[fy]); } else mark[fx] = 1; } for (int i = 1; i <= n; i++) if (!mark[find(i)]) return puts("NO"), 0; puts("YES"); }
T3 NKOJ7836 玩玩异或
题目大意：给定一串数，要求支持两个操作：单点修改和区间查询所有子区间异或和的异或和。
题解：一开始看到这个题傻了，后来看到丁神（%%%！！！）爆切此题，我再仔细分析此题，发现这就是个大水题。
单点修改很简单，用a[i]记录i位置当前的数值，众所周知一个数异或它本身等于0，我们利用这个性质，可以在修改时先再异或一次a[i]然后直接修改a[i]，再将修改后的值异或一次。而区间查询我推了好久，发现了两个规律：
1. 若区间左端点位置和右端点位置奇偶性不同则答案为0.
2. 若区间左右端点均为奇数位，则答案等于区间内所有奇数位上的数的异或和，若都为偶数则答案等于区间内所有偶数位上的数的异或和。
又因为异或具有前缀性质，于是想到用树状数组分别维护奇数位和偶数位异或和，查询时类似前缀一样异或即可（这大概是我写过的最详细的题解了）。
#include <bits/stdc++.h> using namespace std; int c[200005][2], a[200005], n, q; void modify(int x, int p, int k) { for (int i = x; i <= n; i += (i & -i)) c[i][k] ^= p; } int query(int x, int k) { int ans = 0; for (int i = x; i; i -= (i & -i)) ans ^= c[i][k]; return ans; } int main() { scanf("%d%d", &n, &q); for (int i = 1, x; i <= n; i++) scanf("%d", &a[i]), modify(i + 1 >> 1, a[i], i & 1); for (int i = 1, type, l, r; i <= q; i++) { scanf("%d%d%d", &type, &l, &r); if (type == 1) { modify(l + 1 >> 1, a[l] ^ r, l & 1); a[l] = r; } else { if (r - l & 1) { puts("0"); } else { if (l & 1) printf("%d\n", query(r + 1 >> 1, 1) ^ query(l - 1 >> 1, 1)); else printf("%d\n", query(r >> 1, 0) ^ query((l >> 1) - 1, 0)); } } } }
T4 NKOJ3751 扫雷游戏
题面：有一款有趣的手机游戏。棋盘上有n颗地雷，玩家需要至少扫掉其中的k颗雷。
每一步，玩家可以用手指在手机屏幕上划一条直线，该直线经过的地雷都会被扫除掉。
问，最少需要划几次就能扫除k颗以上的地雷？
题解：这个题状压 + 记忆化搜索，先通过斜率判断是否三点一线，用状压记录下共线的情况，然后直接有没扫的点直接逐个搜索将它扫掉即可。
ps：这个题我因为判断共线时将一个减号写成了乘号直接调了半个小时（小声哔哔）。
#include <bits/stdc++.h> using namespace std; struct node { int x, y; }a[(1 << 16) + 5]; int Map[20][20], f[(1 << 16) + 5], n, m; inline bool check(int i, int j, int k) {return (a[i].x - a[j].x) * (a[i].y - a[k].y) == (a[i].y - a[j].y) * (a[i].x - a[k].x);} int dfs(int s) { // printf("%d\n", s); if (f[s] != 0x3f3f3f3f) return f[s]; int sum = 0; for (int i = 1; i <= n; i++) if ((1 << i - 1) & s) sum++; if (n - m >= sum) return f[s] = 0; if (sum == 1) return f[s] = 1; for (int i = 1; i <= n; i++) { if ((1 << i - 1) & s) { for (int j = i + 1; j <= n; j++) { if ((1 << j - 1) & s) f[s] = min(f[s], dfs(s & (~Map[i][j])) + 1); } } } return f[s]; } int main() { for (int pp = 2; pp; pp--) { int tot; scanf("%d%d", &n, &m); tot = (1 << n) - 1; for (int i = 1; i <= n; i++) { scanf("%d%d", &a[i].x, &a[i].y); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i != j) { for (int k = 1; k <= n; k++) { if (check(i, j, k)) Map[i][j] |= (1 << k - 1); } } } } memset(f, 0x3f, sizeof(f)); // for(int s = 0; s <= tot; s ++)f[s] = 0x3f3f3f3f; printf("%d\n", dfs(tot)); memset(Map, 0, sizeof(Map)); memset(a, 0, sizeof(a)); } }