可能是更好的阅读体验

A. Plus One on the Subset

题意

给定一个长度为 \(n\) 的序列，每次选择若干个数字加 \(1\) ，问最少操作几次可以使所有数字相同。

分析

每次操作最小的数字，顺便补上其他小于最大值的数字，因此最少次数为极差。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include 
using namespace std;

void solve()
{
    int n; cin >> n;
    int maxv = -1, minv = 1e9;
    for (int i = 1, x; i <= n && cin >> x; i ++ )
    {
        maxv = max(maxv, x);
        minv = min(minv, x);
    }
    cout << maxv - minv << endl;
}

signed main()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--;) solve();
    return 0;
}

Make AP

题意

给出三个数字，可以选择其中一个数字（也可以不选），使其乘上任意一个正数。

问能否让这三个数字成为等差数列（顺序不能换）。

分析

由于只有三个数字，枚举哪个数字用来乘即可。

类似的题目： CF Good bye 2021 C题

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include 
using namespace std;

#define int long long

void solve()
{
    int a, b, c; cin >> a >> b >> c;
    bool ok = 0;
    int na = 2 * b - c;
    ok |= (na % a == 0 && (c - b) == (b - na) && (na * a) > 0);
    int nb = (a + c) / 2;
    ok |= (nb % b == 0 && (c - nb) == (nb - a) && (nb * b) > 0);
    int nc = (2 * b - a);
    ok |= (nc % c == 0 && (nc - b) == (b - a) && (nc * c) > 0);
    cout << (ok ? "YES" : "NO") << endl;
}

signed main()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--;) solve();
    return 0;
}

C. Division by Two and Permutation

题意

给定长度为 \(n\) 的序列，每次可以选择一个数字 \(x\) 使其变为 \(\lfloor \dfrac x 2 \rfloor\) 。问能否使序列变为一个 \(1 \sim n\) 的排列。

分析

每个数字都必须为 \([1, n]\) 的数字，所以第一步要把所有大于 \(n\) 的数字变为 \([1, n]\) 之间的数字。

从后往前遍历，由于每个数字都需要恰好 \(1\) 个。那么如果当前数字没有，一定不能成功，如果有多个，留下一个并且把剩下的转化为 \(\lfloor \dfrac x 2 \rfloor\) 即可。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include 
using namespace std;

const int N = 55;
int cnt[N];

void solve()
{
    memset(cnt, 0, sizeof cnt);
    int n; cin >> n;
    for (int i = 1, x; i <= n && cin >> x; i ++ )
    {
        while (x > n) x /= 2;
        cnt[x] ++ ;
    }
    for (int i = n; i >= 1; i -- )
    {
        if (!cnt[i]) return cout << "NO\n", void();
        while(cnt[i] > 1) cnt[i / 2] ++, cnt[i] -- ;
    }
    cout << "YES\n";
}

signed main()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--;) solve();
    return 0;
}

D. Palindromes Coloring

题意

给出长度为 \(n\) 的字符串和 \(k\) 种染料，每种染料都至少染 \(1\) 个字符，被染上相同染料的字符可以任意调换顺序。

给字符串染上染料，使得所有被染上相同染料的字符串（子串）为回文串。问长度最小的字符串的最大长度为多少。

分析

由于可以任意调换顺序，因此字符串顺序不是考虑因素。

要把一个子串变成回文串，我们需要任意个偶数对和至多一个任意字符。

那么我们可以求出偶数对的数量以及单个的字符的数量，然后二分答案即可。

注意如果一个字符出现奇数次，我们可以把它拆成若干个偶数对和一个单独的字符。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include 
using namespace std;

#define int long long

int even, odd, k; // 能构成偶数对的字符数量、单独的字符数量

bool check (int x)
{
    int nt = even, no = odd;
    if (x & 1)
    {
        if (k * (x - 1) > nt) return false; // 每个子串至少要 (x-1) 个even
        nt -= k * (x - 1);
        if (nt + no < k) return false; // 注意可以把能构成偶数对的字符数量变成单独的字符使用
        return true;
    }
    else
    {
        if (k * x <= nt) return true;
        else return false;
    }
}

void solve()
{
    even = odd = 0;
    vector a(26);
    int n; cin >> n >> k;
    string s; cin >> s;
    for (char c : s) a[c - 'a'] ++ ;
    for (int x : a)
    {
        if (x & 1) even += x - 1, odd ++ ;
        else even += x;
    }
    int l = 0, r = n;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << r << endl;
}

signed main()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--;) solve();
    return 0;
}

E.Masha-forgetful

题意

给出 \(n\) 个长度为 \(m\) 的字符串，以及需要匹配的字符串 \(s\) （长度也为 \(m\)），问能否把 \(s\) 拆成任意多段（每段长度至少为 \(2\)），使得每一段在前 \(n\) 个字符串出现过。
如果满足，输出 \(k\) 段，且输出每一段在其他字符串出现的首尾位置，以及它出现在哪个字符串。

分析

首先，任何一个不小于 \(2\) 的数字都可以由若干个 \(2\) 和 \(3\) 组成 。

这就意味这我们只需要把 \(s\) 拆成若干个长度为 \(2\) 和 \(3\) 的段即可。

\(dp(i)\) 表示前 \(i-1\) 个字符是匹配的。

在前 \(n\) 个字符串中，找出所有段长度为 \(2\) 和 \(3\) 的信息（即题目要求的首尾位置和出现在第几个字符串）。

然后从前往后遍历 \(s\) ，求出那些位置是匹配的。最后从后往前找到路径即可。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include 
using namespace std;

