26牛客暑假多校7

点击查看题面

K题 D-Mail Institution Codes

题目大意

给定 $n$ 个机构的英文完整名称，每个名称由若干个单词组成。初始时，每个机构的缩写由其所有单词的首字母按顺序拼接而成。

为了消除相同缩写带来的冲突，程序按轮次进行动态调整：

1. 每轮检查所有尚未获得唯一缩写的机构。
2. 尚未唯一的机构会同时更新缩写：第 $k$ 次调整会将名称中的第 $k$ 个单词完整写出，后续单词仍保持首字母形式。
3. 调整后，重新检查所有未锁定机构的缩写。若某个机构的缩写在所有机构中唯一，则该机构的缩写被永久锁定，后续不再更改。
4. 重复上述过程，直到所有机构均获得唯一缩写。

需要按输入顺序输出最终每个机构的缩写。

数据范围：

• $1<n<20$
• 每个机构名称由 $1\le W\le 20$ 个单词组成，单词间以单个空格分隔。
• 每个单词由 $1\le L\le 20$ 个英文字母组成（首字母大写，其余小写）。
• 输入保证所有机构的完整名称两两不同。

---

思路

由于数据规模非常小（$n<20$，单词数与单词长度均不超过 $20$），我们可以直接按照题目规则进行轮次模拟：

1. 结构化存储：使用结构体 st 维护机构信息：

• s：按顺序保存该机构的所有单词。
• suo：布尔值，表示当前缩写是否已唯一并锁定。
• k：整数，表示当前已完整展开的单词数量。
• cur：当前轮次生成的缩写字符串。

2. 缩写构建机制（build 方法）：

• 遍历单词列表 $s$，若单词下标 $i<k$，将整个单词 $s[i]$ 追加到 cur 中；否则仅追加首字母 $s[i][0]$。

3. 模拟轮次循环：

• Step 1：对于所有未锁定的机构（!suo），调用 build() 更新其 cur 字符串。
• Step 2：使用 std::map<string, int> cnt 统计所有机构（包括已锁定与未锁定）当前 cur 的出现频次。
• Step 3：再次遍历，若某个未锁定机构的 cnt[a[i].cur] == 1，说明其缩写已无冲突，将其 suo 置为 true。
• Step 4：统计剩余未锁定机构的数量。若数量为 $0$，终止循环；否则对所有仍未锁定的机构执行 k++，进入下一轮。

---

复杂度分析

时间复杂度： 设机构数量为 $n$，每个机构最大单词数为 $W$，最大单词长度为 $L$。

• 单次构建缩写字符串的时间复杂度为 $O(W\cdot L)$。
• 每一轮统计频次并更新状态的时间复杂度为 $O(n\cdot W\cdot L\log n)$。
• 最多进行 $W+1$ 轮调整即可确保所有名称两两不同（因为完整名称两两不同）。
• 总体时间复杂度为 $O(W\cdot n\cdot W\cdot L\log n)=O(n{W}^{2}L\log n)$。代入数据上限 $20\times {20}^2\times 20\times {\log }_{2}20\approx 7\times {10}^5$ 次基础运算，运行时间在 $1$ 毫秒以内，远远低于 $1.0$ 秒的时间限制。

空间复杂度： 主要空间消耗在于存储单词列表与 map 映射。

• 存储所有机构单词需 $O(n\cdot W\cdot L)$ 空间。
• Map 存储中间字符串需 $O(n\cdot W\cdot L)$ 空间。
• 总体空间复杂度为 $O(n\cdot W\cdot L)$，占用空间不足 $1\text{ MB}$，满足 $1024\text{ MB}$ 的限制。

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct st {
    std::vector<std::string> s;
    bool suo = false;        
    int k = 0;               
    std::string cur;            
     
    void build() {
        cur = "";
        for (int i = 0; i < s.size(); i++) {
            if (i < k) {
                cur += s[i];    
            } else {
                cur += s[i][0];   
            }
        }
    }
};

void fc() {
    int n;
    std::cin >> n;
    std::vector<st> a(n);
    
    std::cin.ignore(); 
    std::string s;
    for (int i = 0; i < n; i++) {
        std::getline(std::cin, s);
        std::stringstream ss(s);
        std::string word;
        while (ss >> word) {
            a[i].s.push_back(word); 
        }
    }
     
    while (1) {
        std::map<std::string, int> cnt;
         
        for (int i = 0; i < n; i++) {
            if (!a[i].suo) a[i].build();
            cnt[a[i].cur]++;
        }
        
        int cn = 0;  
        for (int i = 0; i < n; i++) {
            if (!a[i].suo && cnt[a[i].cur] == 1) {
                a[i].suo = true;
            }
            if (!a[i].suo) cn++;
        }
         
        if (cn == 0) break;
         
        for (int i = 0; i < n; i++) {
            if (!a[i].suo) a[i].k++;
        }
    }
     
    for (int i = 0; i < n; i++) {
        std::cout << a[i].cur << "\n";
    }
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1; 
    while (t--) fc();
    return 0;
}

