BFIALDGH

B

本题试图证明：对于任意一对 $i, j$ （不妨认为 $1 \leq i \leq j$ ) 有： $2^{i \oplus j} \geq 2^{i} + 2^{j}$

先来看对于 $x \leq y$ 能否找到一个z使得 $2^{z} \geq 2^{x} + 2^{y}$

我们知道 $2^{i + 1} = 2^{i} + 2^{i}$ 因此令 $z = y + 1$ ，自然有 $2^{y + 1} \geq 2^{x} + 2^{y}$

也就是说问题转化为对于任意的 $1 \leq i \leq j$ 证明 $i \oplus j \geq j$

当 $i = j$ 时， $i \oplus j = 0 < 1 \leq j$ 无法构造合法解此时直接输出 "NO"

当 $i \neq = j$ 时:

$i \oplus j = j$ 的等号取得的条件是 $i = 0$ or $j = 0$ 都不符合题意
那我们只需要尝试证明 $i \oplus j > j$ 即可。

不妨对两个数字进行按位异或分以下四种情况：

$i_{bi t} = 0, j_{bi t} = 0$ 此时异或的结果还是0 相比于j来说大小不变
$i_{bi t} = 0, j_{bi t} = 1$ 此时异或的结果是1 相比于j来说大小不变
$i_{bi t} = 1, j_{bi t} = 0$ 此时异或的结果是1 相比于j来说变大
$i_{bi t} = 1, j_{bi t} = 1$ 此时异或的结果是0 相比于j来说变小

需要注意的是，高位对低位有绝对的压制作用。也就是说在从高到低的遍历过程中，如果发现已经满足 $i_{bi t} = 1, j_{bi t} = 0$ 那就不用看了；而如果发现 $i_{bi t} = 1, j_{bi t} = 1$ 那数字一定会变小就是不合法的了。

所以问题转化为：如何快速判断对于一个数字x的最高位是否存在 $y > x$ 使得y的这一位是1

如果出现了哪怕一个1 那么就一定能构造出不符合条件的解返回"NO"

如果在遍历的过程中完全没有找到，那就说明完全合法返回 "YES"

那我们只需要开一个61大小的辅助数组用来记录当前位置1的个数

先对数字排个序从大到小枚举

对每一个数字都按位枚举把自己的贡献记录进去

然后判断对于当前数字最高位是否存在1

ac code:

void solve()
{
    int n;
    cin >> n;
    vector<int> v(n);
 
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
    }
 
    /*
    i + j = i ^ j + 2 * (i & j)
    什么时候 i ^ j > i and i ^ j > j
    如果有两个相等的 那就不可能
    如果没有 那么
    不妨设 i < j 那么 要让战斗力不会降低 也就是 i^j 比 j 大 即可
    如果要达成这个目的 就要让i的1刚好对应上j的0
    否则都会比j小
 
    对于一个j 我们想找所有比他小的i => 对于每一个i 我们找比他大的j是不是全部都是0
    */
    vector<int> bits(62, 0);
    sort(all(v), greater<int>());
    for (auto num : v)
    {
        auto cur = num;
        int maxnum = 0;
        int idx = 0;
        while (cur)
        {
            bits[idx] += cur & 1;
            if (cur & 1)
            {
                maxnum = idx;
            }
            cur >>= 1;
            idx++;
        }
 
        if (bits[maxnum] > 1)
        {
            return void(cout << "NO");
        }
    }
    cout << "YES";
}

F

首先破环成链，然后往右边找第一次出现的火和第 $c n t_{1} + 1$ 次出现的火

如果不铺设可控火势，那么对于任何一个大小为 $c n t_{0}$ 的空地在t时间过去后，剩下的空地会变为 $ma x (0, c n t_{0} - 2 t)$

现在我们只能铺设一次可控火势，那么就要找出最大的空地在其中一侧扑火这样火势只能从另一侧蔓延了 t时间后剩下的空地为 $ma x (0, c n t_{0} - 1 - t)$

最后累加答案并输出即可

ac code:

void solve()
{
    int n, k;
    cin >> n >> k;
 
    string s;
    cin >> s;
    s += s;
    int idx1 = -1, idx2 = -1;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1')
        {
            idx1 = i;
            break;
        }
    }
    for (int i = n; i < s.size(); i++)
    {
        if (s[i] == '1')
        {
            idx2 = i;
            break;
        }
    }
 
    // 找出里面最多的0 他可以被挡住一边 然后蔓延
    /*
    蔓延的代价是
    假设一共有m个0 每秒消耗1 一共t秒 那就消耗了 m - 2t
 
    特别的 最多的应该是 (m - 1) - t
    */
 
    vector<int> vv;
    int cur = 0;
    for (int i = idx1; i <= idx2; i++)
    {
        if (s[i] == '0')
        {
            cur++;
        }
        else
        {
            vv.emplace_back(cur);
            cur = 0;
        }
    }
 
    int ans = 0;
    sort(all(vv));
    for (int i = 0; i + 1 < vv.size(); i++)
    {
        ans += max(0ll, vv[i] - 2 * k);
    }
    ans += max(0ll, vv.back() - 1 - k);
    cout << ans;
}

