t1 - 生活在树上 tree

​ 小忆和小艾生活在树上。这颗树 \(T\) 有 \(n\) 个节点，由 \(n-1\) 条边连接。现在树上有一个排列 \(p\) ，每次小艾可以选择一条边 \((u,v)\in T\)，将 \(p_u\) 与 \(p_v\) 交换，小艾的任务是将排列完成排序。为了估算自己至少要交换多少次，小艾找小忆请教，小忆经过思考，写下了这个式子：

\[\frac{1}{2}\sum\limits_{i=1}^{n} dist(i,p_i) \]

​ 小艾经过尝试，发现很巧的是，当前的这个排列刚好达到了小忆给出的下界！他想考考你，你能不能给出一个达到这一下界的排序方案呢？特别地，她还希望你给出的方案的字典序最小。我们认为树上的边是从 \(1\) 至 \(n-1\) 编号的，方案的字典序是由依次比较操作的边的编号决定的。

\(1\leq n\leq 10^3\)

考虑这个式子，这个 \(\frac{1}{2}\) 就非常具有暗示性，说明一次 swap ，可以帮助两个数离终点跟进一步.

题目中保证这个排列刚好达到了给出的下界，说明，存在一种方法，可以使得每一次 swap 都能使两个数离终点更近一步 .

考虑什么方案能使得达到给出的下界，必定是不存在两个相交但不包含的链的 \((a,b)\)，\((c,d)\)，其中 \(a\) 是 \(c\) 的祖先，\(b\) 是 \(d\) 的祖先，\(a\) 是 \(c\) 的祖先，\(b\) 是 \(d\) 的祖先 .

那么，一个合法的方案必定任意任意一次正确的交换都对之后的操作没有影响 .

因此，考虑维护一个 priority_queue ，把每条能进行正确操作的边放入 \(q\) 中 .

每次弹出栈顶的元素，删除，考虑交换之后会对造成那些新边是可以被正确操作的 ，放入 \(q\) .

这个过程有点复杂 . 写的时候要好好考虑 .

时间复杂度 : \(O(n^2\log n^2)\)

空间复杂度 : \(O(n^2)\)

code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	int res=0;
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}	
	return res;
}
inline void print(int res){
	if(res==0){
		putchar('0');
		return;
	}
	int a[10],len=0;
	while(res>0){
		a[len++]=res%10;
		res/=10;
	}
	for(int i=len-1;i>=0;i--)
		putchar(a[i]+'0');
}
int n;
int p[1010],a[1010];
vector<pair<int,int> >g[1010];
vector<pair<int,int> >e;
vector<int>v[1010]; 
priority_queue<int>q;
vector<int>ans;
bool dfs(int x,int fa,int t){
	if(x==t)return true;
	for(int i=0;i<(int)g[x].size();i++){
		int to=g[x][i].first,id=g[x][i].second;
		if(to==fa)continue;
		if(dfs(to,x,t)){
			v[t].push_back(id);
			return true;
		}
	} 
	return false;
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n=read();
	for(int i=0;i<n-1;i++){
		int u=read()-1,v=read()-1;
		g[u].push_back(make_pair(v,i));
		g[v].push_back(make_pair(u,i));
		e.push_back(make_pair(u,v));
	}
	for(int i=0;i<n;i++)a[i]=read()-1;
	for(int i=0;i<n;i++)p[a[i]]=i;
	for(int i=0;i<n;i++){
		dfs(p[i],-1,i);
	}
	for(int i=0;i<(int)e.size();i++){
		int x=e[i].first,y=e[i].second;
		if(v[a[x]].back()==i&&v[a[y]].back()==i){
			q.push(-i);
		}
	}
	while(!q.empty()){
		int id=-q.top();q.pop();
		ans.push_back(id);
		int x=e[id].first,y=e[id].second;
		swap(a[x],a[y]);
		v[a[x]].pop_back();
		v[a[y]].pop_back();
		if(v[a[x]].size()>0){
			id=v[a[x]].back();		
			int nx=e[id].first,ny=e[id].second;
			if(a[nx]==a[x])swap(nx,ny);
			if(v[a[nx]].back()==id)q.push(-id);
		}
		if(v[a[y]].size()>0){
			id=v[a[y]].back();
			int nx=e[id].first,ny=e[id].second;
			if(a[nx]==a[y])swap(nx,ny);
			if(v[a[nx]].back()==id)q.push(-id);
		}
	} 
	for(int i=0;i<(int)ans.size();i++){
		print(ans[i]+1);
		if(i!=(int)ans.size()-1)putchar(' ');
		else putchar('\n');
	}
	return 0;
}
/*inline? ll or int? size? min max?*/
/*
5
5 2
3 2
2 4
1 3
2 1 5 3 4
*/

