本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-16 21:21:42

记录

A-E 速切，F 模拟了近一个小时遗憾缺了一点点，然后发现 G 过的人特别多，去写 G，到结束写的都是假做法。

题解

A - Welcome to AtCoder Land

string 判断即可，略过不表。

B - Ticket Counter

模拟，略过不表。

C - Popcorn

把每个摊位拥有的爆米花种类状压成一个二进制数，然后对 $n$ 个摊位枚举 $2^n$ 种选择，把所有选上的摊位的种类串或起来，如果等于 $2^m-1$ 就是合法的，取 popcount 最小的 $i$ 即可，时间复杂度 $O(2^n\times n)$

D - Souvenirs

先把 $A,B$ 分别升序排序，之后依次处理每个 $B_i$，用指针在 $A$ 上扫，每次找到第一个 $A_k\ge B_i$ 的 $A_k$ 分给 $B_i$ 即可。由于 $A,B$ 都不降，这样一定是最优的。

E - Alphabet Tiles

组合计数 dp。由于最终的串数要求本质不同，所以考虑把 $26$ 个不同字母依次插入串中，设 $f_{i,j}$ 为考虑前 $i$ 个字母时，长度为 $j$ 且本质不同的字符串数，有 $f_{0,0}=1$。

考虑转移，枚举 $k$ 为第 $i$ 个字母出现的次数即可，需要在 $j$ 个位置中选出 $k$ 个放 $i$，其余按顺序放入长度为 $j-k$ 的串，因此有 $f_{i,j}=\sum_{k=0}^{\min(j,C_i)}f_{i-1,j-k}\times \binom{j}{k}$，填表法即可，时间复杂度 $O(26k^2)$

F - Easiest Maze

很显然最短路径长度为 $n$，直接走下来即可。考虑在这条路上拓展，发现每次只能拓展 $2$ 格，因此 $k-n$ 必须为偶数才可能有解。拓展方法为每两行为一组同时向左扩展若干格，最后若多出一行（即 $n$ 为奇数时）可以从 $n-1$ 行向下两格两格扩展，所以最多扩展 $2\lfloor\frac{n(m-1)}{2}\rfloor$ 格，判断无解后模拟填写即可。

G - AtCoder Tour

发现最终的最优方案一定为走到某一格 $(x,y)$ 后一直停在这格直到结束，所以设 $f_{i,j,k}$ 表示走 $k$ 步到达 $(i,j)$ 的最大权值和，用 $f_{i,j,k}+A_{i,j}\times (K-k)$ 更新答案。由于走一个环一定不优于在环上某一点停留，所以 $k$ 取到 $HW$ 时一定已经包含最优解。时间复杂度 $H^2W^2$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-17 10:51:44

记录

AB 切，C 想很久以后吃一发切，D 想一小会后吃一发切，E 最后开始搞线段树，最后发现假了，其实不难。

题解

A. Alice and Books

显然不管怎么分，$A_n$ 一定会贡献到答案中，因此只需要从其余元素中找到最大的单独分一组即可，答案为 $A_n+\max_{i=1}^{n-1}A_i$

B. New Bakery

推式子，当取 $k$ 时，结果为 $(n-k)a+\sum_{i=b-k+1}^bi$，等差数列求和并合并同类项，整理为 ${res}=-\frac12k^2+(b-a +\frac12)k+an$，是 ${res}$ 关于 $k$ 的二次函数，当 $k=b-a+\frac12$ 时取到最大值。由于 $k$ 为整数，同时值域为 $[0,min(n,b)]$，取最接近对称轴的整数即可。

C. Manhattan Permutations

由于 $p$ 是一个排列，如果由 $i$ 向 $p_i$ 连边，每个点的出度和入度都为 $1$，得到的一定为若干个环。考虑构造使得每个环中只有一个 $i$ 满足 $p_i\le i$，因为如果有两个这样的 $i$，直接将其中一个拆出来答案不变，所以这样一定包含了所有方案。

考虑每个环对曼哈顿值的贡献，由于只有一个 $p_i\le i$ 的 $i$，所以整个环的贡献就是 $2(\max(i)-min(i))$，因此最终值也一定是偶数。所以这里把 $k$ 直接除掉了 $2$，只考虑一边的贡献。

之后考虑最大化曼哈顿值，发现将 $i$ 与 $n-i+1$ 两两组合，组成 $\lfloor\frac n2\rfloor$ 个二元环，最终值最大，等差数列求和得到最大值为 $(n+n\mod 2)\lfloor\frac n2\rfloor$，之后贪心地从大到小交换即可。

