A. Filling Diamonds

最左侧的菱形如果竖放的话，右侧其余的放置方案是确定的；当最左侧的菱形能够用两个斜放置的菱形拼凑而成的话，左侧第二个菱形就有上述两种选择方式；以此类推，直到最后一个菱形，只能选择竖放结尾。

因此，有几个菱形就有几种放置方案，即：输入的 $n$ 就为答案。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        cout << n << endl;
    }
    return 0;
}

B. Sorted Adjacent Differences

重排成值上下依次摆动的数组即可。

这个不太好形容，能懂的都懂，不懂的看看代码怎么输出的也就懂了

由于一侧是递增的，一侧是递减的，所以上下摆动之后两两之间的差值一定会满足题目要求。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, a[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1);
        int l = n + 1 >> 1, r = l + 1;
        while (l || r <= n) {
            if (l)
                cout << a[l--] << ' ';
            if (r <= n)
                cout << a[r++] << ' ';
        }
        cout << endl;
    }
    return 0;
}

C. Powered Addition

当 $a_i < a_{i - 1}$ 时，需要增加 $a_{i}$ 的值以满足递增的要求，同时，为了让 $a_i$ 的增加对后续的影响最小，还需要使 $a_i$ 尽可能的小。

又由于一个数总能唯一确定二进制数，所以，我们在 $a_{i - 1} - a_i$ 这个差值的二进制为 $1$ 的位所对应秒数上增加相应的值，就能满足要求，而最终的答案就是所有这样的差中最高的为 $1$ 的二进制位再加上 $1$，这是因为秒数从 $1$ 开始计，需要加上这个偏移量。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
int n, a[N];

int get_res(int x)
{
    int res = 30;
    while (!(x >> res & 1))
        res--;
    return res + 1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        int res = 0;
        a[0] = -1e9;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (a[i] < a[i - 1]) {
                res = max(res, get_res(a[i - 1] - a[i]));
                a[i] = a[i - 1];
            }
        }
        cout << res << endl;
    }
    return 0;
}

D. Edge Weight Assignment

要使填入的不同数字尽可能少，即让填入的数字尽可能的相同，如果每条边都填 $1$，那么何时会发生矛盾？

显然，当两个叶子节点之间的距离为奇数时会不满足题意，此时，该条途径上必须要有一条边取另一个为 $1$ 的二进制位，比如将其中一条边变为 $2$，相应的，为了消去这个二进制位，需要再将一条边的值变为 $3$。同理，如果还有其它的叶子节点之间距离为奇数，也用相同的办法变换即可。

综上，如果任意两个叶子节点之间的距离都是偶数的话，所有边都填 $1$ 就能满足题意，即：最小的数字数量为 $1$；否则的话，需要至少 $3$ 个数字。

那么如何求最大的数字数量？

一个显而易见的贪心思路就是，每走一条边，都让其更高一位的二进制位变成 $1$，那么此时就会有 $n - 1$ 个不同的数字分别对应 $n - 1$ 条边，显然，这是不满足题意的，那么现在的问题就变成，挑选最小的边，更改上面的数值，使整棵树满足要求。

任取两个叶子节点中间的路径为例，每条边上的数值为各不相同的某个为 $1$ 的二进制数，如果想让它满足要求，那么，只需要选择其中一条边，让它的值变为剩余所有边的异或和，那么，这条路径上所有边的异或和就会为 $0$。这个操作虽然变换了一条边上的数，但是变换后的数值也是不曾出现的，所以不会对答案造成影响。

那么，哪种数值变换会使答案数量减少？

显然，当两个叶子节点之间的路径长度为 $2$ 时，这两条边上的数值必须相等，因此，每出现一次该种情况，就应该让答案 $- 1$。

综上，只需要先找出叶子节点之间路径长度为 $2$ 的数量，再用边数减去这个数量，就是使满足题意的最大的填入边上不同的数字数量。

上述上个操作都可以用递归的方式实现。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5, M = 2e5 + 5;
int n;
int root, dis, cnt;
int d[N];
int h[N], e[M], ne[M], idx;
bool leaves[N], vis[N];

