T1 整数

给定32位无符号整数 x & y 以及 x | y 的值，截取 x ^ y 的二进制第 l 到 r 位（0 最低 31 最高）转换成十进制是多少（0 <= l <= r <= 31）。

解法

• x ^ y == (x & y) & (x | y)
• unsigned int 会爆

代码

#include <iostream>
using namespace std;

unsigned long long a, b, l, r, c, d;

int main() {
    freopen("integer.in", "r", stdin);
    freopen("integer.out", "w", stdout);
    cin >> a >> b >> l >> r;
    c = a ^ b;
    for (unsigned int i = 0, j = 0; i < 32; i++) {
        if (i < l) continue;
        if (i > r) break;
        d += ((c >> i) & 1) * (1 << (j++));
    }
    cout << d << endl;
    return 0;
}

T2 转圈

n 个人围成一个圈，编号为 1 ~ n ，每个人手上都有一个数字 a。

从 1 开始，一共进行 n - 1 轮，第 k 轮离开的人是第 k - 1 轮离开的人 i 顺时针方向推 a[i] 个人 (k <= 2)。

求最后一个离开的人的编号。

解法

• 模拟

• 代码

#include <iostream>
#include <queue>
using namespace std;

int n, x;
queue<pair<int, int>> q;

int main() {
    freopen("circle.in", "r", stdin);
    freopen("circle.out", "w", stdout);
    
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        q.push(make_pair(x, i));
    }
    while (q.size() > 1) {
        int u = q.front().first - 1;
        // cout << "Pop:" << q.front().second << endl;
        q.pop();
        while (u--) {
            q.push(q.front());
            q.pop();
        }
    }
    cout << q.front().second << endl;
    return 0;
}

T3 换椅子

一共有 n 个人，编号为 1 ~ n，每个人用以下代码生成一个序号 a[i]。

for (int i = 1; i <= n; i++) p[i] = i;
random_shuffle(p + 1, p + 1 + n);
for (int i = 1; i < n; i++)
     s[p[i]] = p[i + 1];
s[p[n]] = p[1];

之后进行换位置 a[i] = a[a[i]]，进行 k 轮。

给出进行 k 轮后的结果，求初始结果。

解法

• 模拟，观察，发现循环节
• 逆推
• 多测清空

代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int T, n, k;
vector<int> p, b;
vector<vector<int>> pp;

bool sol() {
    vector<int> cp(n + 1);
    for (int i = 1; i <= n; i++) {
        cp[i] = p[p[i]];
    }
    bool flag = true;
    for (int i = 1; i <= n; i++) {
        if (cp[i] != b[i]) {
            flag = false;
            break;
        }
    }
    pp.emplace_back(cp);
    if (flag) {
        return true;
    }
    copy(cp.begin(), cp.end(), p.begin());
    return false;
}

void print() {
    // for (int j = 0; j < pp.size(); j++) {
    //     for (int i = 1; i <= n; i++) {
    //         cout << pp[j][i] << ' ';
    //     }
    //     cout << endl;
    // } 
    for (int i = 1; i <= n; i++) {
        cout << pp[ pp.size() - 1 - (k % pp.size())][i] << ' ';
    }
    cout << endl;
}

int main() {
    freopen("chair.in", "r", stdin);
    freopen("chair.out", "w", stdout);

    cin >> T;
    while (T--) {
        cin >> n;
        p.resize(n + 1);
        pp.clear();
        for (int i = 1; i <= n; i++) {
            cin >> p[i];
        }
        cin >> k;
        b = p;
        while (!sol());
        print();
    }
    return 0;
}

T4 乐队

n 个乐队共有 m 场巡演，有 0 和 1 两种主题。

希望 m 场巡演主题完全相同。

选择对乐队下达命令，对一个乐队下达命令会让它参与的巡演主题反转。

求最小下达命令的次数，无解输出 -1。

解法

• 求解染色 0 和 1 的两种方案取最小
• DFS
• 对于每一条边，第一次染色颜色不同，则需要下一个点染回来
• 如果染色两边依旧与目标颜色对不上，那么无解

代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<vector<tuple<int, char>>> e;
vector<char> vis, col;
int tot, fil;
bool uac = false; // 不成立

void dfs(int u, int tag) {
    vis[u] = 1;
    tot++;
    for (auto [v, w] : e[u]) {
        if (!vis[v]) {
            if ((w ^ col[u]) != tag) { // 需要再次被染色
                fil++;
                col[v] = 1;
            }
            dfs(v, tag);
        } else {
            if ((w ^ col[u] ^ col[v]) != tag) uac = true; // 染两次都不符合条件，不成立
        }
    }
}

int sol(char tag) {
    int res = 0;
    fill(col.begin(), col.end(), 0);
    fill(vis.begin(), vis.end(), 0);
    uac = false;
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        tot = fil = 0;
        dfs(i ,tag);
        if (uac) {
            res = 1e9;
            break;
        }
        res += min(tot - fil, fil); // 反着也是一种方案
    }
    return res;
}

int main() {
    freopen("band.in", "r", stdin);
    freopen("band.out", "w", stdout);
    cin >> n >> m;
    e.resize(n + 1);
    col.resize(n + 1);
    vis.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        e[u].emplace_back(make_tuple(v, char(c)));
        e[v].emplace_back(make_tuple(u, char(c)));
    }
    int ans = min(sol(0), sol(1));
    if (ans == 1e9) ans = -1;
    cout << ans << endl;
    return 0;
}