专栏文章

0610

CCap1taL
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip3xj81
此快照首次捕获于
2025/12/03 05:45
3 个月前
此快照最后确认于
2025/12/03 05:45
3 个月前
查看原文

NFLS T2

大好题啊，属于是应该会做的题了。还是脑子没转过来那个思路
转化前的题意很抽象，写个暴力 n!n! 就能发现真实题意是：
  • 给定长度为 nn 数组 aia_i，要求计数有多少 nn 的排列 PP，满足对于每个最长连续 +1+1 段和连续 −1-1 段 [l,r][l,r]，有 r−l+1≥min⁡i∈[l,r]aPi+1r-l+1\ge\min_{i\in[l,r]}a_{P_i}+1
  • 说人话就是，把排列画在坐标系里，每个 yy 有个限制 aa，要求对于每个最长斜率为 11 的线段，它的长度不能超过涵盖的 yy 的 aa 而已
  • n≤5000n\le 5000
考试的时候唐到家了啊，一直想不出来 poly(n)poly(n) 的做法。一直在思考基于最后序列的 DP。其实也不是，就是思路没转变过来吧
会注意到，这个形式非常好看，每个连续段在值域上是一个连续段
这提示我们在值域上 DP，而不去考虑每个位置放什么东西。
做过这么多划分区间的题，容易有个模糊的思路是，枚举到 ii，就钦定 ii 是最后一段的末尾，尝试枚举左端点 jj，看看能不能转移。aia_i 的限制在这里可以解决。
如果能想到这一步，应该就能想到，先不考虑、也没法考虑这些段在最终序列的位置关系，应该能发现最后乘个阶乘就能大概解决问题
于是记录段数就必不可少了，多了一维，没关系，n≤5000n\le 5000
然后就又发现了一些小问题：
  1. 我们在划分值域，但每一段在最终的序列里，有可能是升序的，也有可能是降序的
  2. 最后如果直接乘段数的阶乘，有可能某些段会连在一起，这就爆炸了，我们的判断全失效了
直觉会告诉我们第一个问题应该好解决，可能有个 22 之类的系数而已，或者得讨论讨论，先暂时不去深究它
对于第二个问题，会发现从阶乘里直接扣掉非法情况这种思路非常完蛋，这太困难了，得记录 O(想想就要炸)O(想想就要炸) 的信息
于是这个时候应该考虑容斥！！
于是这个时候应该考虑容斥！！
于是这个时候应该考虑容斥！！
唉，容斥。唉，容斥。唉，容斥。唉，容斥。
我们想要的是没有任何两段接起来的情况，即重排后值域段的连接数为 00
于是我们可以钦定某些值域段的衔接处必须连接。考虑暴力做法，再开一个维度记录钦定了多少位置就可以了。然后按套路立马发现这个东西很蠢，我们只关心奇偶性来判断 (−1)N(-1)^N，可以在 转移的时候直接取负转移的时候直接取负，也可以开个 0101 状态啥的，这个无所谓了。
现在要解决第一个问题，会发现我们实际上是在思考一些转移细节。一开始想的是对于转移时枚举的每个段，如果长度大于 11 就有个 22 的系数，代表翻还是不翻。然后能察觉，因为我们钦定了一些位置相接，每一段各自翻似乎变得特别抽象，有可能出现值域上不可能相接的情况。第二维度的状态定义还出了问题，如果钦定了连接，重排阶乘数就变了
然后重新理一下思路，会发现，钦定的连接构成了很多 "大段"，可能包含很多小段。小段是真的分段，大段则是容斥的产物。对 aa 的限制是小段内的，但翻转与否是整个大段的问题，因为连接之后一翻都得翻。只有大段长度超过 11 才有 22 的系数。最后的阶乘是对大段数做的。
再之后就简单了。分配一些贡献：让翻转 22 的系数在大段末尾结算，这是合理的；大段的累计在段首或段尾都可以，选择和翻转一起在段尾处理
然后会发现，转移时炸了，我们从前面的某个小段尾转移过来，如果我们希望我们开启一个新的大段，那就需要给上一段结算——翻转系数是必须在段尾结算的，但我们发现我们不知道上一个大段有多长，得再记录一个维度表示所处大段的长度。
再仔细想一下，会发现我们的翻转系数很特殊，几乎都为 22，只有大段长度为 11 时才为 11。于是可以把记录大段长度的维度改为 O(1)O(1) 的，毕竟我们只关心它是不是 11。现在状态数就是 O(n2)O(n^2) 的了。转移容易优化到 O(1)O(1)
一个更优雅但似乎不自然的办法是记录当前段是否是大段尾，好做很多。但本质上来说只是让贡献结算提前了而已，应该没什么区别。而且如果翻转系数不那么简单（长度为 11 才是 11）这个办法就炸了，还是得考虑有多少大段长有用。
CPP
int n;
int a[MAXN];

