这是一篇迟到的 blog，谨以此献给我短暂而美好的 OI 生涯
T1 报数
水但是很可惜
只能说真的很可惜, 考场里我想到了这种做法
但我不知道为什么脑抽以为这个是 $O(n^2)$ 的算法 (其实是 $O(nlogn)$)
然后我果断放弃这种做法......
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e7 + 1000; bool p[N]; int nxt[N]; bool has7(int x) { while (x) { if (x % 10 == 7) return true; x /= 10; } return false; } int init(int n) { for (int i = 1; i <= n; ++ i) { // 用所有含7的数筛掉它的倍数 if (!p[i] && has7(i)) { for (int j = i; j <= n; j += i) if (!p[j]) p[j] = true; } } int end = n; while (p[end]) -- end; // 找到最后一个可以报的数字, 要保证这个值大于1e7 for (int i = end, Nxt = end; ~i; -- i) { if (p[i]) nxt[i] = -1; else { nxt[i] = Nxt; Nxt = i; } } return end; } int main() { cin.tie(0)->sync_with_stdio(0); init(1e7 + 7); int T; cin >> T; while (T --) { int x; cin >> x; cout << nxt[x] << '\n'; } } |
T2 数列
很可惜, 考场里不知道在想什么
把位数和贡献用参数传入优化就能拿 20pts
再加记忆化就能拿 50pts
正解是4维dp
DFS
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> // 20pts #include <algorithm> #include <cstring> using namespace std; typedef long long LL; const int mod = 998244353; const int N = 110; int ans, v[N]; int n, m, k; int popcnt(int x) { int res = 0; while (x) { x -= x & -x; ++ res; } return res; } void dfs(int u, int s, int sum) { if (u > n) { if (popcnt(s) <= k) ans = ((LL)ans + sum) % mod; // 考场里只想到从这里开始计算s和sum,当然浪费了大量的复杂度 return; } for (int i = 0; i <= m; ++ i) { dfs(u + 1, s + (1 << i), ((LL)v[i] * sum) % mod); } } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> k; for (int i = 0; i <= m; ++ i) cin >> v[i]; dfs(1, 0, 1); cout << ans << endl; } |
记忆化搜索或二维DP
状态表示:
- $f _ {u,s}$ 表示取 $u$ 个数且形成的数为 $s$
- 属性 每种方案的权值和
依据最后一个选择划分可得
$$
f _ {u, s} = \sum _ {i = 0} ^ {i \le m} {f _ {u - 1, s - 2 ^ i} \times v[i]}
$$
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include <iostream> #include <algorithm> #include <cstring> using namespace std; typedef long long LL; const LL mod = 998244353; const int N = 110; int v[N]; LL f[35][120005]; int n, m, k; int popcnt(int x) { int res = 0; while (x) { x -= x & -x; ++ res; } return res; } LL dfs(int u, int s) { // 这里不是标准的 dp 只是对第一种做法加记忆化 if (u > n) return popcnt(s) <= k; if (f[u][s] != -1) return f[u][s]; LL res = 0; for (int i = 0; i <= m; ++ i) { res = (res + dfs(u + 1, s + (1 << i)) * v[i] % mod) % mod; } return f[u][s] = res; } int main() { cin.tie(0)->sync_with_stdio(0); memset(f, -1, sizeof f); cin >> n >> m >> k; for (int i = 0; i <= m; ++ i) cin >> v[i]; cout << dfs(n, 0) << endl; } |
四维DP
状态表示
- $f_{i,j,k,p}$ 表示确定了 $S$ 的前 $i-1$ 位，确定了 $a$ 数组中 $j$ 个元素，且 $S$ 的前 $i-1$ 位一共有 $k$ 个 $1$ ，向 $i$ 位进位为 $p$
- 属性 每种方案的权值和
- 因为进位是从低到高所以从低位到高位枚举满足 $dp$ 的无后效性
考虑用 $f_{i,j,k,p}$ 转移
- 设选 $t$ 个 $v[i]$，$t\in [0, n-j]$，相当于对于 $S$ 的第 $i$ 位上贡献了 $t$ 个 $1$
- 则转移为 $f_{i+1,j+t,k+(t+p\&1), t+p>>1}$，第 $i$ 位即为 $t+p\&1$，向 $i+1$ 进位即为 $t+p>>1$
- 贡献为 $f_{i,j,k,p} \times v^t[i]\times C_{n-j}^{t}$，即在 $n-j$ 个位置中任选 $t$ 个位置
复杂度 $O(n^3mk)$
起点
$$
f_{0,0,0,0}=1
$$
目标
$$
res=\sum_{k\in[0,K],p\in[0,n>>1]}^{k+popcnt(p)\le K}{f[m+1][n][k][p]}
$$
- 准确的说 $f_{i,j,k,p}$ 表示的 $S=S_{0..i-1}+(p<<i-1)$，$S_{0..i-1}$ 表示 $S$ 的前 $i-1$ 位，即对应 $k$
- 如果要确定一个方案则 $i=m+1,j=n,\forall k\in[0,K],\forall p\in[0,n>>1]$
- 合法性则要满足 $popcnt(S)\le K$，即 $k+popcnt(p)\le K$
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> // 100pts #include <cstring> #include <algorithm> #define f(a, b, c, d) dp[a][b][c][d] using namespace std; typedef long long LL; const int mod = 998244353; const int N = 35, M = 105; int v[M][N], C[N][N]; int dp[M][N][N][N >> 1]; int n, m, K; int popcnt(int x) { int res = 0; while (x) { x -= x & -x; ++ res; } return res; } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m >> K; for (int i = 0; i <= m; ++ i) { cin >> v[i][1]; for (int j = 2; j <= n; ++ j) v[i][j] = (LL)v[i][j - 1] * v[i][1] % mod; v[i][0] = 1; } // 预处理出v_i^j for (int i = 0; i <= n; ++ i) // 预处理组合数 for (int j = 0; j <= i; ++ j) if (!j) C[i][j] = 1; else C[i][j] = ((LL)C[i - 1][j] + C[i - 1][j - 1]) % mod; f(0, 0, 0, 0) = 1; // 转移 for (int i = 0; i <= m; ++ i) for (int j = 0; j <= n; ++ j) for (int k = 0; k <= K; ++ k) for (int p = 0; p <= n >> 1; ++ p) for (int t = 0; t <= n - j; ++ t) { int &from = f(i, j, k, p), &to = f(i + 1, j + t, k + (t + p & 1), t + p >> 1); to = (to + (LL)from * v[i][t] % mod * C[n - j][t] % mod) % mod; } int ans = 0; for (int k = 0; k <= K; ++ k) for (int p = 0; p <= n >> 1; ++ p) if (k + popcnt(p) <= K) ans = ((LL)ans + f(m + 1, n, k, p)) % mod; cout << ans << endl; } |
T3 方差
这题没得说，我只会暴力
主要思路是：
- 题目中的操作就是交换差分
- 猜想差分数组是单峰时方差最小 (看了一圈题解，很少有能严谨证明的，大多都只是猜想, 我自己也证不出来)
- 考虑 dp
- 将差分数组排序
- 再考虑将每一个数放在首还是尾
正解
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
#include <iostream> #include <cstring> #include <algorithm> #include <vector> #define toMin(a, b) (a > b ? a = b: 0) #define toMax(a, b) (a < b ? a = b: 0) using namespace std; using LL = long long; /** * n^2D=n*\sum a^2 - {\sum a}^2 * 1. 交换差分 * 2. 当差分数组先减后增的时候最优 * * 每次差分考虑放在左边还是放在右边 * f(i, j)表示取前i个数和为j的最小平方和 * i+1的差分可以放在右边或者左边 * * 放在右边时 x=j+b[i+1] * 放在左边时 x=b[i+1] * * 右边转移时 + x^2 * 左边转移时 + x^2 + \sum for c in q {x^2+2*c*x} * => + x^2 + \len q * x^2 + 2*x*\sum q * => + x^2 + i*x^2 + 2*x*j * * 起点为 f[1, b[1]]=0 * 答案为 \min for (i, j):v in f {n * v - j^2} */ const int N = 1e4 + 10, M = N * 600; const LL INF = 0x3f3f3f3f3f3f3f3f; int a[N], b[N]; LL f[M]; int main() { cin.tie(0)->sync_with_stdio(0); int n, maxAval = -2e9; cin >> n; for (int i = 1; i <= n; ++ i) { cin >> a[i]; toMax(maxAval, a[i]); } f[0] = a[0] = 0; for (int i = 1; i < n; ++ i) { b[i] = a[i + 1] - a[i]; } sort(b + 1, b + n); memset(f, 0x3f, sizeof f); f[0] = a[0] = 0; int mx = 0; for (int i = 1; i < n; ++ i) { a[i] = a[i - 1] + b[i]; if (!b[i]) continue; for (int j = mx; j >= 0; -- j) { if (f[j] == INF) continue; // 当前数列中有i-1个数 // 差分放在左边 LL x = b[i]; toMin(f[j + x * i], f[j] + (LL)i * x * x + (LL)2 * j * x); toMax(mx, j + x * i); // 差分放在右边 x = a[i]; toMin(f[j + x], f[j] + (LL)x * x); toMax(mx, j + x); f[j] = INF; } } LL ans = INF; for (int j = mx; j >= 0; -- j) { if (f[j] == INF) continue; toMin(ans, (LL)n * f[j] - (LL)j * j); } cout << ans << '\n'; } |
参考了这篇题解
我尝试推过这个公式, 确实是对的, 推导也比较巧妙, 可以推推看, 但还是不能解释为什么是单峰的
BFS
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 |
#include <bits/stdc++.h> // 20pts using namespace std; #define to_min(x, y) (x > y ? x = y: 0) typedef long long LL; const int N = 10000 + 10; int n; struct var { int a[11]; inline void change(const int &x) { a[x] = a[x + 1] + a[x - 1] - a[x]; } inline int fc() const { int s = 0, res = 0; for (int i = 1; i <= n; ++ i) { s += a[i]; res += a[i] * a[i]; } return (LL)res * n - s * s; } inline bool operator< (const var &x) const { for (int i = 1; i <= n; ++ i) if (a[i] != x.a[i]) return a[i] < x.a[i]; return false; } inline void out() { for (int i = 1; i <= n; ++ i) cout << a[i] << ' '; cout << endl; } } a; int bfs(var &a) { map<var, bool> mp; queue<var> q; q.push(a); mp[a] = true; int res = a.fc(); while (q.size()) { // 唯一值得欣慰的是我想到了bfs, 至少还能拿个暴力分 var t = q.front(); q.pop(); for (int i = 2; i < n; ++ i) { var tmp = t; tmp.change(i); if (!mp[tmp]) { to_min(res, tmp.fc()); mp[tmp] = true; q.push(tmp); } } } return res; } int main() { // #define noi #ifdef noi freopen("variance.in", "r", stdin); freopen("variance.out", "w", stdout); #endif scanf("%d", &n); for (int i = 1; i <= n; ++ i) scanf("%d", &a.a[i]); printf("%d\n", bfs(a)); } |
模拟退火
模拟退火直接72pts了...... 还tm要什么自行车
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <bits/stdc++.h> // 72pts #define toMin(a, b) a > b ? a = b: 0 using namespace std; typedef long long LL; const int N = 1e4 + 10; int p[N], q[N]; int n; LL ans = __LONG_LONG_MAX__; LL calc() { p[1] = 0; for (int i = 1; i < n; ++ i) p[i + 1] = p[i] + q[i]; LL s = 0, res = 0; for (int i = 1; i <= n; ++ i) { s += p[i]; res += p[i] * p[i]; } res = res * n - s * s; toMin(ans, res); return res; } void SA() { int m = n - 1; random_shuffle(q + 1, q + 1 + m); for (double T = 1e4; T > 1e-4; T *= 0.99) { // 这个参数稳定72pts,其他参数比较看脸 int a = rand() % m + 1, b = rand() % m + 1; // 随机交换差分 LL x = calc(); swap(q[a], q[b]); LL dt = calc() - x; if (exp(-dt / T) < (double)rand() / RAND_MAX) swap(q[a], q[b]); // 如果当前情况更差则有概率跳过去 } } int main() { // #define noi #ifdef noi freopen("variance2.in", "r", stdin); freopen("variance.out", "w", stdout); #endif cin.tie(0)->sync_with_stdio(0); srand(time(0)); cin >> n; for (int i = 1; i <= n; ++ i) cin >> p[i]; for (int i = 1; i < n; ++ i) q[i] = p[i + 1] - p[i]; // 求差分 do SA(); while ((double)clock() / CLOCKS_PER_SEC < 0.9); cout << ans; } |
考虑到单峰性质，可以先随机构造一个单峰的差分数组再退火，可以拿到84pts这个退火算法当真有些意思
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <bits/stdc++.h> // 稳定84,运气好可以多对一个点 #define toMin(a, b) a > b ? a = b: 0 using namespace std; typedef long long LL; const int N = 1e4 + 10; int p[N], q[N], t[N]; int n; LL ans = __LONG_LONG_MAX__; LL calc() { p[1] = 0; for (int i = 1; i < n; ++ i) p[i + 1] = p[i] + q[i]; LL s = 0, res = 0; for (int i = 1; i <= n; ++ i) { s += p[i]; res += p[i] * p[i]; } res = res * n - s * s; toMin(ans, res); return res; } void SA() { int m = n - 1; deque<int> dq; // 用dq构造单峰,开吸氧跑得飞快 for (int i = 1; i < n; ++ i) if (rand() & 1) dq.push_back(t[i]); else dq.push_front(t[i]); for (int i = 1; i < n; ++ i, dq.pop_front()) q[i] = dq.front(); for (double T = 1e4; T > 1e-4; T *= 0.99) { int a = rand() % m + 1, b = rand() % m + 1; LL x = calc(); swap(q[a], q[b]); LL dt = calc() - x; if (exp(-dt / T) < (double)rand() / RAND_MAX) swap(q[a], q[b]); } } int main() { // #define noi #ifdef noi freopen("variance3.in", "r", stdin); freopen("variance.out", "w", stdout); #endif cin.tie(0)->sync_with_stdio(0); srand(time(0)); cin >> n; for (int i = 1; i <= n; ++ i) cin >> p[i]; for (int i = 1; i < n; ++ i) t[i] = p[i + 1] - p[i]; // 求差分 sort(t + 1, t + n); do SA(); while ((double)clock() / CLOCKS_PER_SEC < 0.9); cout << ans; } |
T4 棋局
神仙题
考场里题面都搞不明白
总结
关于往事
当时真是 至暗时刻 (如果可以这么说的话)
文化课的成绩已经排到 200 名开外了, 化学简直稀烂 (没赋过 90+)
技术也不是很理想。照这样的趋势考个大学都费劲
NOIP 也没有发挥好 (前天晚上稍微晚了一点睡, 大概是 11:30, 进考场不知道为什么就是打不起精神...)
因为 T1 莫名其妙的失误搞崩后(其实有想到，但是。。。。总之最后写了一个 50pts)
T2, T4 都什么都没做出来
(旁边那个后进考场的老哥——这是所谓 NOIP “体验名额”——15分钟就敲好了第一题，还小声说了一句"就这"）
(再加上这个老哥敲键盘声音巨响，给我搞得人心惶惶)
T3在考场里自测大样例从 2.2s 调到 1.1s 调了快2h也没有到 1s-
又想到 lry 说 Linux 的 time 会把 cpu 跑满真实测试还会慢一点
当时还有 2h 但是整个人都傻了，去看 T1 有没有做法时已经被思维定势了怎么都想不出来
写 T2 发现写的暴力跑了 1.5s
再看 T4, 发现题目逆天, 可以拿暴力分但很已经几乎不可能了
总之出考场时掂量以下只有 50-60pts 的分数。。。。
当时真的是一句话都说不出来
然后就是不顺心的事情又来到
首先是我在动车上睡觉稍微睡的有多久，醒来就快到了，才想到之前跟家长说 9pm 到黄岩是多么离谱
于是 7pm 时只留我一人在寒冷的火车站等了好久。。。。
第二天我想应当及时止损，于是想早一点到校
结果那天没睡好，到学校又发现没带饭卡只好在学校旁边吃一点，又被我妈数落一翻
还漏看了一条 fc 的消息
再加上 2021scp-s2 前 fc 一句 Logic 你没有机会了 给我心态炸裂再加上 2021scp-s2 前在面馆里吃到蚊子
只能说非常的累，非常的累
该文 就是在这种情况下写出来的
那段时间是自修室全勤，导致白天精神也不是很好，经常在上课时睡着。。。
关于算法学习
其实当时也没掌握怎么学习算法 或许对于一个零基础开始学习七八个月算法的人来说要求太高？
大多数题目都只会模拟而不知正解，AcWing 上刷了那么多题其实大部分都是对着 y总 的板子抄
很少自己完全想明白，但这也有一部分环境因素的影响罢 虽然我觉得如果一切都归结于环境那么不就什么事都做不成了吗
不过至少有一点是可以肯定的——那就是对算法的热爱
如果让我扪心自问的话，那段时间我一定是全力以赴了
现在想来当时确实是有些幼稚——一个刚刚生长的小苗窥到了一片天地
沉淀了这么久，只觉得当时太过浮躁太过激动了
关于算法学习，灵神 的这期视频或许对你有所帮助
他的这个项目也非常不错
关于退役
其实在我打完 2021csp-s2 时我就想过退役了
就和 lry 一样我一开始也不是为了拿奖来的，只是因为喜欢而已
而当 NOIP 结束，在权衡利弊下，为最终还是放弃了 OI
- 2022NOIP 结束只剩1个多月准备首考
- 老师家长的催促
- 个人能力的不足等等
总之我还是非常感谢这段让我成长的时光的
关于自卑与成长
或许曾经的我很讨厌这些东西，因为他们会触及到我最脆弱的地方
当现在我多少想明白了一些关于自卑的东西
曾经的我或许不会承认，但现在的我不得不说我真的很自卑
在阅读了《被讨厌的勇气》一书后，我邂逅了阿德勒心理学——一门关于人如何获得幸福的心理学或者可以称之为哲学
书中说到自卑情结是每个人都存在的
因为人是少有的心灵成长快于肉体成长的动物
那么自然会产生想做而做不到的事情
自卑由此而来。
书中的学问关乎我的整个人生，而我只是稍作阅读并加以实践
我说不清楚这几年来我的成长，但总之是在前进的
大概这些事情还要我将来细细去想
最后
在暴风雨来临的前夜(无论是 2022 反常的气候，还是我波折的命运)，我于繁忙的学业中匆匆写下此文，或许有未能意尽之处，
或许有诸人不认可之处，或许只是胡言乱语，几乎连话都说不清。
至少我还是迈出了脚步，总不至于无路可走。
沉舟侧畔千帆过，病树前头万木春。就用这句话结束这篇博客，继续我的生活罢。
发表回复