思路

数字排列是：

$1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 0$

可以把它看成一条“数轴”：

• 把数字 $1 \sim 9$ 看成 $1 \sim 9$
• 把 $0$ 看成 $10$

---

操作分析

每一位输入需要：

• 移动时间：当前位置到目标数字的距离
  👉 $|cur - target|$

• 按下时间：1 秒

---

总时间

对于每一位数字：

$$时间 = |cur - target| + 1$$

然后更新当前位置：

$$cur = target$$

---

做法

• 初始 $cur = 1$
• 遍历 4 个数字：
  • 把字符转成数字
  • 如果是 $0$，当作 $10$
  • 累加距离 + 1
  • 更新当前位置

---

复杂度

• 每个测试用例：$O(1)$
• 总复杂度：$O(t)$

---

代码（带注释）

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

int main(){
    int t;
    cin >> t;

    while(t--){
        int sum = 0;   // 总时间
        int cur = 1;   // 当前光标位置（初始在1）

        for(int i = 1; i <= 4; i++){
            char c;
            cin >> c;

            int x = c - '0';  // 转成数字

            // 把 0 当作 10
            if(x == 0) x = 10;

            // 移动距离 + 按下
            sum += abs(cur - x) + 1;

            // 更新当前位置
            cur = x;
        }

        cout << sum << endl;
    }

    return 0;
}

思路

删除恰好 $k$ 个字符后，还会剩下：

$$n-k$$

个字符。

这些字符可以任意重排，所以能否变成回文串，只和每个字符出现次数的奇偶性有关。

---

回文串的性质

一个字符串能重排成回文串，当且仅当：

• 如果长度是偶数：所有字符出现次数都必须是偶数
• 如果长度是奇数：最多只有 1 个字符出现次数是奇数

也就是说：

• 剩余串中奇数次数字符个数不能超过 $1$

---

关键转化

设原串中出现次数为奇数的字符个数为 $cnt$。

每删除一个字符，会改变某个字母次数的奇偶性，因此：

• 删除一个字符，奇数字符个数最多改变 $1$

为了让最后能组成回文串，最终奇数字符个数最多为 $1$。

所以只要满足：

$$cnt \le k+1$$

就可以做到。

---

为什么对？

因为：

• 我们有 $k$ 次删除机会
• 每删一个字符，最多能把一个“奇数次字符”调整掉
• 最终允许保留最多 $1$ 个奇数次字符
• 因此只要初始奇数字符个数不超过 $k+1$，就有办法删成合法状态

---

做法

对于每个测试用例：

1. 统计每个字符出现次数
2. 计算有多少个字符出现次数是奇数，记为 $cnt$
3. 判断：
   • 如果 $cnt \le k+1$，输出 YES
   • 否则输出 NO

---

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$（字符集只有 26 个小写字母）

---

代码（带注释）

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

