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

在去年看完之后又看了一遍《献给阿尔吉侬的花束》。

今天发烧没去机房，在宿舍只有手机没有电脑很无聊。

想起来书包里一直有这本书。

为啥是想起来呢，因为去年在南京看完后就一直封存在行李箱里，今年又去南京的时候想要把这本书带着，找半天才发现在行李箱夹层里。

然后七月也没怎么看，来北京的时候顺带捎上了。

没想到还真派上用场了。

又想起去年看完这本书后想要写书评，但不过一小时好像就忘记了。

哦哦我想起来了一件事，这件事一直想要写鲜花，但好像间歇性的忘记。

书评应该写过，记录在当时还健在的日记本上。

这个日记本像查理·高登的近步抱告一样流水账，但他好歹记录了我那一天发生了什么事情。

日记的开端是初二语文老师的周末作业，所以本子上的第一篇日记是那个学期的周天写的。

后来日记本好像再也没有收过，但我还是每天都在写，但与前几天需要给老师检查的日记不一样。这个日记本对当时的我作用是用来为现在的我回忆琐碎但有趣的事件。

这可能是我还没有接触鲜花这个概念时自发的鲜花吧。

日记持续了一年多，这对于不擅长坚持的我来说是一件不得了的事情。（同期也发生了另一件不得了的事情——坚持每晚跑步了大半年，但这两件事的放弃都是同一时间点）

去年暑假，我在从南京回潍坊的火车上匆忙的补了前面12天的日记，但无论如何也补不完了。那12天琐碎的回忆已经被丢入垃圾桶。

于是日记搁置了。

（其实南京期间以及之后大半年也即初三上学期，我有日记的上位替代——题解本，但在寒假后被搁置了）

初中毕业后 我想起来了这几项事件，于是我翻了翻柜子，却只找到了最后三个月的日记。前面八个月的内容大概已经被压成块废物利用了。

当时好像有点沮丧。

我清楚的记得我在日记里记录了我第一次看变身，第一次听igs和烟distance，第一次看到官方媒体中的＂孔乙己＂形象，第一次看某个知名纯爱萝莉本，第一次看完《献给阿尔吉侬的花束》的感觉。这些情感在我用手机打出上面几个字时好像从水面下升起了几个泡，但很快又归于平静。

再次看完这本书，一些回忆被引起，我看着查理·高登的近步抱告，眼前浮现着报告中一幕幕场景。

书中最动人的部分应是智力已退回到原来水平的查理·高登的留言。

因为查理智力比自己高而嫉妒的店员再次成为查理的朋友，艾丽斯变回了纪尼安小姐。

还有：如果你有机会请放一些花在后院的阿尔吉侬坟上。

虽然夜鹿的歌中我并不是很青睐这首，但阿尔吉侬这首歌也还算好听，而且没有歌比这首歌更贴题了。

僕らはゆっくりと忘れていく　とても小さく

我们将渐渐遗忘一切 所忘却的少之又少

少しずつ崩れる塔を眺めるように

却如那逐渐崩塌的高塔一般

僕らはゆっくりと眠っていく

我们将渐入梦乡

ゆっくりと眠っていく

缓缓睡去

貴方はゆっくりと変わっていく　とても小さく

我眼中的你正渐渐改变 那变化微乎其微

あの木の真ん中に育っていく木陰のように

就如生长于那颗树木中间的树荫一般

貴方はゆっくりと走っていく

我眼前的你渐渐向前奔去

長い迷路の先も恐れないままで

从不畏惧地迈向那迷宫尽头

確かに迷いながら

却又心怀迷茫

这次写了好多啊，也有点流水账，但闲下来还是能让人想起来好多事的，比如今天是周一，不是星期四。

以及：手机真难编辑，加引用一开始用的全角，还要手动加换行/tuu

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

小 e 在初三时接触到了算法竞赛，数学思维优秀的他决定加入这个行列。通过课余时间的学习，他成功的拿到了普及组一等奖。在升入高中后，面对压力骤升的文化课与难度增加的算法知识，他在 NOIP 前选择了停课冲刺。但考场上发挥失利，签到题写了字典树而空间爆炸，于是他失去了省选晋级的可能，也失去了D类名额。今年，小 e 已经高二了。他决定奋力一搏。于是他打开了 cspsjtest.noi.cn ，熟练的注册了账号，注册网站上弹出了这样的界面：

今天是肯德基疯狂星期四，请大家 v 我 50 报名初赛。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-03 15:56:48

首先考虑F1。容易想到区间dp。发现在dp的时候区间前面删了几个元素也是非常重要的，所以把它加入状态。

设 $f_{l,r,x}$ 代表 $[l,r]$ 区间在 $[1,l)$ 已经删了最多 $x$ 个的前提下能够进行的操作数。

转移有两方面，一方面是两个区间合并，这时 $f_{l,r,x}=\min_{k=l}^{r-1}\max(f_{l,k,x},f_{k+1,r,x+f_{l,k,x}*2})$ 。

因为前半段区间会影响到后半段，所以后半段可以增加前面删除的个数。

第二方面的转移是对第一个元素进行操作，需要满足 $a_l=l-x\land 2f_{l+1,r,x}<r-l$ ，即一定要先对右边区间删后再对 $l$ 操作，且区间内一定要有剩余元素。

因为状态是最多，所以 $f_{l,r,x}$ 也要向 $f_{l,r,x+2}$ 转移。

第三维只会是偶数，因为每次删除删两个。

但存储的是进行的操作次数，所以在一些时候需要乘二。

（前面半句有点难发现，因为这个调了好久）

$\mathrm{O(n^3)}$ 的状态和 $\mathrm{O(n)}$ 的转移，总体来说是 $\mathrm{O(n^4)}$ 。

code (F1)

const int N=1e2+5;

int a[N];

int f[N][N][N];