int f[5005][5005][2];

int fac[5005];

int gmin(int l,int r){
	int ret=INT_MAX;
	foru(i,l,r){
		chkmin(ret,a[i]);
	}
	return ret;
}

void solve(bool SPE){ 
	n=RIN;
	foru(i,1,n){
		a[i]=RIN;
	}
	
	fac[0]=1;
	foru(i,1,n){
		fac[i]=mul(fac[i-1],i);
	}


	static int s[5005][5005];

	f[0][0][1]=1;
	s[0][0]=1;

	foru(i,1,n){
		int mn=a[i];
		int l=i;

		ford(k,i-1,1){
			chkmin(mn,a[k]);
			if(i-k+1>=mn+1)	break;
			l=k;
		}
		foru(j,0,i){
			
			if(i-2>=0){
				if(j>0){
					mdd(f[i][j][1],mul(s[i-2][j-1],2));
				}
				mdd(f[i][j][0],s[i-2][j]);

				if(l-2>=0){
					if(j>0){
						mmv(f[i][j][1],mul(s[l-2][j-1],2));
					}
					mmv(f[i][j][0],s[l-2][j]);
				}
			}
			// foru(k,l-1,i-2){
			// 	if(j>0){
			// 		mdd(f[i][j][1],mul(rmv(f[k][j-1][1],f[k][j-1][0]),2));
			// 	}

			// 	mdd(f[i][j][0],rmv(f[k][j][1],f[k][j][0]));
			// }


			
			if(j>0){
				mmv(f[i][j][1],mul(f[i-1][j-1][0],2));
				mdd(f[i][j][1],mul(f[i-1][j-1][1],1));
			}

			mmv(f[i][j][0],f[i-1][j][0]);
			mdd(f[i][j][0],f[i-1][j][1]);

			s[i][j]=add(s[i-1][j],rmv(f[i][j][1],f[i][j][0]));
		}
	}

	int ans=0;
	foru(i,0,n){
		mdd(ans,mul(f[n][i][1],fac[i]));
	}

	cout<<ans;

	return ;
}

NFLS T3 (AT_codefestival_2016_final_j)

一轮省集原题。当时没补。
有一个NN行，NN列的正方形，共 N × NN\ \times\ N 个空格。
可以从上下左右四个方向推入方块，共 4 × N4\ \times\ N 个插入口，编号为：
  • 上侧从左到右U1, U2, ..., UNU1,\ U2,\ ...,\ UN
  • 下侧从左到右:D1, D2, ..., DND1,\ D2,\ ...,\ DN
  • 左侧从上到下: L1, L2, ..., LNL1,\ L2,\ ...,\ LN
  • 右侧从上到下：R1, R2, ..., RNR1,\ R2,\ ...,\ RN
如图是插入口的编号，方块可以推动其他方块，使其往推入方向移动一格，但不能把方块推出正方形外。
你有 N × N 个方块，全部都要推入正方形内。每个插入口的推入次数有一定的限制， UiU_i只能推入UiU_i次， DiD_i只能推入DiD_i次，LiL_i只能推入LiL_i次，RiR_i只能推入RiR_i次。 你需要判断这样推入是否可行，如果可行请输出一种方案
n≤300n\le 300

题解

没啥好解的。首先只要写暴力就会意识到，推箱子很唐，改称每次在最近空位上放一个更对。容易发现这样做之后有大好处，每个箱子一经放置一定固定。
于是每个箱子都会来自一个方向，考虑先为每个箱子分配一个方向，用网络流实现，最大流必须是 n2n^2 不然当场炸了。
现在来构造方案。唯一的限制就是，对于一个箱子，它来的方向的箱子必须都比他早放。把限制关系建边，如果是DAG就结束了。问题在如果不是DAG怎么办。
考虑一个环，发现可以通过公式化调整使得这个环爆炸。具体的，让环上每个点指向的方向变成访问它的方向。
但复杂度呢？会注意到调整一个环一定会使得 ∑u(u到它对应方向边界的距离)\sum_u(u到它对应方向边界的距离) 减小一个环长。而这个东西最大就是 n3n^3 的，这就对了。
于是只要能每次都快速找环就行了，或者说，找环的代价和环长同级别就行了，直接 dfs 找环。容易验证一个点如果不在环里，那它之后不会再参与到新环里。转出来的点也是有可能成环的，这个需要保留
O(n3)O(n^3)，感觉最后的均摊有点巧妙。
CPP
int n;
int U[MAXN];
int D[MAXN];
int L[MAXN];
int R[MAXN];