L题 Bobo's Lucky Modulo

题目大意

给定一个正整数 $n$，求满足 $1\le a,b\le n$ 且满足以下错误取模等式的有序数对 $(a,b)$ 的数量：

$$(amodb)+1=amod(b+1)$$

数据范围：

• $1\le n\le {10}^{12}$

---

思路

1. 原理与变形

推导 $a$ 与 $b$ 之间的依赖关系：

设 $a=q\cdot b+r$，其中 $q=\lfloor a/b\rfloor$ 为商，$r=amodb$ 为余数，满足 $0\le r<b$。 方程左边（LHS）为：

$$\text{LHS}=r+1$$

将 $a$ 重新用模数 $b+1$ 展开：

$$a=q(b+1)+(r-q)$$

针对余数与商的关系进行分类讨论：

• 情况一 ($r\ge q$)：此时 $0\le r-q<b+1$，直接可得 $amod(b+1)=r-q$。 代入原方程：$r+1=r-q⟹q=-1$。因为 $a,b\ge 1$，商必须满足 $q\ge 0$，故该情况下无合法解。
• 情况二 ($r<q$)：此时 $r-q<0$，说明 $a$ 除以 $b+1$ 的实际商小于 $q$。 设 $a$ 除以 $b+1$ 的商为 $q-k$ ($k\ge 1$)，余数为 $R$ ($0\le R<b+1$)。 代入展开式：

$$a=(q-k)(b+1)+R=q\cdot b+r⟹R=k(b+1)+r-q$$

令 $\text{RHS}=R=r+1$，代入上式解得：

$$q=k(b+1)-1(k\ge 1)$$

2. 解的周期分布与下界推导

将 $q=k(b+1)-1$ 代回 $a=q\cdot b+r$ 中：

$$a=(k(b+1)-1)b+r=k\cdot b(b+1)-b+r$$

由于 $0\le r<b$，固定 $b$ 时，$a$ 构成了一系列长度为 $b$ 的连续区间：

$$a\in [k\cdot b(b+1)-b,k\cdot b(b+1)-1](k\ge 1)$$

定义周期长度 $d=b(b+1)$，则在每个长度为 $d$ 的周期内，合法的 $a$ 恰好分布在周期的最后 $b$ 个位置（相对偏移量位于 $[b^2,d-1]$）。

取 $k=1,r=0$，可以得到最小的合法 $a$ 的下界：

$$a_{min}=b^2$$

根据题目限制 $a\le n$，得 $b^2\le a\le n⟹b\le \sqrt{n}$。因此，仅需枚举 $b\in [1,\lfloor \sqrt{n}\rfloor ]$，并在 $O(1)$ 时间内计算出每个 $b$ 对应的合法 $a$ 的数量。

3. 统计解的算法步骤

遍历 $b\in [1,\lfloor \sqrt{n}\rfloor ]$：

1. 定义周期：设 $d=b(b+1)$。
2. 计算首个周期 ($k=1$)：合法区间为 $[b^2,d-1]$，贡献解的个数为 $max(0,min(n,d-1)-b^2+1)$。
3. 计算后续周期 ($k\ge 2$)：令剩余数值区间长度为 $k=n-min(n,d-1)$：

• 包含 $k/d$ 个完整周期，每个完整周期贡献 $b$ 个合法解；
• 剩余不完整周期长度为 $c=kmodd$，若 $c>b^2$，则额外贡献 $c-b^2$ 个合法解。

复杂度分析

时间复杂度：$O(\sqrt{n})$。由于 $b\le \sqrt{n}\le {10}^6$，循环最多执行 $\sqrt{n}$ 次，单次循环内均为常数次算术运算。

空间复杂度：$O(1)$。仅使用常数个辅助变量保存中间计算结果。

参考代码...

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void fc() {
    ll n;
    std::cin >> n;
    
    ll ans = 0;
    // 枚举 b (代码中用 i 表示)，根据 a_min = b^2 <= n，i 的上限为 sqrt(n)
    for (ll i = 1; i * i <= n; i++) {
        ll d = i * (i + 1); // 周期长度 d = b * (b + 1)
        
        // 1. 处理第一个周期 (k = 1) 中的合法区间 [i^2, d - 1]
        ll m = std::min(n, d - 1);
        ans += std::max(0LL, m - i * i + 1);
        
        // 2. 处理后续周期 (k >= 2)
        ll k = n - m; // 剩余未统计的数值长度
        
        // 每个完整周期 d 中包含 i 个合法解
        ans += k / d * i;
        
        // 处理最后一个不完整周期
        ll c = k - k / d * d;
        // 如果余下长度 c 超过了非合法前缀 i^2，则加上超出的合法部分
        ans += std::max(0LL, c - i * i);
    }
    
    std::cout << ans << "\n";
}

int main() {
    // 优化输入输出效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    // std::cin >> t;
    while (t--) fc();
    return 0;
}

G题 Both of You, Dance Like You Want to Win!

题目大意