来源 : nflsoj 20034 #10316. 「2020联考北附2」生活在树上

t3 - 大过滤器 filter

在本题中，我们认为文明存在 \(n\) 个级别，而这 \(n\) 个级别又被划分为 \(k\) 个阶段。具体地，我们有数组\(L_0,L_1,\cdots,L_k\)，满足 \(0 =L_0<L_1<\cdots <L_k=n\)，其中第 \(L_{j-1}+1\)到第 \(L_j\) 个文明级别被认为是处于阶段 \(j\) 的。

我们认为一张有向图 \(G=(V,E)\) 刻画了文明可以通过什么手段达到最终级别。若 \((x,y)\in E\)，则说明处于 \(x\) 级别的文明可以尝试进步到 \(y\) 级别（注意这里并不保证 \(x<y\) ！）特别地，由于大过滤器的存在，设 \(x\) 是 \(j\) 阶段的文明，那么y只可能处于 \(j\) 阶段或者 \(j+1\) 阶段，如果 \(y\) 也属于 \(j\) 阶段，那么我们认为这是一次“常规进步”，否则 \(y\) 属于 \(j+ 1\) 阶段，我们认为这是一次“危险进步”。

我们认为现在人类文明所处的级别为 \(1\) 级别，我们的目标是达到 \(i\) 级别，我们需要规划一个进步方案。方案可以表示为 \(1\) 到 \(n\) 的一条路径，我们如此定义一种方案的困难程度：设计数器初始有 \(s=0\) ，我们按顺序考虑这条路径，每次发生一次“常规进步”，那么 \(s\rightarrow s+1\) ，每次发生一次“危险进步”，那么 \(s\to s+2\) ；最后的s值就是该进步方案的困难程度。

对于每个 \(1\leq i\leq n\)，请你判断是否存在一种从 \(1\) 级别进步至 \(i\) 级别的方案，如果存在，那么请规划一种方案使得困难程度最小。输出困难程度 \(\mod 998244353\) .

\(2\leq k\leq n\leq 3\times 10^5,1\leq m\leq 5\times 10^5\)

现在的问题就是 \(s\) 很大，不用高精度，怎么办？

考虑分层 \(bfs\) .

对于每层中，差距不会超过 \(m\) .

那么，不会的是 \(\times 2\) 的边 .

其实，只需要给每个点赋上一个新的值使得当前值不会太大，但是，能够保证比较大小时不会出错 .

那么，可以想到先排序，从大到小每一个值，如果比前面一个值差距 \(d<m\) ，那么，保存原样，否则，当前值是前一个值 \(+m\) .

这样，\(2\times m\) 之后，在下一层，不管怎样，前一个值跟新节点时始终比后一个值小 .

感觉有些妙妙 .

所以，只需要分层 \(bfs\) 之后离散化一下重新赋值就可以了 ，感觉比 t1 简单 .

时间复杂度 : \(\mathrm O(n+m+n\log n)\)

空间复杂度 : \(O(n+m)\)

