2021.4 做题记录
目录
- P5596 【XR-4】题
- P6624 [省选联考 2020 A 卷] 作业题
- CF1197D Yet Another Subarray Problem
- P4124 [CQOI2016]手机号码
- P2051 [AHOI2009]中国象棋
- P3750 [六省联考2017]分手是祝愿
- P4284 [SHOI2014]概率充电器
- P1772 [ZJOI2006]物流运输
- P2604 [ZJOI2010]网络扩容
- P3731 [HAOI2017]新型城市化
- P3749 [六省联考2017]寿司餐厅
- P6136 【模板】普通平衡树（数据加强版）
- P3572 [POI2014]PTA-Little Bird
- P3195 [HNOI2008]玩具装箱
P5596 【XR-4】题 | 数学
题意
求满足 \(y^2-x^2=ax+b\) 的非负整数对 \((x,y)\) 的个数。
题解
\(y^2-x^2=ax+b\)
\(y^2=(x+\dfrac{a}{2})^2+b-\dfrac{a^2}{4}\)
两边乘 \(4\) 得 \(4y^2=(2x+a)^2+4b-a^2\)
\(4y^2-4b+a^2=(2x+a)^2\)
于是 \(4y^2-4b+a^2\) 必须为完全平方数。
令 \(z^2=4y^2-4b+a^2=(2x+a)^2\)，那么 \((z+2y)(z-2y)=a^2-4b\)。
于是我们需要找到 \(a^2-4b\) 的所有因子。
设 \(|a^2-4b|=p\times q\)，\(p,q \in \mathbb{N^+}\land p
则 \(\begin{cases}z-2y=p \\ z+2y=q\end{cases}\)。解得 \(\begin{cases} z=\dfrac{p+q}{2} \\ y=\dfrac{q-p}{4} \end{cases}\)。
因为 \(z=2x+a\) 所以 \(x=\dfrac{z-a}{2}=\dfrac{p+q-2a}{4}\)。
因为 \(x,y\ge 0\) 所以 \(\begin{cases} 4 \mid q-p \\ 4 \mid p+q-2a \\ p+q\ge 2a \end{cases}\)。
然后对于 \(a^2-4b<0\) 的情况要令 \(p\gets -p\)。
P6624 [省选联考 2020 A 卷] 作业题
这个 \(\gcd\) 看起来比较奇怪，先来一波欧拉反演 \(\varphi*1=\text{Id}\)。
记 \(V=\max\{ w_i\}\)。
\[\begin{aligned}&\sum\limits_{T}\left(\sum\limits_{i=1}^{n-1} w_{e_i}\right)\gcd(w_{e_1},\dots,w_{e_{n-1}}) \\&= \sum\limits_T \left(\sum\limits_{d|w_{e_1}\land \dots \land d|w_{e_{n-1}}} \varphi(d)\right)\left( \sum\limits_{i=1}^{n-1} w_{e_i}\right) \\&= \sum\limits_{d=1}^V \varphi(d) \sum\limits_{d|w_1\land \dots\land d|w_{n-1}} \sum w_i \end{aligned} \]枚举 \(d\)，后面那部分就是经典的“计算一张图的生成树边权之和”问题了。
在矩阵中记录 \(w_ix+1\) 这样的二项式即可。注意是模 \(x^2\) 意义下的。
然后消元的时候要注意判 \(0\) 的情况，要不然过不了 UOJ Hack。
但这样复杂度比较高。可以发现当满足 \(d|w_i\) 的边数 \(
CF1197D Yet Another Subarray Problem
仿照最大子段和的做法，设 \(f_i\) 为以 \(i\) 为结尾的、且长度是 \(m\) 的倍数的最大权值。
更新答案时，枚举位置以及零散长度即可。
P4124 [CQOI2016]手机号码
设 \(f_{i,lim,a,b,pre,four,eight}\) 为后 \(i\) 位、\(lim\) 表示是否卡边界、\(a,b\) 表示第 \(i+2,i+1\) 位、\(pre\) 表示前面是否有三个连续数字的合法电话号码个数。
转移显然。
一开始搞了个特别复杂的状态，直接把我整晕了。
P2051 [AHOI2009]中国象棋
这题放在我的任务计划里放了整整一年。。。
首先，可以观察到，一种状态是合法的当且仅当每行每列的炮数都 \(\le2\)。于是设 \(f_{i,j,k}\) 为前 \(i\) 行，有 \(j\) 列没炮，有 \(k\) 列一个炮的方案数。转移分类讨论即可。
如果不讨论边界条件，可以写个函数判断。
int _F(int i,int j,int k){
if(j<0||k<0||j+k>m) return 0;
return f[i][j][k];
}
P3750 [六省联考2017]分手是祝愿
神仙题。
首先，我们可以发现，操作每一个灯的效果都不能被其他灯替换。所以，需要按的灯的序列是唯一的，且按灯的顺序不影响。
从大到小按下亮着的灯，模拟一下，即可求出 \(N\)，表示一定要按的灯的个数。
考虑 dp，设 \(f_i\) 为从 \(i\) 个需要按的灯到 \((i-1)\) 个需要按的灯，期望的操作次数。
于是 \(f_i=\dfrac{i}{n}+\dfrac{n-i}{n}(f_{i+1}+f_i+1)\)。倒着递推即可。
P4284 [SHOI2014]概率充电器
首先有一个简单的想法：设 \(f_u\) 为点 \(u\) 亮的概率，那么 \(f_u=1-(1-q_u)\sum\limits_{(u,v)\in E} (1-p_{u,v}f_v)\)。
但这样点之间会互相影响，只能 \(O(n^3)\) 地高斯消元。
但是，我们可以发现，将这棵无根树看作以点 \(1\) 为根的有根树，假如采用 dfs 序来更新 \(f\)，即，忽略父亲对儿子的影响，因为点 \(1\) 没有父亲，所以 \(f_1\) 是正确的。
所以，可以用换根 dp 来处理。
第二遍 dfs，设 \(g_u\) 为点 \(u\) 亮的概率，那么 \(g_u\) 可以利用 \(g_{fa_u}\) 得出。
妙啊。
P1772 [ZJOI2006]物流运输
考虑对时间区间 dp：设 \(f_{i,j}\) 为 \([i,j]\) 天内的最小成本，那么 \(f_{i,j}=\min\limits_x \{ f_{i,x}+k+f_{x+1,j}\}\)。还有在 \([i,j]\) 天内不换航线的方案，枚举出不能经过的点，然后跑朴素 Dijkstra 即可。
P2604 [ZJOI2010]网络扩容
第一问略。
第二问：设第一问答案为 \(F\)，那么这一问就是要让流量恰好等于 \(F+k\)。
考虑在原图上的每个边 \((u,v,w,0)\)，新建一条 \((u,v,\inf,c)\) 的边，其中 \(c\) 表示题目给定的扩容费用。
为了限制最大流，建立一个虚拟原点 \(S\)，连边 \((S,1,F+k,0)\)。
P3731 [HAOI2017]新型城市化
原图恰好能被分为两个城市群 \(\iff\) 原图是二分图。
城市群 \(\iff\) 独立集。
最大城市群大小至少 \(+1\) \(\iff\) 最大独立集大小至少 \(+1\) \(\iff\) 二分图最大匹配至少 \(-1\) \(\iff\) 求哪些边是二分图最大匹配的必须边。
二分图最大匹配的必须边：边 \((u,v)\) 是必须边的充要条件是它在残量网络上流量为 \(1\)，且在残量网络上 \(u,v\) 不属于同一个强连通分量。
可行边：边 \((u,v)\) 是可行边的充要条件是它在残量网络上流量为 \(1\)，或在残量网络上 \(u,v\) 属于同一个强连通分量。
P3749 [六省联考2017]寿司餐厅
最大权闭合子图
一个有向图 \(G=(V,E)\) 的闭合子图 \(G'=(V',E')\) 满足 \(V'\subset V,E'\subset E\) 且 \(\forall (u,v)\in E',u,v\in V'\)。
每个点都有点权。
求解最大权闭合子图：对于原图中一个权值 \(\ge 0\) 的点 \(i\)，连边 \((S,i,v_i)\)，并让 \(\text{ans}\gets \text{ans}+v_i\)；\(<0\) 的点 \(i\) 连边 \((i,T,-v_i)\)。原图中的边 \(e=(u,v)\) 连边 \((u,v,\inf)\)。
跑一个最大流，令 \(\text{ans}\gets \text{ans}-\text{MaxFlow}\)。
输出方案
跑完最大流，在残量网络中从 \(S\) 能到达的所有点就构成了一个点数最少的方案。
本题
最大权闭合子图主要用来求解有点权和依赖关系的问题：原图中 \(x\to y\) 的边表示若选择 \(x\) 那么一定要选择 \(y\)。
对于本题，对每个食物的区间以及食物的种类搞个点即可。
int num[V],tot;
int Num(int x){
return num[x]?num[x]:(num[x]=++tot);
}
int num2[N][N];
int Num(int l,int r){
return num2[l][r]?num2[l][r]:(num2[l][r]=++tot);
}
ll sum=0;
void Add(int u,ll w){
if(w<0) AddEdge(u,T,-w);
else if(w>0) AddEdge(S,u,w),sum+=w;
}
......
For(i,0,mx){
Add(Num(i),-1LL*m*i*i);
}
For(i,1,n){
Add(Num(i,i),d[i][i]-a[i]);
AddEdge(Num(i,i),Num(a[i]),Inf);
}
For(len,2,n){
for(int i=1,j=i+len-1;j<=n;++i,++j){
Add(Num(i,j),d[i][j]);
AddEdge(Num(i,j),Num(i+1,j),Inf);
AddEdge(Num(i,j),Num(i,j-1),Inf);
}
}
......
sum-=maxFlow;
P6136 【模板】普通平衡树（数据加强版）
以前已经做过这题了，这里重点讲一下线性建无旋 Treap 的方法。虽然这题排序是必不可少的，所以还是 \(O(n \log n)\)，但对于一些维护数列的题，它的 Treap 按 size 分裂，所以不需要排序，可以做到严格线性。
每次选区间的中点，然后递归到左儿子和右儿子即可。
P3572 [POI2014]PTA-Little Bird
单调队列优化 dp。
设 \(f_i\) 为 \(1\to i\) 的最小花费，\(i,j\) 为两个点且 \(i
考虑什么时候点 \(i\) 是完全无用的：
- 当 \(f_i>f_j\)；
- 当 \(f_i=f_j\land h_i\le h_j\)。
于是整个单调队列记一下即可。
P3195 [HNOI2008]玩具装箱
设 \(f_i\) 为前 \(i\) 个玩具的最小花费，那么 \(f_i=\min\{f_j+(j-i-1-L+\sum\limits_{k=j+1}^i C_k)^2 \}\)。
记一下前缀和，设 \(S_i=\sum\limits_{j=1}^i C_j\)。
整理式子得 \(f_i=\min\{f_j+(S_j+j)^2-2(S_j+j)(S_i+i-1-L) \}+(S_i+i-1-L)^2\)。
可以发现，\(\min\) 中的项变成了一项仅与 \(j\) 相关的和一项 \(i,j\) 相关的乘积。
我们考虑两个决策 \(j,k\) 满足 \(j
\(\begin{aligned} f_j+(S_j+j)^2-2(S_j+j)(S_i+i-1-L)&
因为 \(S\) 单调不降，所以 \(S_j+j
\(\begin{aligned}\dfrac{f_j+(S_j+j)^2-f_k-(S_k+k)^2}{S_j+j-S_k-k} &> 2(S_i+i-1-L)\end{aligned}\)
这样，我们将式子化成了左边仅与 \(j,k\) 相关，右边仅与 \(i\) 相关。
因为 \(S_i+i-1-L\) 单调递增，所以当决策 \(j\) 不优于 \(k\) 时，在以后的 \(i\) 中 \(j\) 一定也不优。
令 \(\text{Slope}(j,k)=\dfrac{f_j+(S_j+j)^2-f_k-(S_k+k)^2}{S_j+j-S_k-k}\)。
然后，我们考虑，当有三个决策 \(i,j,k\) 时，如果 \(\text{Slope}(i,j)>\text{Slope}(j,k)\) 那么 \(j\) 一定不比 \(i,k\) 优。
证明比较显然。
于是我们需要维护一个单调队列，用来储存斜率单调不降的一些直线。
当需要判断一个新决策 \(i\) 时，我们先将队首那些斜率小于等于 \(2(S_i+i-1-L)\) 的决策扔掉，并更新答案，然后再将队尾那些斜率不单调不降的决策扔掉。