本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-04-28 16:47:19

更好的阅读体验

在这个直角三角形中，我们设以 $c$ 为底的大三角形面积为 $S_c$，以 $a,b$ 为底的两个小三角形的面积分别为 $S_a,S_b$。

显然，$S_c=\frac{ch}{2}=c^2\cdot\frac{h}{2c}$。我们设 $\frac{h}{2c}=m$，则有 $S_c=mc^2$。

同理，$S_a=a^2\cdot\frac{h_a}{2a}$（其中 $h_a$ 表示三角形 $BPC$ 中以 $a$ 为底的高）。显然该三角形与大三角形 $ABC$ 相似，所以 $\frac{h_a}{2a}=\frac{h}{2c}=m$，所以 $S_a=ma^2$。同理 $S_b=mb^2$。

又因为，$S_c=S_a+S_b$，所以 $mc^2=ma^2+mb^2$，即 $c^2=a^2+b^2$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-07 11:44:16

前言

时隔两年，这个极为经典的题目终于被我 AC 了。经过诸多优化改良，最终得到了这个个人认为比较优美的做法，写篇题解纪念一下，也供参考。

首先，建议读者先对照无注释代码自行理解一下大致过程。

无注释代码

#include<bits\/stdc++.h>
using namespace std;
#define int long long
const int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
const int _1=365,_100=_1*100+24,_400=_100*4+1;
struct date{int y,m,d,ru;} t[4000010];
bool isrun(int year) {
	if(year<0) return (year+1)%4==0;
	return year%4==0&&(year<=1582||year%100!=0||year%400==0);
}
date nxtday(date a) {
	a.d++,a.ru++;
	if(a.y==1582&&a.m==10&&a.d==5) return a.d=15,a;
	if(a.m==2&&a.d==29&&isrun(a.y));
	else if(a.d>mon[a.m]) a.m++,a.d=1;
	if(a.m>12) a.y++,a.y+=!a.y,a.m=1;
	return a;
}
void print(date x) {
	cout<<x.d<<" "<<x.m<<" "<<abs(x.y)<<(x.y<0?" BC":"")<<endl;
}
signed main() {
	t[0]={-4713,1,1,0};
	int _20000101;
	for(int i=1;t[i-1].y<=2000;i++) {
		t[i]=nxtday(t[i-1]);
		if(t[i].y==2000&&t[i].m==1&&t[i].d==1)
			_20000101=t[i].ru;
	}
	int _0=_20000101-_400*5,T,x;
	cin>>T;
	while(T--) {
		cin>>x;
		if(x<=_20000101) print(t[x]);
		else {
			date ans{(x-_0)\/_400*400,1,1,(x-_0)\/_400*_400+_0};
			while(ans.ru+_100+isrun(ans.y)<=x)
				ans.ru+=_100+isrun(ans.y),ans.y+=100;
			while(ans.ru+_1+isrun(ans.y)<=x)
				ans.ru+=_1+isrun(ans.y),ans.y++;
			while(ans.ru<x) ans=nxtday(ans);
			print(ans);
		}
	}
	return 0;
}

解析

大体思路是这样的：$1582$ 年之前的暴力 nxtday 跑出来，而 $1582$ 年之后的想办法逐渐逼近计算。

这里我们暴力跑到了 $2000$ 年（以下讲解只考虑 $2000$ 年以后），并保存了 _20000101 这个常数，表示 $2000$ 年 $1$ 月 $1$ 日的儒略日。原因之一是避免考虑边界情况，而原因之二，就是本做法的灵魂所在：

重点在于 _20000101 这个常数。将这个常数减去五个 $400$ 年（代码中的 _400），就可以反推出“理想状态下”公元 $0$ 年 $1$ 月 $1$ 日的儒略日 _0。这样，我们就可以 $O(1)$ 计算出所求儒略日位于哪一个“$400$ 年周期”中，并得到该周期的第一天的确切 date：

• year=(x-_0)\/_400*400
• ru=(x-_0)\/_400*_400+_0

这两行为本 trick 的精华，建议仔细理解（见程序第 36 行）

求出了本周期第一天的儒略日，接下来就是简单的逼近答案了：先尝试每次加上 $100$ 年（不超过 $4$ 次），再每次加上 $1$ 年（不超过 $100$ 次），最后暴力 nxtday 跑到答案（不超过 $365$ 次）。时间复杂度在可接受范围之内。

详细代码