只有一种特殊情况是在 $n$ 为奇数时，有可能最后剩下 $k=1$ 而没有距离为 $1$ 的点对，这时暴力找到一个没有改变位置的 $i$，将其与 $i+1$ 交换即可，此时若 $i+1$ 未被交换则这两个点贡献 $1$，否则变成三元环，总贡献也会增加 $1$

D. Elections

可以把 $c$ 直接加给 $a_1$，显然跟原题意是等价的。之后求出 $a$ 中最靠前的最大值编号 $k$，显然 $k$ 的答案为 $0$。

考虑其他 $x$ 的答案。由于 $a_x$ 本身已经不是最大值，并且即使是去掉目前最大的 $a_k$，这一部分也会加到编号最小的 $a_i$ 上，最大值一定不降。所以至少要将 $x$ 之前的 $x-1$ 个人全部去掉，才能使 $x$ 为编号最小，$a_x$ 增加以变为最大。

所以维护 $a$ 的前缀和 $s$，若 $s_x\ge a_k$，只需要把前面全去掉即可，答案为 $x-1$。否则需要把前面全去掉，并且把 $x$ 后面的最大值 $a_k$ 也去掉，答案为 $x$。

E. Computing Machine

考虑一个区间的最优操作方案，发现先用 $s$ 中的 $0$ 把 $t$ 中所有能变 $1$ 的变完，再把 $s$ 中所有能变 $1$ 的变完，这样一定是最优的，因为这样保证了第一步之后 $t$ 中的 $1$ 最多，从而最终 $s$ 中的 $1$ 也最多。

接着考虑每一位会怎样被改变。若 $s_i$ 被变为 $1$，需要 $t_{i-1}=1$ 且 $t_{i+1}=1$，$t$ 的这两位又会受到 $s_{i-2},s_i,s_{i+2}$ 的影响，所以对于每一位 $s_i$，都只会受到 $[i-2,i+2]$ 区间内的影响。

因此可以提前对整个区间进行操作，并对最终的 $s$ 求前缀和。询问长度不超过 $4$ 时直接暴力操作求解。超过 $4$ 时由于 $[l+2,r-2]$ 只受区间 $[l,r]$ 内的影响，答案不变，直接记录下原来的答案，再单独对 $[l,l+4]$ 操作并记录前两位的答案，对 $[r-4,r]$ 操作并记录后两位的答案，把三部分相加即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-17 11:42:31

题意

给出 $n$ 个人的票数 $a_i$，同时有 $c$ 票暂时没有固定对象。可以让若干人不参加，这些人原有的票数以及 $c$ 票都会投给参加者中编号最小的那个，最终赢家是票数最多的人中编号最小的。对于每个 $x\in[1,n]$，求出让 $i$ 成为最终赢家最少需要让多少人不参加。

思路

可以把 $c$ 直接加给 $a_1$，显然跟原题意是等价的。之后求出 $a$ 中最靠前的最大值编号 $k$，显然 $k$ 的答案为 $0$。

考虑其他 $x$ 的答案。由于 $a_x$ 本身已经不是最大值，并且即使是去掉目前最大的 $a_k$，这一部分也会加到编号最小的 $a_i$ 上，最大值一定不降。所以至少要将 $x$ 之前的 $x-1$ 个人全部去掉，才能使 $x$ 为编号最小，$a_x$ 增加以变为最大。

所以维护 $a$ 的前缀和 $s$，若 $s_x\ge a_k$，只需要把前面全去掉即可，答案为 $x-1$。否则需要把前面全去掉，并且把 $x$ 后面的最大值 $a_k$ 也去掉，答案为 $x$。

代码

