ARC VP 集合

听了 zjk 的建议，vp ARC 打着玩就当思维训练了。

要注意的是 ARC103 ~ ARC058 这一段的编号比较奇怪，他是按照 abc arc 合并来编号的。

我代码里一般用的是 ARC103D 这样的形式，但是这个实际上在 atc 上的题号是 arc103_b。

卷题记录：https://kenkoooo.com/atcoder/#/table/black_trees 欢迎监督。

目前计划是九月一号之前 vp 完 ARC103 ~ ARC058（随机开题）

ARC080ψ(｀∇´)ψ

CSP2022 考前一天和 hfy 还有 wcx 随机跳了一场 ARC 打着玩，就当开拓思维了。

发现远古 ARC 和 ABC 是成对出现的，相当于 div1 和 div2。

感觉 CDE 都是可做题，CD 比较平凡，E 是小清新思维题，感觉需要擅长观察结论才弄得出来。

F 不太会，以后可以看看

C - 4-adjacentψ(｀∇´)ψ

给你一个序列 \(a\)，你要重排这个序列，使得相邻两项乘积都是 4 的倍数。

如果有解输出 Yes,否则输出 No。

比较简单，考虑分类，一类是奇数，一类是 \(4\) 的倍数，另外一类是不是 \(4\) 的倍数的偶数。

注意到奇数的两边不是边界就一定要是 \(4\)，如果没有 \(2 \times \text{odd}\) 形式的数，那只要奇数个数小于等于 \(4\) 的倍数的个数 \(+ 1\) 即可。

如果有 \(2 \times \text{odd}\) 形式的数，那么奇数的个数必须要是 \(\le\) \(4\) 的倍数的个数的。

然后就没了。

Code

int c = 0, cc = 0, ccc = 0;
cin >> n;
for(int i = 1; i <= n; ++i) {
    cin >> a[i];
    if(a[i] & 1) c++;
    else if(a[i] % 4 == 0) ccc++;
    else if(a[i] % 2 == 0) cc++;
}
if((c > ccc && cc) || c - 1 > ccc) 
    cout << "No" << endl;
else cout << "Yes" << endl;

D - Grid Coloringψ(｀∇´)ψ

给你一个序列 \(a\)，长度为 \(q\)，给定一个 \(n\times m\) 的网格。

保证 \(\sum a_i = n \times m\)，现在要求你染 \(q\) 个 4-联通块出来，其中颜色 \(i\) 要有 \(a_i\) 个格子，构造方案。

\(100\)。

笨比题，蛇形染色即可，显然一定有解。

E - Young Maidsψ(｀∇´)ψ

题目名字好怪。

给你一个 \(1 \sim n, (n \equiv 0 (\mod 2))\) 的排列 \(p\)，你每次可以取出相邻的两个元素，把他们按照原来的顺序扔到一个队列的头部。

问你最后可能得到的字典序最小的排列是什么。

数据范围 \(2e5\)。

感觉很小清新，需要一定观察能力？

首先正着显然不好搞，考虑倒过来观察合法解的形状（感觉和 221025C 的罪人挽歌那题想法类似）。

首先注意到如果取了 \((x, y)\) 这两个位置，那么 \([x + 1, y - 1]\) 这个区间是不能和其它区间组合的，也就是不能跨区间操作。

由此可以发现每次取到的是一个奇数项 + 一个偶数项的形式（不然一定没法把任意一个 \([x + 1, y - 1]\) 取完（因为这样长度不是偶数））。

要字典序最小，谈就需要靠后取到的奇数项尽量小，因为这是一个排列所以我们不用考虑偶数项大小（不会有相同的）。

然后每次我们把当前的可以取的区间拿出来放进一个堆，关键字是奇数项最小值。

每次贪心地取堆顶，决策完之后断三个区间出来，插入回去，不断取直到堆为空，然后就做完了。

维护原序列奇数项的区间最小值和偶数项的区间最小值直接 RMQ，中间空出来的用 \(+\infty\) 补全就行。

Code

// author : black_trees

#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;
const int inf = 0x3f3f3f3f;

int n;
int a[si], b[si], p[si];