I

猜猜题，想要找到一个k 使得对于给定的 $x \neq = y$ ，有 $k % x + x % k = k % y + y % k$ 如果不存在就输出-1

对于任意一个数字 $x > 1$ 总存在 $k = 1$ 使得 $x %1 = 1, 1% x = 1$

因此如果 $x, y > 1$ 那么等式就变为 $1 + 1 = 1 + 1$ 这是显然成立的

特别的 $x = 1$ 时， $x %1 = 0, 1% x = 0$ 因此 $x = 1$ or $y = 1$ 时候需要输出-1

ac code:

void solve()
{
    int a, b;
    cin >> a >> b;
 
    if (a == 1 or b == 1)
    {
        cout << -1;
    }
    else
    {
        cout << 1;
    }
}

A

第一时间想到了dp, 但是细节处理上需要仔细思考。

如果我们设 $f (i, j)$ 是进行到第i天，以j结尾一共有几段连续的1

那么自然有：

f (i, 0) = f (i - 1, 0) + f (i - 1, 1) f (i, 1) = f (i - 1, 1) + f (i - 1, 0) + [i-1] 位置 为 0 时候的方案总数

比方说 i位置最后是0 有k种构造方案，一共有m段连续的1

那么到了i+1位置最后是1 所以每一个构造方案都会增加新的一段

那么i+1位置现在有多少段呢？就是原有的段数(m) + 新增加的段数(k) 因此我们还需要额外维护新的量也就是：

$g (i, j)$ 到了第i天以j结尾一共有多少种合法组成方案

有：

g (i, 0) = g (i - 1, 0) + g (i - 1, 1) g (i, 1) = g (i - 1, 0) + g (i - 1, 1)

最后要输出段数取模参考代码如下：

constexpr int MOD = 998244353;
 
void solve()
{
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
 
    auto add = [&](int i, int j) -> int
    {
        return (i + j) % MOD;
    };
 
    /*
    只有0 -> 1 会让段数增加额外的一段 我们要知道最后的段数之和
    昨天是0 今天是1 段数如何增加？
    昨天0结尾的总方案数 每一个方案都要增加1
    那段数增加了多少呢 是0段+0方案
 
    */
    struct datas
    {
        int fangan, duan;
    };
 
    vector dp(n + 1, vector<datas>(2, {0, 0}));
    if (v[1] != 0)
    {
        dp[1][1].fangan = 1;
        dp[1][1].duan = 1;
    }
    if (v[1] != 1)
    {
        dp[1][0].fangan = 1;
        dp[1][0].duan = 0;
    }
    for (int i = 2; i <= n; i++)
    {
        auto pre = v[i - 1], cur = v[i];
 
        // 如果当前是0 那就不可能新增段数和方案数
        if (cur != 1)
        {
            dp[i][0].fangan = add(dp[i - 1][0].fangan, dp[i - 1][1].fangan);
            dp[i][0].duan = add(dp[i - 1][0].duan, dp[i - 1][1].duan);
        }
 
        if (cur != 0)
        {
            // 有可能产生新的一段 取决于前一天有没有0方案
            dp[i][1].fangan = add(dp[i - 1][1].fangan, dp[i - 1][0].fangan);
            dp[i][1].duan = add(dp[i - 1][1].duan, add(dp[i - 1][0].duan, dp[i - 1][0].fangan));
        }
    }
 
    cout << add(dp[n][0].duan, dp[n][1].duan);
}

L

一个节点要么跟自己指向的节点组合，要么跟指向自己的节点组合；同时由题目得知，每个节点的出度入度均为1 因此这个图一定会形成一片环的森林

接下来我们要删除其中两个节点问能构造多少种合法匹配使得所有节点都被配对

我们可以先不删除点而是看一下环的大小对这个匹配数量的影响

如果环是奇数，那么一定没有办法两两配对
如果环是偶数：
- 如果环大小为2 那么只能配成一对
- 如果环大小大于2 譬如 a → b → c → d → e → f → a 可以有ab cd ef 和 fa bc de 两种构造方案

也就是说对于奇环我们要尝试删去成偶链；对于大小为2的偶环贡献是1；对于大小 $\geq 4$ 的偶环贡献是2

由于点的数目是偶数，因此奇环的数量一定是偶数；而我们只能删除两个点意味着只有奇环数量为2时候能把他们全部变成偶链；

因此：当奇环数量 >2 时，可以直接输出0

当奇环数量为2时候这两个奇环都会变成偶链偶链的贡献恒为1 那么一个奇环能创造多少贡献呢？应该是删除点的方案乘以偶链的贡献

