2023/10/14：暗流涌动

只有那些读懂迹象的人，才能明白什么正在，暗流涌动……

前言

抱歉鸽了好几天！！

最近这段时间在为某些东西攒素材（写好了会放出来），所有做杂题的时间会变少许多。

大家都好强好强……只有我什么都学不会……

本次的闲话被放在了文末，我们先来看题！

eJOI2018

今天来补 KHIN 的传教场。由于有题做过，因此压力比较小！！

感谢 KH 曾经不停地传教让我能在今天摆一摆烂！！

但事后发现我错了，剩下的题也太难写了！

Day1

嘿嘿嘿。

A. Hills

Portal.

唉这个好像是 NOIP 期间随机 CF 计划随到的题？反正做过了。以下是原题解。

设 $f(i,j,k)$ 为当前考虑到 $i$，$k$ 代表当前是不是需要满足的，$j$ 代表总共满足的个数，转移取最小值就行。

#include <bits/stdc++.h>
using namespace std;

int n;
int a[5005];
int f[5005][2505][2];

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);

    memset(f, 0x3f, sizeof(f));
    f[0][0][0] = f[1][0][0] = f[1][1][1] = 0;
    for (int i = 2; i <= n; ++i) {
        f[i][0][0] = 0;
        for (int j = 1; j <= (i + 1) / 2; ++j) {
            f[i][j][0] = min(f[i - 1][j][0], f[i - 1][j][1] + max(0, a[i] - a[i - 1] + 1));
            f[i][j][1] = min(f[i - 2][j - 1][0] + max(0, a[i - 1] - a[i] + 1), 
                             f[i - 2][j - 1][1] + max({0, a[i - 1] - a[i - 2] + 1, a[i - 1] - a[i] + 1}));
        }
    }

    for (int i = 1; i <= (n + 1) / 2; ++i)
        printf("%d ", min(f[n][i][0], f[n][i][1]));
    putchar('\n');
    return 0;
}

[ERROR] B. AB-strings

Portal.

tourist 的题果然神！！但是真难，好毒瘤，这场的最毒瘤的题。

在网上找不到说明白的题解！！这题真的只有 *2800 吗？

KH 说可以不补，那就开摆！

* C. Passports

Portal.

个人认为是这场中仅次于循环排序的好题。

不难想到状压，而且 $P\le 2$，因此 $P=2$ 时只需要枚举子集然后对于子集和补集合并状压 DP
数组即可，因此这里只需要考虑 $P=1$。

设 $f_i$ 代表集合 $i$ 中的签证全部办理完成后的最小结束时间。转移采用刷表法，考虑限制是什么：一个时间内，旅行和办理签证做多做一种。由于签证时间越长越难整，因此按照签证办理时间从小到大枚举。如果我们依次检查其它国家的限制，那么时间复杂度为 $O(n^2 2^n)$。

但这个过程显然是具有单调性的。考虑从限制本身入手：

1. 办理签证的时间不可以撞到出国的时间。
2. 如果 $p$ 正在办理签证，那么这个时间不能考虑办理签证。

按照 $l$ 从小到大考虑限制，维护两个指针来限制两条限制即可。

这样就可以 $O(n2^n)$ 完成了。

#include <bits/stdc++.h>
using namespace std; 
const int INF = 0x3f3f3f3f; 

int n, P; 
int l[24], r[24], t[24], idl[24], idt[24], f[1 << 24]; 

