题意

给定字符串 T（含小写字母和 ?）和字符串 U（仅小写字母），
判断是否可以把 ? 替换成字母，使得最终字符串包含 U 作为子串。

---

思路

直接枚举 T 中所有长度为 |U| 的子串，判断是否可以匹配。

匹配规则：

• 如果是 ? → 可以匹配任意字符 ✔
• 如果是字母 → 必须和 U 对应字符相同 ✔
• 否则 → 不匹配 ❌

只要存在一个位置满足条件，就输出 Yes。

---

代码（带详细注释）

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

int main(){
    string s, t;
    cin >> s >> t;

    // 如果 T 比 U 短，不可能包含
    if(s.size() < t.size()) {
        cout << "No" << endl;
    } else {
        int ok = 0;  // 标记是否存在可行解

        // 枚举子串起点
        for(int i = 0; i <= s.size() - t.size(); i++) {

            int cnt = 0;  // 记录不匹配次数

            // 检查这一段是否可以匹配
            for(int j = 0; j < t.size(); j++) {

                // 如果当前字符不是 '?' 且不等于目标字符
                if(s[i + j] != '?' && s[i + j] != t[j]) {
                    cnt++;  // 不匹配
                }
            }

            // 如果没有不匹配，说明这一段可以成功匹配
            if(cnt == 0) {
                ok = 1;
                break;
            }
        }

        // 输出结果
        if(ok) {
            cout << "Yes";
        } else {
            cout << "No";
        }
    }
}

---

复杂度

• 时间复杂度：O(|T| × |U|)
• 数据范围很小，可以直接暴力

---

总结

本题核心：

把 ? 当作万能字符，枚举所有子串进行匹配即可。

思路

要最小化：

$\sum B_j^2$

关键结论：

• 尽量让大的数单独放，小的数去“补”大数
• 因为平方函数是凸的，大数叠加会更亏

---

做法

1. 将数组排序
2. 取最大的 $m$ 个数作为每个盘子的“基础值”
3. 剩下的 $n-m$ 个小数，从小到大：
   • 依次加到当前盘子上

---

正确性

• 大数尽量分散
• 小数补到已有的大数上
• 避免两个大数相加导致平方爆炸

---

复杂度

• 排序：$O(n \log n)$
• 其余：$O(n)$

---

标程（带注释）

#include<bits/stdc++.h>
#define int long long
using namespace std;

int a[200010], b[200010];

signed main(){
    int n, m;
    cin >> n >> m;

    // 读入数据
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    // 排序（从小到大）
    sort(a + 1, a + 1 + n);

    // 先把最大的 m 个数作为每个盘子的初始值
    for(int i = 1; i <= m; i++){
        b[i] = a[n - m + i];
    }

    // 剩下的 n-m 个小数，从小到大分配
    for(int i = 1; i <= n - m; i++){
        b[n - m - i + 1] += a[i];
    }

    // 计算答案
    long long ans = 0;
    for(int i = 1; i <= m; i++){
        ans += b[i] * b[i];
    }

    cout << ans;

    return 0;
}

---

总结

本题核心：

排序 + 贪心：大数分散，小数补充

题意

有 N 个用户、M 个比赛页面，初始时所有用户都没有任何页面的查看权限。

有 Q 次操作：

• 1 X Y：给用户 X 单独授予页面 Y 的查看权限
• 2 X：给用户 X 授予 所有页面 的查看权限
• 3 X Y：询问用户 X 能否查看页面 Y

对于每次询问操作，输出 Yes 或 No。

---

思路分析

根据题意，一个用户的权限只有两种来源：

1. 被单独授予某个页面
2. 被授予所有页面权限

所以可以对每个用户维护一个集合，记录他已经拥有的权限。

这份代码里使用的是：

map<int,int> look[200010];

表示：

• look[x][y] = 1：用户 x 可以查看页面 y
• look[x][0] = 1：用户 x 可以查看 所有页面

这里把 0 当作一个特殊标记，表示“拥有全部权限”。

---

具体做法