int main(){
    int t;
    cin >> t;

    while(t--){
        int T[200] = {0};   // 统计每个字符出现次数
        int n, k, cnt = 0;
        char c;

        cin >> n >> k;

        for(int i = 1; i <= n; i++){
            cin >> c;
            T[c]++;  // 当前字符次数加1

            // 利用奇偶变化维护奇数字符个数
            if(T[c] % 2 == 1) cnt++;   // 变成奇数
            else cnt--;                // 变成偶数
        }

        // 若奇数字符个数不超过 k+1，则可以
        if(cnt <= k + 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

思路

我们要让整个数组的乘积能被 $k$ 整除，也就是让最终乘积满足：

$$(a_1 \cdot a_2 \cdot \dots \cdot a_n)\bmod k = 0$$

因为这里只关心 对 $k$ 取模后的结果，所以每个数加多少次，其实只需要关心它最后模 $k$ 是多少。

---

为什么可以做 DP

一次操作可以把某个数加 $1$。

对于一个数 $a_i$，如果我们给它加若干次，最终只影响它对 $k$ 的余数。

而且因为模 $k$ 会循环，所以：

• 最多只需要考虑加 $0,1,2,\dots,k$ 次
• 再多就没有必要了

因为 $k\le 5$，状态非常小，可以直接做动态规划。

---

状态设计

设：

$$f[i][j]$$

表示：

• 考虑前 $i$ 个数
• 当前这 $i$ 个数的乘积模 $k$ 等于 $j$
• 所需要的最少操作次数

---

初始状态

只考虑第一个数时：

如果给 $a_1$ 加 $i$ 次，那么它的余数是：

$$(a_1+i)\bmod k$$

于是：

$$f[1][(a_1+i)\bmod k] = i$$

其中 $i$ 枚举 $0\sim k-1$ 也行，你代码里写到 $k$ 也没问题。

---

转移

现在已经知道前 $i$ 个数的状态是 $f[i][j]$。

接下来处理第 $i+1$ 个数，假设给它加 $s$ 次，那么新余数为：

$$(a_{i+1}+s)\bmod k$$

新乘积余数变成：

$$j \times ((a_{i+1}+s)\bmod k)\bmod k$$

所以转移是：

$$f[i+1][j \times (a_{i+1}+s)\bmod k] = \min\big(f[i+1][j \times (a_{i+1}+s)\bmod k],\ f[i][j]+s\big)$$

---

最终答案

我们要求整个乘积能被 $k$ 整除，也就是模 $k$ 为 $0$。

所以答案就是：

$$f[n][0]$$

---

复杂度

状态数很小：

• $i$ 有 $n$ 个
• $j$ 最多 $0\sim k-1$
• $s$ 最多枚举到 $k$

所以总复杂度为：

$$O(n \cdot k \cdot k)$$

由于 $k \le 5$，所以这就是线性的，完全可以通过。

---

代码（带注释）

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

int a[200010], f[200010][10];

int main(){
    int t;
    cin >> t;

    while(t--){
        // 先把 dp 数组赋成很大，表示“不可达”
        memset(f, 0x3f, sizeof(f));

        int n, k;
        cin >> n >> k;

        for(int i = 1; i <= n; i++) cin >> a[i];

        // 初始化：只考虑第 1 个数
        // 给 a[1] 加 i 次，得到不同余数
        for(int i = 0; i < k; i++){
            f[1][(a[1] + i) % k] = i;
        }

        // 依次处理后面的数
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < k; j++){
                // 当前前 i 个数乘积 % k = j

                for(int s = 0; s <= k; s++){
                    // 给第 i+1 个数加 s 次
                    // 新乘积余数 = j * (a[i+1]+s) % k
                    f[i + 1][j * (a[i + 1] + s) % k] =
                        min(f[i + 1][j * (a[i + 1] + s) % k], f[i][j] + s);
                }
            }
        }

        // 最终要求乘积 % k == 0
        cout << f[n][0] << endl;
    }
}

思路

要判断当前集合中是否存在 两条不相交的线段。

设两条线段为：

• $(l_1, r_1)$
• $(l_2, r_2)$

它们不相交，等价于其中一条完全在另一条左边，也就是：

$$r_1 < l_2 \quad \text{或} \quad r_2 < l_1$$

---

关键结论

如果集合中存在一对不相交线段，那么一定有：

• 某条线段的左端点很大
• 某条线段的右端点很小

所以只需要比较：

• 所有线段左端点的最大值 maxL
• 所有线段右端点的最小值 minR

如果：

$$maxL > minR$$

那么就说明：

• 有一条线段起点在 maxL
• 有一条线段终点在 minR
• 它们一定可以构成一对不相交线段

因此答案为 YES。

否则输出 NO。

---

为什么成立

假设：

• 一条线段左端点最大，为 $L$
• 一条线段右端点最小，为 $R$

如果 $L > R$，那么这两条线段一定满足：

$$R < L$$

也就是“右边那条线段的起点已经跑到左边那条线段的终点右边去了”，所以它们不相交。

---

做法

用两个 map 维护：

• l[x]：左端点等于 x 的线段个数
• r[x]：右端点等于 x 的线段个数

这样就能快速得到：

• 最大左端点：l 的最后一个键
• 最小右端点：r 的第一个键

每次操作后判断：

• 若集合为空，输出 NO
• 否则若 maxL > minR，输出 YES
• 否则输出 NO

---

复杂度

每次操作涉及 map 插入、删除、查询：

• 时间复杂度：$O(\log q)$
• 总复杂度：$O(q \log q)$

---

代码（带注释）

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

map<int, int> l, r;  
// l[x] = 左端点为 x 的线段个数
// r[x] = 右端点为 x 的线段个数

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

    for(int i = 1; i <= n; i++){
        char op;
        int a, b;
        cin >> op >> a >> b;

        if(op == '+'){
            // 加入一条线段 (a, b)
            l[a]++;
            r[b]++;
        }else{
            // 删除一条线段 (a, b)
            l[a]--;
            r[b]--;

            // 如果某个端点数量变成 0，就从 map 中删掉
            if(l[a] == 0) l.erase(a);
            if(r[b] == 0) r.erase(b);
        }

        // 如果当前集合非空
        if(l.size()){
            // 最大左端点
            auto it = l.end();
            it--;
            int maxL = it->first;

            // 最小右端点
            auto it1 = r.begin();
            int minR = it1->first;

            // 若 maxL > minR，则存在一对不相交线段
            if(maxL > minR){
                cout << "YES" << endl;
            }else{
                cout << "NO" << endl;
            }
        }else{
            // 空集合不可能存在两条不相交线段
            cout << "NO" << endl;
        }
    }
}