int ans[24][2], fr[1 << 24]; 
void calc(int s, int id) {
    if (!s) return; 
    ans[fr[s]][0] = id; ans[fr[s]][1] = f[s] - t[fr[s]]; 
    calc(s ^ (1 << fr[s]), id); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> P; int u = 1 << n; 
    for (int i = 0; i < n; ++i) cin >> l[i] >> r[i] >> t[i], r[i] += l[i] - 1, idl[i] = idt[i] = i; 
    sort(idl, idl + n, [&](int x, int y) { return l[x] < l[y]; }); 
    sort(idt, idt + n, [&](int x, int y) { return t[x] < t[y]; }); 
    memset(f, 0x3f, sizeof f); f[0] = 1; 
    for (int i = 0; i < u; ++i) if (f[i] != INF) {
        int L = 0, R = 0, now = f[i]; 
        for (int k = 0; k < n; ++k) {
            int j = idt[k]; if (i >> j & 1) continue; 
            while (1) {
                while (L < n && r[idl[L]] < now) ++L; 
                while (R < n && (!(i >> idl[R] & 1) || l[idl[R]] < now)) ++R; 
                if (L < n && l[idl[L]] <= now) { now = r[idl[L]] + 1; continue; }
                if (R < n && l[idl[R]] <= now + t[j]) { now = r[idl[R]] + 1; continue; }
                break;
            }
            if (now + t[j] < l[j] && now + t[j] < f[1 << j | i]) f[1 << j | i] = now + t[j], fr[1 << j | i] = j; 
        }
    }
    if (P == 1) {
        if (f[u - 1] == INF) { return puts("NO"), 0; }
        puts("YES"); calc(u - 1, 1); 
        for (int i = 0; i < n; ++i) printf("%d %d\n", ans[i][0], ans[i][1]); 
    } else {
        for (int s = 0; s < u; ++s) {
            int t = u - 1 - s; 
            if (f[s] == INF || f[t] == INF) continue;  
            puts("YES"); calc(s, 1); calc(t, 2); 
            for (int i = 0; i < n; ++i) printf("%d %d\n", ans[i][0], ans[i][1]); 
            return 0; 
        }
        puts("NO"); 
    }
    return 0; 
}

Day2

嘻嘻嘻。

A. Chemical table

不难猜到结论，将原图构建成二分图，然后应该一个点能到达所有点，DFS 求连通块数即可。

#include <bits/stdc++.h>
using namespace std; 

int n, m, q; 
vector<int> G[400005]; 

bool vis[400005]; 
void dfs(int x) {
    vis[x] = 1; 
    for (int y : G[x]) if (!vis[y]) dfs(y); 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m >> q; 
    while (q--) { 
        int x, y; cin >> x >> y; 
        G[x].emplace_back(n + y); G[n + y].emplace_back(x); 
    }
    int ans = 0; 
    for (int i = 1; i <= n + m; ++i) if (!vis[i]) dfs(i), ++ans; 
    cout << ans - 1 << "\n"; 
    return 0; 
}

B. Prime Tree

Portal.

之前说的“准备的素材”之一，放写过的题解。

由于题目中保证存在 $X=0$，随机一个排列然后按照条件贪心往树里填都是很容易出解的，因此直接随机化加贪心即可。

#include <bits/stdc++.h>
using namespace std;

int n, id[100005], a[100005], tmp[100005], res; 
vector<int> G[100005]; 
mt19937 Rand(time(0)); 
set<int> s; 

int gcd(int x, int y) {
    if (y == 0) return x; 
    return gcd(y, x % y); 
}

void dfs(int x, int fa) {
    if (res) return; 
    for (int i : s) if (!fa || gcd(tmp[fa], id[i]) == 1) { // 给当前点填数
        tmp[x] = id[i]; s.erase(i); 
        break; 
    }
    if (!tmp[x]) { res = 1; return; }
    for (int y : G[x]) if (y != fa) dfs(y, x); 
}

int main(void) {
    int T; scanf("%d", &T); 
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            vector<int> tmp; 
            G[i].swap(tmp); id[i] = i; 
        }
        for (int i = 1; i < n; ++i) {
            int u, v; scanf("%d%d", &u, &v); 
            G[u].emplace_back(v), G[v].emplace_back(u); 
        }
        int ans = n; 
        for (int op = 1;; ++op) {
            shuffle(id + 1, id + n + 1, Rand); s.clear(); 
            for (int i = 1; i <= n; ++i) tmp[i] = 0, s.insert(i); 
            res = 0; dfs(1, 0); 
            if (res == 0) {
                ans = 0; 
                for (int i = 1; i <= n; ++i) a[i] = tmp[i]; 
            }
            if (!ans) break; 
        }
        for (int i = 1; i <= n; ++i) printf("%d ", a[i]); putchar('\n'); 
    }      
    return 0;
}

* C. Cycle Sort

Portal.

被称作为“简单题”的构造题，但确实是好题。放写过的题解。

实际上可以套路地分析。

弱化题目条件。最优解？我不管！我们可以只交换两个数，但是这样还是很难办，数没有放的唯一位置，那么就先做排列！