操作 1：1 X Y

直接记录：

look[x][y] = 1;

表示用户 x 获得页面 y 的权限。

---

操作 2：2 X

记录：

look[x][0] = 1;

表示用户 x 获得所有页面权限。

---

操作 3：3 X Y

只需要判断下面两种情况之一是否成立：

• 用户 x 曾经被单独授予页面 y
• 用户 x 拥有所有页面权限，即存在 look[x][0]

对应代码：

if(look[x].count(y) || look[x].count(0))

若成立输出 Yes，否则输出 No。

---

为什么这样做是对的

因为题目中的权限增加操作不会撤销，所以我们只需要把已经授予过的权限存下来即可。

对于任意一次询问：

• 如果用户已经被单独授予该页面权限，那么答案一定是 Yes
• 如果用户已经被授予所有页面权限，那么不管问哪个页面，答案都一定是 Yes
• 否则就是 No

因此直接判断这两种情况即可，逻辑完全符合题意。

---

复杂度分析

设总操作数为 Q。

每次操作都只进行若干次 map 的插入或查询，时间复杂度为：

• 单次操作：O(log K)
  其中 K 是当前用户已记录权限数
• 总时间复杂度：O(Q log Q)

空间复杂度：

• O(Q)

因为最多只会记录 Q 次授权信息。

---

参考代码（带注释）

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

// look[x] 表示用户 x 的权限信息
// look[x][y] = 1 表示用户 x 可以查看页面 y
// 特别地，look[x][0] = 1 表示用户 x 可以查看所有页面
map<int,int> look[200010];