#include<bits\/stdc++.h>
using namespace std;
#define int long long
const int mon[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
const int _1=365,_100=_1*100+24,_400=_100*4+1;
\/\/方便计算，预处理出格里高利历1年、100年和400年的天数
struct date{int y,m,d,ru;} t[4000010];
\/\/公元前的y为负数
bool isrun(int year) { \/\/闰年判断
	if(year<0) return (year+1)%4==0;
	return year%4==0&&(year<=1582||year%100!=0||year%400==0);
}
date nxtday(date a) { \/\/暴力计算下一天
	a.d++,a.ru++; \/\/天数和儒略日首先增加
	if(a.y==1582&&a.m==10&&a.d==5) return a.d=15,a;
	\/\/特判中间消失的10天
	if(a.m==2&&a.d==29&&isrun(a.y)); \/\/闰年的2月29无需进位
	else if(a.d>mon[a.m]) a.m++,a.d=1; \/\/由日向月进位
	if(a.m>12) a.y++,a.y+=!a.y,a.m=1; \/\/由月向年进位（特判了公元0年不存在）
	return a;
}
void print(date x) { \/\/输出
	cout<<x.d<<" "<<x.m<<" "<<abs(x.y)<<(x.y<0?" BC":"")<<endl;
}
signed main() {
	t[0]={-4713,1,1,0};
	int _20000101;
	for(int i=1;t[i-1].y<=2000;i++) { \/\/暴力打表到2000年
		t[i]=nxtday(t[i-1]);
		if(t[i].y==2000&&t[i].m==1&&t[i].d==1)
			_20000101=t[i].ru; \/\/保存常数2000.1.1儒略日
	}
	int _0=_20000101-_400*5,T,x; \/\/计算“理想状态”下0.1.1儒略日
	cin>>T;
	while(T--) {
		cin>>x;
		if(x<=_20000101) print(t[x]); \/\/直接查表
		else {
			date ans{(x-_0)\/_400*400,1,1,(x-_0)\/_400*_400+_0};
			\/\/计算400周期的第一天（格式为y,m,d,ru）
			while(ans.ru+_100+isrun(ans.y)<=x)
				ans.ru+=_100+isrun(ans.y),ans.y+=100;
			\/\/100年为步长逼近
			while(ans.ru+_1+isrun(ans.y)<=x)
				ans.ru+=_1+isrun(ans.y),ans.y++;
			\/\/1年为步长逼近
			while(ans.ru<x) ans=nxtday(ans);
			\/\/暴力nxtday得到答案
			print(ans);
		}
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-02 10:59:09

A. 假期计划

题意：有一个无向图，点有点权。定义两个节点“可达”当且仅当这两个节点的最短路不超过 $k+1$。求一组互不相同的节点 $\{a,b,c,d\}$ 使得 $1\leftrightarrow a\leftrightarrow b\leftrightarrow c\leftrightarrow d\leftrightarrow 1$ 每步均可达且这四个点的点权和尽可能大。$n\le 2500$。

首先跑 $n$ 遍 BFS，预处理出每两个点的距离。然后我们可以考虑枚举中间两个节点 $b,c$，处理边上两个节点 $a,d$。首先中间两个节点必须是可达的，否则跳过；然后需要满足 $1\leftrightarrow a\leftrightarrow b$，$c\leftrightarrow d\leftrightarrow 1$。由于“可达”是双向的，我们可以对每个节点 $x$ 预处理出所有满足 $1\leftrightarrow y\leftrightarrow x$ 的节点 $y$ 的集合并按 $y$ 的点权从大到小排序。于是容易想到，当我们枚举了 $b,c$ 时，只需要独立地考虑最大的 $v[a]$ 满足 $1\leftrightarrow a\leftrightarrow b$ 和最大的 $v[d]$ 满足 $1\leftrightarrow d\leftrightarrow c$ 即可。但事实并非如此。有可能对于最大的 $v[a]$，$a=c$，或对于最大的 $v[a],v[d]$，$a=d$，这些都会产生冲突（因为要求互不相同），于是可能需要跳过一些节点。容易证明对于 $b,c$ 只需要考虑前三大的即可，所以乘一个 $9$ 的常数暴力判断。

#include<bits\/stdc++.h>
using namespace std;
#define int long long
int v[2510];
vector<int> a[2510];
bool e[2510][2510];
vector<int> to[2510];
bool vis[2510];
signed main() {
	int n,m,kk;
	scanf("%lld%lld%lld",&n,&m,&kk);
	for(int i=2;i<=n;i++)
		scanf("%lld",&v[i]);
	for(int i=1;i<=m;i++) {
		int x,y;
		scanf("%lld%lld",&x,&y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	for(int i=1;i<=n;i++) {
		memset(vis,0,sizeof(vis));
		queue<pair<int,int> > q;
		q.push({i,0});
		while(!q.empty()) {
			auto u=q.front();q.pop();
			if(u.second>kk+1) break;
			if(vis[u.first]) continue;
			vis[u.first]=1,e[i][u.first]=1;
			for(int v:a[u.first])
				if(!vis[v]) q.push({v,u.second+1});
		}
	}
	for(int i=2;i<=n;i++) {
		for(int j=2;j<=n;j++)
			if(i!=j&&e[i][j]&&e[1][j])
				to[i].push_back(j);
		sort(to[i].begin(),to[i].end(),[&](int x,int y) {
			return v[x]>v[y];
		});
	}
	int ans=0;
	for(int i=2;i<=n;i++)
		for(int j=i+1;j<=n;j++) {
			if(!e[i][j]) continue;
			for(int k=0;k<min(3ll,(int)to[i].size());k++)
				for(int l=0;l<min(3ll,(int)to[j].size());l++)
					if(to[i][k]!=j&&to[j][l]!=i&&to[i][k]!=to[j][l])
						ans=max(ans,v[i]+v[j]+v[to[i][k]]+v[to[j][l]]);
		}
	printf("%lld\n",ans);
	return 0;
}

B. 策略游戏

题意：给你两个数组 $a(n),b(m)$，每次询问 $l_1,r_1,l_2,r_2$，进行如下博弈：第一个人先选一个 $i\in[l_1,r_1]$，第二个人再选一个 $j\in[l_2,r_2]$，其中第一个人想使 $a_i\cdot b_j$ 最大，第二个人相反。求最终结果。$n,m,q\le 10^5$。

容易发现，此题可以直接分类讨论正负后贪心。如果第一个人选正数，那么第二个人一定会选能选的最小的数。如果第二个人能选到负数则一定会选，此时第一个人选的正数越小越好，否则越大越好。如果第一个人选负数，那么第二个人一定会选最大值。如果第二个人能选到正数则一定会选，此时第一个人选的越大（即越接近 $0$）越好，否则越小越好。

实现上，可以使用线段树维护两个序列的正数最大值、最小值和负数最大值、最小值，每次区间询问合并区间信息即可。

#include<bits\/stdc++.h>
using namespace std;
int a[2][100010];
#define mid (t[now].l+t[now].r)\/2
#define lson now*2
#define rson now*2+1
struct node {
	int l,r,maxp,minp,maxn,minn;
	bool havep,haven;
	node():havep(0),haven(0){}
};
struct segtree {
	node t[400010];
	node merge(node x,node y) {
		node res;
		res.l=x.l,res.r=y.r;
		res.havep=(x.havep||y.havep);
		res.haven=(x.haven||y.haven);
		if(x.havep&&y.havep) {
			res.maxp=max(x.maxp,y.maxp);
			res.minp=min(x.minp,y.minp);
		}
		else if(x.havep||y.havep) {
			res.maxp=x.maxp*x.havep+y.maxp*y.havep;
			res.minp=x.minp*x.havep+y.minp*y.havep;
		}
		if(x.haven&&y.haven) {
			res.maxn=max(x.maxn,y.maxn);
			res.minn=min(x.minn,y.minn);
		}
		else if(x.haven||y.haven) {
			res.maxn=x.maxn*x.haven+y.maxn*y.haven;
			res.minn=x.minn*x.haven+y.minn*y.haven;
		}
		return res;
	}
	void build(int now,int l,int r,bool flag) {
		t[now].l=l,t[now].r=r;
		if(l==r) {
			if(a[flag][l]>=0) {
				t[now].havep=1;
				t[now].maxp=t[now].minp=a[flag][l];
			}
			else {
				t[now].haven=1;
				t[now].maxn=t[now].minn=a[flag][l];
			}
			return;
		}
		build(lson,l,mid,flag);
		build(rson,mid+1,r,flag);
		t[now]=merge(t[lson],t[rson]);
	}
	node query(int now,int l,int r) {
		if(l<=t[now].l&&r>=t[now].r) return t[now];
		node res;
		if(l<=mid) res=merge(res,query(lson,l,r));
		if(r>mid) res=merge(res,query(rson,l,r));
		return res;
	}
} T1,T2;
void chkmax(long long &x,long long y) {x=(x>y)?x:y;}
int main() {
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[0][i]);
	for(int i=1;i<=m;i++)
		scanf("%d",&a[1][i]);
	T1.build(1,1,n,0);
	T2.build(1,1,m,1);
	while(q--) {
		int l1,r1,l2,r2;
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		node A=T1.query(1,l1,r1);
		node B=T2.query(1,l2,r2);
		long long ans=-1e18;
		if(A.havep) {
			if(B.haven) chkmax(ans,1ll*A.minp*B.minn);
			else chkmax(ans,1ll*A.maxp*B.minp);
		}
		if(A.haven) {
			if(B.havep) chkmax(ans,1ll*A.maxn*B.maxp);
			else chkmax(ans,1ll*A.minn*B.maxn);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

C. 星战

题意：有一张简单的有向图（不保证连通），每条边有可用和不可用两种状态，初始每条边都可用。定义一个图是合法的，当且仅当：

1. 从每个点开始都存在一个合适的移动方式使得能够无限移动下去。
2. 每个点有且仅有一条出边。

你需要进行 $q$ 次操作，每次如下：

1. 给出 $u,v$，将 $u\to v$ 变为不可用。保证此前处于可用状态。
2. 给出 $u$，将所有 $x\to u$ 全部变为不可用。
3. 给出 $u,v$，将 $u\to v$ 变为可用。保证此前处于不可用状态。
4. 给出 $u$，将所有 $x\to u$ 全部变为可用。

每次操作后回答这张图是否合法。$n,m,q\le 5\times 10^5$。

可以发现，合法的限制一是没有用的。因为如果满足了限制二，该有向图一定为一个基环内向树森林，于是每个节点必然可以通向一个环。可以通过反证法简单地证明：如果存在某个点不能无限移动下去，设它的终点为 $x$，根据限制二，$x$ 必然有出边，故不能成为终点，与假设矛盾。

于是问题转化为每次操作后判断是否每个点的出度均为 $1$。

我们考虑通过哈希来维护这一过程。我们给每个点赋一个随机权值，维护当前每条边起点的权值和 $nowsum$ 并预处理所有点的权值和 $all$。此时如果 $nowsum=all$ 等于每个点的权值和，我们就可以认为每个点恰有一个出边。

对于暴力连边和断边的操作，可以直接在 $nowsum$ 上加减。但是对于断点和恢复点的操作我们没法维护。所以考虑增加维护的状态。定义 $now_i$ 为当前可用的、以 $i$ 为终点的所有起点权值和；$sum_i$ 为所有（包括不可用）以 $i$ 为终点的起点权值和。于是，最终方案如下：

1. 暴力连断边：根据定义，$nowsum$ 增/减 $x$ 的权值，$now_y$ 同样增/减 $x$ 的权值。
2. 删点、恢复点：使用 $now_x$ 和 $sum_x$ 计算出 $nowsum$ 需要改变的值，更新即可。

可以感性理解成势能和动能的转化：$now_i$ 维护每个终点的势能（即其起点的权值和），势能越大，删掉该点时 $nowsum$ 就会减少更多。连边和断边相当于直接更改其终点的势能，而连点和断点相当于将其势能归零/回满。

#include<bits\/stdc++.h>
using namespace std;
long long a[500010],sum[500010],now[500010];
signed main() {
	srand(time(0));
	int n,m,q;
	scanf("%d%d",&n,&m);
	long long nowsum=0,all=0;
	for(int i=1;i<=n;i++) a[i]=rand(),all+=a[i];
	for(int i=1;i<=m;i++) {
		int x,y;
		scanf("%d%d",&x,&y);
		sum[y]+=a[x],now[y]+=a[x],nowsum+=a[x];
	}
	scanf("%d",&q);
	while(q--) {
		int op,x,y;
		scanf("%d%d",&op,&x);
		if(op==1||op==3) scanf("%d",&y);
		if(op==1) now[y]-=a[x],nowsum-=a[x];
		else if(op==2) nowsum-=now[x],now[x]=0;
		else if(op==3) now[y]+=a[x],nowsum+=a[x];
		else nowsum+=sum[x]-now[x],now[x]=sum[x];
		if(nowsum==all) puts("YES");
		else puts("NO");
	}
	return 0;
}

D. 数据传输

题意：给你一个树，第 $i$ 个点有点权 $v_i(>0)$，定义一次跳跃是合法的，当且仅当跳跃的两个节点的距离不超过 $k$。每次询问给出两个节点 $s,t$，你需要考虑一个从 $s$ 走到 $t$ 的方案 $s\to c_1\to c_2\to\cdots\to t$ 使得每步跳跃都合法。输出经过的点的最小点权和（即 $\min\limits_c\{s+\sum c+t\}$）。$n,q\le 2\times 10^5,k\le 3$。

首先考虑最简单的 $k=1$ 的情况。此时每步跳跃只能沿着边走，所以答案即为路径上的点权和。可以使用 LCA 和树上差分计算。

对于 $k=2$，我们可以把路径拉出来，每次跳一步或跳两步，通过简单的 $O(n)$ DP 来计算答案（虽然复杂度不可行）。考虑这个做法的正确性：一定是在两点间路径上跳吗？答案是一定的。如果不在两点间路径上跳，情况一定如下图：

我们可以从 $2$ 跳到 $5$ 再跳到 $4$，但这样一定不如从 $2$ 直接跳到 $4$ 优。

对于 $k=3$，情况就变得麻烦多了。此时跳到路径外变得可行了，如下图：

此时如果点 $6$ 的权值比 $2,3,4$ 小，那么最优策略将是 $1\to 6\to 5$。这就导致了我们上一节的 DP 变得不可行。我们考虑加强上面的过程。这次不只是单独把这一条链拉出来，还要把这条链周围一格的点也拉出来一起考虑。容易证明，这条链周围两格的节点是没有考虑的意义的，证明与上面 $k=2$ 链外无意义类似。

然后我们考虑扩展 DP 状态：定义 $f[i][j\in\{0,1,2\}]$ 表示只考虑链上前 $i$ 个点及其周围一格的点，而当前跳到了一个距离 $i$ 为 $j$ 的点上的最小代价。接着考虑转移：

$f[i][0]$。此时就在第 $i$ 个节点本身。可以从第 $i-1$ 个节点本身转移而来，也可以从“与第 $i-1$ 个节点距离为 $1$ 的节点”转移而来（此时需要跳两格），也可以从“与第 $i-1$ 个节点距离为 $2$ 的节点”转移而来（此时需要跳三格）。故：$f[i][0]=\min(f[i-1][0]+v_i,f[i-1][1]+v_i,f[i-1][2]+v_i)$。

$f[i][1]$。此时我们在“与第 $i$ 个节点距离为 $1$ 的节点”上。这有哪些可能性呢？如下图：

此时当前所在的位置有 $i-1,a,b,i+1$ 四种可能性。对于在 $i-1$ 的情况，可以由 $f[i-1][0]$ 转移过来（即保持不动）；对于其他情况，我们只能从 $c$ 或 $i-2$（与 $i-1$ 距离为 $1$ 的点）转移，而不能从 $i-1$ 本身转移。这是因为，如果我们从 $i-1\to a$，下一步往上跳一格后往右至多跳两格，而此时可以直接从 $i-1$ 跳三格过去更优，所以不应从 $i-1\to a$。综上，$f[i][1]=\min(f[i-1][0],f[i-1][1]+mn_i)$，其中 $mn_i$ 为 $i$ 节点的邻居中最小的点权（都在 $i$ 周围的点没有本质区别，自然权值越小越好）。$mn$ 可以预处理出来。

$f[i][2]$。此时在 $c$ 或 $i-2$，距离 $i-1$ 为 $1$，所以直接由 $f[i-1][1]$ 转移而来。$f[i][2]=f[i-1][1]$。

结合以上分析，我们得到了如下的 DP 方程：

$$ \begin{aligned} f[i][0]&=\min(f[i-1][0]+v_i,f[i-1][1]+v_i,f[i-1][2]+v_i)\ f[i][1]&=\min(f[i-1][0],f[i-1][1]+mn_i)\ f[i][2]&=\min(f[i-1][1]) \end{aligned} $$

（最后一个为了统一格式也用 $\min$）容易发现，$f[i]$ 的三个状态完全由 $f[i-1]$ 的三个状态以及其他仅与 $i$ 有关的贡献转移而来。我们可以想到使用矩阵来优化这一步骤。我们新定义一个矩阵乘法：$[A\cdot B]{i,j}=\min\limits_k\{A{i,k}+B_{k,j}\}$。此矩阵乘法同样具有结合律：

$$ \begin{aligned} [A\cdot (B\cdot C)]{i,j}&=\min\limits_k\{A{i,k}+[B\cdot C]{k,j}\}\ &=\min\limits_k\left\{A{i,k}+\min\limits_p\{B_{k,p}+C_{p,j}\}\right\}\ &=\min\limits_k\left\{\min\limits_p\{A_{i,k}+B_{k,p}+C_{p,j}\}\right\}\ &=\min\limits_p\left\{\min\limits_k\{A_{i,k}+B_{k,p}+C_{p,j}\}\right\}\ &=\min\limits_p\left\{\min\limits_k\{A_{i,k}+B_{k,p}\}+C_{p,j}\right\}\ &=\min\limits_p\{[A\cdot B]{i,p}+C{p,j}\}\ &=[(A\cdot B)\cdot C]_{i,j} \end{aligned} $$

这是一个经典的矩阵乘法的定义：内层相加，外层极值。于是，我们可以把 DP 转移转化为下面的矩阵乘法：

$$ \begin{bmatrix} f[i][0] & f[i][1] & f[i][2] \end{bmatrix}

\begin{bmatrix} f[i-1][0] & f[i-1][1] & f[i-1][2] \end{bmatrix} \cdot \begin{bmatrix} v_i & 0 & +\infty\ v_i & mn_i & 0\ v_i & +\infty & +\infty \end{bmatrix} $$

在 $k=2$ 时也类似，转移矩阵稍微改变一下即可。将 DP 变为矩阵的转化直接使得在每个点的转移变得独立，而与具体路径完全无关。

由于结合律，问题转化为求路径上每个节点的矩阵乘积。由于树上的路径可以分为向上的一段和向下的一段，我们考虑倍增求树上 ST 表。定义 $g[i][j]$ 为一个矩阵，表示从第 $i$ 个点开始，往上连续 $2^j$ 个点的矩阵乘积，可以在预处理 LCA 时顺便完成 $g$ 的预处理。同时，定义 $h[i][j]$ 与 $g[i][j]$ 类似，只不过保存的是从上往下乘的结果。最终答案即为向上的总转移矩阵乘向下的总转移矩阵，再乘 $s$ 时的初始状态，使用树上倍增即可。时间复杂度 $qn\log(n)\times k^3$。

#include<bits\/stdc++.h>
using namespace std;
#define int long long
int n,q,k,v[200010];
struct matrix {
	int n,a[3][3];
	matrix operator*(matrix o) {
		matrix res;
		res.n=n;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++) {
				res.a[i][j]=1e18;
				for(int k=0;k<n;k++)
					res.a[i][j]=min(res.a[i][j],a[i][k]+o.a[k][j]);
			}
		return res;
	}
} f[200010][20],g[200010][20];
vector<int> e[200010];
int fa[200010][20],mn[200010],dep[200010];
void dfs(int now,int father,int depth) {
	fa[now][0]=father,dep[now]=depth;
	f[now][0].n=k;
	auto &t=f[now][0].a;
	for(int i=0;i<3;i++)
		t[i][0]=v[now];
	t[0][1]=t[1][2]=0;
	t[1][1]=mn[now];
	t[2][1]=t[0][2]=t[2][2]=1e18;
	if(k==2) t[1][1]=1e18;
	g[now][0]=f[now][0];
	for(int to:e[now])
		if(to!=father) dfs(to,now,depth+1);
}
int LCA(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;i>=0;i--)
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	if(x==y) return x;
	for(int i=19;i>=0;i--)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
signed main() {
	memset(mn,0x3f,sizeof(mn));
	scanf("%lld%lld%lld",&n,&q,&k);
	matrix init;
	init.n=k;
	for(int i=0;i<k;i++)
		for(int j=0;j<k;j++)
			init.a[i][j]=(i!=j)*1e18;
	for(int i=1;i<=n;i++)
		scanf("%lld",&v[i]);
	for(int i=1;i<n;i++) {
		int x,y;
		scanf("%lld%lld",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
		mn[x]=min(mn[x],v[y]);
		mn[y]=min(mn[y],v[x]);
	}
	dfs(1,0,1);
	for(int x=0;x<=19;x++)
		f[0][x]=g[0][x]=init;
	for(int j=1;j<=19;j++)
		for(int i=1;i<=n;i++) {
			fa[i][j]=fa[fa[i][j-1]][j-1];
			f[i][j]=f[i][j-1]*f[fa[i][j-1]][j-1];
			g[i][j]=g[fa[i][j-1]][j-1]*g[i][j-1];
		}
	while(q--) {
		int s,t;
		scanf("%lld%lld",&s,&t);
		int lca=LCA(s,t),x=v[s];
		s=fa[s][0];
		matrix tmp1=init,tmp2=init;
		for(int i=19;i>=0&&s;i--)
			if(dep[fa[s][i]]+1>=dep[lca])
				tmp1=tmp1*f[s][i],s=fa[s][i];
		for(int i=19;i>=0&&t;i--)
			if(dep[fa[t][i]]>=dep[lca])
				tmp2=g[t][i]*tmp2,t=fa[t][i];
		matrix ans=tmp1*tmp2;
		printf("%lld\n",ans.a[0][0]+x);
	}
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-01-19 22:47:55

更好的观看体验

题意：有 $3n$ 张卡片，每张有一个 $1\sim n$ 的数字。每次可以将最左边的 $5$ 张卡片任意排列，删掉前 $3$ 张，如果这三张数字相等则得一分；最后剩下的三张如果相等也的一分。求最大总得分。

模拟一下这个过程可以发现，相当于你有两张“手牌”，每次新加入三张，你从五张中扔掉三张，还是剩下两张。于是可以考虑一个 DP 状态：$f[i][x][y]$ 表示进行 $i$ 次操作，操作后手上剩下的牌为 $x,y$ 的最大得分。转移也不难，枚举下一次新加进来三张后如何选即可。时空复杂度 $O(n^3)$。

仔细想一下，会发现对于相同的 $x,y$，$f[i][x][y]$ 随着 $i$ 的增加永远不会减少，因为最差的情况无非是：每新加三张就把那三张扔掉，永远让 $x,y$ 为手牌，得分永远不会减少。这启发我们考虑 $f[i]\to f[i+1]$ 的变化。

首先，新加入的三张牌 $a,b,c$ 与 $x,y$ 是多少无关，只与当前考虑到哪张牌有关。如果 $a=b=c$，不管 $x,y$ 是多少，一定直接把它扔掉，贪心地立刻得分。正确性容易证明，这里不赘述。接下来考虑不全相等的情况。

如果用上面说的那样“消极”做法，新加入三张牌就扔掉，$f[i+1][x][y]=f[i][x][y]$，这是下限，可以直接从上一维过来，所以只需要考虑哪些 $x,y$ 会发生改变即可。与消极做法相反，要想改变一定要让操作后手牌中有新牌。我们先考虑如何扔牌能造成贡献，再考虑不能造成贡献的情况。

假如三张牌中有两张相等（这里假设是 $a=b$），那么只要 $x,y$ 中有一个与 $a,b$ 相等的牌即可凑起来扔掉，而手牌中的另一张牌与 $c$ 组成新的手牌。此时，我们可以枚举那个“另一张牌”，假设为 $j$，那么有 $f[i][a][j]+1\to f[i+1][j][c]$（这里暂时不考虑两维的手牌的顺序，实现的时候将 $j,c$ 和 $c,j$ 都更改即可）。接下来，考虑两张手牌相等，与另一张相等的新牌配对，可以直接枚举与哪张新牌相等，假设为 $a$，则有 $f[i][a][a]+1\to f[i+1][b][c]$。于是，造成新贡献的考虑完成。

接着考虑不造成新贡献的转移：由于前面说过，新的手牌中必须留新牌，我们可以枚举留哪张新牌，再枚举另一张牌是什么。假设留的新牌是 $a$，另一张牌是 $j$，那么如果 $j=b$ 或 $j=c$，即新的手牌纯用新牌组成，此时旧手牌 $x,y$ 无论是什么都可行。可以维护所有 DP 值的 $\max$。如果 $j$ 不和 $b,c$ 相等，则旧手牌必须有 $j$，我们维护一个数组 $g[j]$ 表示手牌包含 $j$ 的所有 DP 值的 $\max$ 即可。

以上两种转移的次数都是 $O(n)$ 的，接下来说回“继承”：加入三张牌直接扔掉，手牌不变。如果直接枚举 $x,y$，更新 $f[i+1][x][y]=f[i][x][y]$ 的话，复杂度为 $n^2$，所以这里我们偷个懒，省掉第一维 $i$，直接在旧的 $f$ 数组上做修改即可。注意修改必须考虑完所有转移后整体修改，因为原来的转移是 $f[i][x][y]\to f[i+1][x'][y']$，而不能 $f[i+1][x][y]\to f[i+1][x'][y']$。这可以通过 vector 存储 DP 转移实现。具体可以看代码。

#include<bits\/stdc++.h>
using namespace std;
\/\/#define int long long
void chkmax(int &a,int b) {a=a>b?a:b;}
void chkmin(int &a,int b) {a=a<b?a:b;}
int read() {
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)) f=(ch=='-'?-1:f),ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int a[6010],f[2010][2010],g[2010],mx;
signed main() {
	int n=read(),m=n*3,cnt=0;
	for(int i=1;i<=m;i++)
		a[i]=read();
	memset(f,-0x3f,sizeof(f));
	memset(g,-0x3f,sizeof(g));
	f[a[1]][a[2]]=f[a[2]][a[1]]=0;
	g[a[1]]=g[a[2]]=0,mx=0;
	for(int i=3;i<m;i+=3) {
		array<int,3> p={a[i],a[i+1],a[i+2]};
		sort(p.begin(),p.end());
		if(p[0]==p[2]) {cnt++;continue;}
		vector<pair<pair<int,int>,int> > ch;
		auto add=[&](int x,int y,int val) {
			ch.push_back({{x,y},val});
			ch.push_back({{y,x},val});
		};
		if(p[1]==p[2]) swap(p[0],p[2]);
		if(p[0]==p[1]) {
			for(int i=1;i<=n;i++)
				add(i,p[2],f[i][p[0]]+1);
		}
		for(int i=0;i<3;i++) {
			vector<int> q;
			for(int j=0;j<3;j++)
				if(i!=j) q.push_back(p[j]);
			add(q[0],q[1],f[p[i]][p[i]]+1);
		}
		for(int i=0;i<3;i++) {
			for(int j=1;j<=n;j++) {
				bool flag=0;
				for(int k=0;k<3;k++)
					if(i!=k&&j==p[k]) flag=1;
				if(flag) add(p[i],j,mx);
				else add(p[i],j,g[j]);
			}
		}
		for(auto [x,val]:ch) {
			chkmax(f[x.first][x.second],val);
			chkmax(g[x.first],val),chkmax(g[x.second],val);
			chkmax(mx,val);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			chkmax(ans,f[i][j]+(i==a[m]&&j==a[m]));
	printf("%d\n",ans+cnt);
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-08 18:16:40

一道线段树优化建图好题（大雾

扣掉一些边看起来不好做，我们直接大力加上存在的边，然后跑连通块。对于一个点，如果他被扣掉了 $k$ 个邻居，那么没扣掉的那些形成了至多 $k+1$ 个连续段，可以用线段树优化建图向每个连续段各用 $\log$ 的代价连边。

由于总共扣掉了 $m$ 条边，所以总共连边的次数是 $O(m)$ 的，建图复杂度为 $m\log m$，产生 $O(n+m)$ 个点、$O(n+m)$ 条边的有向图。

注意到线段树优化建图建的是有向图，如果直接建无向图就会让所有点都在一个连通块。所以按照有向的线段树优化建图做法，如下：

（图为 2 向 3,4 连边）（由于是点向区间连边，只需要一棵线段树即可）

注意到，在 $2$ 向 $3,4$ 连边时，$3,4$ 也会向 $2$ 连边，故连通块一定形成强连通分量，也不会产生直接连无向图的问题。于是最后对新图跑一下强连通分量即可。

#include <bits\/stdc++.h>
using namespace std;
vector<int> a[200010], e[600010];
int n, m, tot, rt;
struct node{int lson, rson;} t[600010];
#define mid (l + r) \/ 2
void build(int &now, int l = 1, int r = n) {
	if (l == r) {now = l + n; return;}
	now = ++tot;
	build(t[now].lson, l, mid), build(t[now].rson, mid + 1, r);
	e[now].push_back(t[now].lson), e[now].push_back(t[now].rson);
}
void add(int now, int ql, int qr, int x, int l = 1, int r = n) {
	if (ql <= l && qr >= r) {e[x].push_back(now); return;}
	if (ql <= mid) add(t[now].lson, ql, qr, x, l, mid);
	if (qr > mid) add(t[now].rson, ql, qr, x, mid + 1, r);
}
int dfn[600010], low[600010], cnt;
int st[600010], top, col[600010], colcnt, sz[600010];
bool in[600010];
void dfs(int now) {
	low[now] = dfn[now] = ++cnt;
	st[++top] = now, in[now] = 1;
	for (int v : e[now]) {
		if (!dfn[v]) dfs(v), low[now] = min(low[now], low[v]);
		else if (in[v]) low[now] = min(low[now], dfn[v]);
	}
	if (low[now] == dfn[now]) {
		colcnt++;
		while (st[top] != now)
			col[st[top]] = colcnt, in[st[top]] = 0, top--;
		col[st[top]] = colcnt, in[st[top]] = 0, top--;
	}
}
signed main() {
	scanf("%d%d", &n, &m), tot = n * 2;
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y), a[y].push_back(x);
	}
	for (int i = 1; i <= n; i++)
		e[i + n].push_back(i);
	build(rt, 1, n);
	for (int i = 1; i <= n; i++) {
		a[i].push_back(0), a[i].push_back(n + 1);
		sort(a[i].begin(), a[i].end());
		for (int j = 1; j < a[i].size(); j++) {
			if (a[i][j - 1] + 1 == a[i][j]) continue;
			add(rt, a[i][j - 1] + 1, a[i][j] - 1, i);
		}
	}
	for (int i = 1; i <= tot; i++)
		if (!dfn[i]) dfs(i);
	for (int i = 1; i <= n; i++)
		sz[col[i]]++;
	sort(sz + 1, sz + colcnt + 1);
	vector<int> ans;
	for (int i = 1; i <= colcnt; i++)
		if (sz[i]) ans.push_back(sz[i]);
	printf("%d\n", (int)ans.size());
	for (int x : ans) printf("%d ", x);
	puts("");
	return 0;
}

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

前言

看了看其他题解，得出了一个结论：我太菜了，根本看不懂。。。

经过自己一番瞎搞，竟然做出来了？！

0.基本变量

int n,ans=0; \/\/ans是储存最终答案最大值
struct word \/\/记录一个单词的基本信息
{
	char begin,end; \/\/起止字符
	int size; \/\/长度
	bool vis; \/\/是否被搜索过
	word(){vis=0;} \/\/初始化
}a[17];

1.暴搜过样例

首先，根据题意，我们很容易想到一种暴搜方案：

int dfs(int now,int num) \/\/now:当前单词编号 num:之前的单词长度和
{
	int flag=a[now].end,len=num+a[now].size,res=len;
	\/*
	flag:储存当前单词的终止字符，用来筛选下一个单词
	len:储存包括当前单词的单词长度和
	res:储存经过当前单词的最佳答案
	*\/
	a[now].vis=1; \/\/标记
	for(int i=1;i<=n;i++)
		if(a[i].begin==flag&&!a[i].vis)
			res=max(res,dfs(i,len)); \/\/更新最佳答案
	a[now].vis=0; \/\/回溯
	return res; \/\/完结
}

这样，我们就愉快地得到了70分

2.优化出奇迹

为什么会超时呢？

当数据出现形如

ABBBBBA
ABBBBA
ABBBA
ABBBBBBA
ABBBA

的数据时，我们的暴搜会把每一个都搜一遍，直接达到了最高复杂度 $n!$ ，所以面对这种情况，我们可以用贪心的方法，对于首尾字母相同的单词，每次选最长的。

那我们肯定不能每次选单词时都算一遍最大值，于是我们进行一个sort的预处理：

bool cmp(word a,word b){return a.size>b.size;}

sort(a+1,a+n+1,cmp);

提前按照长度从大到小排序，这样就能保证拥有同样首尾字母的单词中首先被选的一定是最长的。

当我们搜索到一个单词时，面对同样尾字母的下一个单词（首字母肯定都和当前单词的尾字母一样），最长的总比短的要好，而我们通过排序已经保证了第一个选的是最长的，所以选了一个后，相同尾字母的其他单词就都不用考虑，所以我们要做一个标记，标记char done[17]，done[i]储存第$i$个被选中的单词尾字母，那么与它有同样尾字母的就不用选了。于是我们在搜索中加入判断

bool go_on=1;
\/\/count是done数组的长度
for(int j=1;j<=count;j++) \/\/遍历done数组每一个元素
	if(a[i].end==done[j]) \/\/判断此单词的尾字母在done中出现
	{
		go_on=0;
		break;
	}

和标记

if(go_on) \/\/如果done中没有出现该尾字母，就递归搜索，并把该尾字母加入done中
{
	res=max(res,dfs(i,len));
	done[++count]=a[i].end;
}

哦，别忘了初始化(这个不用解释了吧)

int count=0,done[17];
for(int i=1;i<=16;i++)
	done[i]='?';

这样，我们就得到了一份完整的AC代码

#include<bits\/stdc++.h>
using namespace std;
int n,ans=0;
struct word
{
	char begin,end;
	int size;
	bool vis;
	word(){vis=0;}
}a[17];
bool cmp(word a,word b){return a.size>b.size;}
int dfs(int now,int num)
{
	int flag=a[now].end,len=num+a[now].size,res=len;
	int count=0,done[17];
	for(int i=1;i<=16;i++)
		done[i]='?';
	a[now].vis=1;
	for(int i=1;i<=n;i++)
	{
		if(a[i].begin==flag&&!a[i].vis)
		{
			bool go_on=1;
			for(int j=1;j<=count;j++)
				if(a[i].end==done[j])
				{
					go_on=0;
					break;
				}
			if(go_on)
			{
				res=max(res,dfs(i,len));
				done[++count]=a[i].end;
			}
		}
	}
	a[now].vis=0;
	return res;
}
int main()
{
	string s;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		a[i].begin=s[0],
		a[i].end=s[s.size()-1],
		a[i].size=s.size();
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		a[i].vis=1;
		ans=max(ans,dfs(i,0));
		a[i].vis=0;
	}
	cout<<ans<<endl;
	return 0;
}

完结撒花～

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-08-15 10:36:11

本篇题解献给和我一样看不懂其他题解的状压DP小白

相信大家都是看了其他题解看不懂才看到这篇题解的（莫名自信），所以什么每行棋子数递减啊，每行的棋子都排在左边啊，就不用我多说了，直接切入正题（大段文字多，请耐心观看）。

轮廓线DP

没见过不用慌，我也没见过（雾

轮廓线，就是把矩阵从右上角到左下角沿着有棋子和没棋子的分界线描一下，往下走就用1表示，往左走就用0表示。这样我们就得到了一个01串，即一个二进制数，这就是我们的DP状态。

例如（图丑勿喷）

这种情况下轮廓线状态为左左下左下下左左下，即$001011001_{(2)}=89$

我们设$f[s]$（$s$就是轮廓线状态）表示从轮廓线表示的局面一直下到最终下满的过程中“先手-后手”最大是多少。我们可以发现，只根据s就可以知道已经下了那些棋，但不能知道具体是黑棋还是白棋，然而根据$f$的定义，$f[s]$的值和前面怎么下的没有关系，它只管之后怎么下，所以我们只用一维轮廓线就OK，不需要记录之前怎么下的。

那么状态有了，怎么转移呢？以上图为例，即将要白棋（后手）下棋，后手肯定希望他下的一步棋能使得从现在开始（以前的我们不管）先手-后手得分尽可能小（如果是负数那他更开心了），所以$f[s]=\min\limits_{所有再下一步棋可能得到的方案s'}f[s']-b[x][y]$（$x,y$就是即将下的那一步棋的坐标）。

同理，如果即将先手下，就把上面的式子里min改成max（因为他希望下这步棋能使得他的得分-对方的得分最大），$-b[x][y]$改成$+a[x][y]$。

这样我们就可以用记忆化搜索很容易地跑出来了。

哎等等，我们还有两个问题没解决，观察上面的式子，我们还不知道怎么枚举“所有再下一步棋可能得到的方案$s'$”，也不知道怎么根据轮廓线的变化找出具体坐标x和y啊？

我们一个一个解决，先看第一个问题。还是以上图为例，白棋（后手）可以下在$(1,4),(2,3),(4,1)$三个位置，但转移的时候电脑只知道当前的轮廓线，所以我们需要找这三个点的共同特点，那就是处在轮廓线左和下的拐角处，也就是轮廓线中先出现一个0，再出现一个1。现在我们知道了轮廓线上放棋子的位置，怎么得出放棋子后的轮廓线状态呢？我们还是以上图为例，如果我们放在$(2,3)$处，进行一个对比。

原：$001011001_{(2)}$

新：$001101001_{(2)}$

我们发现只有第四位和第五位变了，而原先的第四位和第五位就是我们之前说的先出现一个0，再出现一个1，那么转移就是把0变成1，把1变成0。

具体来说，就是当我们枚举到一个$i$，使得原状态的（从低位数）第$i$位是1，第$i+1$位是0，那么就把状态异或上$3<<i$（可以对照例子手推一下）。

开始讨论第二个问题，我们知道该在轮廓线的哪一位上下棋，怎么知道那步棋的具体坐标呢？这个问题比较容易解决，只需要在枚举$i$时维护当前看到哪个坐标即可（详见代码）。

代码

#include<iostream>
using namespace std;
int n,m;
int a[20][20],b[20][20];
int f[1048580];
bool vis[1048580];
int dfs(int s,bool now)\/\/s是轮廓线状态，now记录是先手还是后手（虽然可以根据s算出来，但这样比较方便）
{
	if(vis[s])\/\/记忆化搜索标配
		return f[s];
	vis[s]=1;
	if(s==(1<<(n+m))-(1<<m))\/\/已经填满棋子（即n个下加m个左）
		return 0;
	int num0=0,num1=0;\/\/维护坐标（已经出现多少个左\/多少个下
	if(now)\/\/先手
	{
		f[s]=-2147483647;
		for(int i=0;i<n+m-1;i++)
		{
			num1+=((s&(1<<i))>>i);
			num0+=(!((s&(1<<i))>>i));
			if((s&(1<<i))>0&&(s&(1<<(i+1)))==0)
				f[s]=max(f[s],dfs(s^(3<<i),0)+a[n-num1+1][num0+1]);\/\/递归计算
		}
		return f[s];
	}
	else\/\/后手
	{
		f[s]=2147483647;
		for(int i=0;i<n+m-1;i++)
		{
			num1+=((s&(1<<i))>>i);
			num0+=(!((s&(1<<i))>>i));
			if((s&(1<<i))&&!(s&(1<<(i+1))))
				f[s]=min(f[s],dfs(s^(3<<i),1)-b[n-num1+1][num0+1]);\/\/递归计算
		}
		return f[s];
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>b[i][j];
	cout<<dfs((1<<n)-1,1)<<endl;
	\/\/(1<<n)-1是初始状态，即m个左加n个下（一步棋也没下）
	return 0;
}

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

更好的阅读体验

基础的DP各位大佬已经讲得很明白了，本文主要讲一讲优化

DP状态很容易想到：$f[i]$ 表示打完第 $i$ 只鼹鼠能获得的最多数量。

转移：$f[i]=\min\limits_{j<i,\ t[i]-t[j]>=dis(i,j)}f[j]+1$，即对于每一个打完第 $j$ 个能来得及走到第 $i$ 个的 $j$，算最大的 $f[j]+1$。

重点来了！！

优化

我们发现，如果时间差大于 $2\times n$，无论在天涯海角哪里都能走到，又因为输入的时间是升序排列，我们只需要在转移时维护 $g[i]$ 表示 $\max\limits_{j<=i}f[i]$，这样在转移 $f[i]$ 时就可以先用 $start=upper\_bound-1$ 找出最后一个“时间差大于 $2\times n$” 的鼹鼠，他前面的鼹鼠无论多远都能到达，就可以直接用 $g[start]$ 来代替，枚举时就只需要从 $start$ 开始枚举了。

#include<bits\/stdc++.h>
using namespace std;
int t[10010],x[10010],y[10010];
int f[10010],g[10010];
int dis(int a,int b) {
	return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
	for(int i=1;i<=m;i++) {
		int start=max(0,int(upper_bound(t+1,t+i,t[i]-2*n)-t-1));
		f[i]=g[start]+1;
		for(int j=max(1,start);j<i;j++) {
			if(t[i]-t[j]>=dis(i,j))
				f[i]=max(f[i],f[j]+1);
		}
		g[i]=max(g[i-1],f[i]);
	}
	printf("%d\n",g[m]);
    return 0;
}

哎哎哎，别急着走，后面还有：

继续优化

我们发现，由于时间是递增的，所以 $i$ 的 $start$ 一定不会小于 $i-1$ 的 $start$，所以我们用 $start[i]$ 记录第 $i$ 只鼹鼠的 $start$，那么 $upper\_bound$ 时就只需要从 $start[i-1]$ 开始查找。

#include<bits\/stdc++.h>
using namespace std;
int t[10010],x[10010],y[10010];
int f[10010],g[10010],start[10010];
int dis(int a,int b) {
	return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
	for(int i=1;i<=m;i++) {
		start[i]=max(0,int(upper_bound(t+start[i-1],t+i,t[i]-2*n)-t-1));
		f[i]=g[start[i]]+1;
		for(int j=max(1,start[i]);j<i;j++) {
			if(t[i]-t[j]>=dis(i,j))
				f[i]=max(f[i],f[j]+1);
		}
		g[i]=max(g[i-1],f[i]);
	}
	printf("%d\n",g[m]);
	return 0;
}

哎哎哎，别急着走，后面还有：

继续继续优化

我们甚至可以直接不用 $upper\_bound$ 和 $start$ 数组了（没错），开一个变量 $start$，维护当前的 $start$，转移之前用一个

for(;t[i]-t[start+1]>=2*n;start++);

来更新 $start$，可以发现，整个程序运行下来，$start$ 最多只会更新 $n$次，所以复杂度可忽略。

最终代码：

#include<bits\/stdc++.h>
using namespace std;
int t[10010],x[10010],y[10010];
int f[10010],g[10010],start;
int dis(int a,int b) {
	return abs(x[a]-x[b])+abs(y[a]-y[b]);
}
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
	for(int i=1;i<=m;i++) {
		for(;t[i]-t[start+1]>=2*n;start++);
		f[i]=g[start]+1;
		for(int j=max(1,start);j<i;j++) {
			if(t[i]-t[j]>=dis(i,j))
				f[i]=max(f[i],f[j]+1);
		}
		g[i]=max(g[i-1],f[i]);
	}
	printf("%d\n",g[m]);
	return 0;
}

不开O2可达48ms，可见优化非常显著。

请勿抄袭，如果一定要抄，请理解明白后再抄

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-09-30 11:14:49

赛时 AC 2道题，掉大分（哭）

更好的阅读体验

A. Casimir's String Solitaire

题目传送门

$Problem$

给你一个仅含 A,B,C 的字符串，每次可以删掉一个 A 和一个 B，或一个 B 和一个 C，位置、顺序不限，问能不能删完。

$t\le 1000,len\le 50$

$Solution$

大水题，只需要判断 A 的数量加 C 的数量是否等于 B 的数量。一开始脑抽还判断 A 的数量是否等于 C 的数量

B. Shifting Sort

题目传送门

$Problem$

定义对一段区间的 Cyclically Shift（以下简称Shift） 操作为：

1. 指定一个数 $x(x\le len)$ 为操作的周期。
2. 每次将区间左移一位，移出去的那一位放到最右边，重复 $x$ 次。

给你一个数列 $a$，问如何用不超过 $n$ 次 Shift 操作将 $a$ 排好序（不要求使用次数最少，只要不超过 $n$ 就行）。

$1\le t \le 1000,2\le n\le 50$

$Solution$

注意只要求不超过 $n$ 次，也就意味着我们只需要每一次把一个数排好序就行了。我们可以每次挑选最大的数，通过一次 Shift 操作（$x=1$）将它移到最右边的位置，如果已经在该在的位置就不操作，每次都能将一个数归位，重复 $n$ 次即可。

eg.

原序列
2 5 1 4 3
将5归位
2 1 4 3 5
将4归位
2 1 3 4 5
将2归位
1 2 3 4 5

由于 $n$ 很小，暴力找最大值就可以。

C. Ticks

题目传送门

$Problem$

给你一个 $n\times m$ 的网格图，每个格子有 * 和 . 两种状态，* 表示填，. 表示不填，问能不能通过若干个大小超过 $k$ 的“V字形”表示出这个图形（V 的两条边必须一样长，机房的两位大佬就是没判断这个而 FST 了）。

“V字形”大小的定义：

*...*
.*.*.
..*..

的大小为 $2$。

$1\le k\le n\le 10,1\le m\le 19$

$Solution$

注意到 $n$ 和 $m$ 的范围很小，完全可以通过暴力求解。对于每一个格子，尽可能多的往上延伸，如果超过 $k$ 就把覆盖格子的标记一下，最后判断是否都被覆盖完。

D. Productive Meeting

题目传送门

$Problem$

在一场见面会中有 $n$ 个人，会议开始后他们会两两交谈，每个人有一定的耐心值 $a_i$，第 $i$ 个人在交谈 $a_i$ 次后会离开会议，两个人可以交谈多次，请找出一种方案使得总交谈次数尽可能多。

$1\le t\le 1000,\sum n\le 2\times 10^5,\sum a_i\le 2\times 10^5$

$Solution$

由于 $\sum a_i$ 不大，我们可以依次考虑每一次交谈，容易想到每次让耐心值最大的两个人交谈是最优方案。

实现 1

先排好序，每次让剩余耐心值最大的两个人交谈，耐心值--，在考虑维护序列单调性，可以通过一通 lower_bound 和 upper_bound 以及 swap 来实现，时间复杂度 $O((\sum a_i)\log(n))$。

实现 2

使用 lower_bound 和 upper_bound 来维护需要考虑一大堆细节（我调错调了一下午加一晚上），不如用堆来维护。每次从堆里拿出两个耐心值最大的人，耐心值--，如果还有剩余耐心值，就把他们再扔回堆里，用 STL 的优先队列实现非常简洁，时间复杂度也是 $O((\sum a_i)\log(n))$。

E1. Permutation Minimization by Deque

题目传送门

在 Codeforces 中首次被 hack 祭。

$Problem$

给你一个 $1-n$ 的排列，你需要把它们按顺序扔进双端队列里，你可以决定从哪一端扔。需要使得最终双端队列里的数的字典序最小。

$1\le t\le 1000,\sum n\le 2\times 10^5$

$Solution\ 1$

由于要让字典序最小，肯定最小的值放在最前面，最小值之前的数的放法先不管，放完最小值之前的数之后在把最小值放在最前面，最小值后面的数就只能从后面挨个放了。而最小值之前的数我们可以递归处理。

具体实现中我们需要用 ST 表维护区间最小值，再用分治递归的方法实现。

$Solution\ 2$

从通过人数上看，这道题的简单程度可是仅次于 A 题，怎么会这么复杂呢？

考虑用贪心的思想，先扔进去第一个数，以后对于每一个数，如果它比队首小，就扔到队首（这样可以让结果的字典序尽可能小），否则就扔到队尾（如果还扔到队首字典序就大了）。就是这么简单。

E2. Array Optimization by Deque

题目传送门

$Problem$

给你一个长度为 $n$ 的数列（注意不是排列），你需要把它们按顺序扔进双端队列里，你可以决定从哪一端扔。需要使得最终双端队列里的逆序对尽可能少。

$1\le t\le 1000,\sum n\le 2\times 10^5,-10^9\le a_i\le 10^9$

$Solution$

同样是贪心，对于每个数，如果放在队首，则贡献的逆序对数为前面比它小的数的个数，反之则为比它大的数的个数，这个数放在队首还是队尾对以后的方法不会产生干扰，所以只需要判断它前面是比它大的多还是比它小的多，这可以用树状数组或权值线段树维护。由于 $a_i$ 的值跨度过大，需要先进行离散化处理。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2021-10-08 11:30:11

更好的阅读体验

没打比赛，赛后做出3道。 这场比赛题目质量很高，非常巧妙。

A. CQXYM Count Permutations

$Problem$

求有多少 $2n$ 的排列满足存在超过 $n$ 个 $i$ 使得 $p_i<p_{i+1}$，答案对 $10^9+7$ 取模。

$\sum n\le 10^5$

$Solution$

这题就非常巧妙了，当我们使劲想想不出来时，正难则反，考虑有多少 $2n$ 的排列满足存在超过 $n$ 个 $i$ 使得 $p_i>p_{i+1}$，这时候我们就会发现：这不是一样吗？没错，答案就是 $\frac{(2n)!}{2}$。

B. Diameter of Graph

$Problem$

每次给定 $n,m,k$ 问能不能构造一个 $n$ 个点，$m$ 条边的简单无向图使得图的直径小于 $k-1$。

一张图的直径定义为最短路最长的两个点的最短路长度。

$t\le 10^5,n,m,k\le 10^9$

$Solution$

始终没有明白为什么要“小于 $k-1$”，直接 k-=2 后变成 $\le k$。

考虑这道题可以转化为构造一个 $n$ 个点，$m$ 条边的直径尽可能小的图。

首先判断能否连通，即 $m<n-1$，然后判断是否必须有重边，即 $m>\frac{n(n-1)}{2}$，如果出现这两种情况则为不合法，直接排除。而且，如果 $k<1$，也直接排除，因为不可能存在两个点的距离 $<1$。

然后考虑能否构造出直径为 $1$ 的图。我们发现只有完全图的直径为 $1$，因为任意两个点都可以直径过 $1$ 条边到达。所以，如果 $k=1$，只有完全图才成立，否则不成立。接着在考虑能否构造出直径为 $2$ 的图。我们会发现只要图连通，就一定能构造出来直径为 $2$ 的图，因为菊花图的直径为 $2$，而在菊花图上加边不会让直径变大，所以只要 $k>1$ 就一定能构造出来。

C. Portal

$Problem$

给定一张 $n\times m$ 的矩阵，每个格子有空和黑曜石两种状态，你可以花费一步操作将空格子变成黑曜石或将黑曜石变成空格子。一个子矩阵可以形成传送门需要具备以下条件：

1. 高度 $\ge 5$，宽度 $\ge 4$。注意，传送门不能横过来看，宽就是宽，高就是高。
2. 中间部分必须全是空格子。
3. 四周边框必须全是黑曜石。
4. 四角不限。

问至少需要几次操作才能搭建一个传送门。

$\sum n\le 400,\sum m\le 400$

$Solution$

这道题我从9月30号读题一直到10月8号才做出来，历尽了千辛万苦。

记输入的矩阵为 $a$，用 $0$ 表示空格，$1$ 表示黑曜石。

首先预处理出每一行的前缀和，以便我们 $O(1)$ 查询一段横向区间里有多少块黑曜石，我们用 $s[i][j]$ 表示。

然后，枚举合法的左右边界（$r-l\ge 3$），我们记 $len=r-l-1$ 表示中间部分的宽度，对于每一个左右边界，记 $t[i]$ 表示前 $i$ 行全变成 $100...001$ 的格式需要花费的步数，本质上是竖向的前缀和：$t[i]=t[i-1]+(s[i][r-1]-s[i][l])+(2-a[i][l]-a[i][r])$。然后我们考虑如何 $O(1)$ 计算搭建一段以 $u$ 为上边界，$d$ 为下边界的传送门的步数：首先让中间和左右边框合法（$t[d-1]-t[u]$），再让上边框合法（$len-(s[u][r-1]-s[u][l])$），同理再让下边框合法（$len-(s[d][r-1]-s[u][l])$）。加起来，则为：

$t[d-1]-t[u]+(len-(s[d][r-1]-s[d][l]))+(len-(s[u][r-1]-s[u][l]))$

将与 $u,d$ 有关的项分开，方便处理：

$2len+(t[d-1]-s[d][r-1]+s[d][l])-(t[u]+s[u][r-1]-s[u][l])$

我们记 $f[i]=t[i-1]-s[i][r-1]+s[i][l],g[i]=t[i]+s[i][r-1]-s[i][l]$，则上式可简化为 $2len+f[d]-g[u]$。

现在考虑从上到下扫下边界，对于每一个下边界，我们要使步数尽可能小，即让 $2len+f[d]-g[u]$ 尽可能小，就要让 $g[u]$ 尽可能大，于是我们从上到下扫的时候，记录以下当前扫过的 $g[u]$ 的最大值 $maxn[i]=\max(maxn[i-1],g[i])$，那么对于每一个下边界 $d$，最小步数就为 $2len+f[d]-maxn[d-4]$，整个算法的时间复杂度就可以做到 $O(m^2n)$。