signed main(){
	signed _T=read();
	while(_T--){
		int n=read();
		for(int i=1;i<=n;i++)
			a[i]=read();
		for(int len=2;len<=n;len++){
			for(int l=1;l+len-1<=n;l++){
				int r=l+len-1,mx=0;
				for(int x=0;x<=l-1;x+=2){
					f[l][r][x]=max(mx,f[l+1][r][x]+(a[l]==l-x&&f[l+1][r][x]*2!=r-l));
					for(int k=l;k<r;k++)
						f[l][r][x]=max(f[l][r][x],f[l][k][x]+f[k+1][r][x+f[l][k][x]*2]);  
					mx=max(mx,f[l][r][x]);
				}
			}
		}print(f[1][n][0]),pc('\n');
	}
	return 0;
}

然后考虑优化。发现（最好能）对于一个区间，其前面能够被删除的数越多越好，因为自己不会影响前面。

那么考虑记录这个而非区间内最大操作次数，代价是不能对操作数量计数，这里有一个套路是固定使区间删完，然后再用一个dp来合并答案。

那么状态是 $f_{l,r}$ 表示若想吧 $[l,r]$ 删完，$[1,l)$ 最少进行几次操作。

转移也是两方面，合并和第一个元素进行操作。

合并是简单的，$f_{l,r}=\min_{k=l}^{r-1} \max(f_{l,k},f_{k+1,r}-\frac{k-l+1}{2})$ 。

因为可以先对左边操作，右边所需要的就可以相应减少。

若是对 $l$ 进行操作则需满足 $\frac{l-a_l}{2}\geq f_{l+1,r-1}\land l\equiv a_l\pmod{2} $ 。

同样需要注意前者，需要先删里面才能删外面。

初始值设为无穷大。

这样状态就缩减到了 $\mathrm{O(n^2)}$ ，总复杂度 $\mathrm{O(n^3)}$ 。

后面的合并答案写了一个傻傻的 $\mathrm{O(n^3)}$ dp，但能过。

好像只需要设 $g_i$ 表示前 $i$ 项最多进行 $g_i$ 次操作就行了。

code

const int N=8e2+5;

int a[N];

int f[N][N];

int ans[N][N];

signed main(){
	signed _T=read();
	while(_T--){
		int n=read();
		for(int i=1;i<=n;i++)
			a[i]=read();
		for(int len=2;len<=n;len+=2){
			for(int l=1;l+len-1<=n;l++){
				int r=l+len-1;
				f[l][r]=inf;
				if(a[l]<=l&&a[l]%2==l%2&&f[l+1][r-1]<=(l-a[l])\/2)
					f[l][r]=(l-a[l])\/2;
				for(int k=l+1;k<r;k+=2)
					f[l][r]=min(f[l][r],max(f[l][k],f[k+1][r]-(k-l+1)\/2));
			}
		}
		int mx=0;
		ans[0][0]=0;
		for(int i=1;i<=n;i++)
			ans[0][i]=-inf;
		for(int i=1;i<=n;i++){
			for(int j=0;j<=n;j++){
				ans[i][j]=ans[i-1][j];
				for(int l=i-1;l>=1;l-=2){
					if(f[l][i]<=j-(i-l+1)\/2)
						ans[i][j]=max(ans[i][j],ans[l-1][j-(i-l+1)\/2]+(i-l+1)\/2);
				}
				mx=max(mx,ans[i][j]);
			}
		}print(mx),pc('\n');
	}
	return 0;
}

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

Link

感觉就很扫描线。

需要注意这里全部都是小于号，不能取等，在离散化的时候需要注意加入 $x-1$ 和 $x+1$ 。在扫描线的时候也要特别注意一下边界问题。

还有一个细节是需要初始化，因为答案对应贡献可能为 $0$ ，这时需要初始化为 $\{0,1\}$ 。

注意左右端点不能取等。

(一开始写了一个酷似扫描线的枚举左端点求最优右端点的一个东西，但是挂了，调不出来)

code

const int N=6e5+5;

struct Seg_Tree{
	int t[N<<2],tag[N<<2],c[N<<2];
	void pushup(int x){
		if(t[ls]>=t[rs])
			c[x]=c[ls],t[x]=t[ls];
		else
			c[x]=c[rs],t[x]=t[rs];
	}
	void pushdown(int x){
		t[ls]+=tag[x];
		tag[ls]+=tag[x];
		t[rs]+=tag[x];
		tag[rs]+=tag[x];
		tag[x]=0;
	}
	void update(int x,int l,int r,int L,int R,int a){
		if(L<=l&&r<=R){
			t[x]+=a;
			tag[x]+=a;
			return;
		}
		if(tag[x]!=0)
			pushdown(x);
		if(L<=mid)
			update(ls,l,mid,L,R,a);
		if(R>mid)
			update(rs,mid+1,r,L,R,a);
		pushup(x);
	}
	void build(int x,int l,int r){
		tag[x]=t[x]=0;
		if(l==r)
			c[x]=l;
		else{
			build(ls,l,mid);
			build(rs,mid+1,r);
			pushup(x);
		}
	}
}T;

struct upd{
	int l,r,x,w;
	bool operator<(upd ano)const{
		return x<ano.x;
	}
}Q[N];
int tot;

int X[N],len; 

int l[N],r[N];

signed main(){
	int n=read(),limit=1e9;
	for(int i=1;i<=n;i++){
		l[i]=read(),r[i]=read();
		X[++len]=l[i],X[++len]=r[i];
		X[++len]=min(limit,l[i]+1),X[++len]=max(0ll,l[i]-1);
		X[++len]=min(limit,r[i]+1),X[++len]=max(0ll,r[i]-1);
	}
	X[++len]=0,X[++len]=limit;
	sort(X+1,X+1+len);
	len=unique(X+1,X+1+len)-X-1;
	T.build(1,1,len);
	for(int i=1;i<=n;i++){
		l[i]=lower_bound(X+1,X+1+len,l[i])-X;
		r[i]=lower_bound(X+1,X+1+len,r[i])-X;
		if(l[i]>1&&l[i]+1<=r[i]-1){
			Q[++tot]={l[i]+1,r[i]-1,1,1};
			Q[++tot]={l[i]+1,r[i]-1,l[i],-1};
		}
		if(r[i]<len){
			Q[++tot]={r[i]+1,len,l[i]+1,1};
			Q[++tot]={r[i]+1,len,r[i],-1};
		}
	}
	sort(Q+1,Q+1+tot);
	pir ans={0,1};
	int mx=0;
	for(int i=1,j=1;i<=len;i++){
		while(j<=tot&&Q[j].x==i){
			T.update(1,1,len,Q[j].l,Q[j].r,Q[j].w);
			j++;
		}
		if(mx<T.t[1]){
			ans={X[i],X[T.c[1]]};
			mx=T.t[1];
		}
	}print(ans.fi),pc(' '),print(ans.se),pc('\n');
	return 0;
}

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