观察样例。比如样例 $5$，它合并了两个操作，但是后面多出了一个操作。手玩后发现操作是可以合并的，但是最后要多出来一个长度为合并的操作数的操作。

现在考虑怎么将这个做法扩展到可以重复的数上。排列给了什么便利？每个点的入度出度都为 $1$，但如果它不是排列，它只会满足入度出度相等。

可以使用有向图的方式刻画这个过程：将 $a_i$ 的最终位置向 $a_i$ 连边，然后在这个图上找环，并且每条边经过恰好一次。这是欧拉路！在存边的时候记录一下 $i$，因为这就是方案。

#include <bits/stdc++.h>
using namespace std;

int n, s, m; 
int a[200005], b[200005], to[200005]; 
bool vis[200005]; 
vector<pair<int, int>> G[200005];
vector<bool> ban[200005]; 
vector<vector<int> > ans; 
vector<int> road; int cur[200005]; 

void dfs(int x) {
    vis[x] = 1; 
    for (; cur[x] < G[x].size(); ++cur[x]) if (!ban[x][cur[x]]) {
        int y = G[x][cur[x]].first, w = G[x][cur[x]].second; 
        ban[x][cur[x]] = 1; 
        dfs(y); road.emplace_back(w); 
    }
}

int main(void) {
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[i] = a[i];
    sort(b + 1, b + n + 1); int nn = unique(b + 1, b + n + 1) - (b + 1);  
    for (int i = 1; i <= n; ++i) to[i] = a[i] = lower_bound(b + 1, b + nn + 1, a[i]) - b;
    sort(to + 1, to + n + 1); // to 为最终的 a
    for (int i = 1; i <= n; ++i) if (a[i] != to[i]) {
        ++m; 
        G[to[i]].emplace_back(a[i], i); ban[to[i]].emplace_back(0);
    }
    if (m > s) return puts("-1"), 0;
    for (int i = 1; i <= n; ++i) if (!vis[i] && G[i].size()) {
        road.clear(); dfs(i); 
        ans.push_back(road); 
    } 
    for (int i = 0; i < ans.size(); ++i) reverse(ans[i].begin(), ans[i].end());
    
    if (min(int(ans.size()), s - m) > 1) {
        int t = min(int(ans.size()), s - m); road.clear(); road.emplace_back(ans[0][0]);
        for (int i = ans.size() - t + 1; i < ans.size(); ++i) {
            for (int x : ans[i]) ans[0].emplace_back(x); 
            road.emplace_back(ans[i][0]); ans[i].clear(); 
        }
        for (int i = 1; i < t; ++i) ans.pop_back(); 
        reverse(road.begin(), road.end()); ans.push_back(road); 
    }
    printf("%u\n", ans.size()); 
    for (int i = 0; i < ans.size(); ++i) {
        printf("%u\n", ans[i].size()); 
        for (int x : ans[i]) printf("%d ", x); 
        putchar('\n'); 
    }
    return 0;
}

总结

题目质量：循环排序 > 互素树 > 护照 = AB-Strings。

看来机器人也是会说谎的。可能是每个人的观点不同。

蔚蓝之海

再次重读了一些东西，越来越觉得希特勒在二战前期的运气是真的好，好到离谱了。虽然不排除就是当时时代的原因。

最近听了一些比较神秘的歌，它们给我一种“暗流涌动”的感觉。就是你，二向箔降维打击。

波澜壮阔的背后，实则是太阳系的毁灭。为什么，会是这样呢……

《克罗地亚狂想曲》用最为欢快的节奏描述了一个饱受战火摧残的残垣断壁；诺曼底用波光粼粼的海面描述了一场人类历史上规模最大的登陆作战。

为什么呢？这是为什么呢？

绝望到空灵的程度，这是什么？

在被摧毁的大地上获得新生——如克罗地亚废墟上的那朵白色小花。

在天际线，不要停留

After Memories

我可以告诉你，我现在写的这些东西也是在打素材，您信吗？

本来这篇应该两天前就发的，但是一直鸽到了今天！都怪这几天太摆了（实际上身体出了一些奇怪的问题，而且一直在打素材）！

不过现在好的差不多了，那就开始认真摆烂吧（

不知道为什么想哭，也许与人的离别是常态，与过去的离别也是必然，跪倒在你的墓碑前，感叹着那连神都打不败的你。