D - Two-Colored Dominoes
E - Speedrun
题意
给定 \(n,m,k\) 。你需要考虑一个序列 \(t\)。
\(n\) 个要求：\(t_i \equiv h_i\mod k\)。
\(m\) 个要求：\(t_{u_i} \le t_{v_i}\)。
求 \(\min(\max\{t\}-\min\{t\})\)。
思路
假设我们需要求 \(\min(\max\{t\})\)。
那么实际上可以拓扑排序+枚举 \(\lfloor \frac{t_i}{k} \rfloor\) + 堆做到 \(O(n\log_2{n})\) 求出答案以及相应的 \(t\)。
然后我们考虑对于 \(t_i < k\) 的 \(t_i\) 额外构成一个 \(t'\)。而我们可以枚举以 \(t'_i\) 为 \(\min\{t\}\) ，并求出答案。
直接这样做 \(O(n^2\log_2{n})\)，寄。
我们考虑按照 \(t'_i\) 从小到大的顺序枚举，每次把所有不合法的 \(t_j\) 加上 \(k\)，直到满足条件。
我们会发现由于拓扑排序的加上取模的性质，每个 \(t_j\) 最多会加一次 \(k\)。所以总时间复杂度 \(O(n\log_2{n})\)。
上述的操作可以用 map 实现。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int T, n, m, dk, h[200005], x, y, tim[200005];
int rd[200005], firs[400005], nex[400005], to[400005], tot;
bool is_move[200005];
queue < int > Q;
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > gq;
map < pair < int , int > , bool > mp;
void Add (int u, int v){
++ tot;
nex[tot] = firs[u];
firs[u] = tot;
to[tot] = v;
}
void Clear (){
for (int i = 1;i <= n;++ i){
rd[i] = 0;
firs[i] = 0;
is_move[i] = false;
}
tot = 0;
mp.clear ();
}
signed main (){
scanf ("%lld", &T);
while (T --){
scanf ("%lld%lld%lld", &n, &m, &dk);
Clear ();
for (int i = 1;i <= n;++ i)
scanf ("%lld", &h[i]);
for (int i = 1;i <= m;++ i){
scanf ("%lld%lld", &x, &y);
Add (x, y);
++ rd[y];
}
for (int i = 1;i <= n;++ i)
if (rd[i] == 0)
Q.push (i);
for (int d = 0;! Q.empty ();++ d){
while (! gq.empty ())
gq.pop ();
while (! Q.empty ()){
gq.push (make_pair (h[Q.front ()], Q.front ()));
Q.pop ();
}
int nt, u, v;
while (! gq.empty ()){
nt = gq.top ().first;
u = gq.top ().second;
tim[u] = nt + d * dk;
mp[make_pair (tim[u], u)] = true;
gq.pop ();
for (int e = firs[u];e;e = nex[e]){
v = to[e];
-- rd[v];
if (rd[v] == 0){
if (h[v] < nt)
Q.push (v);
else
gq.push (make_pair (h[v], v));
}
}
}
}
int st, ed, Ans = 1e18;
while (! is_move[mp.begin ()->first.second]){
map < pair < int , int > , bool > :: iterator it = mp.begin ();
is_move[it->first.second] = true;
st = it->first.first;
ed = mp.rbegin ()->first.first;
Ans = min (Ans, ed - st);
tim[it->first.second] += dk;
Q.push (it->first.second);
mp.erase (it);
while (! Q.empty ()){
int u = Q.front ();
mp[make_pair (tim[u], u)] = true;
Q.pop ();
for (int e = firs[u];e;e = nex[e]){
int v = to[e];
if (tim[v] < tim[u]){
mp.erase (make_pair (tim[v], v));
tim[v] += dk;
is_move[v] = true;
Q.push (v);
}
}
}
}
printf ("%lld\n", Ans);
}
return 0;
}
F - Divide, XOR, and Conquer
题意
给一个长为 \(n\) 的序列 \(a\)，初始区间为 \([1,n]\)。
每次可以将区间分成左右两段：\([l,k],[k+1,r]\)。\(k\) 由你自选。
然后选取两段区间中异或和较大的那一段（如果两段相等，则任意选择）。
对于每个 \(i\) 问最后能不能得到区间 \([i,i]\)。
思路
记 \(S(l,r)\) 表示 \([l,r]\) 区间异或和，记 \(E(x)\) 表示 \(x\) 的二进制下最高位。
然后我们会发现对于 \(e>E(S(l,r))\) 的位，我们无论怎么划分，两边这位的异或值都相等（同为 \(1\) 或 同为 \(0\)）。
而对于 \(E(S(l,r))\) 这一位，若一个区间内的这位为 \(1\)，则另一个区间中的这位为 \(0\)，否则另一个区间中的这位为 \(1\)。总之，我们只需要选出包含奇数个这位为 \(1\) 的数的区间，那么这个区间一定会被选。而两段异或和相等的情况，只能出现在 \(S(l,r)=0\) 的情况下，这时可以随便划分。
所以我们对于每个 \([l,r]\) 判断其是否合法，等价于找到一个区间 \([l,R],R>r\) 合法，且 \(E(S(l,r))=E(S(l,R))\) 或 \(S(l,R)\) 随便选。\(r\) 端点同理。
所以我们可以记录 \(bl_l\) 为 \(l\) 作为左端点时的合法区间最高位合集，\(br\) 同理。然后我们可以从大到小枚举区间，然后判断 \((E(S(l,r)) \in bl_l) \lor (E(S(l,r)) \in br_r) \lor (\exists [l,R]:R>r,S(l,R) = 0) \lor (\exists [L,r]:L<l,S(L,r) = 0)\) ，若为真，则 \([l,r]\) 合法，否则不合法。其中 \(\lor\) 是逻辑运算或，\(\exists\) 表示存在。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int T, n, a[10005], bl[10005], br[10005], s[10005];
char Ans[10005];
int log2_ (int u){
int l = 1, r = 61;
while (l < r){
int mid = l + r >> 1;
if ((u >> mid) > 0)
l = mid + 1;
else
r = mid;
}
return l - 1;
}
bool Check (int l, int r){
if (l == 1 && r == n)
return 1;
if (bl[l] >> 60 & 1)
return 1;
if (br[r] >> 60 & 1)
return 1;
int S = s[r] ^ s[l - 1];
return (S & bl[l]) > 0 || (S & br[r]) > 0;
}
void Operation (int l, int r){
int S = s[r] ^ s[l - 1], bit;
if (S == 0)
bit = 60;
else
bit = log2_ (S);
bl[l] |= 1ll << bit;
br[r] |= 1ll << bit;
}
void Solve (){
scanf ("%lld", &n);
for (int i = 1;i <= n;++ i){
scanf ("%lld", &a[i]);
s[i] = s[i - 1] ^ a[i];
Ans[i] = '0';
bl[i] = br[i] = 0;
}
for (int len = n;len >= 1;-- len)
for (int l = 1, r = len;r <= n;++ l, ++ r)
if (Check (l, r)){
Operation (l, r);
if (len == 1)
Ans[l] = '1';
}
for (int i = 1;i <= n;++ i)
putchar (Ans[i]);
puts ("");
}
signed main (){
scanf ("%lld", &T);
while (T --)
Solve ();
return 0;
}
G - Swaps
题意
给你一个序列 \(a\) ，每次可以将 \(a_{a_i}\) 和 \(a_i\) 的值交换。问可以得到多少种不同的 \(a\)，操作不同但 \(a\) 最终相同的情况只记一种。
思路
好题。
先考虑 \(a_i\) 的本质是将当前位置和 \(a_i\) 位置上的数交换，注意是当前位置，所以我们可以对于每个 \(a_i\) 将其扩展成一个二元组 \(b_x = (a_i,i)\) 使每个位置上的信息唯一（注意到随着交换，\(x\) 不一定等于 \(i\)），然后我们考虑把 \((a_i,i)\) 当成一个编号为 \(i\) 的操作，具体为将当前位置和 \(a_i\) 位置上的数交换。
然后我们发现我们对于选取的一个固定的操作集，不管用什么顺序进行操作，最后的序列一定是一定的，所以说计数考虑乘法原理而不需要顺序。
这时候我们考虑建图，连边 \(i \to a_i\)。记 \(out_i\) 为 \(i\) 出边个数，\(in_i\) 为 \(i\) 入边个数，\(IN_i\) 为 \(i\) 入边的另一端点构成的集合。显然 \(out_i = 1,in_i \ge 1,\forall j \in IN_i:a_j = i\) 。
然后对于这个交换操作还有性质，即两个不同的 \(a\) 值交换后不管做什么操作都不会回到原序列，因为交换前 \(a_i \ne i,a_j=i\)，交换后 \(a'_j = a_i,a'_i=i\)，而以 \(i\) 作为起点只能和自己交换，以 \(i\) 作为终点只能和 \(a_k=i\) 交换，都属于相同值交换，无意义。
我们考虑反向拓扑序计算答案。
假设 \(a_i\) 点的答案已经被计算（实际上我们不关心 \(a_i\) 当前的值），这时考虑 \(i\) 点的答案，然后我们会发现有 \(in_i\) 个点指向 \(i\)，这时实际上我们只要在这 \(in_i\) 个点中选了 \(x\) 并让 \(a_i\) 与 \(a_x\) 交换，这时 \(a_i\) 的值已经是 \(i\) 了，对于其他的 \(j \in IN_i - \{x\}\) 有 \(a_j = i\) ，无论选哪个 \(j\) 都和选 \(j\) 之前的序列一样，无意义。
所以我们对于 \(i\) 点，要么不与 \(IN_i\) 中任何一点交换，要么只与其中一点交换，方案数为 \(in_i + 1\)。由于我们是反向拓扑序计算，所以这些情况都是链上的情况，而且互相之间不影响。
因为 \(n\) 个点 \(n\) 条边，所以必有环，且必为简单环。所以考虑环上的情况。我们依然考虑用链的方式计算（但显然会算重），然后考虑哪些地方算重了。实际上我们发现刚刚漏掉了一个很重要的情况，因为我们刚刚不关心 \(a_i\) 的当前值，但假如 \(a_i=i\)，实际上我们对于 \(i\) 的方案数就不是 \(in_i + 1\) 而是 \(1\) 了，因为无论怎么交换都是相同值交换，无意义，所以只能不交换。而我们稍加分析又可知若 \(a_i=i\) 那么 \(a_i\) 一定在环上，（要么为自环，否则 \(i\) 作为 \(a\) 值只能继承自指向 \(i\) 的点，而继承是指一个点继承其指向的位置上的 \(a\) 值） 。
然后好消息是，环上只有这个地方会算重，所以考虑减去。考虑某一刻 \(a_i=i\)，但这时我们还没有算它，这种情况只有当环上其他点都选择被环上的点继承，有 \(1\) 种可能，而这时 \(i\) 只能选择不被任何一个点继承，只有 \(1\) 种方案，而我们原本计算的这个点的选择有 \(in_i+1\) 种，所以在环上的整体贡献对于每个点都要减去 \(in_i\)，所以这个环的总贡献为：
然后我们把环当成一个已经计算贡献的点，对于链因为不会算重，所以贡献直接是 \((in_i+1)\)。
所以答案就是贡献乘起来：
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9 + 7;
int n, a[1000005], d[1000005], Ans = 1;
int vis[1000005];
signed main (){
scanf ("%lld", &n);
for (int i = 1;i <= n;++ i){
scanf ("%lld", &a[i]);
++ d[a[i]];
}
for (int i = 1;i <= n;++ i){
if (vis[i] > 0)
continue;
int u = i, v = i, Res = 1;
while (vis[u] == 0){
vis[u] = i;
u = a[u];
}
while (v != u){
(Ans *= d[v] + 1ll) %= mod;
v = a[v];
}
if (vis[u] != i)
continue;
do {
(Res *= d[v] + 1ll) %= mod;
v = a[v];
} while (v != u);
do {
(Res += mod - d[v]) %= mod;
v = a[v];
} while (v != u);
(Ans *= Res) %= mod;
}
printf ("%lld\n", Ans);
return 0;
}