Link

考虑枚举其中一个最大值，然后求在这个最大值下另一个的最大值最小是多少。

后者就是一个每次插入一条边，求最小生成树。

最小生成树的边数是 $\mathrm{O(n)}$ 级别的，且一条边在插入后若有一时刻不存在于最小生成树中，则永远不会出现在最小生成树上。

直接维护边集，插入排序，复杂度是 $\mathrm{O(mn \lpha (n))}$ 。

code

const int N=2e2+5,M=5e4+5;

struct DSU{
	int fa[N],sum[N];
	void init(int n){
		for(int i=1;i<=n;i++)
			fa[i]=i,sum[i]=1; 
	}
	int fd(int x){
		return fa[x]==x?x:fa[x]=fd(fa[x]);
	}
	void merge(int x,int y){
		x=fd(x),y=fd(y);
		if(x!=y){
			if(sum[x]<sum[y])swap(x,y);
			fa[y]=x;
			sum[x]+=sum[y];
		}
	}
}D;

struct edge{
	int u,v,x,y;
	bool operator<(edge ano)const{
		return x<ano.x;
	}
}E[M],e[N];
int tot;
int n;
int tmp[N];

int mx;
bool tag;

void add(int id){
	for(int i=1;i<=tot+1;i++){
		if(e[i].y>E[id].y){
			tot++;
			for(int j=tot;j>=i;j--)
				swap(e[j],e[j+1]);
			e[i]=E[id];
			break;
		}
	}
\/\/	for(int i=1;i<=tot;i++)
\/\/		print(e[i].u),pc(' '),print(e[i].v),pc(' '),print(e[i].x),pc(' '),print(e[i].y),pc('\n');
	D.init(n);
	int cnt=0;
	mx=0;
	tag=0;
	for(int i=1;i<=tot;i++){
		int u=e[i].u,v=e[i].v;
		if(D.fd(u)!=D.fd(v)){
			mx=e[i].y;
			D.merge(u,v);
			tmp[++cnt]=i;
		}
	}
	if(cnt==n-1)
		tag=1;
	for(int i=1;i<=cnt;i++)
		e[i]=e[tmp[i]];
	tot=cnt;
	e[tot+1].y=inf;
}

signed main(){
	n=read();int m=read(),X=read(),Y=read();
	for(int i=1;i<=m;i++)
		E[i]={read(),read(),read(),read()};
	sort(E+1,E+1+m);
	int ans=inf;
	e[1].y=inf;
	for(int i=1;i<=m;i++){
		int j=i;
		while(j<=m&&E[j].x==E[i].x)
			add(j++);
		if(tag)
			ans=min(ans,E[i].x*X+mx*Y);
		i=j-1;
	}print(ans>=inf-2?-1:ans),pc('\n');
	return 0;
}

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

Link

发现应该枚举删除哪些字母，那么如何快速求出某一个删除方案的代价？

考虑拆贡献。对于一个位置 $r$ ，能与其产生代价的左边相邻点 $l$ 的个数为 $\mathrm{O(k)}$ 级别。

因为不能存在两个 $l$ 对应的字母相同。（因为这里如果需要靠前的 $l$ 与 $r$ 相邻就需要把靠后的 $l$ 删掉，但两者只能同时存在或同时被删除）

对于这个性质，可以用高维前缀和来预处理代价。所有包含在 $(l,r)$ 的字母都应被删除，还要保证 $l$ 和 $r$ 没被删除。容斥一下即可。

高维前缀和的原理是另一种处理前缀和的方式。二位前缀和一般采用容斥的方法来递推，但高维前缀和的维数太多，容斥就寄了。另一种方式是一位一位推，可以看代码。

值得注意的，两种方案不同当且仅当字符串不同，所以需要离散化。

code

const int N=2e5+5,M=24;

char s[N];

int v[M][M];

int frm[N][M];

int f[(1<<M)+5];

int w[M];

signed main(){
	int n=read(),m=read(),T=read();
	scanf("%s",s+1);
	for(int i=1;i<=m;i++)
		w[i]=read();
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++)
			v[i][j]=read();
	for(int i=1;i<=n;i++){
		int nw=s[i]-'A'+1;
		for(int j=1;j<=m;j++)
			frm[i][j]=frm[i-1][j];
		pir tmp[M];
		for(int j=1;j<=m;j++)
			tmp[j]={-frm[i][j],j};
		sort(tmp+1,tmp+1+m);
		int S=0;
		for(int j=1;j<=m&&tmp[j].fi!=0;j++){
			f[S]+=v[tmp[j].se][nw];\/\/中间被删掉
			f[S|(1<<(nw-1))]-=v[tmp[j].se][nw];\/\/不能包含右端点
			f[S|(1<<(tmp[j].se-1))]-=v[tmp[j].se][nw];\/\/不能包含左端点
			f[S|(1<<(nw-1))|(1<<(tmp[j].se-1))]+=v[tmp[j].se][nw];\/\/同时包含被减了两次，加回来
			S|=(1<<(tmp[j].se-1));
			if(tmp[j].se==nw)\/\/不加也行
				break;
		}
		frm[i][nw]=i;
	}
	int all=(1<<m)-1;
	for(int i=1;i<=m;i++)\/\/先枚举维再枚举数字，一维一维推，不重。
		for(int k=0;k<=all;k++)
			if(k&(1<<(i-1)))
				f[k]+=f[k^(1<<(i-1))];
	int ans=0;
	for(int k=0;k<all;k++){
		int sum=0;
		for(int l=k;l;l^=lowbit(l))
			sum+=w[__lg(lowbit(l))+1];\/\/其实这个代价可以看作是删除方案包含了这一个字符，可以直接一起与前面的容斥处理
		ans+=f[k]+sum<=T;
	}print(ans),pc('\n');
	return 0;
}

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