ISAP<500*500+500*5,500*500*10,int,INT_MAX> g;

int gid(int x,int y){
	return n*(x-1)+y;
}
int goid(char dr,int i){
	switch (dr)
	{
	case 'U':
		return n*n+i;
	case 'D':
		return n*n+n+i;
	case 'R':
		return n*n+n*2+i;
	case 'L':
		return n*n+n*3+i;
	}
	exit(1);
}

int to[505][505];
void out(int id){
	int x=(id-1)/n+1;
	int y=id-(x-1)*n;
	// cerr<<' '<<x<<' '<<y<<endl;
	cout<<"UDRL"[to[x][y]];
	if(to[x][y]==0 || to[x][y]==1){
		cout<<y;
	}else{
		cout<<x;
	}
	cout<<'\n';
}

vector<int> dp[505*505];

void solve(bool SPE){ 
	n=RIN;
	foru(i,1,n){
		U[i]=RIN;
	}
	foru(i,1,n){
		D[i]=RIN;
	}
	foru(i,1,n){
		L[i]=RIN;
	}
	foru(i,1,n){
		R[i]=RIN;
	}

	g.set(n*n+4*n+2,n*n+4*n+1,n*n+4*n+2);
	static int id[505][505][4];
	foru(i,1,n){
		foru(j,1,n){
			g.add_edge(g.S(),gid(i,j),1);
			id[i][j][0]=g.add_edge(gid(i,j),goid('U',j),1);
			id[i][j][1]=g.add_edge(gid(i,j),goid('D',j),1);
			id[i][j][2]=g.add_edge(gid(i,j),goid('R',i),1);
			id[i][j][3]=g.add_edge(gid(i,j),goid('L',i),1);
		}
	}
	foru(i,1,n){
		g.add_edge(goid('U',i),g.T(),U[i]);
		g.add_edge(goid('D',i),g.T(),D[i]);
		g.add_edge(goid('R',i),g.T(),R[i]);
		g.add_edge(goid('L',i),g.T(),L[i]);
	}

	int num=g.maxflow();

	if(num!=n*n){
		cout<<"NO";
		return ;
	}
	
	foru(i,1,n){
		foru(j,1,n){
			foru(c,0,3){
				if(g.qry_w(id[i][j][c])!=1){
					to[i][j]=c;
					break;
				}
			}
			// cout<<to[i][j];
		}
		// HH;
	}
	
	static bool vis[505][505];
	static stack<pair<pair<int,int>,int>> st;
	static bool in[505][505];
	auto dfs=[](auto& dfs,int u,int v,int come)->void {
		in[u][v]=1;
		st+=mkp(mkp(u,v),come);
		// cein<<"pushed "<<mkp(mkp(u,v),come)<<endl;

		auto tryout=[&u,&v,&dfs](int x,int y)->bool {
			if(vis[x][y])	return false;

			// cerr<<u<<' '<<v<<" tryout "<<x<<' '<<y<<endl;
			if(in[x][y]){
				// cerr<<u<<' '<<v<<" boom "<<x<<' '<<y<<endl;
				// cerr<<"change "<<x<<" "<<y<<" from "<<to[x][y]<<" to "<<to[u][v]<<endl;
				to[x][y]=to[u][v];
				while(1){
					auto [p,q]=st.top().fi;
					int dr=st.top().se;
					// cerr<<"take out "<<p<<' '<<q<<' '<<dr<<endl;
					st.pop();
					in[p][q]=0;
					if(p==x && q==y){
						break;
					}else{
						// cerr<<"change "<<p<<" "<<q<<" from "<<to[p][q]<<" to "<<dr<<endl;
						to[p][q]=dr;
					}
				}
				return true;
			}
			while(!vis[x][y]){
				dfs(dfs,x,y,to[u][v]);
				if(in[u][v]==0)	return true;	
			}
			return false;
		};

		switch (to[u][v])
		{
		case 0:
			foru(i,1,u-1){
				if(tryout(i,v))	return ;
			}
			break;
		case 1:
			foru(i,u+1,n){
				if(tryout(i,v))	return ;
			}
			break;
		case 2:
			foru(i,v+1,n){
				if(tryout(u,i))	return ;
			}
			break;
		case 3:
			foru(i,1,v-1){
				if(tryout(u,i))	return ;
			}
			break;
		}
		assert(in[u][v]==1);
		in[u][v]=0;
		vis[u][v]=1;
		// cerr<<"exit "<<u<<' '<<v<<endl;
		// cein<<"exitpop "<<st.top()<<endl;
		st.pop();
	};
	foru(i,1,n){
		foru(j,1,n){
			if(vis[i][j])	continue;
			while(!vis[i][j]){
				dfs(dfs,i,j,-1);
			}
		}
	}
	// dfs(dfs,3,2,1);
	// foru(i,1,n){
	// 	foru(j,1,n){
	// 		cout<<to[i][j];
	// 	}
	// 	HH;
	// }

	// exit(0);

	foru(i,1,n){
		foru(j,1,n){
			switch (to[i][j])
			{
			case 0:
				foru(k,1,i-1){
					dp[gid(k,j)]+=gid(i,j);
				}
				break;
			case 1:
				foru(k,i+1,n){
					dp[gid(k,j)]+=gid(i,j);
				}
				break;
			case 2:
				foru(k,j+1,n){
					dp[gid(i,k)]+=gid(i,j);
				}
				break;
			case 3:
				foru(k,1,j-1){
					dp[gid(i,k)]+=gid(i,j);
				}
				break;
			}
		}
	}

	static queue<int> q;
	static int d[505*505];
	foru(u,1,n*n){
		for(auto v:dp[u]){
			d[v]++;
		}
	}
	foru(u,1,n*n){
		if(d[u]==0){
			q.push(u);
		}
	}
	while(!q.empty()){
		int u=q.front();
		q.pop();
		out(u);
		for(auto v:dp[u]){
			d[v]--;
			if(d[v]==0){
				q.push(v);
			}
		}
	}



	return ;
}

