感受
寒假的时候SCNUcsoj举办了十一场寒假训练赛，很荣幸有机会成为出题人之一。小谢、小罗和我（我是小妹），一起出了第十场的题。故写此篇以纪念首次出题的经历。
出题前：
看了一下OIWiki上的出题，第一句话“出题人要有一定的水平”就不符合了。
发现了一个洛谷项目CyaRon，用来造数据和对拍很方便。
出题时：
大家分工后每人出两题，一道简单的一道难的。因为水平有限，所有题都原创有点难，但因为是学校的训练赛，所以就用了一些原题，其中有两道原创题。
最后的知识点分布是签到题1，签到题2，简单的DP，线段树，贪心，难一点的DP。
出题花的时间比想象中要久，因为会比平时做题更加关注细节，更在意时间复杂度，用更多的做法来验证数据的正确性。比如我改编了一道DP题，但是又用BFS的方法做了一遍。又由于担心太简单了，就加了素数筛的内容，结果造数据的时候发现数据有规律。查阅资料发现，这就是哥德巴赫猜想。我真的不记得哥德巴赫猜想的具体内容。是不是早几百年出生，我也可以当数学家了。
和队友一起出题很有趣，特别是经过小罗对题面的“魔改”，每个人的题都“梦幻联动”，一部连续剧就出来了。
观赛时：
出题人不参赛，于是就可以愉快地上帝视角观赛了。说实话，看大家写自己的题，比自己比赛紧张多了，也害怕数据出问题。既希望大家做出来，又不希望大家做出来。基本上两个半小时没有闲过，比自己比赛忙多了，一直在后台看大家的提交，比自己比赛还要沉浸，也是很有意思。看到有人拿到一血特别兴奋。看到有人卡题，真替他着急。总之，大家都好强Orz。
第一次出题经验不足，也有瑕疵，但是这次出题也让我学到了很多。
下面看题吧~
A.黑白棋
题面
Description
注意本题特殊的时间限制
KK终于开学了，开学的第一天晚上他感觉到很无聊，于是开始和舍友玩黑白棋游戏，在KK即将要输掉的时候，他想到了一个新的游戏形式。
他把$n$个棋子排成一排，然后进行一些操作，每次操作都有两种方案可选：
1.将区间$[L,R]$中所有棋子的颜色改变，即黑棋变成白棋，白棋变成黑棋。
2.询问区间$[L,R]$中间有多少颗白棋，统计并输出结果
在一开始，所有的棋子都是黑色的。
在设计完游戏后，KK突然想起来寒假作业还没有写完，于是KK立马开始赶作业并把这个问题委托给了机智的你，希望你可以在每次询问后给出正确的答案。
Input
第一行输入两个整数$n$和$m$表示棋子的数目和可以操作的次数（$2≤n≤10^5，1\le m\le 10^5$)
接下来$m$行，每行有三个整数$op$、$L$、$R$ $(op\in {0,1}\ \ 1≤L,R≤n)$
$op$为$0$表示第一种操作，$op$为$1$表示第二种操作。
Output
对于每一次的询问操作输出一行，为统计结果。
Sample Input 1
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
Sample Output 1
1
2
题解
原题洛谷P3870开关线段树
小谢出的
这题还好检查了一下，发现数据弱了，暴力可以900ms过，所以把时间限制改了。
本题时间限制为$500ms$，故暴力模拟不可取。
本题有多种解法，包括但不限于分块、线段树，这里提供一种使用线段树的解法。区间修改，区间查询。
线段树节点存储对应区间内的黑棋和白棋数，每次改变棋子的操作对应将区间内的黑白棋的数目对调。
#include <bits/stdc++.h>
#define N 100010
using namespace std;
typedef long long ll;
struct node {
int l, r;
int black, white, lz;
} tree[4 * N]; //四倍空间以上
// 建树
// 一开始只有黑棋
void build(int i, int l, int r) {
tree[i].l = l;
tree[i].r = r;
if (l == r) {
tree[i].black++;
return;
}
int mid = (l + r) / 2;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
tree[i].black = tree[i * 2].black + tree[i * 2 + 1].black;
}
//向下传递
inline void pushdown(int i) {
if (tree[i].lz != 0) {
swap(tree[i * 2].black, tree[i * 2].white);
swap(tree[i * 2 + 1].black, tree[i * 2 + 1].white);
tree[i * 2].lz ^= 1;
tree[i * 2 + 1].lz ^= 1;
tree[i].lz = 0;
}
}
//改变
inline void change(int i, int l, int r) {
if (tree[i].l >= l && tree[i].r <= r) {
tree[i].lz ^= 1;
swap(tree[i].black, tree[i].white);
return;
}
pushdown(i);
if (tree[i * 2].r >= l)
change(i * 2, l, r);
if (tree[i * 2 + 1].l <= r)
change(i * 2 + 1, l, r);
tree[i].black = tree[i * 2].black + tree[i * 2 + 1].black;
tree[i].white = tree[i * 2].white + tree[i * 2 + 1].white;
}
//询问
int search(int i, int l, int r) {
if (tree[i].l >= l && tree[i].r <= r)
return tree[i].white;
pushdown(i);
int sum = 0;
if (tree[i * 2].r >= l)
sum += search(i * 2, l, r);
if (tree[i * 2 + 1].l <= r)
sum += search(i * 2 + 1, l, r);
return sum;
}
int main() {
int n, m;
cin >> n >> m;
build(1, 1, n);
int op, l, r;
for (int i = 1; i <= m; i++) {
cin >> op >> l >> r;
if (op == 0)change(1, l, r);
else cout << search(1, l, r) << endl;
}
}
B.糖果店
题面
Description
KK非常喜欢吃巧克力的，今天是开学前一天，他非常开心，他决定去糖果店买巧克力。他跟老板关系特别好，老板提出要跟他玩游戏，若KK取胜，他就可以免单今天买的巧克力；若老板赢了，KK就要给双倍的巧克力费用。
现在他们面前有一个$n\times m$个巧克力块组成的大巧克力，他们可以把这个大巧克力掰成两块巧克力，并吃掉其中一块，若最后对方没有办法继续往下掰，则对方输掉游戏。
假设KK与糖果店老板都足够聪明，若从老板先开始掰，请问谁最后会取得胜利？
Input
输入一行两个整数$n,m(1≤n,m≤10^6)$
Output
若老板会赢，输出BOSS，若KK会赢，输出KK
Sample Input 1
1 2
Sample Output 1
BOSS
题解
不太大众化的签到题。
小谢的原创题，没有原题。当时深夜时拿来内部自测的时候，我也是想了一会。
现场比赛的时候数据还是出了点问题，数据造得太少了，有人用别的做法（不对的）也碰巧过了。
这题的数据弱了（造数据的时候想少了一点），正确想法应该是判断巧克力是否正方形。
若巧克力一开始是长方形的，则老板可以把它掰成正方形的，而KK无论怎么操作都只能掰成长方形的，故老板可以一直掰回正方形的，直到最后变成一个$1\times1$的巧克力，此时KK就输掉了比赛。
相反，若一开始巧克力是正方形的，则在老板每次操作后，KK都可以把巧克力掰回正方形的，直到最后变成一个$1\times1$的巧克力，则最后KK取胜。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
if (n == m)cout << "KK";
else cout << "BOSS";
}
C.再分巧克力
题面
Description
KK屡战屡胜，免费得到好多巧克力，而且在和老板分巧克力时吃了太多巧克力了，现在吃不下了，于是叫来了$n$个好朋友，一起分巧克力。
现在每个好朋友手里都分到了$a_i$块巧克力，这时KK发现分巧克力给有些朋友多，有些朋友少，觉得不公平，于是KK觉得应该让每个好朋友得到一样多的巧克力（即让每个好朋友拥有的巧克力一样多），这时KK不知道怎么分巧克力了，于是求助了机智的你，并要求每一次只能从一个好朋友手里拿走两块巧克力到另一个好朋友手上。
问至少需要再移动拿走多少次巧克力可以让每个好朋友手上的巧克力块数一样多。如果方案不存在输出$-1$。
Input
输入包含一个测试用例。
测试用例的第一行包含一个整数$n$ ( $ 1≤n≤100 $ )，接下来的一行包含$n$个整数 $a_i$ ( $1≤a_i≤10^6$ )。
Output
输出一行表示最少需要拿走移动多少次巧克力可以让每个好朋友手上的巧克力块数一样多。
Sample Input 1
3
13 9 5
Sample Output 1
2
题解
比较大众化的签到题。
小罗出的。（原题忘了，我做过的一道分糖果的题的简单版）
巧克力块总数不能被均分时，不成立输出$-1$
巧克力平均块数减去每个朋友的巧克力块数不是$2$的倍数时，不成立输出$-1$
其余情况只需要记录巧克力块数小于平均数的朋友的移动次数即可
移动次数为：
$d=avg-a[i]$
$ans+=d/2$
#include <iostream>
using namespace std;
int a[105];
int main() {
int n, ave = 0, ans = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
ave += a[i];
}
bool flag = 1;
if (ave % n != 0)flag = 0;
else {
ave /= n;
for (int i = 1; i <= n; i++) {
int d = ave - a[i];
if (d % 2 != 0)flag = 0;
else if (d > 0)ans += d / 2;
}
}
if (flag)cout << ans << endl;
else cout << "-1" << endl;
return 0;
}
D.老板称重
题面
Description
老板与KK玩完分巧克力游戏后，心里掂量掂量，想计算到底少了多少巧克力，亏本了多少。于是老板拿出了他的传家宝天平，发现这一架天平用了太久了，游码没了，但是祖祖辈辈传下来了无穷无尽的砝码，奇怪的是，这些砝码的重量都是任意的素数。
现在老板想要用天平和砝码称出剩下$q$块巧克力的重量，用$w_i$表示第$i$块巧克力的重量。这时老板又不会了，看到你帮助KK分巧克力那么厉害，于是又求助了机智的你，想让你求出对于每块巧克力，最少需要使用多少个砝码才能称出其重量呢？
砝码可以放在天平两边。
Input
第一行包含一个整数$q(1\leq{q}<10000)$，表示老板需要称出的巧克力的块数。
接下来$q$行，每行包含一个正整数$w_i(2\leq{w_i}\leq{10000})$，表示需要称重的第$i$块巧克力的重量。
Output
输出$q$行，每行包含一个整数，第$i$行表示称出第$i$块巧克力的重量需要的砝码的最小个数。
Sample Input 1
2
4
9
Sample Output 1
2
2
Hint
对于样例，第一次询问:$4=2+2$或$4=7-3$，第二次询问：$9=2+7$或$9=11-2$
题解
我改编的DP背包题。题面灵感来源于蓝桥杯砝码称重，DP做法灵感来源于洛谷P1679神奇的四次方数，BFS做法灵感来源于洛谷P1135奇怪的电梯。
题目大意
给定一个正整数$w_i$。初始状态为$0$，每次操作可以在当前状态加或减一个素数，问最少进行几次操作可以变成最终状态$w_i$。
法一：BFS
现场没有人用这种方法。可能是BFS冷门。
先素数打表预处理，然后初始从$0$开始BFS，每次枚举加或减的素数，（减一个素数$p$也可以看作加一个$-p$）将结果全部记录下来，每次询问$O(1)$输出即可
时间复杂度$O(n\pi(n))$其中$\pi(n)$是不大于n的素数个数。$\pi(n)\approx{n/lnn}$
//BFS
#include<iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 1e4 + 5;
const int INF = 0x3f3f3f3f;
int w, q;
int ans[maxn];
bool a[maxn];
vector<int> prime;
queue<int> Q;
void Euler_Sieve(int n, bool a[]) {//素数线性筛法
memset(a, 0, sizeof(a));
a[0] = a[1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i] == 0) {
prime.push_back(i);
}
for (int j = 0; j < prime.size() && prime[j] * i <= n; j++) {
a[prime[j] * i] = 1;
if (i % prime[j] == 0)break;
}
}
}
int main() {
memset(ans, INF, sizeof ans);
Euler_Sieve(10000, a);
int s = prime.size();
for (int i = 0; i < s; i++) {
prime.push_back(-prime[i]);
}
ans[0] = 0;
Q.push(0);
while (!Q.empty()) {
int temp = Q.front();
Q.pop();
for (int i = 0; i < prime.size(); i++) {
int n = temp + prime[i];
if (n >= 0 && n <= 10000 && ans[n] == INF) {
ans[n] = ans[temp] + 1;
Q.push(n);
}
}
}
cin >> q;
while (q--) {
cin >> w;
cout << ans[w] << endl;
}
return 0;
}
法二：完全背包
比较明显的做法，但现场只有4人用DP。
每个素数$p$可以看作是重量为$p$，价值为$1$的物品。减一个素数$p$也可以看作加一个$-p$，因此可以把$-p$看作重量为$-p$，价值为$1$的物品。这些物品有无限个。若素数有$N$个，则问题转化为有$2N$种物品，求使总重量等于$w_i$所获得的总价值最小值。
先素数打表预处理，再进行一次完全背包，结果全部记录，每次询问$O(1)$输出即可。
（也可以进行两次完全背包，先加素数进行一次，再减素数进行一次）。
时间复杂度$O(n\pi(n))$其中$\pi(n)$是不大于n的素数个数。
//DP
#include<iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1e4 + 5;
const int INF = 0x3f3f3f3f;
int N, w, q;
int dp[maxn];
vector<int> prime;
bool a[maxn];
void Euler_Sieve(int n, bool a[]) {//素数线性筛法
memset(a, 0, sizeof(a));
a[0] = a[1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i] == 0) {
prime.push_back(i);
}
for (int j = 0; j < prime.size() && prime[j] * i <= n; j++) {
a[prime[j] * i] = 1;
if (i % prime[j] == 0)break;
}
}
}
int main() {
memset(dp, INF, sizeof dp);
Euler_Sieve(10000, a);
int s = prime.size();
for (int i = 0; i < s; i++) {
prime.push_back(-prime[i]);
dp[prime[i]] = 1;
}
N = prime.size();
for (int i = 0; i < N; i++) {
for (int j = 0; j <= 10000; j++) {
if (j - prime[i] > 0 && j - prime[i] <= 10000)
dp[j] = min(dp[j], dp[j - prime[i]] + 1);
}
}
cin >> q;
while (q--) {
cin >> w;
cout << dp[w] << endl;
}
return 0;
}
法三：数论
由著名的哥德巴赫猜想可知，任一大于$2$的整数都可写成三个质数之和，任一大于$2$的偶数都可写成两个质数之和。因此答案只能是$1$，$2$或$3$。
在比赛前，我的做法是通过枚举找到答案是$1$或$2$的数，剩下的数的答案都是$3$。
时间复杂度$O(\pi(n)\pi(n))$其中$\pi(n)$是不大于n的素数个数。
//数论
#include<iostream>
#include <vector>
#include <cstring>
#include <map>
using namespace std;
const int maxn = 1e4 + 5;
const int INF = 0x3f3f3f3f;
int w, q;
map<int, int> ans;
vector<int> prime;
bool a[maxn];
void Euler_Sieve(int n, bool a[]) {//素数线性筛法
memset(a, 0, sizeof(a));
a[0] = a[1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i] == 0) {
prime.push_back(i);
}
for (int j = 0; j < prime.size() && prime[j] * i <= n; j++) {
a[prime[j] * i] = 1;
if (i % prime[j] == 0)break;
}
}
}
int main() {
Euler_Sieve(10000, a);
for (int i = 0; i < prime.size(); i++)ans[prime[i]] = 1;
for (int i = 0; i < prime.size(); i++) {
for (int j = 0; j < prime.size(); j++) {
if ((prime[i] + prime[j]) >= 0 && (prime[i] + prime[j]) <= 10000 && ans[prime[i] + prime[j]] == 0)
ans[prime[i] + prime[j]] = 2;
if ((prime[i] - prime[j]) >= 0 && (prime[i] - prime[j]) <= 10000 && ans[prime[i] - prime[j]] == 0)
ans[prime[i] - prime[j]] = 2;
}
}
cin >> q;
while (q--) {
cin >> w;
if (ans[w] == 1 || ans[w] == 2)cout << ans[w] << endl;
else cout << 3 << endl;
}
return 0;
}
但是现场基本上都是这样做的。（可能是受到我的hint的影响？）
这个数是质数的时候，答案是$1$；否则是偶数的时候，答案是$2$；否则是奇数且它-2后的奇数是质数的时候，答案是$2$；其余的答案是$3$。
时间复杂度$O(n\sqrt{n})$
#include<iostream>
using namespace std;
const int maxn = 1e4 + 5;
int w, q;
bool isPrime(int x) {
if (x <= 1)return false;
for (int i = 2; i * i <= x; i++) {
if (x % i == 0)return false;
}
return true;
}
int main() {
cin >> q;
while (q--) {
cin >> w;
if (isPrime(w))cout << 1 << endl;
else if (w % 2 == 0 || isPrime(w - 2) || isPrime(w + 2))
cout << 2 << endl;
else cout << 3 << endl;
}
return 0;
}
E.老板装糖果
题面
Description
在老板搬店铺的时候，他发现他有大量散装糖果。店里有一些固定容量的糖罐可以装这些糖果。他想装尽量多的糖果以便不亏损，实在装不下就丢弃剩下的糖果。每个糖罐可以装的糖果数量有限制，而且糖罐能够装的总重量不能超过每个糖罐的限制。当然一个糖罐也可以不装任何东西。任何两个糖果都有一个特征，它们中总有一个的重量是另外一个的整数倍，当然它们也可能相等。
Input
输入的第一行包含两个数$n$和$m$。表示糖罐的数量以及糖果的数量。$(1≤n, m≤100000)$ 。
第二行包含$n$个整数$w_i$，表示每个糖罐能够装的最大重量。$(1≤w_i≤10^9)$ 。
第三行包含$m$个整数$m_j$，表示每个糖果的重量。$(1≤m_j≤10^9)$。
Output
输出要求仅包含一个数，为能够装进糖罐的最多的糖果数量。
Sample Input 1
2 4
13 9
4 12 2 4
Sample Output 1
3
题解
原题洛谷P3462，一道紫题，现场有3人过了Orz。
法一：贪心+进制转换
糖果两两互为倍数关系，从小到大排序，可以发现不同的糖果种类数最多是$log(10^9)$，只有$30$左右。
根据贪心的思想，糖果从小到大依次装入一定是最优的,把每个糖罐的容量写成糖果大小的进制表示，比如当有$3,9,18,54$这些种类的糖果时，$133$的容量可以写成$2\times54+1\times18+0\times9+2\times3+1$，末尾的$+1$永远用不上，可以舍弃， 那么各位从低到高分别是$(2,0,1,2)$。
把所有糖罐都写成这种表示，并把同一位上全部累加。比如说我们还有一个糖罐$(0,1,2,0)$，那么两个糖罐累加的结果就是$(2,1,3,2)$。
当我们正在放大小为$3$的糖果时，就使用最低位上的容量。比如我们只有$1$个大小为$3$的糖果，那么塞入以后剩余容量为$(1,1,3,2)$。
接下来要放大小为$9$的糖果，最低位上的那个$1$就永远用不上了。假如我们有$2$个$9$，而第二位上只有 $1$的容量，那么就往高位借一个$18$拆成两个$9$，变成$(1,3,2,2)$，然后塞入后剩余$(1,1,2,2)$。以此类推。
时间复杂度$O(nlogm)$
#include<iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, a[maxn], b[maxn], num[maxn], c[35], tot, cnt[35];
bool dfs(int id) {//首先核对是否够减，不够要依次借位
if (id > tot)return false;
if (cnt[id]) {
cnt[id]--;
return true;
}
if (dfs(id + 1)) {
cnt[id] += c[id + 1] / c[id];
cnt[id]--;
return true;
}
return false;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
sort(b + 1, b + m + 1);
for (int i = 1; i <= m; i++) {
if (b[i] != b[i - 1]) c[++tot] = b[i];
num[i] = tot;
}
for (int i = 1; i <= n; i++)
for (int j = tot; j; j--) {
cnt[j] += a[i] / c[j];
a[i] %= c[j];
}
for (int i = 1; i <= m; i++) {
if (!dfs(num[i])) {
cout << i - 1 << endl;
return 0;
}
if (i == m)cout << m << endl;
}
return 0;
}
法二：贪心+二分
根据贪心的思想，糖果从小到大放最优，二分答案$mid$，转化为判断前$mid$小的糖果能否放完。
如何判断前$mid$小的$mid$个糖果能否放完？因为糖果两两互为倍数关系，所以每个糖果都是某个数$x$的倍数，所以每个糖罐的容量都是$x$的倍数加上一个小于$x$的数。如果前$mid$个糖果都能放下，则最大的糖果必须能放下，于是可以，从大到小考虑糖果，依次扫描每个糖罐，能放就放，且与糖罐顺序无关。如果有不能放下的情况，则前$mid$小的$mid$个糖果不能放完。
由于糖果重量都成倍数关系，所以最多只有$O(logm)$种不同的数字。时间复杂度为$O(nlogmlogm)$。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, a[maxn], b[maxn], c[maxn];
bool check(int x) {
int i, j, k, t;
for (i = 1; i <= n; i++)c[i] = a[i];
for (; x; x = j) {
for (j = x - 1; b[x] == b[j]; j--);
for (t = x - j, i = 1; i <= n && t; i++) {
k = c[i] / b[x];
if (k > t) k = t;
c[i] -= k * b[x], t -= k;
}
if (t)return false;
}
return true;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> a[i];
for (int i = 1; i <= m; i++)cin >> b[i];
sort(b + 1, b + m + 1);
int l = 0, r = m;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid))l = mid;
else r = mid - 1;
}
cout << l;
return 0;
}
F.加水
题面
Description
KK面前有$n$个连续排放在一排的桶，编号分别为$1,2,……n$。这$n$个桶里面装着一定重量的水。KK附近有个水龙头，KK想将桶里的水变成不一样重量的水量，看看有多少种不同的组合。但是KK最多可以选择不同的桶组合加水$k$次。
每一次加水KK需要先选定这一排桶中的一个或多个连续的桶，即如果KK有$3$个桶分别为$1，2，3$号桶，KK要么只拿$1$号桶，要么只拿$2$号桶，要么只拿$3$号桶，要么只拿$1$号$2$号两个桶，要么只拿$2$号$3$号两个桶，要么一次拿$1，2，3$号三个桶一起拿，但是不能一次操作中同时只拿$1$号和$3$号桶。
选定好要取走的桶后，KK就去将这些桶中的水都加到和取的这些桶中最重的那一桶重量相同。问最终会有几种可能的最终桶的重量组合。答案对$10^9+7$取模。
Input
第一行两个数$N$和$K$。第二行$N$个数，第$i$个数表示编号$i$的桶的水的重量（单位：kg）。 $N,K≤500$
Output
输出最终可能的各桶重量组合序列的种数，答案记得取模。
Sample Input 1
3 2
3 1 2
Sample Output 1
4
题解
这题我是不会的（挖坑）
罗姐出的，原题我忘了
这一题把所有桶看成一个序列，每次取桶相当于取这个序列的子串。桶的重量也就相当于序列串上的数字。
容易发现最终所有桶的重量的相对顺序不变，即所有数字的相对顺序不变，每个数字可能的覆盖范围由两边第一个比它大的数决定。一个数可以延申到最左的左端点，和最右的右端点。
如果不考虑操作次数，那么解决方法就是，选出序列中的一段，将这一段变为同一个数值，这个数值是这个子串最大的那个数值，并且区间之间的相对位置不改变，计算这样的序列组合有多少种。
但又因为本题需要考虑操作的次数，我们发现对于求一个合法的目标序列，即求在操作次数最多$k$次的情况下得到的序列组合种数。最优的操作方案显然就是按照从小到大的顺序对每个数进行操作，并且对每个数的操作至多一次。
于是我们发现，只有当且仅当某个数不在最终序列中出现，我们不需要对它进行操作， 或者该数在最终序列种出现的位置恰好仅为该数的原序列中位置。操作 k 次，即最终序列只有 k 段子串（数），那么就不算一段子串（数），需要特判。
那么就想到了dp，先暴力找出每个数 $a[i]$可以延申到的区间左端点，右端点，记下来$[l,r]$，$dp[k][i]$表示第 $k$ 段子串，当前计算到原序列第$i$个数的段。
那么 dp 方程出来了一条：$dp[i][j]+=\sum dp[k][j-1],l<k<r$
如果$[l,r],l==r$，即有：$dp[i][j]+=dp[i-1][j-1]$
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 505
#define mod 1000000007
using namespace std;
int n, m, a[N], dp[N][N];
int main() {
scanf("%d%d", &n, &m);
int i, j, k, l, r, now;
for (i = 1; i <= n; i++)scanf("%d", &a[i]);
dp[0][0] = 1;
for (i = 1; i <= n; i++) {
l = i;
while (l > 1 && a[l - 1] < a[i])l--;
r = i;
while (r < n && a[r + 1] < a[i])r++;
dp[i][m] = (dp[i][m] + dp[i - 1][m]) % mod;
for (j = m; j; j--) {
for (k = l, now = dp[l - 1][j - 1]; k <= r; k++) {
dp[k][j] = (dp[k][j] + now) % mod;
now = (now + dp[k][j - 1]) % mod;
}
dp[i][j - 1] = (dp[i][j - 1] + dp[i - 1][j - 1]) % mod;
dp[i][j] = (dp[i][j] - dp[i - 1][j - 1] + mod) % mod;
}
}
int ans = 0;
for (i = 0; i <= m; i++)ans = (ans + dp[n][i]) % mod;
printf("%d\n", ans);
return 0;
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1300773281@qq.com