Link

设 $f_i$ 表示以第 $i$ 天作为某一段连续跑步的最后一天，设 $g_i=\max_{j=1}^if_i$ ，那么有转移方程 $f_i=\max_{j=i-k+1}^i g_{j-2}+w(j,i)-d(i-j+1)$ ，也即 $f_i=\max_{j=i-k+1}^i g_{j-2}+w(j,i)-(i+1)\times d+j\times d)$。

相当于枚举这段区间的左端点。$w(l,r)$ 表示从第 $l$ 天跑到第 $r$ 天能获得的能量补充。

第一项与最后一项可以直接取最值，第三项只跟 $i$ 有关无需考虑，中间那个 $w(l,r)$ 可以用扫描线维护。

但是跑步天数是 $n$ ，非常大，所以只能离散化。考虑到某一段跑步的最后一天一定是一个任务的完成日期，只保留这一天，为了方便扫描线也保留每个任务的开始日期。

转移的时候要注意那个 $g_{j-2}$ ，离散化后其实是把在 $i$ 前面且最后一个不与 $i$ 相邻的下标 $x$ 放到 $i$ 上，可以特判 $i-1$ 是否合法或直接二分。

注意转移顺序， $i$ 是可以从 $i$ 转移的，但 $f_i$ 只会从比 $i$ 小的位置转移。

我在实现的时候把 $f$ 和 $g$ 合并在一起了，感觉读起来更难也更容易出错，不建议合在一起写。

特别注意，在扫描线的时候，两维都是可以离散化的，但在枚举其中一维的时候要记得这一维有没有离散化，我就因为两维都离散化但却在枚举的时候判断的是离散化前的数字导致第一组大样例过不去（

code

const int N=2e5+5;

int X[N],len;

\/\/线段树实现了区间加，清空和区间查，为了美观不放上来了

struct upd{
	ll l,r,x,w;
	bool operator<(upd ano)const{
		return x<ano.x;
	}
}Q[N];
int tot;

ll f[N];

int x[N],y[N],w[N];

signed main(){
	signed c=read(),_T=read();
	while(_T--){
		len=tot=0;
		int n=read(),m=read(),k=read();ll d=read();
		for(int i=1;i<=m;i++){
			x[i]=read(),y[i]=read(),w[i]=read();
			X[++len]=x[i],X[++len]=x[i]-y[i]+1;
		}
		sort(X+1,X+1+len);
		len=unique(X+1,X+1+len)-X-1;
		for(int i=1;i<=m;i++){
			int l=lower_bound(X+1,X+1+len,x[i]-y[i]+1)-X;
			int r=lower_bound(X+1,X+1+len,x[i])-X;
			Q[++tot]={1,l,r,w[i]};\/\/就是这里，r是要枚举的那一维，我在这里存的是离散化后的值，但在后面判断却用了离散化前的值
		}
		sort(Q+1,Q+1+tot);
		for(int i=1,j=1;i<=len;i++){
			int lst=lower_bound(X+1,X+1+len,X[i]-1)-X-1;
			T.update(1,1,len,i,i,f[lst]+X[i]*d);\/\/更新第i个点的贡献
			
			while(j<=tot&&Q[j].x==i)\/\/这里是Q[j].x==i而不是Q[j].x==X[i]，就是上面说的离散化前与后的问题。
				T.update(1,1,len,Q[j].l,Q[j].r,Q[j].w),j++;\/\/扫描线
			
			int frm=lower_bound(X+1,X+1+len,X[i]-k+1)-X;
			f[i]=max(f[i-1],T.query(1,1,len,frm,i)-X[i]*d-d);\/\/取最值
		}print(f[len]),pc('\n');
		T.init(1,1,len);
	}
	return 0;
}

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

Link

这里会给出多种解法。

首先可以发现 $n,m\leq 1000$ 是骗人的，用鸽巢搞一下发现 $n+m-1\leq k$ ，范围很小可以直接搜。

但是直接只存左上角经过了哪些颜色进行暴力搜索会T，如何剪枝？

首先是可行性剪枝。如果剩下的可以用的颜色比从当前点往右下角走的步数还要少就直接寄了。

其次还有对称性。如果用一个这张棋盘上尚未出现的颜色，那么当前点是用这个颜色还是其他尚未出现过的颜色都是等价的。

根据这个有一个简单的基于dfs的实现。

code

const int N=12;

int apr[N][N]; 
int mp[N][N];
bool has[N];

int n,m,k;
int ans;

void dfs(int x,int y){
	if(y>m)
		x++,y=1;
	if(x>n){
		ans++;
		return;
	}
	apr[x][y]=apr[x][y-1]|apr[x-1][y];\/\/左上角颜色并
	if(k-__builtin_popcount(apr[x][y])<n-x+m-y+1)\/\/可行性
		return;
	if(mp[x][y]){\/\/已经填过了
		if(apr[x][y]&(1<<(mp[x][y]-1)))
			return;
		apr[x][y]|=1<<(mp[x][y]-1);
		dfs(x,y+1);
	}else{
		int sum=0;
		bool tag=0;
		for(int i=((1<<k)-1)^apr[x][y];i;i^=lowbit(i)){
			if(has[__lg(lowbit(i))+1]){\/\/已经出现过
				apr[x][y]|=lowbit(i);
				dfs(x,y+1);
				apr[x][y]^=lowbit(i);
			}else{\/\/尚未出现过
				has[__lg(lowbit(i))+1]=1;
				if(tag==0){\/\/还没计算过贡献
					sum=ans;\/\/留存快照
					apr[x][y]|=lowbit(i);
					dfs(x,y+1);
					apr[x][y]^=lowbit(i);
					sum=ans-sum;\/\/与之前快照做差
					tag=1;
				}else
					ans+=sum;\/\/所有没有用过的颜色在这里的贡献一样。
				has[__lg(lowbit(i))+1]=0;
			}
		}
	}
}