有 $n$ 个同步模块（$n$ 为偶数），每个模块有一个正整数相位修正值 $a_i$。已知每种数值出现的次数均为偶数。 MAGI 与 NERV 操作员进行 $n/2$ 轮在线博弈：

1. 每轮 MAGI 选择两个尚未使用的模块 $(u_r,v_r)$ 给出。

2. 操作员必须立即将其中一个安装到初号机（左侧），另一个安装到二号机（右侧），且安装后不可更改。

问操作员是否存在一种确定性策略，使得无论 MAGI 如何自适应选择，最终两台 EVA 安装的模块数值之和完全相等。

数据范围：

• $2\le n\le 2\times {10}^5$ 且 $n$ 为偶数

• $1\le a_i\le {10}^9$

• 保证序列中每个数值的出现次数均为偶数

---

思路

1. 原理与分类讨论

本题的核心在于全信息在线零和博弈下的确定性策略构造。对于包含偶数个元素且每种数值均出现偶数次的序列，我们需要判断玩家（操作员）能否对对手（MAGI）自适应给出的任意点对进行左右定侧，使最终两侧元素之和严格相等。

通过对数值种类数 $k$ 进行分类讨论，可得出当且仅当不同数值种类数 $k\le 3$ 时存在必胜确定性策略的充要条件：

(1) 不同数值种类 $k\le 3$ 的必胜构造策略

• $k=1$：所有元素数值相同，对手每轮给出的必定是同值对 $(A,A)$，直接将其分别放入左右两侧，两侧差值始终为 $0$。

• $k=2$（数值为 $A,B$）：

• 若对手给出同值对 $(A,A)$ 或 $(B,B)$，直接左右平分；

• 若对手给出异值对 $(A,B)$，采用交替定向策略：第 $1$ 次按 $(A,B)$ 放置，第 $2$ 次按 $(B,A)$ 放置。

• 由于 $A,B$ 的总出现次数均为偶数，异值对 $(A,B)$ 的总数量必然为偶数。因此交替定向后两两抵消，最终总差值为 $0$。

• $k=3$（数值为 $A,B,C$）：

• 对 $(A,B)$、$(B,C)$、$(C,A)$ 三种异值对分别独立进行交替定向。

• 若某类异值对出现偶数次，则该类异值对完全抵消；

• 若三类异值对均剩下 $1$ 对未配对，只需将这最后的 $3$ 对分别定向为 $(A,B)$、$(B,C)$ 与 $(C,A)$（形成一个三元代数环）。其对两侧差值的贡献为：

$$(A-B)+(B-C)+(C-A)=0$$

因此总差值依然能完美抵消为 $0$。

(2) 不同数值种类 $k\ge 4$ 的必败证明

当至少存在 $4$ 种不同数值时，对手可以通过构造“二次联动攻击”强制使玩家无法平衡：

• 设其中最小的 $4$ 个互不相同的数值为 $A<B<C<D$，且每种数值至少有 $2$ 个。

• 第一阶段：对手前两轮先后给出 $(A,B)$ 和 $(C,D)$。 玩家不论如何放置，假设最终左侧放置了 $p,q$，右侧放置了 $r,s$（其中 $p,q,r,s$ 分别为 $A,B,C,D$ 的某种排列）。

• 第二阶段：对手利用剩余的第二份元素，将它们重新配对为 $(p,q)$ 与 $(r,s)$ 给出。

• 无论玩家在第二阶段如何定向，两侧总差值的绝对值均满足：

$$|(p+q-r-s)\pm (p-q)\pm (r-s)|=2|u-v|$$

其中 $u\in \{p,q\}$ 且 $v\in \{r,s\}$。由于 $A,B,C,D$ 四数互不相同，必然有 $2|u-v|\ne 0$。剩余的同值元素两两抵消后也无法消除该差值，玩家必败。

2. 算法具体步骤

根据上述原理，本题无需模拟博弈全过程，只需对输入数据进行离散化统计：

1. 使用 std::map 或 std::unordered_map 统计序列中出现的不同数值种类数 $k$。

2. 若 $k\le 3$，说明可以通过交替定向与环形构造策略保证平衡，输出 YES；

3. 若 $k>3$，对手可以通过四元素联动构造必败态，输出 NO。

复杂度分析

时间复杂度：$O(n\log n)$。遍历数组并使用 std::map 进行频次统计，耗时为 $O(n\log n)$。（若改用 std::unordered_map 可优化至 $O(n)$）。远低于 $2.0$ 秒的时间限制。

空间复杂度：$O(n)$。用于哈希表存储最多 $n$ 个元素的频次信息。

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void fc() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    
    std::map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        ++cnt[a[i]]; // 统计每种数值的出现次数
    }
    
    // 根据博弈充要条件：不同数值种类数 <= 3 时必胜，否则必败
    std::cout << (cnt.size() <= 3 ? "YES" : "NO") << "\n";
}

int main() {
    // 优化标准输入输出流性能
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    // std::cin >> t;
    while (t--) fc();
    return 0;
}