题意
有 \(n\) 个人，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。
因此，对于不同的开枪顺序，最后死的人也不同。
问最后死的人数最小值以及最大值。 \((1 \le n \le 10^6)\)
题解
不难发现是一道思博构造题。
首先考虑下最大值，我们只需要把这张图分三种情况讨论：
- 单个自环，贡献为 \(1\)
- 一个大于 \(1\) 的环，贡献为 \(len - 1\)
- 一个基环树，贡献为 \(size - num_{leaf}\)
对于最小值的话，我们可以不断模拟。
具体来说就是一开始把入度为 \(0\) 的人加入，这些人是活着的，然后他们瞄准的人就是必死的。
每次考虑连续三个点就行了，他们的顺序就是 活 \(\to\) 死 \(\to\) 活 的。（其实第三个人不一定活的）
然后我们对于第三个点的入度就会 \(-1\) ，如果为 \(0\) 我们加进队列继续操作。（这就意味着，它在其中任何一次死了。我们都不会加进去）
然后这样不断操作，最后只会留下环，不难发现环上至少死 \(\displaystyle \lceil \frac{len}{2} \rceil\) 个人，这样就可以做完了qwq
总结
构造题认真想想还是想的出来的，但是需要大胆猜想小心求证才行qwq
代码
这道题实现起来其实有一些巧妙之处，建议读者仔细阅读。（参考了一下 ACist大佬的博客 )
我这个代码加上流输入，就可以取得 BZOJ 速度 rank1 的好成绩qwq
#include <bits/stdc++.h>#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)using namespace std;inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}namespace pb_ds
{ namespace io{const int MaxBuff = 1 << 16;const int Output = 1 << 22;char B[MaxBuff], *S = B, *T = B;#define getc() ((S == T) && (T = (S = B) + fread(B, 1, MaxBuff, stdin), S == T) ? 0 : *S++)char Out[Output], *iter = Out;inline void flush(){fwrite(Out, 1, iter - Out, stdout);iter = Out;}}template<class Type> inline Type read(){using namespace io;register char ch; register Type ans = 0; register bool neg = 0;while(ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;ch == '-' ? neg = 1 : ans = ch - '0';while(ch = getc(), '0' <= ch && ch <= '9') ans = ans * 10 + ch - '0';return neg ? -ans : ans;}
}using namespace pb_ds;void File() {
#ifdef zjp_shadowfreopen ("1124.in", "r", stdin);freopen ("1124.out", "w", stdout);
#endif
}const int N = 1e6 + 1e3;int n, aim[N], deg[N], maxlive, minlive; bitset<N> dead, arrive;int main () {File();n = read<int>();For (i, 1, n) ++ deg[aim[i] = read<int>()];queue<int> Q;For (i, 1, n) if (!deg[i]) Q.push(i), ++ minlive;while (!Q.empty()) {int u = aim[Q.front()], v = aim[u]; Q.pop();++ maxlive; if (dead[u]) continue ;dead[u] = true; arrive[v] = true;if (!(-- deg[v])) Q.push(v);}For (i, 1, n) if (deg[i] && !dead[i]) {int len = 0; bool flag = false;for (register int u = i; !dead[u]; u = aim[u]) dead[u] = true, ++ len, flag |= arrive[u];if (!flag && len > 1) ++ minlive;maxlive += len / 2;}printf ("%d %d\n", n - maxlive, n - minlive);return 0;
}
