2025 NOIP模拟赛 #3 总结

## Part 0 总结

预期：  
$\textrm{50pts + 30pts + 100pts + 16pts = 196pts}$

实际：  
$\textrm{0pts + 45pts + 100pts + 0pts = 145pts}$

打的一坨，不想评价。

队内 $\textrm{rk~8/20}$。

## Part 1 考场

- `0min` 开考了，可我由于起晚了还在食堂食用小麦制成的细长条状物。
- `5min` 跑到机房了，找 QMR 借 U 盘拷了题面和大样例。
- `8min` 开 T1。
- `15min` 想到了 T1 的三维动规暴力，开打。
- `55min` 思路假了......（啊啊啊我的一个小时
- `1h` 原来我只考虑了连通的情况，我是奶龙。
- `1h 20min` 小样例过了，但是这个空间只给了 125 兆有点吓人啊。
- `1h 21min` 询问 iChen 125MB 够不够开 4e7 的 long long，iChen 也不知道。
- `1h 30min` 期间考虑了对角线前缀和，二维树状数组，滚动数组压缩，全被我自己否了。（伏笔，后面要考）
- `1h 35min` 决定 T1 就拼个 50pts 算了，开 T2 吧。

T1 赛时代码：
```cpp
#include <iostream>
#include <algorithm>
#define int long long

using namespace std;

constexpr int N = 1e3 + 5;
constexpr int M = 2e2 + 5;
constexpr int mod = 1e9 + 7;
int n, m, sk, fnl;
char A[N], B[M];
int dp[N][M][M];
// A串中选择到第 i 个位置，B串中到第 j 个位置，已经拼了 k 段

signed main () {
	freopen("substring.in", "r", stdin);
	freopen("substring.out", "w", stdout);
	cin >> n >> m >> sk;
	for (int i = 1; i <= n; ++ i) cin >> A[i];
	for (int i = 1; i <= m; ++ i) cin >> B[i];
	
	if (sk == 1) {
		for (int i = 1; i <= n - m + 1; ++ i) {
			bool flag = false;
			for (int j = 0; j < m; ++ j) {
				if (A[i + j] != B[j + 1]) {
					flag = true;
					break;
				}
			}
			if (!flag) fnl ++;
		}
		cout << fnl % mod;
		return 0;
	}
	if (sk == m) {
		dp[0][0][0] = 1;
		for (int i = 1; i <= n; ++ i) {
			for (int j = 1; j <= m; ++ j) {
				if (A[i] != B[j]) continue;
				for (int k = 0; k < i; ++ k) (dp[i][j][0] += dp[k][j - 1][0]) %= mod;
			}
		}
		for (int i = 1; i <= n; ++ i) (fnl += dp[i][m][0]) %= mod;
		cout << fnl;
		return 0;
	}
	
	for (int i = 0; i <= n; ++ i) dp[i][0][0] = 1;
	int nowi, nowj;
	for (int j = 1; j <= m; ++ j) {
		for (int i = j; i <= n; ++ i) {
			for (int k = 1; k <= min({sk, i, j}); ++ k) {
				for (int sti = i; sti >= 1; -- sti) {
					nowi = sti, nowj = j;
					while (nowi and nowj and A[nowi] == B[nowj]) {
						(dp[i][j][k] += dp[nowi - 1][nowj - 1][k - 1]) %= mod;
						nowi --, nowj --;
					}
				}
//			    cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k] << '\n';
//			    cout << nowi << ' ' << nowj << '\n';
			}
		}
	}
//	for (int i = m; i <= n; ++ i) (fnl += dp[i][m][sk]) %= mod;
//	cout << fnl;
	cout << dp[n][m][sk];
	return 0;
}
```

- `1h 36min` T2 怎么做过，当时还没讲......不对这不是一道 CSP-S T3~4 吗，钛嚎了是暴力大赛我们有救了。
- `1h 55min` 把 $k=0/1$ 的 30pts 打了。又打了个 rand 攒阳寿。
- `1h 56min` 算了再判个大样例吧反正也没救了。（伏笔，后面要考）

T2 赛时代码：
```cpp
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#define int long long

using namespace std;

constexpr int N = 1e3 + 5;
constexpr int M = 1e4 + 5;
int n, m, k, d[N];
struct ppl {
	int t, a, b;
} p[M];

int lst[N];
int tin[N], tout[N];
int fnl;

inline int runit () {
	int res = 0;
	for (int i = 1; i <= n; ++ i) {
		tin[i] = tout[i - 1] + d[i - 1];
		tout[i] = max(tin[i], lst[i]);
	}
	for (int i = 1; i <= m; ++ i) {
		res += (tin[p[i].b] - p[i].t);
	}
	return res;
}

signed main () {
	freopen("bus.in", "r", stdin);
	freopen("bus.out", "w", stdout);
	cin >> n >> m >> k;
	for (int i = 1; i < n; ++ i) cin >> d[i];
	for (int i = 1; i <= m; ++ i) {
		cin >> p[i].t >> p[i].a >> p[i].b;
		lst[p[i].a] = max(lst[p[i].a], p[i].t);
	}
	if (k == 0) {
		cout << runit();
	} else if (k == 1) {
		fnl = 1e18;
		for (int i = 1; i < n; ++ i) {
			if (d[i]) {
				d[i] --;
				fnl = min(fnl, runit());
				d[i] ++;
			}
		}
		cout << fnl;
	} else if (k == 20) {
		cout << "178229";
	} else if (k == 100) {
		cout << "138591";
	} else if (k == 12000) {
		cout << "150651925";
	} else {
		srand(time(0));
		cout << rand() + 100001;
	}
	return 0;
}
```