int main(){
    int n, m, q;
    cin >> n >> m >> q;

    for(int i = 1; i <= q; i++){
        int op, x, y;
        cin >> op >> x;

        if(op == 1){
            // 操作 1：给用户 x 授予页面 y 的权限
            cin >> y;
            look[x][y] = 1;

        }else if(op == 2){
            // 操作 2：给用户 x 授予所有页面权限
            // 用 0 作为特殊标记
            look[x][0] = 1;

        }else{
            // 操作 3：询问用户 x 是否能查看页面 y
            cin >> y;

            // 如果用户拥有页面 y 的单独权限
            // 或者拥有所有页面权限，就输出 Yes
            if(look[x].count(y) || look[x].count(0)){
                cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }
    }

    return 0;
}

---

总结

这题本质上就是一个 权限记录模拟题。

核心做法：

• 用 map 记录每个用户能看的页面
• 用 0 这个特殊键表示“拥有所有页面权限”
• 查询时判断“单独权限”或“全部权限”是否存在即可

实现简单，思路清晰，适合直接模拟。

题意

给定一个长度为 $N$ 的整数序列 $A$，要求删除尽可能少的元素，使剩下的新序列 $B$ 满足：

对于任意 $1 \le i < j \le |B|$，都有：

$|B_i - B_j| \ne D$

求最少删除多少个元素。

---

思路分析

我们不妨换个角度思考：

• 设最终保留下来的元素个数最多为 $ans$
• 那么最少删除数就是 $N-ans$

所以本题等价于：

在原序列中尽量保留更多元素，使得任意两个被保留的数之差的绝对值不等于 $D$

---

情况一：$D=0$

当 $D=0$ 时，条件变成：

$|B_i-B_j| \ne 0$

也就是：

$B_i \ne B_j$

所以最终序列中 每个值最多只能保留一个。

做法很简单：

• 用 set 统计不同数字个数
• 设不同数字个数为 $k$
• 那么最多保留 $k$ 个
• 最少删除 $N-k$

---

情况二：$D>0$

如果两个数之差等于 $D$，那么它们不能同时保留。

注意到如果两个数差为 $D$，那么它们对 $D$ 取模后的余数一定相同。

所以可以把所有数按 A_i mod D 分组，不同组之间互不影响，分别计算后再相加即可。

---

为什么按余数分组

因为若：

$x-y=D$

那么：

$x \bmod D = y \bmod D$

因此只有 同一个余数组内 的数，才可能互相冲突。

于是每个余数组可以单独处理。

---

组内怎么做

假设某一组里有若干不同的值，并且我们统计出每个值出现了多少次。

例如这一组的值按从小到大排列后是：

$x_1, x_2, x_3, \dots$

若：

$x_i - x_{i-1} = D$

那么这两个值冲突，不能同时选。

否则它们之间没有直接冲突。

这就变成了一个经典的 打家劫舍 / 路径 DP：

• 每个不同的值看成一个点
• 点权是这个值出现的次数
• 相邻且差为 $D$ 的两个点不能同时选
• 求最多能选多少个元素

---

状态设计

设当前处理到这一组的第 $cnt$ 个不同数。

定义：

• $f[cnt][0]$：前 $cnt$ 个数中，第 $cnt$ 个数 不选 时，最多能保留多少个元素
• $f[cnt][1]$：前 $cnt$ 个数中，第 $cnt$ 个数 选 时，最多能保留多少个元素

设当前值是 $t1$，出现次数是 $t2$。

1. 当前值与上一个值不冲突

即：

$t1-d \ne last$

那么当前值可以自由选或不选：

$f[cnt][0] = \max(f[cnt-1][0], f[cnt-1][1])$

$f[cnt][1] = \max(f[cnt-1][0], f[cnt-1][1]) + t2$

2. 当前值与上一个值冲突

即：

$t1-d = last$

这时如果当前值选了，上一个值就不能选：

$f[cnt][0] = \max(f[cnt-1][0], f[cnt-1][1])$

$f[cnt][1] = f[cnt-1][0] + t2$

最后这一组的最大可保留数就是：

$\max(f[last][0], f[last][1])$

把所有组的结果加起来，就是总共最多能保留的元素数。

---

复杂度分析

设不同数字个数总数不超过 $N$。

• 统计出现次数：$O(N \log N)$
• 每个组做一次 DP，总复杂度也是 $O(N)$ 级别
• 总时间复杂度：$O(N \log N)$
• 空间复杂度：$O(N)$

可以通过本题数据范围。

---

参考代码（简单注释）

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

map<int, int> s[1000010];

int main() {
    int n, d;
    cin >> n >> d;

    // 特判 D=0：相同数字不能同时保留
    if(d == 0){
        set<int> st;
        for(int i = 1; i <= n; i++) {
            int t;
            cin >> t;
            st.insert(t);
        }
        cout << n - st.size();
        return 0;
    }

    // 按照 t%d 分组，并统计每个值出现次数
    for(int i = 1; i <= n; i++) {
        int t;
        cin >> t;
        s[t % d][t]++;
    }

    int ans = 0;  // 最多能保留的元素个数

    // 枚举每个余数组
    for(int i = 0; i < d; i++) {
        int f[s[i].size() + 2][2] = {0};
        int cnt = 1, last = -1e9;

        // 枚举这一组内的不同数（map 自动有序）
        for(auto it = s[i].begin(); it != s[i].end(); it++){
            int t1 = it->first;   // 当前值
            int t2 = it->second;  // 当前值出现次数

            // 如果和上一个值不构成差 d
            if(t1 - d != last){
                f[cnt][0] = max(f[cnt - 1][0], f[cnt - 1][1]);
                f[cnt][1] = max(f[cnt - 1][0], f[cnt - 1][1]) + t2;
            }else{
                // 如果和上一个值构成差 d，则不能同时选
                f[cnt][0] = max(f[cnt - 1][0], f[cnt - 1][1]);
                f[cnt][1] = f[cnt - 1][0] + t2;
            }

            last = t1;
            cnt++;
        }

        ans += max(f[cnt - 1][0], f[cnt - 1][1]);
    }

    // 最少删除 = 总数 - 最多保留
    cout << n - ans;
}

---

总结

这题的关键是两个转化：

1. 最少删除 转化成 最多保留
2. 按照 模 $D$ 的余数分组，把问题拆成若干个互不影响的小问题

组内再做一次经典的线性 DP 即可解决。