【20230801暑期提高特训营】摸底考试#1
T1-三值的排序
\(100pts\)
Solution
可以考虑预处理三个值的个数。
如果当前的值不在正确的位置，则在其应当在的位置范围内寻找是否有当前位置上应该放置的数字。
若有则直接交换，若没有则任选数字交换，并统计答案。
T2-日记
\(100pts\)
Solution
预处理筛出来 \(10^6\) 以内的所有的质数，对于这些质数做一个前缀和。
然后二分区间的一个端点，记录下长度为 \(k\) 的不超过 \(N\) 最大区间和即可。
T3-分蛋糕
没想到 \(DP\)， 爆搜 \(15pts\)。
Solution
区间 \(DP\) 套路题。先把环复制一份枚举断环的点。
\(f_{i,j}\) 表示区间 \(i\sim j\) 能获得的最大贡献。
小 \(Y\) 的选择一共两种，小 \(Z\) 的选择是唯一确定的，可以直接转移，复杂度 \(O(1)\)
T4-都市
又一个爆搜 \(30pts\)
Solution
先将读入的数字排序，最小值是 \(a_1+a_2\)，次小值是 \(a_1+a_3\)。然后枚举 \(a_2+a_3\) 的值，解方程可得 \(a_1, a_2, a_3\)。
在读入的数字中将 \(a_1+a_2, a_2+a_3, a_1+a_3\) 删除，则剩下的数字最小的一定是 \(a_1+a_4\) ，便可以解出当前情况下的 \(a_4\) ，以此类推。并用数据结构维护快速删数和回溯过程。
T5-街灯
前 \(30pts\) 暴力统计，另 \(30pts\) 全部对 \(p\) 取模后直接主席树（没打挂不错）。共 \(60pts\)。
Solution
考虑根号分治，假设能处理出 \(l\sim r\) 之间各个数字的个数。
当 \(p\leq 100\) 时可以提前预处理 \(O(1)\) 回答。
当 \(p>100\) 时暴力统计 \(v,p+v,2\times p+v,\cdots\) 的个数之和，这样的数最多 \(100\) 个。
处理区间数字个数可以通过莫队实现。
【20230802暑期提高特训营】摸底考试#2
T1-数学题
\(100pts\) （不过不用写判质数但是我写了）
Solution
从小到大枚举 \(N\) 的因数，枚举到的数一定是质数，第二个枚举到的数即为答案。
T2-子序列
\(100pts\) 折半搜索板子
Solution
折半搜索板子题，将 \(n\) 个数分两半分别爆搜，合并时使用二分等手段快速查询即可。
T3-模
\(100pts\) \(OJ\) 交题忘删 \(freopen\)
Solution
观察数据范围发现 \(m\leq 10\)，所以直接开 \(m\) 棵线段树暴力维护对应取模后的值，属于比较简单好写的线段树。
T4-组队
暴力判断冲突获得 \(30pts\)
Solution
考虑 \(DP\)，\(f[i][j]\) 表示的就是划分到 \(i\) ，当前改变过 \(j\) 个数能够划分出的最小段数。
枚举上次划分到 \(k\) ，则从 \(f[k][p]\) 转移到 \(f[i][j]\) ，且如果假定把 \([k+1, i]\) 作 为一个整段，在这段中需要改变的数为 \(num\) ，则有 \(p+num=j\) 。
考虑预处理上个划分点到 \(i\) 消耗了多少次修改，设 \(l[i][x]\) 表示最小的 \(p o s\) 使得 \([p o s, i]\) 作为一个整段时消耗了 \(x\) 次修改，则 \(f[i][j]=\min (f[i][j], f[l[i][x]][j-x]+1)\)。
在 \(l[i][j]\) 中，对于一个确定的 \(j\) ，当 \(i\) 增时， \(l[i][j]\) 必然单调不减，所以对于一个 \(j\) 能双指针求，预处理复杂度可接受 。
T5-玩树
看到数据范围知道一定不是高精，但奈何不会更高明的算法只能写高精，然后爆零。
Solution
引理:答案的路径中，最多有一个 \(2\)，除此之外全为 \(1\)。
如果有一个 \(2\) 则 \(n\) 为奇数且一定在路径中点，否则没有 \(2\)。
所以可以将大于 \(2\) 的点删去，每个连通块中，\(DP\) 算答案即可。
设 \(f[x][1/2]\) 表示 \(x\) 子树中乘积为 \(1/2\) 的链最大长度，则 \(f[x][j\times a[x]]=\max\{f[v][j]\}+1\) ，同时统计答案即可。
【20230807暑期提高特训营】NOIP训练赛#1
T1-奇怪的冰雹
没加特判 \(100->90pts\)
Solution
注意到最多有 \(4\) 个木桶，设 \(f[i][j][k][l]\) 为木桶完好程度为 \(i,j,k,l\) 时的概率，暴力转移即可。
T2-完美划分
把 \(DP\) 的所有信息都想全了，唯独不会“枚举”前一个断点。于是爆搜 \(20pts\)
Solution
预处理前缀和，设 \(f[i][j]\) 表示前 \(i\) 个数划分 \(j\) 段的最大答案。
枚举上一个划分点 \(l\)，则 \(f[i][j]=\max(f[i][j],f[l][j-1]+fabs(suma[i]-suma[l]-sumb[l]+sumb[i]))\)
T3-智能小球
一眼 \(DP\) 先写暴力，然后发现矩阵优化的形式，套上 \(100pts\)
Solution
首先使用 \(Floyd\) 算法计算每对点之间的最短路。
然后可以根据最短路的矩阵计算出任意两个点之间转移的概率，得到概率矩阵，使用矩阵快速幂优化。
T4-运输货物
T5-道路规划
写个特殊性质写挂了喜提 \(0pts\)
Solution
将 \([S, T]\) 这个区间上的最小生成树从中间䢃开。分为两种情况讨论。
- 1: 中间的边没有在最小生成树内, 这样左右两边都是一颗不包含这条边的生成树。
- 2: 中间的边在最小生成树内, 这样两边都是包含这条边的生成树。
这样一来可以用线段树来维护这个结构，用 \(Tree[x][i][j],\{i,j\}=0/1\) 分别表示区间 \(x\) 在左右两边的竖边被包含在内或不被包含在内的情况下的最小生成树权值。就可以支持修改边权了。
建议结合代码食用。
【20230808暑假提高特训营】NOIP训练赛#2
T1-探险
写 \(bfs\) 时间复杂度假了，得到 \(50pts\)。
Solution
在 \(bfs\) 过程中，假设当前位置是 \((x,y)\)，下一步能走到 \((x+1,y),(x+2,y),\cdots,(x+k,y)\)
如果发现 \(dis[x+i][y]\leq dis[x][y]\)，那么不必再将 \((x+i,y),(x+i+1,y),\cdots,(x+k,y)\) 放进 \(bfs\) 的队列中。
T2-合成
\(100pts\)
Solution
开个堆暴力模拟结束
T3-健身
完全想不到 \(DP\)，枚举全排列 \(40pts\)
Solution
考虑进行状态压缩 \(DP\),设 \(dp[s]\) 为已经确定的训练项目状态是 \(s\) 时的训练效果之和的最大值。
状态为 \(s\) 时，如果 \(i\) 项目在当前状态下是还没有被确定顺序的项目，那么将 \(i\) 项目安排在当前状态下已经确定顺序的 \(j\) 项目后面。
则有转移 \(f[s|(1<<i)]=\max(f[s|(1<<i)],f[s]+\sum_{j=0}^{n-1}(s\& (1<<j))\times a[j][i]\)，答案为 \(f[(1<<n)-1]\)
T4-顽皮的猴子
甚至不会打暴力，满脑子只有树剖，然后挂了 \(0\)。
Solution
直接树上权值主席树，求 \(LCA\) 差分即可。
T5-咕咕咕
大力 \(dfs\) 有 \(10pts\)
Solution
考虑 \(dp\)，套路是定义 \(f_i\) 表示使 \(1\sim i\) 覆盖，且没有线段右端点比 \(i\) 大时的权值，对每条线段考虑，在 \(i=r\) 的时候，选这条线段需要让转移点 \(j\) 在 \((l-1)\sim i\) 之间才能满足覆盖。
但是不能直接相加，因为排序后对于当前的线段，有可能原来无法构成连续段的方案会被当前线段补上，故在转移时可以乘上一些线段的权值，即 \(f_i=\sum_{j=l-1}^i f_j\times w_{j+2,i}\ \ \ \ w_{i, j}=\prod_{k=1}^m [i \leq l_k] [r_k \leq j] (v_k+1)\)。
其中 \((v_k+1)\) 表示每条线段选或不选。\(w\) 从 \(j+2\) 开始是因为必须要留出至少一个位置才能乘 \(w\) ，否则这种方案会在前面被统计，再乘就会算重。
【20230819暑假提高特训营】NOIP训练赛#3
T1-幸运数字Ⅱ
\(100pts\)
Solution
预处理出所有幸运数字做前缀和即可。
T2-小树精灵
暴力求 \(LCA\) 统计答案得 \(50pts\)