在本题中这个结果就是奇环上点的数量乘以 1

对于剩下的偶环小于4的乘以1 大于等于4的乘以2

记录这两条奇环的大小分别为 $l_{1}, l_{2}$ ，偶环中大小大于等于4的数量为 $t o t 4$ 等于2的数量为 $t o t 2$

也就是 $l_{1} * l_{2} * 2^{t o t 4}$

当奇环数量为0的时候我们要从偶环中删除两个点是否可以选择两个不同的偶环呢？如果这么做会产生两条奇链，这是我们不愿看到的

因此我们只能枚举每一条偶环从中删除两个节点这两个节点的删去不能使得这个环变为两条奇链

手玩一下可以发现对于 a → b → c → d → e → f → a 这条偶环我们可以从ace 中删除一个，从bdf 中删除一个记录这条环的大小为 $l$ 那么总共删除的方案数为 $(\frac{l}{2})^{2}$

这条环的匹配数量应该是方案数乘以偶链贡献而偶链的贡献（正如前文提到的那样）是1 因此这个偶环的贡献就是 $(\frac{l}{2})^{2}$

而剩下的环贡献应当是 $2^{t o t 4 - (l \geq 4)}$

最后要枚举 $l$ 答案为 $\sum (\frac{l}{2})^{2} * 2^{t o t 4 - (l \geq 4)}$

用快速幂加速运算，注意取模

ac code:

constexpr int MOD = 998244353;
// -9.2e18 ~ 9.2e18
 
int add(int i, int j)
{
    return (i + j) % MOD;
}
 
int mul(int i, int j)
{
    return (i % MOD * j % MOD) % MOD;
}
 
int ksm(int base, int exp)
{
    int ans = 1;
    while (exp)
    {
        if (exp & 1)
        {
            ans = mul(ans, base);
        }
        base = mul(base, base);
        exp >>= 1;
    }
    return ans;
}
 
void solve()
{
    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> v[i];
    }
 
    vector<int> vis(n + 1);
    vector<int> odd, even2, even4;
    for (int i = 1; i <= n; i++)
    {
        if (vis[i])
        {
            continue;
        }
 
        auto cur = i;
        int tot = 0;
        while (!vis[cur])
        {
            tot++;
            vis[cur] = 1;
            cur = v[cur];
        }
        if (tot & 1)
        {
            odd.emplace_back(tot);
        }
        else
        {
            if (tot == 2)
            {
                even2.emplace_back(tot);
            }
            else
            {
                even4.emplace_back(tot);
            }
        }
    }
 
    if (odd.size() > 2)
    {
        return void(cout << 0);
    }
 
    if (odd.size() == 2)
    {
        cout << mul(mul(odd[0], odd[1]), ksm(2, even4.size()));
        return;
    }
 
    // 现在全都是偶数 要求和
    int ans = 0;
    // 如果把2删掉 那就删没了 所以对于每一个2 把他删掉的结果都是  ksm(2, even4.size())
    // 所以这样的贡献一共有 even2.size() 个 要乘起来
 
    ans = add(ans, mul(ksm(2, even4.size()), even2.size()));
 
    // 如果把4删掉 对于每一个大于等于4的 删掉会导致 他的贡献是 ksm(num / 2, 2);
    // 剩下even4.size() - 1 个 4 贡献是ksm(2, even4.size() - 1)
    // 2的贡献都不用管的
 
    for (auto num : even4)
    {
        ans = add(ans, mul(ksm(num / 2, 2), ksm(2, even4.size() - 1)));
    }
    cout << ans;
}

G

H

n个点，m条有向边，使用第i条公路时，车辆耗时 $t_{i}$ 分钟从 $u_{i}$ 前往 $v_{i}$ 每一次升级可以让路段通行时间减少 $w_{i}$ 分钟可以进行多次升级

现在有q次询问，每次给出参数k，代表总共有k次升级次数，保证对于任意的 $i$ ， $t_{i} - w_{i} \cdot k > 0$

求从1到n的最短用时

先学习单次询问： k是固定的假如我们要对 $l_{1} l_{2} l_{3}$ 三条边升级那么一定不如对 $w_{i}$ 最大的一条边进行多次升级因为 $w_{i}$ 最大就可以尽可能的减少用时

问题转化为选择一条边让边权由 $t_{i}$ 变为 $t_{i} - w_{i} \cdot k$ 求1到n的最短路

设 $d (i, j)$ 为从i到j的最短路，那么枚举 i ， $an s = min (an s, d (1, u_{i}) + t_{i} - w_{i} \cdot k + d (v_{i}, n))$

这两个最短路可以通过正反dij来求，参考 dijk

对于多次询问需要掌握凸包这个再补吧…

Alisa的数字花园

探索

20250717

BFIALDGH

B

F

I

A

L

G

H

关系图谱

目录