20250722

F

记 a + b = tot 分 n >= tot 和 n < tot 两类讨论。

• 对于 n < tot 如果 n <= a 那么一定无法做到；如果 n > a 那么直接可以做到 输出0
• 对于 n >= tot 我们直接令 n %= tot 表示可以经历完整的 n / tot 轮；对于剩下的余数 当 n > a 时一个都不用删，当 n <= a 时候必须全部删完。

D

签到。 根据题目意思，我们可以发现 当已经有现成的 a 个并列的1 我们总可以先把他变成0然后再跟前后连续的一个0组成a + 1 个并列的0 也就是说 只要找到 a 个现成的连续1 或者 a + 1 个现成的连续0 我们就可以做到无限扩增，即输出 n 。 对于剩下的情况 那就一步都无法操作 直接输出 count(all(s), '1') 即可。

J

一个重要的发现是 我们把 $[x,y](x>y)$ 变成 $[x-y,y\ast 2]$ 之后，左右的gcd是没有变化的，这个很容易证明。 也就是说 对于 100 200 这样的情况 其实完全等价于 1 2。 这之后 赛时猜了个 x + y 属于 二的次幂 … 就过了 附上官方给的证明。 令：判断数字 num 是否是 2的次幂，只需要判断 num & (num - 1) 是否等于0即可。

ac code:

void solve()
{
    int x, y;
    cin >> x >> y;
 
    int g = __gcd(x, y);
    int s = (x + y) / g;
 
    if ((s & (s - 1)) != 0)
    {
        cout << -1;
    }
    else
    {
        cout << 63 - __builtin_clzll(s);
    }
}

A

赛时没有注意到 1 <= f[i] <= i 注意到之后就很好写了。 对于 0-based 的 第i行第i列，实际上它占用的格子就是 v[i][0] ~ v[i][i] 和 v[0][i] ~ v[i][i] 这两条 因为要让 mex = i 前面有 0 ~ i - 1 一共 i 个元素 所以是刚刚好的。 对于第一行 / 第一列 由于 mex <= 1 那么 这一列的剩下格子里 必须要大于1的才能出现；对于第二行 / 第二列，必须要大于2的才能出现…以此类推 一个比较简单的构造思路如下：

void solve()
{
    int n;
    cin >> n;
    vector<int> f(n);
    for (int i = 0; i < n; i++)
    {
        cin >> f[i];
    }
 
    vector<vector<int>> a(n, vector<int>(n, 0));
 
    for (int i = 0; i < n; i++)
    {
        if (f[i] == 1)
        {
            // 初始化全为0 什么都不做也行
        }
        else
        {
            for (int j = 0; j < f[i] - 2; j++) // 第一行得是2 第二行得是3 以此类推 直到f[i] - 1被放下
            {
                a[i][j] = a[j][i] = j + 2;
            }
 
            a[i][i] = 1; // 对角线处放1
        }
    }
 
    // 输出
}

E

两个数字可以被同时除以d 那么d就是他们的公因数；譬如12和16可以同时被4整除的话，自然也可以同时被2整除；根据质因数分解定理，任何一个大于1的正整数都可以被分解为质数的乘积。

因此 如果要让数列中所有数字经过这样的操作之后相等，其实就是判断 我们能否通过两两配对互相减少的方式 让这些数字中的每一个质数数量都减少到0

不妨对每一个独立的质数p展开讨论： 对于 n % 2 == 0 我们任选两个数字并让他们同时 *p or /p 质数数量的奇偶性是不会变的 那么如果cnt[p] % 2 == 0 最后就一定能被全部消去，反之则一定会留下一个；

对于 n & 1 我们做上面同样的操作 可以发现最后会留下一个，但是剩下就有若干对都是0 只需要把他们同时乘以 p 即可让数字达到一样。 以 2 3 7 为例，其实通过

v[0] *= 3 * 7
v[1] *= 2 * 7
v[2] *= 2 * 3

即可让他们相等 亦即对于任何一个质数 我们让较少的若干对一直乘 就能达到效果。 特别的，对于 n == 2 我们判断的唯一条件就是 v[0] == v[1] 这一点也很好想，如果本来不相同的话不管怎么操作都不能让他们相同。

那么最后要解决的问题就是如何高效率计算质因数了，可以用 $O(n^2)$ 复杂度把每一个数字的最小质因子都预先求出来，然后$O(1)$查询即可，具体可以参考下方代码：

const int MAXN = 5000100;
vector<int> minP(MAXN + 1);
 
void pre()
{
    // 计算最小质因子表
    for (int i = 0; i <= MAXN; i++)
    {
        minP[i] = -1;
    }
 
    for (int i = 2; i <= MAXN; i++)
    {
        if (minP[i] == -1) // i是质数
        {
            for (int j = i; j <= MAXN; j += i)
            {
                if (minP[j] == -1)
                {
                    minP[j] = i;
                }
            }
        }
    }
}
 
void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
 
    // 特殊情况
    if (n == 2)
    {
        cout << (a[0] == a[1] ? "YES" : "NO") << endl;
        return;
    }
 
    if (n % 2 == 1)
    {
        cout << "YES" << endl;
        return;
    }
 
    // 统计每个质因子的总出现次数
    map<int, int> cnt;
    for (int x : a)
    {
        while (x > 1)
        {
            int p = minP[x];
            int tot = 0;
            while (x % p == 0)
            {
                x /= p;
                tot++;
            }
            cnt[p] += tot;
        }
    }
 
	// 检查所有质因子的出现次数是否都是偶数
    for (auto &[p, tot] : cnt)
    {
        if (tot % 2 == 1)
        {
            cout << "NO" << endl;
            return;
        }
    }
 
    cout << "YES" << endl;
}