#include<iostream>
#define int long long 
using namespace std;
const int N=2e5+10;
int n,c,mx,a[N],s[N];
void sol()
{
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>a[i];
	a[1]+=c,mx=1;
	for(int i=1;i<=n;i++)
	{
		s[i]=s[i-1]+a[i]; 
		if(a[mx]<a[i]) mx=i;
	}
	for(int i=1;i<=n;i++) cout<<(i==mx?0:(s[i]>=a[mx]?i-1:i))<<' ';
	cout<<'\n';
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T; cin>>T;
	while(T--) sol();
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-17 14:00:54

题意

给定 $s,t$ 两个 $01$ 串，有以下两种操作：

• 若 $s_i=0$ 且 $s_{i+2}=0$，可将 $t_{i+1}$ 赋为 $1$。
• 若 $t_i=1$ 且 $t_{i+2}=1$，可将 $s_{i+1}$ 赋为 $1$。

求经过若干次操作后 $s$ 中 $1$ 的最大个数。

思路

考虑一个区间的最优操作方案，发现先用 $s$ 中的 $0$ 把 $t$ 中所有能变 $1$ 的变完，再把 $s$ 中所有能变 $1$ 的变完，这样一定是最优的，因为这样保证了第一步之后 $t$ 中的 $1$ 最多，从而最终 $s$ 中的 $1$ 也最多。

接着考虑每一位会怎样被改变。若 $s_i$ 被变为 $1$，需要 $t_{i-1}=1$ 且 $t_{i+1}=1$，$t$ 的这两位又会受到 $s_{i-2},s_i,s_{i+2}$ 的影响，所以对于每一位 $s_i$，都只会受到 $[i-2,i+2]$ 区间内的影响。

因此可以提前对整个区间进行操作，并对最终的 $s$ 求前缀和。询问长度不超过 $4$ 时直接暴力操作求解。超过 $4$ 时由于 $[l+2,r-2]$ 只受区间 $[l,r]$ 内的影响，答案不变，直接记录下原来的答案，再单独对 $[l,l+4]$ 操作并记录前两位的答案，对 $[r-4,r]$ 操作并记录后两位的答案，把三部分相加即可。

代码

#include<iostream>
using namespace std;
const int N=2e5+10;
int n,q,pre[N],s[N],t[N],ts[N],tt[N];
char ss[N],st[N]; 
void solv(int l,int r)
{
	int len=r-l+1;
	for(int i=l;i<=r;i++) ts[i-l+1]=s[i],tt[i-l+1]=t[i];
	for(int i=1;i+2<=len;i++) if(!ts[i]&&!ts[i+2]) tt[i+1]=1;
	for(int i=1;i+2<=len;i++) if(tt[i]&&tt[i+2]) ts[i+1]=1;
	for(int i=1;i<=len;i++) ts[i]+=ts[i-1];
}
void sol()
{
	cin>>n>>ss>>st>>q;
	for(int i=1;i<=n;i++) s[i]=ss[i-1]-'0',t[i]=st[i-1]-'0';
	solv(1,n);
	for(int i=1;i<=n;i++) pre[i]=ts[i];
	while(q--)
	{
		int l,r; cin>>l>>r;
		if(r-l<4) solv(l,r),cout<<ts[r-l+1]<<'\n';
		else
		{
			int res=pre[r-2]-pre[l+1];
			solv(l,l+4),res+=ts[2];
			solv(r-4,r),res+=(ts[5]-ts[3]);
			cout<<res<<'\n';
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T; cin>>T;
	while(T--) sol();
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-19 14:06:28

记录

A 模拟，C 是倍增/LCA/树上差分板子，之后回来看发现 B 是二分，全写了。D 贪心，用线段树优化，写完又调一共一个小时。

最后 A 过了，B 由于避开精度问题乘了分母导致需要开 __int128，但是在乘法上没有强转导致溢出，挂了 $30$；C 把 $i$ 手误敲成 $y$ 过样例所以爆零了；D 由于需要严格次大值，但写成了次大值挂了 $10$ 分。赛后杰哥讲了 E 感觉也能做。

题解

A. 训练士兵

枚举 $i\in[1,1e6]$ 表示每个人的第 $i$ 次训练，若第 $i$ 次不花费 $S$ 组团训练，而是分别单独训练，代价会变成 $\sum_{k=1}^n[c_k\ge i]p_k$，所以预处理 $t_i$ 表示 $\sum_{k=1}^n[c_k=i]p_i$。初始令 $now$ 为所有 $p_i$ 的和，每处理完第 $i$ 次就减去 $t_i$，直到 $now<S$ 时退出，此时的 $i-1$ 便为最终组团训练的次数，最终计算即可。

B. 成绩统计

先推式子，得到方差为 $\frac{1}{k}(\sum_{i=1}^k a_i^2-\frac{sum^2}{k})<T$，为了避免精度问题，左右同乘 $k^2$，得到 $k\sum_{i=1}^k a_i^2-sum^2<T\times k^2$。

然后发现这个问题有单调性，即若前 $i$ 个数可以满足题意，则前 $i+1$ 个数一定可以满足，因为一定可以按照前 $i$ 个数的方法选。同时为了使方差尽可能小，所选的一定是排好序后连续的 $k$ 个数。所以考虑进行二分答案。

check 时把前 $x$ 个数拿出来排序，然后预处理前缀和和前缀平方和，找到最小的区间与 $T\times k^2$ 比较即可。要注意如果为了避免精度问题这样做，最大数会到 ${10}^{20}$，开个 __int128 就行，注意乘的时候强转类型即可。

C. 零食采购

考虑树上差分，设 $f_{i,u}$ 表示从根到 $u$ 的路径上 $c_k=i$ 的 $k$ 的个数。分别对 $i\in[1,20]$ 树上差分求出路径上是否有 $i$ 即可。

D. 封印宝石

显然贪心，即从第一个盒子起都尽可能让魔力值大，在此前提下再尽可能减少体力消耗。所以从 $1$ 到 $n$ 依次填，每次从 $[i,\min(i+k,n)]$ 中取能取且最靠前的最大值，并将对应值赋为 $-1$ 表示已经用过即可。由于不能有魔力值相同的相临盒子，所以需要求出最大值和严格次大值依次尝试，线段树维护即可。

E. 因数计数

值域小，为了方便表示设值域 $P={10}^5$。先开桶 $t_x$ 表示 $x$ 出现的次数。同时预处理出每个数编号不相等的因数个数 $s_x$ 和倍数个数 $b_x$，时间复杂度为调和级数 $O(P\ln P)$。

考虑先算出 $i\ne j$ 且 $a_i\mid a_j$ 的 $(i,j)$ 数量 $k$，枚举较小数 $m$，得 $m=\sum_{x=1}^{P}t_x\times b_x$。

有了以上问题的答案，平方一下就是 $a_i\mid a_k,a_j\mid a_l$ 且 $i\ne k,j\ne l$ 的 $(i,j,k,l)$ 组数，还需要容斥减去 $i=j,i=l,k=j,k=l$ 的组数。

首先先减去满足一个条件的：

• $i=j$，较小数相等，枚举这个数 $x$，取两个倍数，组数为 $\sum_{x=1}^P t_x\times b_x^2$。
• $k=l$，较大数相等，枚举这个数 $x$，取两个因数，组数为 $\sum_{x=1}^P t_x\times s_x^2$。
• $i=l$ 或 $j=k$，即一组中较大数与另一组中较小数相等。枚举相等的中间值 $x$，取一个因数和一个倍数，组数为 $\sum_{x=1}^P 2(t_x\times b_x\times s_x)$。

还需要加上满足两个条件的：

• $i=j$ 且 $k=l$，此时两个较小数和两个较大数分别相等，组数即为最初求出的 $(i,j)$ 数量 $m$。
• $i=l$ 且 $j=k$，由于倍数的要求限制了 $i\le k,j\le l$，所以此时 $i,j,k,l$ 均相等，枚举相等值 $x$，组数为 $\sum_{x=1}^Pt_x(t_x-1)$。
• 其他四种情况都会产生 $i=k$ 或 $j=l$，与已经确定的条件 $i\ne k,j\ne l$ 冲突，所以组数为 $0$。

之后满足三个或四个条件也会产生同样的冲突，组数均为 $0$，不用处理。

这样就做完了，但是由于 $n^4$ 达到了 ${10}^{20}$ 级别，开 __int128 才能确保通过。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-20 10:51:33

思路

（是 @Iceturky 的思路，在此拜谢）

值域小，为了方便表示设值域 $P={10}^5$。先开桶 $t_x$ 表示 $x$ 出现的次数。同时预处理出每个数编号不相等的因数个数 $s_x$ 和倍数个数 $b_x$，时间复杂度为调和级数 $O(P\ln P)$。

考虑先算出 $i\ne j$ 且 $a_i\mid a_j$ 的 $(i,j)$ 数量 $m$，枚举较小数 $x$，得 $m=\sum_{x=1}^{P}t_x\times b_x$。

有了以上问题的答案，平方一下就是 $a_i\mid a_k,a_j\mid a_l$ 且 $i\ne k,j\ne l$ 的 $(i,j,k,l)$ 组数，还需要容斥减去 $i=j,i=l,k=j,k=l$ 的组数。

首先先减去满足一个条件的：

• $i=j$，较小数相等，枚举这个数 $x$，取两个倍数，组数为 $\sum_{x=1}^P t_x\times b_x^2$。
• $k=l$，较大数相等，枚举这个数 $x$，取两个因数，组数为 $\sum_{x=1}^P t_x\times s_x^2$。
• $i=l$ 或 $j=k$，即一组中较大数与另一组中较小数相等。枚举相等的中间值 $x$，取一个因数和一个倍数，组数为 $\sum_{x=1}^P 2(t_x\times b_x\times s_x)$。

还需要加上满足两个条件的：

• $i=j$ 且 $k=l$，此时两个较小数和两个较大数分别相等，组数即为最初求出的 $(i,j)$ 数量 $m$。
• $i=l$ 且 $j=k$，由于倍数的要求限制了 $i\le k,j\le l$，所以此时 $i,j,k,l$ 均相等，枚举相等值 $x$，组数为 $\sum_{x=1}^Pt_x(t_x-1)$。
• 其他四种情况都会产生 $i=k$ 或 $j=l$，与已经确定的条件 $i\ne k,j\ne l$ 冲突，所以组数为 $0$。

之后满足三个或四个条件也会产生同样的冲突，组数均为 $0$，不用处理。

这样就做完了，但是由于 $n^4$ 达到了 ${10}^{20}$ 级别，开 __int128 才能确保通过。

代码

#include<iostream>
#define int __int128
using namespace std;
const int N=1e5+10;
const int P=1e5;
int read()
{
	int s=0,w=1;
	char ch; ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar();}
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
void print(int x)
{
	if(x>=10) print(x\/10);
	putchar(x%10+'0');
}
int n,ans,t[N],s[N],b[N];
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) t[read()]++;
	for(int i=1;i<=P;i++) if(t[i])
	{
		for(int j=i*2;j<=P;j+=i) if(t[j])
			b[i]+=t[j],s[j]+=t[i];
		b[i]+=t[i]-1,s[i]+=t[i]-1;
		ans+=t[i]*b[i];
	}
	ans*=(ans+1); \/\/无限制和 i=k && j=l 
	for(int i=1;i<=P;i++) if(t[i])
	{
		ans-=t[i]*b[i]*b[i]; \/\/ i=j
		ans-=t[i]*s[i]*s[i]; \/\/ k=l
		ans-=2*t[i]*b[i]*s[i]; \/\/ i=l || j=k
		ans+=t[i]*(t[i]-1); \/\/ i=l && j=k 
	}
	print(ans);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-20 10:59:42

记录

BC 恶心题一共被卡一个小时，DEF 切得挺顺的，总体不难。

题解

B. s-palindrome

预处理出所有本身左右对称的字母，判断左右对应位置字母，要求是 pq 或 bd 或相同且自身对称，同时若长度为奇数，正中间的字母本身也需要自身对称。

C. Exponential notation

基本分讨，分别处理小数点左右两边，略过不表。

D. Swaps in Permutation

发现如果把 $u,v$ 可交换看作 $u,v$ 之间连了一条边，那么每个连通块内的元素都可以任意交换。用并查集维护连通性，在每个连通块中尽可能用大的 $p_i$ 填到小的 $i$ 中，这样字典序一定最大。

E. Xor-sequences

从朴素 dp 入手，设 $f_{i,j}$ 表示填了 $i$ 个数，第 $i$ 个数是 $a_j$ 的方案数，有转移 $f_{i,j}=\sum_{k=1}^n[{popcount(a_j\oplus a_i)}\mod 3=0]f_{i-1,k}$，发现系数一直不变，可以用矩阵优化，把系数填成转移矩阵，用矩阵快速幂加速即可，时间复杂度 $O(n^3\log k)$

F. Couple Cover

发现 $a_i$ 值域以及询问值域 $P$ 很小，所以先开桶 $t_i$，枚举倍数也能维护出 $[1,P]$ 内所有数会作为乘积多少次，时间复杂度 $O(P\log P)$。计算答案时考虑容斥，先把上面所说的次数预处理前缀和 $s_i$，用总方案数 $n(n-1)$ 减去询问的 $s_{k-1}$，也就是不到 $k$ 的方案数即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-21 21:59:36

原题单

剩余题单（包括课后题）

拜谢杨爹/bx/bx/bx

背包 DP

J - Cow Exhibition G

考虑把 $S,F$ 中的一种看作费用，另一种看作收益，把所有值加个常数变成非负，转化为 $01$ 背包求解，最后找到两种值都非负的最大值即可。

数位 DP

K - windy 数

用 dfs，由高位到低位填，参数为填到的位数 $x$，是否贴上界，是否有前导 $0$，上一位是 $last$，判断是否能填时要么有前导 $0$，要么跟上一位差的绝对值满足要求。加上没有前导 $0$ 且不贴上界时对于 $(x,last)$ 的解个数可以优化时间复杂度。

话说学长说更建议用递推写，感觉递推式子就是 $(x,last)$ 的数组，还没有了解过。

L - 01串 Stringsobits

求符合条件的第 $k$ 小数，考虑二分或倍增。这里二分一个数 $x$，求 $[0,x]$ 中符合条件的数个数 $s$，以 $s\ge k$ 来 check。求数的个数用数位 DP，参数里加入还能填的 $1$ 的个数即可，初始为 $(n,L,1)$。

N - Making Shapes

Too Hard. 大体是把每个向量选择的次数和各种和全都变成二进制进行数位 DP。

单调队列优化 DP

I - Mowing the Lawn G

不能安排连续超过 $K$ 只奶牛，考虑转化成找出若干只奶牛不安排，也就是选出的任意两只奶牛之间距离不能超过 $K+1$。设 $f_i$ 表示前 $i$ 只奶牛选出的最小效率和，则 $f_i=\min_{j=i-(k+1)}^{i-1}f_j+E_i$。

发现一定会用 $f_j$ 合法的最小值更新，所以若 $x<y$ 且 $f_x\ge f_y$，$x$ 一定永远不优于 $y$，用双端队列维护单调队列，每次从队首弹出过期元素，从队尾弹出不优的元素，保证队内的 $f_i$ 单调递减，每次用队首来转移即可。

M - PTA-Little Bird

设 $f_i$ 为跳到 $i$ 所需的最小代价，则 $f_i=\min_{j=i-k}^{i-1}f_j+[d_i\ge d_j]$，考虑用单调队列，需要判断两个点的优劣。发现 $f_x<f_y$ 时 $x$ 一定更优，若 $f_x=f_y$， 则 $d_x>d_y$ 时 $x$ 一定更优。因为每次的代价仅为 $1$，所以这样是对的。把 $(f_i,d_i,i)$ 放入单调队列，用队首更新即可。

树形 DP

E - Centroids

先找出重心，原重心一定合法。以重心 $g$ 为根计算每个点的子树大小。若 ${siz}_x=\frac n2$，可以直接把这颗子树拆下来，把剩余的 $\frac n2$ 接到指定的根上，保证会成为重心。所以 $x$ 子树内的点均合法。

对于其他点，断开自己子树显然是不合法的，那么只能断开 $g$ 其他子树中 $siz$ 最大的 $k$，且直接接到 $x$ 上。那么 $siz_x,siz_k$ 均小于 $\frac n2$，只要 $n-siz_x-siz_j\le\frac n2$ 即合法。预处理一下 $g$ 子树的前缀后缀 $siz$ 最大值，求子树 $m$ 时用前缀和后缀的最大值作为 $siz_k$ 即可。

G - 树上染色

考虑把贡献拆到边上，并在从子树合并到父节点时考虑进去。所以若子树 $v$ 中有 $j$ 个黑点，贡献的次数为 $S=j(k-j)+(siz_v-j)(n-siz_v-(k-j))$。合并入父节点时，转移为 $f_{u,i}=\min_{j=0}^{{siz}v} f{u,i-j}+f_{v,j}+Sw$。

注意外层 $i$ 逆序枚举以保证 $01$ 背包的性质，内层枚举顺序无所谓，但是一定要在开始时处理 $j=0$，也就是直接把这个子树中纯白的情况考虑进去了，否则在后面会直接加上 $Sw$ 导致算重。

C - 小 N 的独立集

考虑最朴素的算法，$2^n$ 枚举每个点的取值，然后直接 $O(n)$ 跑树上最大独立集，设 $f_{u,0/1}$ 表示 $u$ 不选/选时，$u$ 子树内的最大收益。接着考虑 DP 套 DP，把 $f$ 设入状态，设 $g_{u,v_0,v_1}$ 为以 $u$ 为根的子树中 $u$ 不选时最大值为 $v_0$，选时最大值为 $v_1$ 的方案数，更新时用 $g_{v,p,q}$ 更新 $g_{u,i+\max(p,q),j+p}=g_{u,i+\max(p,q),j+p}+g_{v,p,q}\times g_{u,i,j}$。

但是这样复杂度为 $O(n^4k^4)$，无法通过，考虑把后两维修改压一下，变成 $g_{u,v_0,v_1}$ 表示强制不选 $u$ 时最大为 $v_0$，不强制时最大为 $v_1$。可以发现 $v_1-v_0\le w_u\le k$，所以改为 $g_{u,v_0,d}$ 表示强制不选 $u$ 时最大为 $v_0$，不强制时最大为 $v_0+d$，转移时 $g_{u,i+p+q,\max(i+p+q,i+j+p)-(i+p+q)}$ 加上 $g_{u,i,j}\times g_{v,p,q}$，时间复杂度 $O(n^2k^4)$

H - 船往低处流

Too Hard. 好像是各种换根分讨，感觉很麻烦。

斜率优化

D - 序列分割

首先注意到确定分割位置后，无论分割顺序怎样，最终的结果相同，因为每个元素都会与所有与其所在部分不同的元素相乘。所以设 $f_{i,j}$ 表示考虑到前 $i$ 个元素，分了 $j$ 块的最大得分，有 $f_{i,j}=\max_{k=j-1}^{i-1}f_{k,j-1}+s_k(s_i-s_k)$，其中 $s$ 是 $a$ 的前缀和数组。

把 $j$ 维滚动掉，拆开这个式子，得到 $f_{i}=\max_{k=1}^{i-1}f_{k}+s_ks_i-s_k^2)$，即 $-s_is_k+f_i=f_k-s_k^2$，把 $-s_i$ 看作 $k$，$s_k$ 看作 $x$，$f_i$ 看作 $b$，$f_k-s_k^2$ 看作 $y$，就是 $kx+b=y$ 的形式。相当于拿着斜率为 $-s_i$ 的直线在第一象限扫，扫到最高的经过某一点 $(s_k,f_k-s_k^2)$ 时为最大截距 $f_i$。

所以按照 $(s_k,f_k-s_k^2)$ 维护一个上凸包，也就是斜率递减的折线。每次找到最后一条斜率大于目前 $-s_i$ 的线段，最优决策点即为这条线段后面的端点，可以二分。但是由于 $-s_i$ 递减，也就是所用直线的斜率递减，所以说决策点不会前移，用双端队列同时一直在队头弹出无用的点，每次的决策点就是队头了。

A - Yet Another Partiton Problem

Too Hard. 分治 + 斜率优化，还是太困难了。

决策单调性

F - Dispatch Money

Too Hard. 分治 + 决策单调性，还是太困难了。

其他 Trick

B - 经营与开发

发现每次相当于给答案加一个值 $x_i$ 并使后面的答案乘一个值 $y_i$，若 $type=1$，则 $x_i=a_iw,y_i=(1-0.01k)$，否则 $x_i=-b_iw,y_i=(1+0.01c)$，发现按顺序枚举会有后效性，考虑倒序处理，每次相当于乘上 $y_i$ 并加上 $x_i$，由于其他影响本处操作的操作在前面，所以后效性没了，求出最后答案乘上原始的 $w$ 即可。

O - 管道取珠

发现 $a_i^2$ 相当于操作两轮且序列相同的方案数，所以设 $f_{i,j,k}$ 表示两轮都操作了 $i$ 次，第一轮在上管取了 $j$ 个，第二轮在上管取了 $k$ 个，且操作序列相同的方案数。则转移有：

• $j>0,k>0,a_j=a_k$ 时，$f_{i,j,k}=f_{i,j,k}+f_{i-1,j-1,k-1}$。
• $j>0,a_j=b_{i-k}$ 时，$f_{i,j,k}=f_{i,j,k}+f_{i-1,j-1,k}$。
• $k>0,b_{i-j}=a_k$ 时，$f_{i,j,k}=f_{i,j,k}+f_{i-1,j,k-1}$。
• $b_{i-j}=b_{i-k}$ 时，$f_{i,j,k}=f_{i,j,k}+f_{i-1,j,k}$。

答案即为 $f_{n+m,n,n}$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-12 09:32:10

题意

给出 $n$ 个字符串，求这些字符串两两之间最长公共前缀长度的和。

思路

暴力地两两计算显然会超时，需要优化。

考虑按位求解。按照当前位之前的位全部一致的要求分组。因此在每一组中，若当前位某一字母有 $k$ 个且 $k>1$，则会产生 $\frac{k(k-1)}{2}$ 的贡献。

为了接着处理后面的位，要在处理时把还没处理完的字符串按照这一位的值分组，处理完这一位后再分组处理下一位。

如此，若设字符串总长度为 $S$，由于每一位只会被处理一次，时间复杂度为 $O(S)$。

具体看代码实现。

代码

#include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N=3e5+10;
int n,ans;
string s[N];
vector <int> st;\/\/初始的组，包含所有字符串 
void sol(vector <int> &sg,int pos)
{
	vector <int> ts[27];
	int c[27];
	for(int i=0;i<26;i++) c[i]=0;
	for(int k:sg)
	{
		int id=s[k][pos]-'a';
		c[id]++;
		if(s[k].size()>pos+1) ts[id].push_back(k);\/\/只有这一位相同，才可能继续在同一组 
	}\/\/处理这一组中的所有字符串 
	for(int i=0;i<26;i++) if(c[i]>1)
	{
		ans+=c[i]*(c[i]-1)\/2;\/\/处理贡献 
		if(ts[i].size()>1) sol(ts[i],pos+1);\/\/继续处理下一位 
	} 
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i],st.push_back(i); 
	sol(st,0);
	cout<<ans;
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-16 16:09:32

题意

有 $n$ 个城市，$m$ 个依次进行的活动，初始有无穷多的钱且位于城市 $1$。在 $T_i$ 城市参加第 $i$ 个活动可以获得 $P_i$ 的钱，而从 $i$ 城市移动到 $j$ 城市需要花费 $C\times\left|i-j\right|$ 的钱，求最多能净赚多少钱。

思路

考虑动态规划解决。

设 $f_i$ 为最终停在第 $i$ 个城市能赚的最大钱数，有初值 $f_1=0$。由于要取最大值，将所有 $i\neq 1$ 的 $f_i$ 赋为负无穷。

接着需要依次处理每个活动，每次有转移式 $f_{T_i}=\max(f_{T_i},P_i+\max\limits_{j=1}^{n}(f_j-C\times\left|T_i-j\right|))$，其中要保证 $f_j$ 不为负无穷，否则没有意义。

如果每次转移时暴力地遍历整个 $f$ 数组，时间复杂度为 $O(mn)$，必然超时，需要更快速地求出转移式的第二项。

考虑使用数据结构优化时间复杂度，发现如果能把第二项中含 $j$ 的部分看成整体，就能用线段树维护最大值来解决。

那么需要通过分讨拆掉绝对值，因此化简得：

• 当 $j\leq T_i$ 时，$f_j-C\times\left|T_i-j\right|=-C\times T_i+f_j+C\times j$。
• 当 $j\geq T_i$ 时，$f_j-C\times\left|T_i-j\right|=C\times T_i+f_j-C\times j$。

发现两个式子中含 $i$ 的部分在每次转移时都是定值，因此当含 $j$ 的部分最大时，整个式子也最大。

因此可以用线段树分别维护 $f_j+C\times j$ 和 $f_j-C\times j$ 的区间最大值，每次转移时分别求 $\left[ 1,T_i\right]$ 和 $\left[T_i,n\right]$ 的最大值，再进行更新。

形式化地，先求 $k=\max(-C\times T_i+\max\limits_{j=1}^{T_i}(f_j+C\times j),C\times T_i+\max\limits_{j=T_i}^{n}(f_j-C\times j))$，再更新$f_{T_i}=\max(f_{T_i},P_i+k)$。

时间复杂度为 $O(m \log n)$。

代码

#include<iostream>
#define int long long
using namespace std;
const int N=2e5+10;
const int inf=1e18;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-') w=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9') { s=s*10+ch-'0',ch=getchar();}
	return s*w;
}
int n,c,m,ans,ct=1,f[N];
struct nod
{
	int l,r,w[2];
}a[N*2];
void pushup(nod &u,nod lc,nod rc)
{
	u.w[0]=max(lc.w[0],rc.w[0]),u.w[1]=max(lc.w[1],rc.w[1]);
}
void build(int u,int l,int r)
{
	if(l==r)
	{
		if(l==1) a[u].w[0]=c,a[u].w[1]=-c;
		else a[u].w[0]=a[u].w[1]=-inf;
		return;
	}
	int mid=(l+r)\/2;
	a[u].l=++ct,build(ct,l,mid);
	a[u].r=++ct,build(ct,mid+1,r);
	pushup(a[u],a[a[u].l],a[a[u].r]);
}
void change(int u,int l,int r,int p)
{
	if(l==r)
	{
		a[u].w[0]=f[l]+l*c,a[u].w[1]=f[l]-l*c;
		return;
	}
	int mid=(l+r)\/2;
	if(p<=mid) change(a[u].l,l,mid,p);
	else change(a[u].r,mid+1,r,p);
	pushup(a[u],a[a[u].l],a[a[u].r]); 
}
nod query(int u,int l,int r,int ll,int rr)
{
	if(l>=ll&&r<=rr) return a[u];
	int mid=(l+r)\/2;
	if(rr<=mid) return query(a[u].l,l,mid,ll,rr);
	if(ll>mid) return query(a[u].r,mid+1,r,ll,rr);
	nod res;
	pushup(res,query(a[u].l,l,mid,ll,rr),query(a[u].r,mid+1,r,ll,rr));
	return res;
}
signed main()
{
	n=read(),c=read(),m=read();
	for(int i=2;i<=n;i++) f[i]=-inf;
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int x=read(),w=read();
		int ta=query(1,1,n,1,x).w[0],tb=query(1,1,n,x,n).w[1];
		if(ta!=-inf) ta-=x*c;
		if(tb!=-inf) tb+=x*c;
		int ts=w+max(ta,tb);
		if(ts>f[x]) f[x]=ts,change(1,1,n,x);
	}
	for(int i=1;i<=n;i++) ans=max(ans,f[i]);
	cout<<ans;
	return 0;
}