class Segment_Tree {
    private:
        struct node {
            int l, r;
            int minv;
        } t[si << 2];
        inline void pushup(int p) {
            t[p].minv = min(t[p << 1].minv, t[p << 1 | 1].minv);
        }
    public:
        void build(int p, int l, int r) {
            t[p].l = l, t[p].r = r;
            if(l == r) { t[p].minv = b[l]; return; }
            int mid = (l + r) >> 1;
            build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
            pushup(p);
        }
        int query(int p, int ql, int qr) {
            int ret = inf, l = t[p].l, r = t[p].r;
            if(ql <= l && r <= qr) return t[p].minv;
            int mid = (l + r) >> 1;
            if(ql <= mid) ret = min(ret, query(p << 1, ql, qr));
            if(qr > mid) ret = min(ret, query(p << 1 | 1, ql, qr));
            return ret;
        }
} tr[2];

struct Interval {
    int l, r;
    int odd, even;
    bool operator < (const Interval &t) const {
        return odd > t.odd;
    }
};
std::priority_queue<Interval> q;

void Insert(int l, int r) {
    if(l > r) return;
    int x = tr[l & 1].query(1, l, r), y = tr[l & 1 ^ 1].query(1, p[x] + 1, r);
    q.push({l, r, x, y});
}
void Assign(Interval t)  {
    Insert(t.l, p[t.odd] - 1), Insert(p[t.odd] + 1, p[t.even] - 1), Insert(p[t.even] + 1, t.r);
}

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i], p[a[i]] = i;

    memset(b, 0x3f, sizeof b);
    for(int i = 1; i <= n; i += 2)
        b[i] = a[i];
    tr[1].build(1, 1, n);
    memset(b, 0x3f, sizeof b);
    for(int i = 2; i <= n; i += 2) 
        b[i] = a[i];
    tr[0].build(1, 1, n);

    Insert(1, n);
    while(!q.empty()) {
        Interval u = q.top(); q.pop();
        cout << u.odd << " " << u.even << " ";
        Assign(u);
    }

    return 0;
}

F - Unknown.ψ(｀∇´)ψ

我不会。

ARC076ψ(｀∇´)ψ

这次是 NOIP2022 考前和 hfy 一起进行脑洞打开。

因为懒所以盒盒代码。

C - Reconciled?ψ(｀∇´)ψ

给你 \(n\) 只带编号的狗，\(m\) 只带编号的猴。

要求出满足没有任意的狗/猴连通块的排列方式。

\(1\le n, m\le 1e5\)。

简单题，注意到 \(|n - m| \ge 2\) 必定无解。

然后 \(n = m\) 的时候答案是 \(n!m!\)。

如果是 \(|n - m| = 1\)，答案是 \(2n!m!\)。

D - Built?ψ(｀∇´)ψ

定义两个点的 \(dis\) 为 \(\min(|x_1 - x_2|, |y_1 - y_2|))\)。

给定 \(n,(1\le n \le 1e9)\) 个点，求使得这些点联通的代价最小值。

联通两点的代价是 \(dis\)。

本质是求最小 dis 生成树，直接加边是 \(O(n^2)\) 的不能接受。

注意到其实我们可以对 \(x, y\) 分别排个序，然后对于一个点，让他和它在排列上的左右两点连边就行了。

然后一遍 MST 完事。

E - Connected?ψ(｀∇´)ψ

给出一个 \(R\times C\) 的棋盘，其中 \(1\) 到 \(n\) 之间的每个正整数都会在棋盘上出现两次，

给定第 \(i\) 个数出现的位置，要求把每一对相同的数用线（粗细忽略不计）连起来，且线不能相交也不能越过棋盘边界，求是否能完成。

\(R,C 1e8, n 1e5\)。

注意到只有两端在边界的线才会对答案造成影响，其它的在里面转几下就行了。

所以只需要考虑判所有两端都在边界的点对形成的连线是否相交。

注意到这个实际上可以钦定一个转圈的方向（顺时针，逆时针），把这个东西当成括号序列。然后判断一下括号序列是否合法就行。

F - Unknownψ(｀∇´)ψ

我不会。

ARC103ψ(｀∇´)ψ

这里是系统性 vp 的开始，之前只能算是偶尔玩玩。

vp date: 2023/06/02
Finish date: 2023/06/02

Status/Problem	C	D	E	F
Difficulty	826	2677	1722	2836
Solved	Yes	No	No	No
Correction	/	Yes	Yes	Yes
Solution	Yes	Yes	Yes	Yes

考场 E 想到正解了，但是没调完，赛后 1min 才过.

是期末考试前 vp 的，这段时间心情不太好，所以这个算是调节。

C - /\/\/\/ψ(｀∇´)ψ

给你一个长度为 \(n\) 的序列，你每次可以修改一个位置，问将序列变好的最小操作次数

一个序列 \(a\) 是好的，当且仅当 \(a\) 中只有两个数，并且 \(\forall i, a_i = a_{i + 2}\)。