void add(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void get_leaves()
{
    for (int i = 1; i <= n; i++)
        if (d[i] == 1) {
            if (!root)
                root = i;
            leaves[i] = true;
        }
    return;
}

void dfs(int u, int fa, int d)
{
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)
            continue;
        dfs(j, u, d + 1);
        if (leaves[j])
            dis |= (d + 1) & 1;
    }
    return;
}

void find_two_dis(int u, int fa, int d)
{
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)
            continue;
        if (!d)
            find_two_dis(j, u, d + 1);
        else if (leaves[j]) {
            vis[j] = true;
            cnt++;
        }
    }
    return;
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add(u, v);
        add(v, u);
        d[u]++;
        d[v]++;
    }
    get_leaves();
    dfs(root, -1, 0);
    for (int i = 1; i <= n; i++)
        if (leaves[i] && !vis[i])
            find_two_dis(i, -1, 0);
    printf("%d %d\n", dis & 1 ? 3 : 1, n - 1 - cnt);
    return 0;
}

E. Perfect Triples

多手算几个答案，全都写成二进制形式，就能发现规律：

1. $a$ 的最高为 $1$ 的位总是偶数位，如：$1$ 的二进制中最高为 $1$ 的位为第 $0$ 位，$4$ 的二进制中最高为 $1$ 的位为第 $2$ 位。
2. $b$ 的最高为 $1$ 的位总是奇数位，如：$2$ 的二进制中最高为 $1$ 的位为第 $1$ 位，$8$ 的二进制中最高为 $1$ 的位为第 $3$ 位。
3. $b$ 的最高为 $1$ 的二进制位总是为 $a$ 的最高为 $1$ 的二进制位的后一位。
4. $a$ 的最低两个二进制位会在 $00, 01, 10, 11$ 之间依次循环，且一轮循环结束之后会影响较高的两个二进制位进行循。
5. $b$ 的最低两个二进制位会在 $00, 10, 11, 01$ 之间依次循环，且一轮循环结束之后会影响较高的两个二进制位进行循环。
6. 根据 $4, 5$ 条可以得到，在确定了最高为 $1$ 的二进制位之后，较低的所有二进制位可以由低到高两两一组，分成四进制的形式，只是该四进制的枚举顺序需要以 $4, 5$ 两条中的顺序为准。
7. 在 $a$ 的最高位 $1$ 确定之后，$a$ 每次都会 $+1$，而每次增加都会相应的得到 $b, c$，因此，如果当前确定完 $a$ 的最高位之后离目标还差 $d$ 个数的距离，那么 $a$ 就应该增加 $\frac{d}{3}$，而最终答案为 $a, b, c$ 中的哪一个则需要看 $d\ \%\ 3$ 的值。

在发现上述规律之后，根据规律用代码实现即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const LL F[4] = { 0, 1, 2, 3 }, G[4] = { 0, 2, 3, 1 };

LL solve(int bit, LL d)
{
    LL a = 1ll << bit, b = 1ll << (bit + 1);
    LL n = d / 3;
    vector<int> q;
    while (n) {
        q.push_back(n % 4);
        n /= 4;
    }
    for (int i = 0; i < q.size(); i++) {
        a |= F[q[i]] << (i << 1);
        b |= G[q[i]] << (i << 1);
    }
    n = d % 3;
    if (!n)
        return a;
    if (n == 1)
        return b;
    return a ^ b;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        LL n;
        cin >> n;
        int bit = 0;
        while (1ll << (bit + 2) <= n)
            bit += 2;
        cout << solve(bit, n - (1ll << bit)) << endl;
    }
    return 0;
}

PS: 以后可能会有一段时间不会这样连续地更新每一场 $cf$ 的题解了，虽然这一场距离当初比赛也鸽了挺久的了 最近发现，自己其实很容易很容易很容易卡在前中期题上，导致剩下的一些虽然明面上难度更难，但却能写的算法题连看都没时间看（这可能也是为啥 $cf$ 分数总是上不去的原因），所以接下去决定更改一下方式，可能会集中刷一波 $cf$ 上通过人数超过四位数的题，写成一个简单的题解集合，较难的题的话准备刷一遍《算法竞赛进阶指南》（希望自己能坚持下去吧 $hh$，立个 $flag$ 下学期开学前写完进阶指南的题解，至少把能写的都写一遍，然后下半年，趁着自己的学长队友还没有全毕业，好好抱着现有的大腿打 $ACM$，毕竟明年的形式谁都说不好~