using tp = tuple;

void solve()
{
    tp f2[10][10], f3[10][10][10]; // f2(i, j)表示从 ij 这样的段出现的信息
    int n, m; cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        string s; cin >> s;
        for (int j = 0; j < m; j ++ )
        {
            if (j + 1 < m) f2[s[j]-'0'][s[j+1]-'0'] = {j + 1, j + 2, i + 1};
            if (j + 2 < m) f3[s[j]-'0'][s[j+1]-'0'][s[j+2]-'0'] = {j + 1, j + 3, i + 1};
        }
    }

    string s; cin >> s;
    vector dp(m + 1); // dp(i)表示前面i-1个位置是否可以
    dp[0] = true;
    for (int i = 0; i < m; i ++ )
    {
        if (!dp[i]) continue;
        if (i + 1 < m && f2[s[i]-'0'][s[i+1]-'0'] != tp(0, 0, 0)) dp[i + 2] = true;
        if (i + 2 < m && f3[s[i]-'0'][s[i+1]-'0'][s[i+2]-'0'] != tp(0, 0, 0)) dp[i + 3] = true;
    }

    if (!dp[m]) return cout << "-1\n", void();

    int i = m; // 记录路径
    vector ans;
    while(i)
    {
        if (i >= 1 && dp[i - 2] && f2[s[i-2]-'0'][s[i-1]-'0'] != tp{0, 0, 0})
        {
            ans.push_back(f2[s[i-2]-'0'][s[i-1]-'0']);
            i -= 2;
        }
        else
        {
            ans.push_back(f3[s[i-3]-'0'][s[i-2]-'0'][s[i-1]-'0']);
            i -= 3;
        }
    }

    reverse(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (auto t : ans) cout << get<0>(t) << ' ' << get<1>(t) << ' ' << get<2>(t) << endl;
}

signed main()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--;) solve();
    return 0;
}

F. Interacdive Problem

题意

给出数字 \(n\) ，要求猜出数字 \(x\) ，其中 \(1 \le x \lt n \le 1000\) 。

可以给出询问 \(+ \ \ c\) ，表示令 \(x = x + c\) ，之后给出 \(\lfloor \dfrac x n \rfloor\) 。

最多可以操作 \(10\) 次。

分析

可以把 \(x\) 写成 \(x / n * n + x \% n\) 。

二分答案，假设 \(mid = x\) ，即 \(mid = mid / n * n + mid \% n\) 。

询问 \(n - mid \% n\) ，这样可以使 \(x + n - mid \% n = x / n * n + n + x \% n - mid \% n\) 。

发现倍数增加了，那么有 \(x \% n \ge mid \% n\) ，即 \(mid \le x\) 。

否则 \(mid \gt x\) 。

注意由于 \(x\) 已经加上了 \(n - mid \% n\) ，那么 \(l\) 和 \(r\) 也要加上，保证 \(l \le x \le r\) 。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include 
using namespace std;

void solve()
{
    auto query = [&] (int add)
    {
        cout << "+ " << add << endl;
        return cin >> add, add;
    };
    auto submit = [&] (int ans)
    {
        cout << "! " << ans << endl;
        exit(0);
    };

    int n; cin >> n;
    int l = 1, r = n - 1;
    while(l < r)
    {
        int mid = l + r + 1 >> 1;
        int to = n - mid % n, now = query(to);
        if (now >= mid / n + 1) l = mid;
        else r = mid - 1;
        l += to, r += to;
    }
    submit(r);
}

signed main()
{
    cout.tie(0)->sync_with_stdio(0);
    // int _; for (cin >> _; _--;)
        solve();
    return 0;
}

G. MinOr Tree

题意

给出一张无向图，求或和最小的生成树。

分析

按位分析，从大到小，假设当前位为 \(bit\) 。

由于要求最小或和，那么最好情况下，我们只合并所有在 \(bit\) 位上为 \(0\) 和点。

如果合并完发现没有用上所有点，那么说明要想生成最小生成树，必须要 \(bit\) 位上为 \(1\) 的点。

考虑下一位前，由于当前位已经被考虑过，所以要把所有在当前位为 \(1\) 的边变为当前位为 \(0\) 。

Code

/* 终点是一切概率的结束，也是一切期望的开始 */
#include 
using namespace std;

void solve()
{
    int n, m; cin >> n >> m;
    vector u(m), v(m), w(m);
    for (int i = 0; i < m; i ++ )
    {
        cin >> u[i] >> v[i] >> w[i];
        -- u[i], -- v[i];
    }
    int ans = 0;
    for (int j = 29; j >= 0; j -- )
    {
        vector> E(n);
        for (int k = 0; k < m; k ++ )
        {
            if (w[k] < (1 << j))
            {
                E[u[k]].push_back(v[k]);
                E[v[k]].push_back(u[k]);
            }
        }
        vector used(n, false);
        used[0] = true; // 从0号点开始bfs
        queue Q; Q.push(0);
        while(!Q.empty())
        {
            int x = Q.front(); Q.pop();
            for (int y : E[x])
            {
                if (!used[y])
                {
                    used[y] = true;
                    Q.push(y);
                }
            }
        }
        if (used != vector (n, true))
        {
            ans |= 1 << j;
            // 这一位已经考虑过了，把j位上为1的数字去掉
            for (int k = 0; k < m; k ++ )
                if (w[k] >> j & 1) w[k] ^= 1 << j;
        }
    }
    cout << ans << endl;
}

signed main()
{
    cout.tie(0)->sync_with_stdio(0);
    int _; for (cin >> _; _--;) solve();
    return 0;
}