code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	int res=0;
	while(ch>='0'&&ch<='9'){
		res=(res<<3)+(res<<1)+ch-'0';
		ch=getchar();
	}
	return res;
} 
inline void print(int res){
	if(res==0){
		putchar('0');
		return;
	}
	int a[10],len=0;
	while(res>0){
		a[len++]=res%10;
		res/=10;
	}
	for(int i=len-1;i>=0;i--)
		putchar(a[i]+'0');
}
const long long inf=1e18+10;
const int mod=998244353;
int n,m,k;
int lv[300010],L[300010];
vector<int>g[300010],v[300010];
int a[300010];
long long dis[300010];
priority_queue<pair<long long,int> >q;
int fr[300010];
vector<int>nei[300010];
void get_dis1(int level){
	while(!q.empty())q.pop();
	for(int i=0;i<(int)v[level].size();i++){
		int x=v[level][i];
		if(dis[x]!=inf)q.push(make_pair(-dis[x],x));
	}
	while(!q.empty()){
		long long cost=-q.top().first;
		int x=q.top().second;
		q.pop();
		if(cost>dis[x])continue;
		for(int i=0;i<(int)g[x].size();i++){
			int to=g[x][i];
			if(lv[x]!=lv[to])continue;
			if(dis[to]>dis[x]+1){
				dis[to]=dis[x]+1;
				fr[to]=x;
				q.push(make_pair(-dis[to],to));
			}
		}
	}
	vector<long long>tmp;
	for(int i=0;i<(int)v[level].size();i++){
		int x=v[level][i];
		if(dis[x]!=inf)tmp.push_back(dis[x]);
	}
	sort(tmp.begin(),tmp.end());
	tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
	vector<long long>nw;
	nw.push_back(0);
	for(int i=1;i<(int)tmp.size();i++){
		if(tmp[i]-tmp[i-1]<m)nw.push_back(nw.back()+tmp[i]-tmp[i-1]);
		else nw.push_back(nw.back()+m);
	}
	for(int i=0;i<(int)v[level].size();i++){
		int x=v[level][i];
		if(dis[x]!=inf){
			int id=lower_bound(tmp.begin(),tmp.end(),dis[x])-tmp.begin();
			dis[x]=nw[id];
		}
	}
}
void get_dis2(int level){
	for(int i=0;i<(int)v[level].size();i++){
		int x=v[level][i];
		if(dis[x]==inf)continue;
		for(int j=0;j<(int)g[x].size();j++){
			int to=g[x][j];
			if(lv[to]==lv[x]+1){
				if(dis[to]>dis[x]*2){
					dis[to]=dis[x]*2;
					fr[to]=x;
				}
			}
		}
	}
}
void dfs(int x){
	for(int i=0;i<(int)nei[x].size();i++){
		int to=nei[x][i];
		if(lv[to]==lv[x]&&fr[to]==x){
			dis[to]=(dis[x]+1)%mod;
		}
		if(lv[to]==lv[x]+1&&fr[to]==x){
			dis[to]=(dis[x]+dis[x])%mod;
		}
		dfs(to);
	}
}
int main(){
	freopen("filter.in","r",stdin);
	freopen("filter.out","w",stdout);
	n=read();m=read();k=read();
	L[0]=0;L[k]=n;
	for(int i=1;i<=k-1;i++)L[i]=read();
	for(int i=1;i<=k;i++){
		for(int j=L[i-1]+1;j<=L[i];j++){
			lv[j]=i;
			v[i].push_back(j);
		}
	}
	for(int i=0;i<m;i++){
		int u=read(),v=read();
		g[u].push_back(v);
	}
	memset(fr,-1,sizeof(fr));
	for(int i=1;i<=n;i++)dis[i]=inf;
	dis[1]=0;
	for(int i=0;i<=k;i++){
		get_dis1(i);
		get_dis2(i);
	}
	for(int i=1;i<=n;i++){
		if(fr[i]!=-1){
			nei[fr[i]].push_back(i);
		}
	}
	for(int i=1;i<=n;i++)dis[i]=-1;
	dis[1]=0;
	dfs(1);
	for(int i=1;i<=n;i++){
		if(dis[i]==-1){
			putchar('-');
			putchar('1');
		}
		else{
			print(dis[i]);
		}
		putchar('\n');
	}
	return 0;
}
/*inline? ll or int? size? min max?*/

来源 : nflsoj 20034 #10318.「2020联考北附2」大过滤器