NOIP 2023 游记

· · 生活·游记

Day -1

复习最近一场模拟赛，题解也没看懂多少，就睡了。

Day 0

去考点（就是我们学校，喜），感觉不错。

Day 1

08：30 开考，读题。

08：40 读题结束，开 A 题。

A 词典

大事记

08：45 打了 m=1 特殊数据，40pts 到手。

08：50 发现了 m=2 的特殊性质，70pts 到手。

08：55 手玩样例，想到了正解，狂敲代码。

09：00 四个大样例全部通过！跟 m \leq 2 的骗分代码开始对拍，开 B 题。

解法

当 m=1 时，每个字符串都是一个单独的字符，这时无法进行字符交换，只有 ASCII 值最小的那种字符才有可能（ASCII 值最小的字符不一定唯一）。

当 m=2 时，使用 O(n^2) 枚举；对于两个字符串 si, sj，求出它们字符反转之后的 is, js，然后判断是否有可能符合要求（si < sj || si < js || is < sj || is < js）即可。

正解思路是，遍历 $n$ 个字符串：对于第 $i$ 个字符串，将其字符**升序排序**，将其他字符串字符**降序排序**，可以证明，这时如果第 $i$ 个字符串字典序最小那么一定可以；否则一定不可以。读入时预处理每个字符串的两种排序结果即可通过本题。 #### 考场代码 | [提交记录](https://www.luogu.com.cn/record/135766088) ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; ll n, m; string iarr[3005]; // initial string sarr[3005]; // sorted (shengxu) string jarr[3005]; // sorted (jiangxu) string minstr = "z"; int main() { freopen("dict.in", "r", stdin); freopen("dict.out", "w", stdout); cin >> n >> m; for (int i = 1; i <= n; i ++) { cin >> iarr[i]; if (minstr > iarr[i]) { minstr = iarr[i]; } sarr[i] = iarr[i]; sort(sarr[i].begin(), sarr[i].end()); jarr[i] = sarr[i]; reverse(jarr[i].begin(), jarr[i].end()); } if (m == 1) { for (int i = 1; i <= n; i ++) { if (iarr[i] == minstr) { cout << "1"; } else { cout << "0"; } } cout << '\n'; return 0; } for (int i = 1; i <= n; i ++) { bool ok = true; for (int j = 1; j <= n; j ++) { if (i == j) continue; if (sarr[i] >= jarr[j]) { ok = false; break; } } if (ok) cout << "1"; else cout << "0"; } cout << '\n'; return 0; } ``` ### B 三值逻辑 #### 大事记 09：10 理解完题意，发现测试点 $1,2$ 可以用 $O(3^n)$ 搜索搞定，开始敲代码。 09：50 调完搜索代码，看测试点 $3,4$，发现特殊性质。 10：10 看测试点 $5,6$，感觉找到了性质但是发现是假的。 10：30 没想出更深的解法了，去看 C 题。 #### 解法 对于 $n,m \leq 10$ 的情况，可以进行 $O(3^n)$ 搜索，枚举每一个变量的三种初始值情况，再模拟判断，找到最少的 `Unknown` 变量个数。期望得分 $20pts$。 对于 $v$ 只有可能是 `T`，`F`，`U` 的情况，先将数组中变量的值都设为 `T`，再模拟一遍操作，对变量正常进行赋值，最后统计 `U` 的个数即可。期望得分 $40pts$。 #### 考场代码 | [提交寄录](https://www.luogu.com.cn/record/135766104) ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 5e5 + 10; ll C, n, m, q, kx, ky; ll a[N], b[N]; ll ca[N], cb[N]; void Output() { for (int i = 1; i <= n; i ++) cout << ca[i] << " "; cout << endl; for (int i = 1; i <= m; i ++) cout << cb[i] << " "; cout << endl; } bool check_zero() { for (int i = 1; i <= n; i ++) { if (ca[i] == 0) return true; } for (int i = 1; i <= m; i ++) { if (cb[i] == 0) return true; } return false; } bool check_same() { for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { if (ca[i] == cb[j]) return true; } } return false; } bool check_big() { int i = 1, j = 1; while (1) { int tj = j, ti = i; while (ca[i] > cb[j]) { j++; } j--; while (ca[i] > cb[j]) { i++; } i--; if (i >= n && j >= m) return true; if (tj == j+1 && ti == i+1) break; } if (i >= n && j >= m) return true; else return false; } bool check_small() { int i = 1, j = 1; while (1) { int tj = j, ti = i; while (ca[i] < cb[j]) { j++; } j--; while (ca[i] < cb[j]) { i++; } i--; if (i >= n && j >= m) return true; if (tj == j+1 && ti == i+1) break; } if (i >= n && j >= m) return true; else return false; } void work() { if (check_zero() || check_same()) { cout << "0"; return; } else { if (check_big() || check_small()) cout << "1"; // if (check_big()) cout << "1"; else cout << "0"; } } int main() { freopen("expand.in", "r", stdin); freopen("expand.out", "w", stdout); cin >> C >> n >> m >> q; for (int i = 1; i <= n; i ++) { cin >> a[i]; ca[i] = a[i]; } for (int i = 1; i <= m; i ++) { cin >> b[i]; cb[i] = b[i]; } if (C == 1) { if (a[1] == b[1] || a[1] == 0 || b[1] == 0) cout << "0"; else cout << "1"; } else { work(); } for (int ti = 1; ti <= q; ti ++) { cin >> kx >> ky; for (int i = 1; i <= n; i ++) ca[i] = a[i]; for (int i = 1; i <= m; i ++) cb[i] = b[i]; ll tx, ty, tv; for (int k = 1; k <= kx; k ++) { cin >> tx >> tv; ca[tx] = tv; } for (int k = 1; k <= ky; k ++) { cin >> ty >> tv; cb[ty] = tv; } if (C == 1) { if (a[1] == b[1] || a[1] == 0 || b[1] == 0) cout << "0"; else cout << "1"; } else { work(); } } return 0; } ``` ### C 双序列扩展 #### 大事记 10：30 手玩样例，发现两个性质，用这两个性质过掉了样例，但是赛后发现这两个性质都是假的…… 10：40 去找 $n,m \leq 2$ 的性质，但是找了半天没找着。 11：00 发现错误的 $O(nm)$ 解法，算了一会儿之后发现是假的。 11：10 尝试去捣特殊性质，但是没有捣出来，去看 D 题。 #### 解法 当 $n=m=1$ 时，如果 $x_1=y_1$，那么一定不满足要求；如果 $x_1 ≠ y_1$，那么一定满足要求。 #### 考场代码 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 5e5 + 10; ll C, n, m, q, kx, ky; ll a[N], b[N]; ll ca[N], cb[N]; void Output() { for (int i = 1; i <= n; i ++) cout << ca[i] << " "; cout << endl; for (int i = 1; i <= m; i ++) cout << cb[i] << " "; cout << endl; } bool check_zero() { for (int i = 1; i <= n; i ++) { if (ca[i] == 0) return true; } for (int i = 1; i <= m; i ++) { if (cb[i] == 0) return true; } return false; } bool check_same() { for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { if (ca[i] == cb[j]) return true; } } return false; } bool check_big() { int i = 1, j = 1; while (1) { int tj = j, ti = i; while (ca[i] > cb[j]) { j++; } j--; while (ca[i] > cb[j]) { i++; } i--; if (i >= n && j >= m) return true; if (tj == j+1 && ti == i+1) break; } if (i >= n && j >= m) return true; else return false; } bool check_small() { int i = 1, j = 1; while (1) { int tj = j, ti = i; while (ca[i] < cb[j]) { j++; } j--; while (ca[i] < cb[j]) { i++; } i--; if (i >= n && j >= m) return true; if (tj == j+1 && ti == i+1) break; } if (i >= n && j >= m) return true; else return false; } void work() { if (check_zero() || check_same()) { cout << "0"; return; } else { if (check_big() || check_small()) cout << "1"; // if (check_big()) cout << "1"; else cout << "0"; } } int main() { freopen("expand.in", "r", stdin); freopen("expand.out", "w", stdout); cin >> C >> n >> m >> q; for (int i = 1; i <= n; i ++) { cin >> a[i]; ca[i] = a[i]; } for (int i = 1; i <= m; i ++) { cin >> b[i]; cb[i] = b[i]; } if (C == 1) { if (a[1] == b[1] || a[1] == 0 || b[1] == 0) cout << "0"; else cout << "1"; } else { work(); } for (int ti = 1; ti <= q; ti ++) { cin >> kx >> ky; for (int i = 1; i <= n; i ++) ca[i] = a[i]; for (int i = 1; i <= m; i ++) cb[i] = b[i]; ll tx, ty, tv; for (int k = 1; k <= kx; k ++) { cin >> tx >> tv; ca[tx] = tv; } for (int k = 1; k <= ky; k ++) { cin >> ty >> tv; cb[ty] = tv; } if (C == 1) { if (a[1] == b[1] || a[1] == 0 || b[1] == 0) cout << "0"; else cout << "1"; } else { work(); } } return 0; } ``` ### D 天天爱打卡 #### 大事记 11：30 饿死了，干面包。 11：40 看特殊性质，好像有了思路，但是没有过对应的大样例。 12：00 发现测试点 $1,2$ 中 $n\leq 18$，可以 $O(2^n)$ 枚举每天打卡或者不打卡。 12：15 开始颓。 #### 解法 当 $n \leq 18$ 时，$O(2^n)$ 枚举每天打卡或者不打卡，判断 $k$ 天限制和每个任务是否完成即可。 #### 考场代码 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 1e5 + 10; ll C, T, n, m, k, d; ll x[N], y[N], v[N]; bool vis[N]; bool check_k(int idx) { for (int i = idx - k; i <= idx; i ++) { if (!vis[i]) return false; } return true; } bool check_task(int l, int r) { for (int i = l; i <= r; i ++) { if (!vis[i]) return false; } return true; } int main() { freopen("run.in", "r", stdin); freopen("run.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0); cin >> C >> T; // scanf("%lld%lld", &C, &T); while (T--) { // scanf("%lld%lld%lld%lld", &n, &m, &k, &d); cin >> n >> m >> k >> d; for (int i = 1; i <= m; i ++) { // scanf("%lld%lld%lld", &x[i], &y[i], &v[i]); cin >> x[i] >> y[i] >> v[i]; } ll ans = 0; for (int i = 0; i < (1 << n); i ++) { for (int j = 0; j < n; j ++) { if (i & (1 << j)) { vis[j + 1] = 1; } else { vis[j + 1] = 0; } } bool boom = false; for (int j = k + 1; j <= n; j ++) { if (check_k(j)) { boom = true; break; } } if (boom) continue; ll tans = 0; for (int j = 1; j <= m; j ++) { if (check_task(x[j] - y[j] + 1, x[j])) { tans += (v[j] - y[j] * d); } } ans = max(ans, tans); } cout << ans << '\n'; // printf("%lld\n", ans); } return 0; } ``` ## 总结 预估得分：$100+40+[0,5]+[0,8]=[140,153]$，本次超常发挥，下次继续加油！