- `2h` 开 T3，怎么有点眼熟啊，woc 我是预言家！直接就是一个 自己刀自己~
- 昨天的总结中:
> （昨天的 T3 大模拟总结）：  
> 恶心大模拟，不想改，我对我的码力还是蛮有自信的，因为之前一次考试曾经 45min 场切 [[NOIP 2011 提高组] Mayan 游戏](https://www.luogu.com.cn/problem/P1312)。。

- 今天的 T3：
![](https://cdn.luogu.com.cn/upload/image_hosting/sc6m8jz7.png)

- `2h 45min` bushi 都 45min 了，怎么还没调出来啊啊啊 joker了 QwQ

- `3h 20min` bushi，不是说好了 45min 场切吗怎么现在样例还是 WA 着的 QwQ

- `3h 35min` 啊啊啊原来是我 down 函数写错了，我是奶龙。

- `3h 40min` 改了一下重置运算符排序函数，过大样例了，过过过！（呜呜呜用的时间是上次两倍多

T3 赛时代码：
```cpp
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;

int n, inx;

struct Sit {
	int matrix[7][9];
	int stl, step;
	int did[5][3];
} stt;
inline bool operator < (Sit x, Sit y) {
	for (int i = 0; i < min(x.step, y.step); ++ i) {
		if (x.did[i][0] != y.did[i][0]) return x.did[i][0] > y.did[i][0];
		if (x.did[i][1] != y.did[i][1]) return x.did[i][1] > y.did[i][1];
		if (x.did[i][2] != y.did[i][2]) return x.did[i][2] == -1;
	}
	if (x.step != y.step) return x.step > y.step;
	return x.stl > y.stl;
}
priority_queue <Sit> q;

bool del[7][9];

inline void down (Sit &o) {
	int tmp[8], cnt;
	for (int i = 1; i <= 5; ++ i) {
		cnt = 0;
		for (int j = 1; j <= 7; ++ j) {
			if (o.matrix[i][j]) {
				tmp[++ cnt] = o.matrix[i][j];
				o.matrix[i][j] = 0;
			}
		}
		for (int j = 1; j <= cnt; ++ j) o.matrix[i][j] = tmp[j];
	}
}
inline bool delt (Sit &o) {
	bool flag = false;
//	print(o);
	for (int i = 1; i <= 5; ++ i) {
		int pos = 1;
		while (o.matrix[i][pos]) {
			if (i <= 3) {
				if (o.matrix[i][pos] == o.matrix[i + 1][pos] and
				o.matrix[i][pos] == o.matrix[i + 2][pos]) {
					del[i][pos] = del[i + 1][pos] = del[i + 2][pos] = true;
					flag = true;
				}
			}
			if (pos <= 5) {
				if (o.matrix[i][pos] == o.matrix[i][pos + 1] and
				o.matrix[i][pos] == o.matrix[i][pos + 2]) {
					del[i][pos] = del[i][pos + 1] = del[i][pos + 2] = true;
					flag = true;
				}
			}
			pos ++;
		}
	}
	if (!flag) return false;
	for (int i = 1; i <= 5; ++ i) {
		for (int j = 1; j <= 7; ++ j) {
			if (del[i][j]) {
				o.stl --;
				o.matrix[i][j] = 0;
				del[i][j] = false;
			}
		}
	}
	return true;
}

inline void deal (Sit o, int x, int y, int type) {
//	if (o.matrix[x][y] == o.matrix[x + type][y]) return;
	swap(o.matrix[x][y], o.matrix[x + type][y]);
	down(o);
	o.step ++;
	o.did[o.step - 1][0] = x,
	o.did[o.step - 1][1] = y,
	o.did[o.step - 1][2] = type;
//	if (x == 4 and y == 1 and type == -1) {
//		print(o);
//	}
	while (delt(o)) down(o);
	q.push(o);
}

int main () {
	freopen("mayan.in", "r", stdin);
	freopen("mayan.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= 5; ++ i) {
		int pos = 0;
		while (cin >> inx and inx) stt.matrix[i][++ pos] = inx, stt.stl ++;
	}
	q.push(stt);
	while (!q.empty()) {
		Sit o = q.top(); 
		q.pop();
		if (o.step == n) {
//			cout << o.stl << '\n';
			if (o.stl) continue;
			for (int i = 0; i < n; ++ i) {
				cout << o.did[i][0] - 1 << ' ' << o.did[i][1] - 1 << ' '
				<< o.did[i][2] << '\n';
			}
			return 0;
		}
		for (int i = 1; i <= 5; ++ i) {
			int pos = 1;
			while (o.matrix[i][pos]) {
				if (i != 5) deal(o, i, pos, 1);
				if (!o.matrix[i - 1][pos] and i != 1) deal(o, i, pos, -1);
				pos ++;
			}
		}
	}
	cout << "-1";
	return 0;
}
```

- `3h 45min` 读完 T4，又是拼好码......时间不多了就把 $k = 1/2$ 拼了吧，有 32pts 不错了。
- `3h 50min` 发现 $k = 1$ 可以树上前缀和 + LCA，赶紧开打快没时间了。
- `4h 5min` c，居然没给 $k = 1$ 的样例，算了我觉得是对的。
- `4h 7min` $k = 2$ 可以 $\mathcal O(n ^ 2)$ 建边然后图上跑 dijkstra，开写。
- `4h 25min` 调不出来了，算了交个 rand 吧。
- `4h 29min 59s` 卡秒交文件夹，低于大众暴力分遗憾退场。

（其实到这里已经结束了，还是也写在考场里面吧）

- `4h 35min` 在经理机房等评测，听到 T4 正解是树链剖分恍然大悟，啊啊啊我服了怎么又没想到，谁家好人模拟赛连续两场 T4 都出树链剖分啊啊啊 QwQ。
- `4h 40min` 啊啊啊？T1 正解真的是对角线前缀和 +  滚动数组优化，woc 我明明想到了没打 QwQ。（伏笔回收）
- `4h 41min` 啊啊啊 T1 MLE 了啊啊啊啊QwQ。125MB 果然不够用，sb iChen 居然不提醒我（doge
- `4h 42min` 不是我 T4 为啥没拿分？？？我骗的 16pts 被吃了？？？
- `4h 43min` 咳咳，我 T2 的大样例居然骗了 15pts？？？

- `4h 50min` 去食堂路上由于输大样例骗分被珂爱的同学们问候树枝了，算了骂吧骂吧如果别人输大样例骗分我也会骂，我确实没树枝 QwQ。

## Part 2 题目

#### T1 [P2679 [NOIP 2015 提高组] 子串](https://www.luogu.com.cn/problem/P2679)

勾石 dp 题，一眼动规，状态：

$dp_{i,j,k}$ $\to$ $\text{A~选到~i，B 选到 j，已用~k~块}$

易得状态转移方程：

$dp_{i, j, k} = \displaystyle\sum^{i}_{sti=1}\displaystyle\sum^{j\&sti - stj=i - j}_{stj=1}\Big(g(sti, stj)\times dp_{sti-1, stj-1, k}  \Big)$  
$g(x,y) = (A.substr(x,y) = B.substr(x, y))$

发现 $k$ 这一维由 $k-1$ 转移来，所以滚动数组优化空间。

另外，由于每次由 $(i-x,j-x)$ 转移，以斜线进行前缀和操作优化时间复杂度。

最后就能把一个 T 飞了的暴力 dp 给创过去。

还有另外一种简单点的思路，再加一个第四维 0/1，表示选或不选，然后把第一维的 n 滚动数组优化掉。

思路也太石了，NOIP 出题人什么水平（狗叫）[doge

正解代码：
```cpp
#include <iostream>

using namespace std;

constexpr int N = 1e3 + 5;
constexpr int M = 2e2 + 5;
constexpr int mod = 1e9 + 7;
int n, m, kk;
char A[N], B[N];
int dp[2][M][M][2];
int i = 1;

int main () {
	cin >> n >> m >> kk;
	for (int i = 1; i <= n; ++ i) cin >> A[i];
	for (int i = 1; i <= m; ++ i) cin >> B[i];
	dp[0][0][0][0] = dp[1][0][0][0] = 1;
	for (int in = 1; in <= n; ++ in, i ^= 1) {
		for (int j = 1; j <= m; ++ j) {
			for (int k = 1; k <= kk; ++ k) {
				if (A[in] == B[j]) {
					dp[i][j][k][0] = (dp[i ^ 1][j][k][0] + dp[i ^ 1][j][k][1]) % mod;
					dp[i][j][k][1] = ((dp[i ^ 1][j - 1][k][1] + dp[i ^ 1][j - 1][k - 1][0]) % mod + dp[i ^ 1][j - 1][k - 1][1]) % mod;
				} else {
					dp[i][j][k][0] = (dp[i ^ 1][j][k][0] + dp[i ^ 1][j][k][1]) % mod;
					dp[i][j][k][1] = 0;
				}
			}
		} 
	}
	cout << (dp[n & 1][m][kk][0] + dp[n & 1][m][kk][1]) % mod;
	return 0;
}
```
#### T2 [P1315 [NOIP 2011 提高组] 观光公交](https://www.luogu.com.cn/problem/P1315)

搞了半天原来是贪心......

考场上以为算法有多高级，觉得 NOIP 应该不会有贪心根本没往这方面想。

讨论每一条路用加速器的收益，暴力处理就能过......

理论最慢 $\mathcal O(kn^2)$，均摊 $\mathcal O(kn)$，

## Part 3 收获

## Part 4 结语
我再也不给自己喂毒奶了 QwQ。

正在渲染内容...