signed main(){
	n=read(),m=read(),k=read();
	if(n+m-1>k){
		print(0),pc('\n');
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			has[mp[i][j]=read()]=1;\/\/已经出现过的颜色
		}
	}
	dfs(1,1);
	print(ans%((int)1e9+7)),pc('\n');
	return 0;
}

还有一个tourist的程序实现。

他建立了若干映射，用当前枚举所填的颜色去映射到棋盘上已经实际填的颜色上去（当然可能实际什么都没填）。

最后判一下是否产生冲突即可。同时每一个没有实际对应颜色的填上的颜色都是可以随便填的。

放个代码

code by tourist

#include<bits\/stdc++.h>
using namespace std;
const int md=1000000007;
int n,m,k;
int ans=0;
int a[42][42];
int bad[42][42][42];
int res[42][42];
int mp[42];
void go(int row,int col,int mc)
{
	if(row==n)
	{
		for(int c=1;c<=mc;c++)
			for(int qc=c+1;qc<=mc;qc++)
				if(mp[c]!=0&&mp[qc]!=0&&mp[c]==mp[qc])\/\/看看有没有冲突
					return;
		int free=0,cols=k;\/\/free是自由元，没有实际映射颜色，可以随便填，cols则是还没有被实际填上的颜色（即被映射的颜色）
		for(int c=1;c<=mc;c++)
		{
			if(mp[c]==0)
				free++;\/\/c这个颜色没有实际对应颜色
			else
				cols--;\/\/有实际对应颜色，可用颜色减一
		}
		int cur=1;
		for(int c=1;c<=free;c++)
		{
			cur*=cols;\/\/自由元贡献
			cols--;
		}
		ans+=cur;
		if(ans>=md)
			ans-=md;
		return;
	}
	for(int c=1;c<=k&&c<=mc+1;c++)
	{
		if(bad[row][col][c])
			continue;\/\/左上角出现过这种颜色
		for(int x=row;x<n;x++)
			for(int y=col;y<m;y++)
				bad[x][y][c]++;\/\/给右下角打标记
		res[row][col]=c;
		int ok=1;
		if(a[row][col]!=0)\/\/有实际颜色
			if(mp[c]!=0&&mp[c]!=a[row][col])\/\/产生冲突
				ok=0;
		if(ok)
		{
			bool flag=false;
			if(mp[c]==0)\/\/还没有实际对应颜色
			{
				mp[c]=a[row][col];\/\/放上这一个位置实际填的颜色，当然也可能没填
				flag=true;
			}
			int nmc=c>mc?c:mc;
			if(col<m-1)
				go(row,col+1,nmc);
			else
				go(row+1,0,nmc);
			if(flag)
				mp[c]=0;
		}
		for(int x=row;x<n;x++)
			for(int y=col;y<m;y++)
				bad[x][y][c]--;
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	if(n+m-1>k)
	{
		printf("%d\n",0);
		return 0;
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d",&a[i][j]);
	go(0,0,0);
	printf("%d\n",ans);
	return 0;
}

还有一份代码，实现的比较美观。

它通过传参来记录当前方案可以通过交换颜色来达到多少种方案。

code by SergeyRogulenko

int t[10][10];
int d[10][10];
int a[10][10];
int64 res;
int n, m, k;
int s[1024];

void go(int x, int y, int cmask, int64 w, int rem) {\/\/分别表示到了哪里，用了哪些颜色，贡献与还有多少颜色没用过
	if (x == n) {
		res += w;\/\/加上当前方案的贡献
		return;
	}	
	int mask = 0;\/\/左上角的颜色
	if (x > 0)
		mask |= t[x-1][y];
	if (y > 0)
		mask |= t[x][y-1];
	if (mask & d[x][y]) return;\/\/与右下角产生冲突
	if (a[x][y] >= 0) {
	        t[x][y] = mask | (1 << a[x][y]);
		go(x + (y + 1) \/ m, (y + 1) % m, cmask, w, rem);
		return;
	}
	forn(i, k)
		if (!((mask|d[x][y]) & (1 << i)) && (cmask & (1 << i))) {\/\/枚举用过的颜色
			t[x][y] = mask | (1 << i);
			go(x + (y + 1) \/ m, (y + 1) % m, cmask, w, rem);\/\/直接搜
		}
	forn(i, k)
		if (!((mask|d[x][y]) & (1 << i)) && !(cmask & (1 << i))) {\/\/枚举没用过的颜色
			t[x][y] = mask | (1 << i);
			go(x + (y + 1) \/ m, (y + 1) % m, cmask | (1 << i), w * rem, rem-1);\/\/贡献数量增加，这个位置无论天rem里的哪一个颜色都是可以的，所以乘上rem
			break;\/\/搜一遍即可
		}
} 

int64 calc(int cmask) {
	res = 0;
	int rem = k;
	forn(i, k)
		if (cmask & (1 << i))
			rem--;
	go(0, 0, cmask, 1, rem);
	return res;
}

int main ()
{
	cin >> n >> m >> k;
	if (n + m - 1 > k) {
		cout << 0 << endl;
		return 0;
	}
	forn(i, n)
		forn(j, m) {
			cin >> a[i][j];
			a[i][j]--;
		}
	int cmask = 0;
	ford(i, n)
		ford(j, m) {
			int mask = 0;
			if (a[i][j] != -1) {
				mask |= 1 << a[i][j];
			}
			cmask |= mask;
			if (i + 1 < n) {
				d[i][j] |= d[i+1][j];	
			}
			if (j + 1 < m) {
				d[i][j] |= d[i][j+1];	
			}\/\/右下角
			if (d[i][j] & mask) {
				cout << 0 << endl;
				return 0;
			}
			d[i][j] |= mask;
		}
	cout << calc(cmask) % 1000000007 << endl;
	return 0;
}

上面的代码都是基于dfs，这题也能dp。

若从上到下，从左到右枚举的话，对于每一种颜色，我们只关心它最靠左的被填的位置的列下标。因为所有被填的数（不包括棋盘上已经有的）都在当前位置的上方（非严格），那么越靠左管辖区域就越大。

那么设 $f_{x,y,S}$ 表示到了 $(x,y)$ ，每一种颜色最靠左的下标为 $S$ 的方案数。

发现每一种颜色的下标都是 $[1,m+1]$ ，$m+1$ 表示从未使用过。这个范围很小，可以用四位二进制数存，这样 $S$ 的大小就是 $2^{4\times10}$ 左右。显然装不满。

可以用map或umap来存，转移的时候直接遍历上一个位置的所有 $S$ 。

我没写dp的版本，贴一个别人的代码。

code by tomasz.kociumaka

int a[50][50];
unordered_map<LL, int> M[100];

int us[10];

int main(){
	ios_base::sync_with_stdio(false);
    int n,m,k;
    cin >> n >> m >> k;
    if (n+m-1 > k) {
        cout << 0 << endl;
        return 0;
    }    
    REP(i, n) REP(j, m) {
        cin >> a[i][j];
        if (a[i][j] > 0) us[a[i][j]-1] = 1;
    }
    if (n < m) {
        REP(i, m) REP(j, i) swap(a[i][j], a[j][i]);
        swap(n,m);
    }
    if (n == 1 && m == 1) {
        if (a[0][0] == 0) {
            cout << k << endl;
            
        } else {
            cout << 1 << endl;
        }
        return 0;
    }
    int A = a[0][0];
    int B = a[n-1][m-1];
    if (A != 0) {
        REP(i, n) REP(j,m) {
            if (i == 0 && j == 0) continue;
            if (a[i][j] == A) {
                cout << "0" << endl;
                return 0;
            }
        } 
        us[A-1] = 0;
    }
    if (B != 0) {
        REP(i, n) REP(j, m) {
            if (i == n-1 && j == m-1) continue;
            if (a[i][j] == B) {
                cout << "0" << endl;
                return 0;
            }
        }
        us[B-1] = 0;
    }
    FOR(i, 1, k-1) {
        us[i] += us[i-1];
    }
    REP(i, n) REP(j, m) {
        if (a[i][j] != 0) a[i][j] = us[a[i][j]-1];
    }
    int mlt = 1;
    int rem = k-us[k-1];
    if (A == 0 && B == 0) mlt = rem*(rem-1);
    else if (A == 0 || B == 0) mlt = rem-1;
    \/\/以上部分都是把第一个和最后一个位置给扣掉，因为这两个位置独占两种颜色，剪掉能减低复杂度
    LL z = 0;
    REP(i, k) {
        z = 16* z + 11;
    }
    M[1][z] = 1;
    int ph = 1;
    REP(i, n) REP(j, m) {
        if (i == 0 && j == 0) continue;
        if (i == n-1 && j == m-1) continue;
        REP(l,k-2) {\/\/把两种颜色剪掉后就只有k-2种了
            if (a[i][j] > 0 && a[i][j] != l+1) continue;
            FORE(it, M[ph]) {
                LL v = it->X;
                LL c = (v>>(4*l))&15;
                if (((v>>(4*l))&15) <= j) continue;
                v ^= c<<(4*l);
                v |= j<<(4*l); 
                M[ph+1][v] += it->Y;
                M[ph+1][v] %= INF;
            }
        }
        ++ph; \/\/下一个位置
    }
    LL res = 0;
    FORE(it, M[ph]) {
        res += it->Y;
        res %= INF;
    }
    cout << (res*mlt)%INF << endl;\/\/乘上第一个和最后一个位置的贡献
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-07 10:38:56

Link

怎么还有德扑的，不会打。

你是职业选手吗？我觉得我是。

我的大体思路是多用几个结构体。卡牌有结构体，准备出的5张牌也有结构体，对于后者比较麻烦，我在里面放了一个opt来表示其属于哪种等级，还放了若干函数来判断是哪种牌型。

主函数则直接枚举剩下的两张的取值，然后7选5排下序，两边各出最强牌。

排序的cmp函数写的比较长（

另外实现了一个按字典序比较两个vector的函数，感觉会比较方便。

写了6.5K，感觉还行。长但是好写。

code

const int N=15;

bool t[1000];

struct card{\/\/牌
	int c,w;
	card(){c=w=0;}
	bool operator<(card ano)const{
		return w>ano.w;
	}
	void mkcard(char *ss){\/\/制作卡牌
		if(ss[1]=='C')
			c=1;
		if(ss[1]=='D')
			c=2;
		if(ss[1]=='H')
			c=3;
		if(ss[1]=='S')
			c=4;
		if(ss[2]=='T')
			w=10;
		else if(ss[2]=='J')
			w=11;
		else if(ss[2]=='Q')
			w=12;
		else if(ss[2]=='K')
			w=13;
		else if(ss[2]=='A')
			w=14;
		else
			w=ss[2]-'0';
		t[c*15+w]=1;
	}
}my[N],ur[N];


struct handin{\/\/准备要出的5张牌，姑且称为手牌
	int opt;\/\/牌型
	card p[7];\/\/牌
	bool samecol(){\/\/是否同花
		bool tag=1;
		for(int i=2;i<=5;i++)
			tag&=p[i].c==p[1].c;
		return tag;
	}
	int continuous(){\/\/是否是顺子（注意特判皇家顺）
		if(p[5].w==2&&p[4].w==3&&p[3].w==4&&p[2].w==5&&p[1].w==14)
			return 1;
		bool tag=1;
		for(int i=2;i<=5;i++)
			tag&=p[i].w==p[i-1].w-1;
		return (int)tag+(tag&&(p[1].w==14));
	}
	bool four(){\/\/是否有炸弹
		map<int,int>mp;
		for(int i=1;i<=5;i++)
			mp[p[i].w]++;
		for(auto i:mp){
			if(i.se==4)
				return 1;
		}return 0;
	}
	bool three(){\/\/是否有三张
		map<int,int>mp;
		for(int i=1;i<=5;i++)
			mp[p[i].w]++;
		for(auto i:mp){
			if(i.se==3)
				return 1;
		}return 0;
	}
	int two(){\/\/有几对
		int num=0;
		map<int,int>mp;
		for(int i=1;i<=5;i++)
			mp[p[i].w]++;
		for(auto i:mp){
			num+=i.se==2;
		}return num;
	}
	void load_handin(){\/\/加载牌型
		sort(p+1,p+6);
		if(samecol()&&continuous())\/\/同花顺&皇家同花顺 
			opt=8+continuous();
		else if(four())\/\/炸弹 
			opt=8;
		else if(three()&&two())\/\/三带二 
			opt=7;
		else if(samecol())\/\/同花 
			opt=6;
		else if(continuous())\/\/顺子 
			opt=5;
		else if(three())\/\/三 
			opt=4;
		else if(two()==2)\/\/两对 
			opt=3;
		else if(two()==1)\/\/一对 
			opt=2;
		else\/\/散牌
			opt=1;
	}
};

bool compare_less(handin a,handin b){\/\/比较两个vector
	for(int i=1;i<=5;i++)
		if(a.p[i].w!=b.p[i].w)
			return a.p[i].w>b.p[i].w;
	return 0;
}

bool cmp(handin a,handin b){\/\/比较两组牌谁更大，值得注意的是两组牌都是已经按照数字大小排过序的了（在load_handin函数里）
	if(a.opt!=b.opt)\/\/不同牌型
		return a.opt>b.opt;
	else{
		handin x,y;
		map<int,int> mpa,mpb;
		for(int i=1;i<=5;i++)
			mpa[a.p[i].w]++,mpb[b.p[i].w]++;
		if(a.opt==10)\/\/皇家同花顺 
			return 0;
		else if(a.opt==9){\/\/同花顺
			if(a.p[1].w==14)\/\/因为一定不是皇家同花顺，那么这里的14就是1，只要有出现就说明是最小顺子
				return 0;
			else if(b.p[1].w==14)
				return 1;
			else
				return a.p[1].w>b.p[1].w;
		}else if(a.opt==8){\/\/炸弹 
			for(auto i:mpa){
				if(i.se==4)
					x.p[1].w=i.fi;\/\/优先比炸弹谁大
				else
					x.p[2].w=i.fi;
			}
			for(auto i:mpb){
				if(i.se==4)
					y.p[1].w=i.fi;
				else
					y.p[2].w=i.fi;
			}
			return compare_less(x,y);
		}else if(a.opt==7){\/\/三带二 
			for(auto i:mpa){
				if(i.se==3)
					x.p[1].w=i.fi;\/\/优先比3张谁大
				else
					x.p[2].w=i.fi;
			}
			for(auto i:mpb){
				if(i.se==3)
					y.p[1].w=i.fi;
				else
					y.p[2].w=i.fi;
			}
			return compare_less(x,y);
		}else if(a.opt==6){\/\/同花 直接比
			return compare_less(a,b); 
		}else if(a.opt==5){\/\/顺子 注意区分皇家顺与最小顺的14地位
			if(a.continuous()!=b.continuous())
				return a.continuous()>b.continuous();
			if(a.p[1].w==14)
				return 0;
			else if(b.p[1].w==14) 
				return 1;
			else
				return a.p[1].w>b.p[1].w;
		}else if(a.opt==4){\/\/三 
			int nw=4;
			for(auto i:mpa){
				if(i.se==3)
					x.p[1].w=i.fi;\/\/先比3
				else
					x.p[--nw].w=i.fi;\/\/其次比最大的单牌，在遍历map的时候是先小后大，所以要反过来放
            }
			nw=4;
			for(auto i:mpb){
				if(i.se==3)
					y.p[1].w=i.fi;
				else
					y.p[--nw].w=i.fi;
			}
			return compare_less(x,y);
		}else if(a.opt==3){\/\/两对 
			int nw=3;
			for(auto i:mpa){
				if(i.se==2)\/\/先比大对子在比小对子最后单牌
					x.p[--nw].w=i.fi;
				else
					x.p[3].w=i.fi;
			}
			nw=3;
			for(auto i:mpb){
				if(i.se==2)
					y.p[--nw].w=i.fi;
				else
					y.p[3].w=i.fi;
			}
			return compare_less(x,y);
		}else if(a.opt==2){\/\/一对 
			int nw=5;
			for(auto i:mpa){
				if(i.se==2)
					x.p[1].w=i.fi;\/\/先比对子再比最大单，次大单，最小单
				else
					x.p[--nw].w=i.fi;
			}
			nw=5;
			for(auto i:mpb){
				if(i.se==2)
					y.p[1].w=i.fi;
				else
					y.p[--nw].w=i.fi;
			}
			return compare_less(x,y);
		}else
			return compare_less(a,b);\/\/单牌直接挨个比
	}
}

void readin(){
	char ys1[N],ys2[N],os1[N],os2[N];
	char tbll[4][N];
	scanf("%s",ys1+1);
	if(ys1[1]=='#')
		exit(0);
	scanf("%s%s%s",ys2+1,os1+1,os2+1);
	for(int i=1;i<=3;i++)
		scanf("%s",tbll[i]+1);
	my[1].mkcard(ys1);
	my[2].mkcard(ys2);
	ur[1].mkcard(os1);
	ur[2].mkcard(os2);
	my[3].mkcard(tbll[1]);
	my[4].mkcard(tbll[2]);
	my[5].mkcard(tbll[3]);
	ur[3].mkcard(tbll[1]);
	ur[4].mkcard(tbll[2]);
	ur[5].mkcard(tbll[3]);\/\/制作卡牌
}

handin tmp[1000];

signed main(){
	while(1){
		memset(t,0,sizeof(t));
		readin();
		int sum=0,win=0;
		for(int ic=1;ic<=4;ic++){
			for(int iw=2;iw<=14;iw++){\/\/枚举第一张牌
				if(t[ic*15+iw])
					continue;
				t[ic*15+iw]=1;
				my[6].c=ic,my[6].w=iw;
				ur[6].c=ic,ur[6].w=iw;
				for(int jc=1;jc<=4;jc++){
					for(int jw=2;jw<=14;jw++){\/\/第二张
						if(t[jc*15+jw])
							continue;
						my[7].c=jc,my[7].w=jw;
						ur[7].c=jc,ur[7].w=jw;
						handin mygo,urgo;\/\/两人准备要出的牌
						int all=(1<<7)-1;
						int tot=0;
						for(int k=1;k<=all;k++){
							if(__builtin_popcount(k)==5){
								int nw=0;
								++tot;
								for(int j=1;j<=7;j++)
									if(k&(1<<(j-1)))
										tmp[tot].p[++nw]=my[j];
								tmp[tot].load_handin();
							}
						}
						sort(tmp+1,tmp+1+tot,cmp);
						mygo=tmp[1];
						tot=0;
						for(int k=1;k<=all;k++){
							if(__builtin_popcount(k)==5){
								int nw=0;
								++tot;
								for(int j=1;j<=7;j++)
									if(k&(1<<(j-1)))
										tmp[tot].p[++nw]=ur[j];
								tmp[tot].load_handin();
							}
						}
						sort(tmp+1,tmp+1+tot,cmp);
						urgo=tmp[1];
						win+=cmp(mygo,urgo);\/\/直接比较即可
						sum++;
					}
				}
				t[ic*15+iw]=0;
			}
		}
\/\/		cout<<win<<" "<<sum<<endl;
		printf("%.10lf\n",1.0*win\/sum);
	}
	return 0;
}

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

Link

之前写的题解

发现每次删除或加入影响的点数量很少，考虑暴力将这些点拆出来再依次加入。

那么分为下标和高度两维考虑，分别开一个线段树，这样才能够让每次删除与插入达到 $\mathrm{O(\log n)}$ 的级别。

我用两个堆来存两维最小的 $10$ 棵树的信息。需要时刻注意这两个堆之间的联动关系，如删除的时候要注意另一个堆中的元素要删除（我用了一个标记数组），插入的时候要同时插入另一个堆。

答案又另开了一个可删堆来存，非常唐。

实际上答案直接从这两棵线段树中任一棵查一个全局最大值即可。

代码写得比之前要好读一些。

code

const int N=2e5+50;

struct Seg_Tree{
	int t[N<<2];
	void pushup(int x){t[x]=max(t[ls],t[rs]);}
	void update(int x,int l,int r,int c,int a){
		if(l==r){
			t[x]=a;
			return;
		}
		if(c<=mid)
			update(ls,l,mid,c,a);
		else
			update(rs,mid+1,r,c,a);
		pushup(x);
	}
	int query(int x,int l,int r,int L,int R){
		if(L<=l&&r<=R)
			return t[x];
		int mx=0;
		if(L<=mid)
			mx=max(mx,query(ls,l,mid,L,R));
		if(R>mid)
			mx=max(mx,query(rs,mid+1,r,L,R));
		return mx;
	}
}T1,T2;
bool tag[N];
priority_queue<pir>he,at;\/\/高度和下标的堆，插入和删除时要从这两个堆中找会影响到的数

pir tmp[15];int tot;

int f[N];
priority_queue<int>ans,del;

int lim;

void calc1(pir x){\/\/插入高度最小的
	int i=x.fi,h=x.se;
	f[i]=T1.query(1,1,lim,i+1,lim)+1;
	T1.update(1,1,lim,i,f[i]);
	T2.update(1,1,lim,h,f[i]);
	ans.push(f[i]);
	he.push({-h,i});
	
}

void calc2(pir x){\/\/插入下标最小的
	int i=x.fi,h=x.se;
	f[i]=T2.query(1,1,lim,h+1,lim)+1;
	T1.update(1,1,lim,i,f[i]);
	T2.update(1,1,lim,h,f[i]);
	ans.push(f[i]);
	at.push({-i,h});
}

int get_ans(){\/\/获取答案，这里的答案用了一个堆，这个堆需要支持删除元素，所以又开了个del
	while(!del.empty()&&ans.top()==del.top())
		ans.pop(),del.pop();
	if(ans.empty())\/\/WA on 2
		return 0;
	return ans.top();
}

signed main(){
	int n=read(),m=read();
	lim=m+10;
	for(int i=m;i>=1;i--){
		if(read()==1){
			int x=read(),height=read()+i;\/\/偏移
			tot=0;
			while(!he.empty()&&-he.top().fi<height){\/\/比自己矮的树
				if(!tag[he.top().se]){\/\/没被删过
					tmp[++tot].fi=he.top().se,tmp[tot].se=-he.top().fi;
					del.push(f[tmp[tot].fi]);
					T1.update(1,1,lim,tmp[tot].fi,0);
					T2.update(1,1,lim,tmp[tot].se,0);\/\/删除
				}
				he.pop();
			}
			tmp[++tot]={x,height};\/\/插入
			at.push({-x,height});\/\/另一个堆也要记得插入
			while(tot)\/\/剩下的插回树上
				calc1(tmp[tot--]);
		}else{
			int x=read();
			tot=0;
			while(!at.empty()&&tot<x){
				tmp[++tot].fi=-at.top().fi,tmp[tot].se=at.top().se;\/\/必定没被删除过
				del.push(f[tmp[tot].fi]);
				T1.update(1,1,lim,tmp[tot].fi,0);
				T2.update(1,1,lim,tmp[tot].se,0);\/\/删除
				at.pop();
			}
			tag[tmp[tot].fi]=1;\/\/删除标记
			f[tmp[tot].fi]=0;\/\/清空
			tot--;\/\/删掉这个元素
			while(tot)\/\/插回来
				calc2(tmp[tot--]);
		}
		print(get_ans()),pc('\n');
	}
	return 0;
}