保证 \(n\) 是偶数，\(1\le n, a_i \le 10^5\)。

奇偶位置分开考虑是很好想到的，并且它们两个子序列相互独立不影响。

可以注意到，每次一定是保留子序列里出现次数最多的那个，剩下的全部改完。

因为奇偶不能相同，所以还要判一下。

这题开始的时候还考虑了很多情况，但其实最后都归化到了这两个情况。

所以总结一个教训：如果是看起来很像分类讨论的题，多想想是不是可以归化，这样有助于简化思考，也不会那么烦。

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 1e5 + 10;

int n;
struct node {
    int val, cnt;
    bool operator < (const node &rhs) const {
        return cnt > rhs.cnt;
    }
} odd[si], even[si];

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n;
    for(int i = 1; i <= si - 10; ++i)
        odd[i].val = even[i].val = i,
        odd[i].cnt = even[i].cnt = 0;
    for(int i = 1; i <= n; ++i) {
        int val; cin >> val;
        if(i & 1) odd[val].cnt += 1;
        else even[val].cnt += 1;
    }
    sort(odd + 1, odd + 1 + si - 10);
    sort(even + 1, even + 1 + si - 10);

    if(odd[1].val == even[1].val) {
        int ans = 0x3f3f3f3f;
        ans = min(n - odd[1].cnt - even[2].cnt, ans); // 在没有确定的情况下，不要轻易断言变量的大小关系。
        ans = min(n - even[1].cnt - odd[2].cnt, ans); // 我开始的时候把这两个情况分开按 [1]cnt 考虑了，忽略了 [2]cnt。
        cout << ans << endl;
    }
    else cout << n - odd[1].cnt - even[1].cnt << endl;

    return 0;
}

D - Robot Armsψ(｀∇´)ψ

给你 \(n\) 个，网格上的点，你需要构造一个机械臂，使得机械臂从 \((0, 0)\) 开始，能通过弯折关节的方式到达这些点。

机械臂有 \(m\) 个段，段和段之间的关节可以是任意转动的，但是只有上下左右四个方向。

现在你需要给出段的长度序列 \(c\)，并对每个点构造可行的方案，\(m\) 也是你来构造。

\(1\le n \le 1000, |x_i, y_i| \in [0, 10^9]\)。

要求你构造的 \(m \in [1, 40], c_i \in [1, 10^{12}]\)。

无解输出 -1

看到这个数据范围很容易想到，\(2^{40} > 10^{12}\) 并且没大多少。

于是我们可以考虑二进制拆分，注意到如果存在 \((x_i + y_i) \not\equiv (x_j + y_j) \pmod 2\)，显然无解。

然后奇数可以通过位移得到偶数的情况。

那么剩下的，就考虑二进制拆分即可，注意从高位考虑。

Code

// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long

using namespace std;
using i64 = long long;

const int si = 1e3 + 10;

int n, m;
int pw[si], ck[2];
int x[si], y[si], cnt;

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> x[i] >> y[i];
        ck[(x[i] + y[i]) & 1] += 1;
    }
    if(ck[0] && ck[1]) return cout << "-1" << endl, 0;
    for(int i = 38; ~i; --i)
        pw[++cnt] = 1ll << i;  
    if(ck[0]) pw[++cnt] = 1ll;
    cout << cnt << endl;
    for(int i = 1; i <= cnt; ++i) 
        cout << pw[i] << " \n"[i == cnt]; 

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= cnt; ++j) {
            if(abs(x[i]) > abs(y[i])) {
                if(x[i] < 0) cout << "L", x[i] += pw[j];
                else cout << "R", x[i] -= pw[j];
            }
            else {
                if(y[i] < 0) cout << "D", y[i] += pw[j];
                else cout << "U", y[i] -= pw[j];
            }
        }
        cout << endl;
    }
    return 0;
}

E - Tr/eeψ(｀∇´)ψ

给你一个长度为 \(n\) 的 01 串 \(s\)，你需要判断 \(s\) 是否能生成一颗树。

生成方式是：如果 \(s_i = \texttt{1}\)，那么存在一条边，切断之后有一个大小为 \(i\) 的连通块。

反之，无论我们怎么切割，都应当无法构造出一个大小为 \(i\) 的连通块。

你需要给出解，或者输出 -1。

\(2\le n \le 10^5\)。

首先能观察到，\(s\) 应当是一个回文串，不然不合法（我们需要补上 \(s_0 \texttt{0}\)。）。

我们需要有辩证思维，思考一下这个条件是否是充要条件。

