6-26
T1多米诺骨牌
Hades 与 Dionysus 在狂饮后玩起了多米诺骨牌的小游戏。 现在桌上有 n 块多米诺骨牌，每块多米诺骨牌上半部分和下半部分上都有一 个整数。每次翻转可让一块多米诺骨牌上下翻转，即上下部分数交换。 Hades 想 让 n 块骨牌上半部分的数加起来是一个偶数，而 Dionysus 想让这 n 块骨牌下半 部分的数加起来是一个偶数。喝醉的两人都不肯退让，非要达到自己的目的。路 过的 Hephaestus 在扫了一眼桌上的骨牌后瞬间给出了一个让两人都满意且翻转 次数最少的方案，便转身离去，留下呆滞的二人。 可这还没完，喝得烂醉的二人很快忘记了 Hephaestus 所说的方案， Hades 说 他还记得最少的翻转次数， Dionysus 不愿被比下去，只好来请教你了。
发现了以下性质：
-对于上下都是偶数或都是奇数的骨牌，交换它是没有意义的。
-对于上下一奇一偶的骨牌，翻转它能使总和从两个奇数变为两个偶数。
-对于目前总和为一奇一偶的情况无论怎么翻转都无法达成目标。
std:
#include <bits/stdc++.h> typedef long long ll; using std::min; using std::max; #define INF 1e18 #define pE() puts("") #define W(x) write(x) #define rd() read<ll>() #define lowbit(x) -x & x #define pS() putchar(' ') #define E(i, l, r) for (int i = l; i <= r; ++ i) template <typename T> inline T read() { T x = 0; bool f = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x / 10) write(x / 10); putchar((x % 10) ^ 48); } const int N = 1e4 + 5; int n, a[N], b[N]; ll sumx, sumy; int main() { freopen("domino.in", "r", stdin); freopen("domino.out", "w", stdout); n = rd(); E(i, 1, n) { a[i] = rd(); b[i] = rd(); sumx += a[i]; sumy += b[i]; } sumx %= 2; sumy %= 2; if (sumx + sumy == 1) W(-1); else if (sumx == 0 && sumy == 0) W(0); else { bool flag = 0; E(i, 1, n) if ((a[i] % 2) ^ (b[i] % 2)) { W(1); flag = 1; break; } if (!flag) W(-1); } return 0; }
T2队列
N 个学生排队站在食堂的面包窗口前，在面包没有准备好之前，这个队伍发 生了一些变化。 若第 i 个位置上是一个男生，而他后面(i+1 的位置)是一个女生，出于某种目 的，他会与这位女生交换位置，使她能更接近窗口。这样的交换需要 1 秒的时间。 这样的位置交换会一直持续到无法再交换为止。即所有的女生都在男生前面。 问这样的交换会持续多久。
假设现在已经知道前一个女孩到达指定地点的时间记为 ans 对于当前的一个女孩，存在两种情况： --她到达前一个女孩初始位置后一位时，那个女孩还没有走掉，如： MFFFFFFMMF 那么这个女孩所需的时间为 ans+1。 --她到达前一个女孩初始位置后一位时，那个女孩已经走掉了，如： MFMMMF 发现此时在前一个女孩的牺牲‘铺垫’下，这个女孩可以一直走到她 最终的位置， 即她所需的时间为‘初始位置-最终位置’。 两者取 max 即为当前女孩到达最终位置所需的时间。
std：
#include <bits/stdc++.h> typedef long long ll; using std::min; using std::max; #define INF 1e18 #define pE() puts("") #define W(x) write(x) #define rd() read<ll>() #define lowbit(x) -x & x #define pS() putchar(' ') #define E(i, l, r) for (int i = l; i <= r; ++ i) template <typename T> inline T read() { T x = 0; bool f = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x / 10) write(x / 10); putchar((x % 10) ^ 48); } const int N = 1e6 + 5; int n; int ans, cnt, cntm; char inp; bool flag; int main() { freopen("queue.in", "r", stdin); freopen("queue.out", "w", stdout); while ((inp = getchar()) == 'M' || inp == 'F') if (inp == 'M') { if (cnt) cnt--; cntm++, flag = 1; } else if (flag) ans = cntm + cnt++; W(ans); return 0; }
T3可持久化数组
Motto 有一个长为 n 可持久化数组，在初始时刻(t=0)，第 i 个位置上的数为 ai，他会对这个可持久化数组进行 m 个操作或询问。 Motto 在每个整数时刻 t(1<=t<=m)会问你一个问题，或者对这个数组作一个 修改：
-
0 a b 将第 a 个位置上的数改成 b，且这一时刻第 a 个位置上的数视为 b。
-
1 a b 询问第 a 个位置上时刻为 b(t=b)时的数值。
开 n 个 vector，每个 vector 维护这个位置曾经的版本，和曾经这个位置为 该版本的最早时间和最晚时间。修改直接 push_back，查询的话可以在 vector 上二分查找。
std：
#include <bits/stdc++.h> typedef long long ll; using std::min; using std::max; #define INF 1e18 #define pE() puts("") #define W(x) write(x) #define rd() read<ll>() #define lowbit(x) -x & x #define pS() putchar(' ') #define E(i, l, r) for (int i = l; i <= r; ++ i) template <typename T> inline T read() { T x = 0; bool f = 0; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = 1; c = getchar(); } while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x / 10) write(x / 10); putchar((x % 10) ^ 48); } const int N = 1e5 + 5; struct Node { int data; int id; }; int n, m; std::vector<Node> V[N]; int main() { freopen("array.in", "r", stdin); freopen("array.out", "w", stdout); n = rd(); m = rd(); E(i, 1, n) { int x = rd(); V[i].push_back({x, 0}); } E(i, 1, m) { int opt = rd(); int x, y; x = rd(); y = rd(); if (opt == 0) V[x].push_back({y, i}); else { int l = 0, r = V[x].size() - 1; while (l < r) { int mid = l + r + 1 >> 1; if (V[x][mid].id <= y) l = mid; else r = mid - 1; } W(V[x][l].data); pE(); } } return 0; }
T4毒瘤 hzq
由于 hzq 出了大量的毒瘤题，机房里的同志们开始商量如何针对 hzq 搞事情。 某同志提出了一个建议：在校园里堵住他。 一中的校园非常大，为了将问题简单化，我们将校园看作一个 n 个点， m 条 边的无向连通图。 然而 hzq 知道了自己即将被搞事情，他对校园里的每条边定义了一个危险值， 他每天一定且仅会在某棵关于危险值的最小生成树的所有树边上出现至少一次。 刚才提出意见的同学根据自己对 hzq 的了解，猜测到了他每天会在满足什么 样的条件的边上出现，可是校园这么大， hzq 每天会在哪些边上出现呢？ 其实刚才提出意见的同学就是你，请你告诉机房里的同志们，在一天的时间 里，对于每一条道路， hzq 一定会出现，还是一定不会出现，还是可能会出现。
将边按权值从小到大排序，对于相同权值的所有边，将 所有不必要的边(即连接的两点可以通过更小权值的边连通的边)的答案标记为 ‚No‛ ，将剩下的边单独拎出来，用 tarjan 求割边，割边的答案为‚Yes‛ ，其 余边的答案为‚I AM NOT SURE!!!‛
std：
#include <bits/stdc++.h> using namespace std; #define fi first #define se second mt19937_64 gen(time(0)); using u64 = unsigned long long; int n, m; struct edge { int u, v, w, ans, id; bool is; } e[300005]; int b[100005]; int find(int x) { if (b[x] == x) return x; return b[x] = find(b[x]); } vector <pair <int, int>> G[100005]; int f[100005][17], g[100005][17], dep[100005], dfn[100005], timer = 0, sz[100005]; void dfs(int u, int ff) { dfn[u] = ++timer, sz[u] = 1; f[u][0] = ff, dep[u] = dep[ff] + 1; for (int i = 1; i <= 16; ++i) { f[u][i] = f[ f[u][ i - 1 ] ][ i - 1 ]; g[u][i] = max(g[u][ i - 1 ], g[ f[u][ i - 1 ] ][ i - 1 ]); } for (auto v : G[u]) if (v.fi != ff) { g[ v.fi ][0] = v.se; dfs(v.fi, u); sz[u] += sz[ v.fi ]; } } int qry_max(int x, int y) { if (dep[x] < dep[y]) swap(x, y); int ans = 0; for (int i = 16; ~i; --i) { if (dep[ f[x][i] ] >= dep[y]) { ans = max(ans, g[x][i]); x = f[x][i]; } if (x == y) return ans; } for (int i = 16; ~i; --i) { if (f[x][i] != f[y][i]) { ans = max({ans, g[x][i], g[y][i]}); x = f[x][i], y = f[y][i]; } } ans = max({ans, g[x][0], g[y][0]}); return ans; } map <int, vector <int>> E, Q; u64 t[100005], h[300005]; void add(int x, u64 v) { for (; x <= n; x += x & -x) t[x] ^= v; } u64 qry(int x) { u64 ans = 0; for (; x; x -= x & -x) ans ^= t[x]; return ans; } int main() { freopen("hzq.in", "r", stdin), freopen("hzq.out", "w", stdout); ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; ++i) { cin >> e[i].u >> e[i].v >> e[i].w; e[i].id = i, e[i].is = false; } sort(e + 1, e + m + 1, [&] (edge a, edge b) { return a.w < b.w; }); iota(b + 1, b + n + 1, 1); for (int i = 1; i <= m; ++i) { int fx = find(e[i].u), fy = find(e[i].v); if (fx != fy) { b[fx] = fy, e[i].is = true; G[ e[i].u ].emplace_back(e[i].v, e[i].w); G[ e[i].v ].emplace_back(e[i].u, e[i].w); } } dfs(1, 0); for (int i = 1; i <= m; ++i) if (!e[i].is) { int now = qry_max(e[i].u, e[i].v); if (e[i].w > now) e[i].ans = -1; else if (e[i].w == now) e[i].ans = 0; } for (int i = 1; i <= m; ++i) if (e[i].is) { Q[ e[i].w ].push_back(i); } else E[ e[i].w ].push_back(i); vector <int> V; for (int i = 1; i <= m; ++i) V.push_back(e[i].w); for (int i = 1; i <= m; ++i) h[i] = gen(); sort(V.begin(), V.end()); V.erase(unique(V.begin(), V.end()), V.end()); for (auto w : V) { for (auto i : E[w]) { int u = e[i].u, v = e[i].v; u64 val = h[ e[i].id ]; add(dfn[u], val), add(dfn[v], val); } for (auto i : Q[w]) { int u = e[i].u, v = e[i].v; if (dep[u] < dep[v]) swap(u, v); if (qry(dfn[u] - 1) == qry(dfn[u] + sz[u] - 1)) e[i].ans = 1; else e[i].ans = 0; } for (auto i : E[w]) { int u = e[i].u, v = e[i].v; u64 val = h[ e[i].id ]; add(dfn[u], val), add(dfn[v], val); } } sort(e + 1, e + m + 1, [&] (edge a, edge b) { return a.id < b.id; }); for (int i = 1; i <= m; ++i) { if (e[i].ans == 1) cout << "Yes\n"; else if (e[i].ans == 0) cout << "I AM NOT SURE!!!\n"; else if (e[i].ans == -1) cout << "No\n"; } return 0; }