ISAP

感觉各种算法都应该模板化一点，自己简单备一个 ISAP 的板子
只有我觉得 ISAP 比 Dinic 更符合人类直觉吗
首先从 tt 到 ss 给图分层，之后只在不同层之间跑流量
那又要说了，这不炸了吗，同层的边不都没了？所以如果一个点出边流量都跑完了，把它往更高层上提一个单位
CPP
gap[dep[u]]--;
if(gap[dep[u]]==0)	dep[s]=n+1;	//断层了炸了，不用流了
dep[u]++;
gap[dep[u]]++;
这使得它可以继续流同层的流量了，对的不能再对了，这有哪里不对吗
跑的还快还好写，拿来求最大流很对了
CPP
template<int N,int M,class D,D INF>
class ISAP{
	struct edge{
		int v;
		int nxt;
		D w;
	}e[M*2+5];
	int ecnt=1;
	int head[N+5],cur[N+5],dep[N+5],gap[N+5];
	int n,s,t;

	void add_e(int u,int v,D w){
		e[++ecnt]={v,head[u],w};
		head[u]=ecnt;
	}

	void bfs(){
		static queue<int> q;
		while(!q.empty())	q.pop();
		foru(i,1,n)	dep[i]=-1,gap[i]=0;
		dep[t]=0,gap[0]=1;
		q.push(t);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=head[i];i;i=e[i].nxt){
				int v=e[i].v;
				if(dep[v]!=-1)	continue;
				dep[v]=dep[u]+1;
				gap[dep[v]]++;
				q.push(v);
			}
		}
	}
	D dfs(int u,D flow){
		if(u==t)	return flow;
		D used=0;
		for(int &i=cur[u];i;i=e[i].nxt){
			int v=e[i].v;
			if(e[i].w==0 || dep[u]!=dep[v]+1)	continue;
			D x=dfs(v,min(flow-used,e[i].w));
			e[i].w-=x;
			e[i^1].w+=x;
			used+=x;
			if(used==flow)	return used;
		}
		gap[dep[u]]--;
		if(gap[dep[u]]==0)	dep[s]=n+1;
		dep[u]++;
		gap[dep[u]]++;
		return used;
	}
public:
	void clear(){
		foru(i,1,n)	head[i]=dep[i]=gap[i]=0;
		n=s=t=0;
		ecnt=1;
	}
	void set(int _n,int _s,int _t){
		n=_n,s=_s,t=_t;
	}
	int add_edge(int u,int v,D w){
		add_e(u,v,w);
		add_e(v,u,0);
		return ecnt-1;
	}
	int S()const{
		return s;
	}
	int T()const{
		return t;
	}
	D qry_w(int id)const{
		return e[id].w;
	}
	D maxflow(){
		bfs();
		D flow=0;
		while(dep[s]<n){
			foru(i,1,n)	cur[i]=head[i];
			flow+=dfs(s,INF);
		}
		return flow;
	}
};


ISAP<500,100000,LL,1e18> g;

g.set(N,S,T)

int edgeid=g.add_edge(g.S(),x,1);
g.add_edge(x,g.T(),1);

cout<<g.maxflow()<<endl;
cout<<g.qry_w(edgeid)<<endl;
这很好了

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...