似乎不是，因为 \(s_1\) 应当是 \(\texttt{1}\)，因为任意一个节点数大于 \(2\) 的树都应当有叶子节点。

可以发现这就是充要条件了，那么考虑构造解。

（剩下的部分也是考场想到的，但是怎么想到的我也觉得很神奇）

一个比较 Tricky 的想法是，我们考虑这棵树的生成过程，从小到大开始满足 siz。

显然 \(1\) 是一个孤立的节点，此时我们可以看作，是有一个两个节点的链存在，只不过另一个节点里面包含了剩下的 \(n - 1\) 个节点而已。

类似就是，尝试按照题目的过程，维护断掉的这条边和两个连通块，通过枚举的方式不断生成最终的树。

剩下的事情就是尝试构造出更大的 siz，并且不会产生新的 siz。

我们可以发现，如果之前没有其它子树可以用，那么对于一个 \(siz = val\)，我们在当前节点下挂 \(val - 1\) 个节点即可。

剩下的部分也可以找一个现成的子树挂在上面，然后不够的再补上，可以发现这样从“下”往“上”加入，是不会有新的 siz 产生的。

其实这部分可以不要并查集，我们可以直接用上一个 \(s_i = \texttt{1}\) 的 \(i\)。

然后很快就能构造出来了。

Code

// author : black_trees

#include <set>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <utility>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

const int si = 2e5 + 10;

int n;
bool valid(string s) {
    if(s[1] != '1') return false;
    for(int i = 0; i <= n; ++i)
        if(s[i] != s[n - i]) return false;
    return true;
} 

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    string s; 
    cin >> s, n = (int)s.size(), s = '0' + s;
    if(!valid(s)) return cout << "-1" << endl, 0;

    int ls = 0;
    cout << 1 << " " << 2 << endl;
    for(int i = 2; i < n; ++i) {
        cout << ls + 1 << " "  << i + 1 << endl;    
        if(s[i] == '1') ls = i;
    }

    return 0;
}

F - Distance Sumsψ(｀∇´)ψ

给你一个序列 \(a\)，你需要用 \(a\) 生成一棵无权树，满足以下条件：

若 \(a_i = val\)，那么树上标号为 \(i\) 的节点，到其它节点的距离之和为 \(val\)

保证 \(a_i\) 不相同，值域 \(10^{12}\)，\(2\le n \le 10^5\)。

构造方案，或者输出 -1。

我们考虑一下，这道题的 SPJ 应该怎么写。

就是一个换根 dp 对吧：

\(a(u) = a(fa) - 2siz(u) + n\)。

我们可以合并相同变量：\(a(fa) = a(u) + 2siz(u) - n\)。

可以注意到，在一条到根节点的链上，节点的 \(a\) 是递减的。

也就是说叶子节点是链上最大的，根是最小的。

而且我们注意到，因为 \(a\) 互不相同，所以如果我们钦定叶子节点，可以知道它的 \(fa\) 的编号。

因为刚才发现的性质，如果我们从大到小遍历，那么先遍历到的一定不会是在后遍历到的祖先集合中。

也就是说我们找到了一个阶段，可以从叶子节点开始递推，一层一层确定编号。

然后注意到我们只满足了 \(a\) 的限制，没考虑无解的问题，那么，如果发现构造的时候冲突了，或者构造出来的父节点对应不上，就是无解了。

感觉这题非常有意思！！其实也是考虑生成过程，然后通过找到阶段性质一步步确定答案！

Code

// author : black_trees

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long 

using namespace std;
using i64 = long long;

const int si = 1e5 + 10;

int n, siz[si];
int pa[si], dep[si], d[si];
std::map<int, int> idx;

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n;
    for(int i = 1; i <= n; ++i) 
        cin >> d[i], idx[d[i]] = i, siz[i] = 1;
    sort(d + 1, d + 1 + n);

    for(int i = n; i > 1; --i) {
        int u, fa;
        u = idx[d[i]], fa = idx[d[i] + siz[u] * 2 - n];
        pa[u] = fa, siz[fa] += siz[u];
        if(!fa || pa[fa]) return cout << "-1" << endl, 0;
    }
    int dis = 0;
    for(int i = 2, u; i <= n; ++i)
        u = idx[d[i]], dep[u] = dep[pa[u]] + 1, dis += dep[u];
    if(dis != d[1]) return cout << "-1" << endl, 0;
    for(int i = 2; i <= n; ++i) 
        cout << idx[d[i]] << " " << pa[idx[d[i]]] << endl;

    return 0;
}

最后更新: June 3, 2023