首页 > 其他分享 >寒假集训总结

寒假集训总结

时间：2024-02-04 21:34:10浏览次数：27  
标签：总结 tmp cnt int ++ 寒假 maxn ans 集训

图论

拓扑排序

定义

在一张图上，将所有节点排序，使得每个节点的父节点都在其前面出现。

如果图上有环，则这张图没有拓扑序。

模版（BFS）
bool topo(){
    queue<int> q;
    for (int i=1;i<=n;i++) if (!deg[i]) q.push(i);
    while (!q.empty()){
        cnt++;
        int u=q.front();q.pop();
        for (int v:g[u]){
            deg[v]--;
            if (!deg[v]) q.push(v);
		}
    }
    return (cnt==n);
}
例题

例一 NOIP2020排水系统

不是很板子，主要是分数计算部分需要用到高精度（或是__int128）。

#include<bits/stdc++.h>
using namespace std;
using ll=__int128;
const int maxn=1e5+7;

int deg[maxn],cnt,n,m,id[maxn];
vector<int> g[maxn];
queue<int> q;

ll gcd(ll a,ll b){
	if (b==0) return a;
	return gcd(b,a%b);
}

ll lcm(ll a,ll b){
	return a*b/gcd(a,b);
}

struct water{
	ll p,q;
}ans[maxn];

water plu(water a,water b){
	water anss;
	if (a.q==b.q) {
		anss.q=a.q;
		anss.p=a.p+b.p;
	}else{
		ll lc=lcm(a.q,b.q);
		anss.p=lc/a.q*a.p+lc/b.q*b.p;
		anss.q=lc;
	}
	return anss;
}

water chu(water a,int b){
	ll tmp=gcd(a.p,b);
	b/=tmp;a.p/=tmp;
	a.q*=b;
	return a; 
}

void topo(){
	for (int i=1;i<=n;i++){
		if (!deg[i]) q.push(i);
	}
	while (!q.empty()){
		int u=q.front();q.pop();
		if (g[u].empty()) continue;
		water tmp={0,1};
		if (ans[u].p) tmp=chu(ans[u],g[u].size());
//		cerr<<u<<' '<<ans[u].p<<' '<<ans[u].q<<' '<<tmp.p<<' '<<tmp.q<<' '<<g[u].size()<<'\n';
		for (int v:g[u]){
//			cerr<<v<<'\n';
			deg[v]--;
			ans[v]=plu(tmp,ans[v]);
//			cerr<<v<<' '<<ans[v].p<<' '<<ans[v].q<<'\n';
			if (!deg[v]) q.push(v);
		}
	}
}

void write(ll x){
	if (x>9) write(x/10);
	putchar('0'+(x%10));
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		int d,v;cin>>d;ans[i].q=1,ans[i].p=0;
		if (!d) id[++cnt]=i;
		while (d--){
			cin>>v;
			g[i].push_back(v);
			deg[v]++;
		}
	}
	for (int i=1;i<=m;i++) ans[i].p=1;
	topo();
	for (int i=1;i<=cnt;i++){
		ll g=gcd(ans[id[i]].p,ans[id[i]].q);
		write(ans[id[i]].p/g);putchar(' ');
		write(ans[id[i]].q/g);putchar('\n');
//		cout<<()<<' '<<(ans[id[i]].q/g)<<'\n';
	}
	
	return 0;
}

例二 POI2015 PUS

看起来是差分约束的简化版，可用拓扑排序，但建边的复杂度为 \(O(n^3)\)，无法接受。

看到区间，想到线段树，进而想到线段树优化建图（模版题），优化后时间复杂度为 \(O(n\log n)\)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=6e5+7;
using ll=long long;
typedef pair<int,int> PII;

int lson[maxn],rson[maxn],n,m,s,idx,a[maxn],deg[maxn],cnt,dis[maxn],root,id[maxn];
vector<PII> g[maxn];
bool vis[maxn];

void build(int u,int l,int r){
    if (l==r){
        id[l]=u;idx=max(idx,u);return;
    }
    int mid=(l+r)>>1;
    lson[u]=++idx;rson[u]=++idx;
    build(lson[u],l,mid);
    build(rson[u],mid+1,r);
    g[u].push_back({lson[u],0});deg[lson[u]]++;
    g[u].push_back({rson[u],0});deg[rson[u]]++;
}
void update(int p,int pl,int pr,int l,int r,int u){
    if (l<=pl&&pr<=r){
        g[u].push_back({p,1});deg[p]++;return ;
    }
    int mid=(pl+pr)>>1;
//    cerr<<p<<' '<<mid<<' '<<pl<<' '<<pr<<' '<<l<<' '<<r<<'\n';
    if (l<=mid) update(lson[p],pl,mid,l,r,u);
    if (r>mid) update(rson[p],mid+1,pr,l,r,u);
}

queue<int> q;
bool topo(){
	for (int i=1;i<=idx;i++) if (!deg[i]) q.push(i);
	while (!q.empty()){
		int u=q.front();q.pop();cnt++;
		for (auto p:g[u]){
			int v=p.first,w=p.second;
			dis[v]=min(dis[v],dis[u]-w);
			if (dis[u]-w<a[v]) return 0;
			deg[v]--;if (!deg[v]) q.push(v);
		}
	}
	return (cnt==idx);
}

int main(){
	scanf("%d%d%d",&n,&s,&m);idx=1;
    build(1,1,n);
    for (int i=1;i<=s;i++){
    	int idd;scanf("%d",&idd);scanf("%d",&a[id[idd]]);
    	dis[id[idd]]=a[id[idd]];
	}
	for (int i=1;i<=m;i++){
		int l,r,k;scanf("%d%d%d",&l,&r,&k);
		int pre=l;idx++;
		for (int i=1;i<=k;i++){
			int x;scanf("%d",&x);
			g[id[x]].push_back({idx,0});deg[idx]++;
			if (pre<=x-1) update(1,1,n,pre,x-1,idx);
			pre=x+1;
		}
		if (pre<=r) update(1,1,n,pre,r,idx);
	}
    for (int i=1;i<=idx;i++) if (!dis[i]) dis[i]=1e9;
    if (!topo()) {
    	printf("NIE");return 0;
	}
	for (int i=1;i<=n;i++) {
		if (dis[id[i]]<1){
			printf("NIE");return 0;
		}
	}
	printf("TAK\n");
	for (int i=1;i<=n;i++) printf("%d ",dis[id[i]]);
	
	return 0;
}

欧拉图

定义
  • 欧拉回路：通过图中每条边恰好一次的回路
  • 欧拉通路：通过图中每条边恰好一次的通路
  • 欧拉图：具有欧拉回路的图
  • 半欧拉图：具有欧拉通路但不具有欧拉回路的图
例题

封锁阳光大学

在图中删去一些点，使得图不连通，删去的点在图中不能相邻。

可以考虑在每个连通块内染色，选取每个连通块中总数更少的颜色的点的数量之和作为答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+7;

vector<int> g[maxn];
int color[maxn],n,m,deg[maxn],cnt[2];
bool vis[maxn];

bool bfs(int u){
	queue<int> q;
	q.push(u);color[u]=1;cnt[0]++;
	while (!q.empty()){
		int u=q.front();q.pop();
	    for (int v:g[u]){
	    	if (color[v]==color[u]) return 0;
	    	if (!color[v]){
	    		color[v]=3-color[u];
                cnt[color[v]-1]++;
	    		q.push(v);
			}
		}
	}
	return 1;
}

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		g[u].push_back(v);g[v].push_back(u);
		deg[u]++;deg[v]++;
	}
	bool f=1;
    int ans=0;
	for (int i=1;i<=n;i++){
		if (!color[i]&&deg[i]) {
            f&=bfs(i);
            ans=ans+min(cnt[0],cnt[1]);
            cnt[0]=cnt[1]=0;
        }
        
	}
	if (!f) printf("Impossible");
	else {
		printf("%d",min(ans,n-ans));
	}
	
	return 0;
}

Riding the Fences骑马修栅栏

欧拉回路板子题。

先找到奇点，如果没有奇点就默认1为奇点。

从奇点开始DFS，遍历所有与之相邻的点，并删去两点之间的一条边。

在DFS过程中记录答案，最后输出答案即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=507;

int g[maxn][maxn],n,m,node[maxn],deg[maxn],ans[1027],cnt;
bool visnod[maxn];

void dfs(int u){
	for (int i=1;i<=n;i++){
		int v=node[i];
		if (g[u][v]){
			g[u][v]--;g[v][u]--;
			dfs(v);
		}
	}
	ans[++cnt]=u;
}

int main(){
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		g[u][v]++;g[v][u]++;
		visnod[u]=visnod[v]=1;
		deg[v]++;deg[u]++;
	}
	for (int i=1;i<=500;i++) if (visnod[i]) node[++n]=i;
	int st=node[1];
	for (int i=1;i<=n;i++){
		if (deg[node[i]]&1){
			st=node[i];break;
		}
	}
	dfs(st);
	for (int i=cnt;i>0;i--) printf("%d\n",ans[i]);
	
	return 0;
}

垃圾运输

欧拉回路拆环。

如果一条边的s==t，则不要这条边，没有意义。

如果有点的度数为奇数，那么肯定无解，输出NIE

在DFS的过程中判断当前元素是否已入栈，如果在就遇到了环，记录答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7,maxm=2e6+7;
typedef pair<int,int> PII;

vector<PII> g[maxn];
vector<int> ans[maxn];
stack<int> stk;
int deg[maxn],n,m,edgeid,anscnt;
bool visn[maxn],vise[maxm],ins[maxn];

void dfs(int u){
    visn[u]=1;
    for (auto p:g[u]){
        int v=p.first,id=p.second;
        int tmp;
        if (id&1) tmp=id+1;
        else tmp=id-1;
        if (vise[id]) continue;
        vise[id]=vise[tmp]=1;
        dfs(v);
    }
    if (!ins[u]){
        stk.push(u);ins[u]=1;
    }else{
        ans[++anscnt].push_back(u);
        int t=stk.top();
        while (t^u) {
            stk.pop();ins[t]=0;ans[anscnt].push_back(t);t=stk.top();
        }
        ans[anscnt].push_back(u);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for (int i=1;i<=m;i++){
        int u,v,s,t;cin>>u>>v>>s>>t;
        if (s^t){
            g[u].push_back({v,++edgeid}),g[v].push_back({u,++edgeid});
            deg[u]++;deg[v]++;
        }
    }
    for (int i=1;i<=n;i++){
        if (deg[i]&1) {
            cout<<"NIE";return 0;
        }
    }
    for (int i=1;i<=n;i++){
        if (!visn[i]) dfs(i);
    }
    cout<<anscnt<<'\n';
    for (int i=1;i<=anscnt;i++){
        cout<<(ans[i].size()-1)<<' ';
        for (int u:ans[i]) cout<<u<<' ';
        cout<<'\n';
    }

    return 0;
}

最小生成树

定义

一个无向连通图的最小生成树为这个图中权值最小的生成树。

模版

Kruskal

与并查集联动了

struct edge{
	int u,v,w;
	bool operator<(const edge &a)const{
		return w<a.w;
	}
}e[maxm];

int find(int x){
	if (fa[x]^x) return fa[x]=find(fa[x]);
	else return x;
}

void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if (fx==fy) return ;
	fa[fy]=fx;
}

bool check(int x,int y){
	return (fa[find(x)]^fa[find(y)]);
}

int kru(){
	int ans=0;
	sort(e+1,e+1+m);
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if (check(u,v)){
			merge(u,v);cnt++;ans+=w;
			if (cnt==n) break;
		}
	}
    return ans;
}

Prim

不经常用，但还是贴一个堆优化的。在图为稠密图时，朴素Prim比Kruskal更快。

int prim(){
    int ans=0;
    memset(dis,0x3f,sizeof dis);
    dis[1]=0;
    q.push({0,1});
    while (!q.empty()){
        if (cnt>=n) break;
        int u=q.top().second,d=q.top().first;q.pop();
        if (vis[u]) continue;
        vis[u]=1;
        cnt++;ans+=d;
        for (auto p:g[u]){
            int v=p.first,w=p.second;
            if (g[u][v]<dis[v]){
                dis[v]=g[u][v];q.push({dis[v],v});
            }
        }
    }
    return ans;
}
例题

破墙

乍一看好像和最小生成树没关系，但我们可以这么想：把每个矩形区域按墙分为两块并看成点，和与其相连的点建权值为0的边，把墙两边的点建权值为破墙所需代价的边。

要使整个图连通且代价最小，考虑最小生成树，求解即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=507;

char mp[maxn][maxn];
int n,m,w[maxn][maxn],id[maxn][maxn],cnt,fa[maxn*maxn*2],size[maxn*maxn*2];

struct edge{
	int u,v,w;
	bool operator<(const edge &a)const{
		return w<a.w;
	}
}e[maxn*maxn*5];

int find(int x){
	if (fa[x]^x) return fa[x]=find(fa[x]);
	return x;
}
void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if (fx==fy) return ;
	fa[fy]=fx;size[fx]+=size[fy];
}

bool check(int x,int y){
	return (fa[find(x)]^fa[find(y)]);
}

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%s",mp[i]+1);
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) scanf("%d",&w[i][j]);
	}
	int tmp=1;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			id[i][j]=tmp;tmp+=2;
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			e[++cnt]=(edge){id[i][j],id[i][j]+1,w[i][j]};
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (i>1) e[++cnt]=(edge){id[i][j],id[i-1][j]+1,0};
			if (i<n) e[++cnt]=(edge){id[i][j]+1,id[i+1][j],0};
			if (j>1) {
				int u,v;
				if (mp[i][j-1]=='\\') u=id[i][j-1];
				else u=id[i][j-1]+1;
				if (mp[i][j]=='\\') v=id[i][j]+1;
				else v=id[i][j];
				e[++cnt]=(edge){u,v,0};
			}
			if (j<n) {
				int u,v;
				if (mp[i][j+1]=='\\') u=id[i][j+1]+1;
				else u=id[i][j+1];
				if (mp[i][j]=='\\') v=id[i][j];
				else v=id[i][j]+1;
				e[++cnt]=(edge){u,v,0};
			}
		}
	}
	sort(e+1,e+1+cnt);
	for (int i=1;i<=2*n*m;i++) fa[i]=i,size[i]=1;
	int ans=0;
	for (int i=1;i<=cnt;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if (check(u,v)){
			ans+=w;merge(u,v);if (size[find(u)]==2*n*m) break;
		}
	}
	printf("%d",ans);
	
	return 0;
}

货车运输

为了使能运输的货物最多，可以跑一遍最大生成树，这样使得两点之间路径上边的最小值最大。

由于数据范围较大，所以不能每次询问都去查找答案。

求树上两点之间边的最值，可以用倍增LCA来做。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int maxn=1e4+7,maxm=5e4+7;

vector<PII> g[maxn];
struct edge{
	int u,v,w;
	bool operator<(const edge &a)const{
		return w>a.w;
	}
}e[maxm];
int n,m,q,fa[maxn],size[maxn],cost[maxn][20],f[maxn][20],dep[maxn];
bool vis[maxn];

int find(int x){
	if (fa[x]^x) return fa[x]=find(fa[x]);
	else return x;
}

void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if (fx==fy) return ;
	fa[fy]=fx;size[fx]+=size[fy];
}

bool check(int x,int y){
	return (fa[find(x)]^fa[find(y)]);
}

void kru(){
	sort(e+1,e+1+m);
	for (int i=1;i<=n;i++) fa[i]=i,size[i]=1;
	for (int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if (check(u,v)){
			merge(u,v);
			g[u].push_back({v,w});
			g[v].push_back({u,w});
			if (size[find(u)]==n) break;
		}
	}
}

void dfs(int u){
	vis[u]=1;
	for (auto p:g[u]){
		int v=p.first,w=p.second;
		if (vis[v]) continue;
		dep[v]=dep[u]+1;
		f[v][0]=u;cost[v][0]=w;
		dfs(v);
	}
}

void init(){
	for (int i=1;i<=n;i++){
		if (!vis[i]){
			dep[i]=1;
			dfs(i);
			f[i][0]=1;
			cost[i][0]=INT_MAX;
		}
	}
	for (int i=1;i<=14;i++){
		for (int j=1;j<=n;j++){
			f[j][i]=f[f[j][i-1]][i-1];
			cost[j][i]=min(cost[j][i-1],cost[f[j][i-1]][i-1]);
		}
	}
}

int lca(int u,int v){
	if (find(u)^find(v)) return -1;
	int ans=INT_MAX;
	if (dep[u]>dep[v]) swap(u,v);
	for (int i=14;i>=0;i--){
		if (dep[f[v][i]]>=dep[u]){
			ans=min(ans,cost[v][i]);
			v=f[v][i];
		}
	}
	if (u==v) return ans;
	for (int i=14;i>=0;i--){
		if (f[u][i]^f[v][i]){
			ans=min(ans,min(cost[u][i],cost[v][i]));
			u=f[u][i],v=f[v][i];
		}
	}
	ans=min(ans,min(cost[u][0],cost[v][0]));
	return ans;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	kru();
	init();
	cin>>q;
	while (q--){
		int u,v;cin>>u>>v;
		printf("%d\n",lca(u,v));
	}
	
	return 0;
}

水壶

把地图抽象成一个图，图上的顶点为建筑物，权值为两个建筑物之间的最短距离，就类似上一题了。

在建图的时候使用BFS，得到最短距离。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int maxn=2007,maxm=5e6+7,maxnn=2002*2002;
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

vector<PII> g[maxnn];
struct edge{
	int u,v,w;
	bool operator<(const edge &a)const{
		return w<a.w;
	}
}e[maxm];
int n,m,p,T,fa[maxnn],siz[maxnn],cost[maxnn][21],f[maxnn][21],dep[maxnn],cnt;
int id[maxn][maxn],dis[maxn][maxn];
char s[maxn][maxn];
bool vis[maxnn],viss[maxn][maxn];

int find(int x){
	if (fa[x]^x) return fa[x]=find(fa[x]);
	else return x;
}

void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if (fx==fy) return ;
	fa[fy]=fx;siz[fx]+=siz[fy];
}

bool check(int x,int y){
	return (fa[find(x)]^fa[find(y)]);
}

void kru(){
	sort(e+1,e+1+cnt);
	for (int i=1;i<=p;i++) fa[i]=i,siz[i]=1;
	for (int i=1;i<=cnt;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if (check(u,v)){
			merge(u,v);
			g[u].push_back({v,w});
			g[v].push_back({u,w});
//			if (siz[find(u)]==p) break;
		}
	}
}

void dfs(int u){
	vis[u]=1;
	for (auto p:g[u]){
		int v=p.first,w=p.second;
		if (vis[v]) continue;
		dep[v]=dep[u]+1;
		f[v][0]=u;cost[v][0]=w;
		dfs(v);
	}
}

void init(){
	for (int i=1;i<=p;i++){
		if (!vis[i]){
			dep[i]=1;
			dfs(i);
			f[i][0]=1;
			cost[i][0]=0;
		}
	}
	for (int i=1;i<=19;i++){
		for (int j=1;j<=p;j++){
			f[j][i]=f[f[j][i-1]][i-1];
			cost[j][i]=max(cost[j][i-1],cost[f[j][i-1]][i-1]);
		}
	}
}

int lca(int u,int v){
	if (find(u)^find(v)) return -1;
	int ans=0;
	if (dep[u]>dep[v]) swap(u,v);
	for (int i=19;i>=0;i--){
		if (dep[f[v][i]]>=dep[u]){
			ans=max(ans,cost[v][i]);
			v=f[v][i];
		}
	}
	if (u==v) return ans;
	for (int i=19;i>=0;i--){
		if (f[u][i]^f[v][i]){
			ans=max(ans,max(cost[u][i],cost[v][i]));
			u=f[u][i],v=f[v][i];
		}
	}
	ans=max(ans,max(cost[u][0],cost[v][0]));
	return ans;
}

queue<PII> q;
void bfs(){
	while (!q.empty()){
		int x=q.front().first,y=q.front().second;q.pop();
		viss[x][y]=1;
		for (int i=0;i<4;i++){
			int fx=x+dx[i],fy=y+dy[i];
			if (fx<1||fx>n||fy<1||fy>m||viss[fx][fy]||s[fx][fy]=='#') continue;
			if (!id[fx][fy]){
				id[fx][fy]=id[x][y];
				dis[fx][fy]=dis[x][y]+1;
				q.push({fx,fy});
			}else if (id[fx][fy]^id[x][y]){
				e[++cnt]=(edge){id[x][y],id[fx][fy],dis[fx][fy]+dis[x][y]};
			}
		}
	}
}

int main(){
	scanf("%d%d%d%d",&n,&m,&p,&T);
	for (int i=1;i<=n;i++){
		scanf("%s",s[i]+1);
	}
	//cerr<<1<<'\n';
	for (int i=1;i<=p;i++){
		int x,y;scanf("%d%d",&x,&y);
		id[x][y]=i;
		q.push({x,y});
	}
	bfs();
	//cerr<<2<<'\n';
	kru();
	//cerr<<3<<'\n';
	init();
	//cerr<<4<<'\n';
	while (T--){
		int u,v;scanf("%d%d",&u,&v);
		cout<<lca(u,v)<<'\n';
	}
	//cerr<<5<<'\n';
	
	return 0;
}

图的连通性

相关定义

  • 强连通：有向图 G 中任意两个结点连通。

  • 强连通分量（Strongly Connected Components，SCC）：极大的强连通子图。

  • 边双连通：在一张连通的无向图中，对于两个点 \(u\) 和 \(v\) ，无论删去哪条边（只能删去一条）都不能使它们不连通，则 \(u\) 和 \(v\) 边双连通。

  • 点双联通：在一张连通的无向图中，对于两个点 \(u\) 和 \(v\)，无论删去哪个点（只能删去一个，且不能删 \(u\) 和 \(v\) 自己）都不能使它们不连通，则 \(u\) 和 \(v\) 点双连通。

  • 缩点：将强联通分量缩成一个点。

模版

Tarjan

void tarj(int u){
	dfn[u]=low[u]=++pos;
	instk[u]=1;
	stk[++tt]=u;
	for (int v:g[u]){
		if (!dfn[v]){
			tarj(v);
			low[u]=min(low[v],low[u]);
		}else if (instk[v]) low[u]=min(low[u],dfn[v]);
	}
	if (dfn[u]==low[u]){
		cnt++;
		while (stk[tt]^u){
			int tmp=stk[tt];tt--;
			group[tmp]=cnt;
			instk[tmp]=0;
			mon[cnt]=min(mon[cnt],a[tmp]);
		}
		int tmp=stk[tt--];
		group[tmp]=cnt;
		instk[tmp]=0;
		mon[cnt]=min(mon[cnt],a[tmp]);
	}
}

缩点

for (int i=1;i<=r;i++){
	if (!dfn[p[i]]) tarj(p[i]);
}
for (int u=1;u<=n;u++){
	for (int v:g[u]){
		if (group[u]^group[v]){
            ng[u].push_back(v);
        }
	}
}
例题

间谍网络

将间谍之间的关系建成图，把告发者指向被告发者。

从可以贿赂的间谍开始跑Tarjan，如果几个间谍形成了一个环，就把他们缩成一个点，点权为几个间谍中最小的点权。

如果在tarjan后还有没有遍历到的点，就判断无解。

最后，将所有入度为0的点的点权相加，得到答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3007;

vector<int> g[maxn];
int n,r,m,a[maxn],p[maxn],dfn[maxn],low[maxn],follow[maxn],pos,cnt;
int stk[maxn],tt,mon[maxn],deg[maxn];
bool instk[maxn];

void tarj(int u){
	dfn[u]=low[u]=++pos;
	instk[u]=1;
	stk[++tt]=u;
	for (int i=g[u].size()-1;i>=0;i--){
		int v=g[u][i];
		if (!dfn[v]){
			tarj(v);
			low[u]=min(low[v],low[u]);
		}else if (instk[v]) low[u]=min(low[u],dfn[v]);
	}
	if (dfn[u]==low[u]){
		cnt++;
		while (stk[tt]^u){
			int tmp=stk[tt];tt--;
			follow[tmp]=cnt;
			instk[tmp]=0;
			mon[cnt]=min(mon[cnt],a[tmp]);
		}
		int tmp=stk[tt--];
		follow[tmp]=cnt;
		instk[tmp]=0;
		mon[cnt]=min(mon[cnt],a[tmp]);
	}
}

int main(){
	memset(a,0x3f,sizeof a);
	memset(mon,0x3f,sizeof mon);
	scanf("%d",&n);
	scanf("%d",&r);
	for (int i=1;i<=r;i++){
		scanf("%d",&p[i]);scanf("%d",&a[p[i]]);
	}
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		g[u].push_back(v);
	}
	for (int i=1;i<=r;i++){
		if (!dfn[p[i]]) tarj(p[i]);
	}
	for (int i=1;i<=n;i++){
		if (!dfn[i]){
			printf("NO\n%d",i);return 0;
		}
	}
	for (int u=1;u<=n;u++){
		for (int v:g[u]){
			if (follow[u]^follow[v]) deg[follow[v]]++;
		}
	}
	int ans=0;
	for (int i=1;i<=cnt;i++){
		if (!deg[i]) ans+=mon[i];
	}
	printf("YES\n%d",ans);
	
	
	return 0;
}

抢掠计划

把ATM机看成点，点权即为ATM机中的钱数。如果几个点形成了一个环，就把这几个点缩成一个点，缩点的点权为几个点的点权和，如果几个点中有酒吧，这个缩点也可以看成酒吧。

最后跑一遍最长路，统计答案即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn=500007;

int dfn[maxn],low[maxn],group[maxn],mon[maxn],mon2[maxn],dp[maxn];
int n,m,st,p,stk[maxn],tt,now,cnt,deg[maxn];
bool instk[maxn],isbar[maxn],bar[maxn];
vector<int> g[maxn],ng[maxn];

void tarj(int u){
	dfn[u]=low[u]=++now;
	stk[++tt]=u;instk[u]=1;
	for (int v:g[u]){
		if (!dfn[v]){
			tarj(v);
			low[u]=min(low[u],low[v]);
		}else if (instk[v]) low[u]=min(low[u],dfn[v]);
	}
	if (dfn[u]==low[u]){
		group[u]=++cnt;
		while (stk[tt]^u){
			int tmp=stk[tt--];
			instk[tmp]=0;
			group[tmp]=cnt;
			mon2[cnt]+=mon[tmp];
			bar[cnt]|=isbar[tmp];
		}
		tt--;
		instk[u]=0;
		mon2[cnt]+=mon[u];
		bar[cnt]|=isbar[u];
	}
}

queue<int> q;

void topo(){
	q.push(group[st]);
	while (!q.empty()){
		int u=q.front();q.pop();
//		cerr<<"u:"<<u<<' '<<dp[u]<<'\n';
		for (int v:ng[u]){
//			cerr<<"v:"<<v<<' '<<deg[v]<<'\n';
			dp[v]=max(dp[v],dp[u]+mon2[v]);
			deg[v]--;if (!deg[v]) q.push(v);
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		int u,v;scanf("%d%d",&u,&v);
		g[u].push_back(v);
	}
	for (int i=1;i<=n;i++) scanf("%d",&mon[i]);
	scanf("%d%d",&st,&p);
	for (int i=1;i<=p;i++){
		int tmp;scanf("%d",&tmp);
		isbar[tmp]=1;
	}
	tarj(st);
	for (int u=1;u<=n;u++){
		if (!dfn[u]) continue;
		for (int v:g[u]){
			if (group[u]^group[v]){
				ng[group[u]].push_back(group[v]);
				deg[group[v]]++;
			}
		}
	}
	dp[group[st]]=mon2[group[st]];
	topo();
	int ans=0;
	for (int i=1;i<=cnt;i++) if (bar[i]) ans=max(ans,dp[i]);
	printf("%d\n",ans);
//	for (int i=1;i<=n;i++) cerr<<group[i]<<'\n';
	
	return 0;
}

数据结构

并查集

一种维护元素所属集合的数据结构。

模版
void init(int n){
    for (int i=1;i<=n;i++) fa[i]=i;
}
int find(int x){
    if (fa[x]^x) return fa[x]=find(fa[x]);
    return x;
}
void merge(int x,int y){
    int fx=find(x),fy=find(y);
    if (fx==fy) continue;
    fa[fy]=fx;
}
例题

队形变换

可以看出行和列的变换是互不干扰的，所以分开来看，最后将两遍的答案相乘。

如果两行可以互换，就把这两行合并到同一个集合中。不难证明，同一个集合中的任意两行都可互换，所以一个集合内的方案数为 \(size!\)，最后将所有答案相乘即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
using ll=long long;
const int maxn=57,mod=998244353;

int h[maxn][maxn],n,m,fa[maxn],jc[maxn],size[maxn],ans=1;

void init(){
	jc[1]=1;jc[0]=1;
	for (int i=2;i<=50;i++) jc[i]=jc[i-1]*i,jc[i]%=mod;
}

int find(int x){
	if (fa[x]^x) return fa[x]=find(fa[x]);
	else return x;
}

void merge(int x,int y){
	int fx=find(x),fy=find(y);
	if (fx==fy) return;
	fa[fx]=fy;
}

signed main(){
	init();
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			scanf("%lld",&h[i][j]);
		}
	}
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++){
			bool f=1;
			for (int k=1;k<=n&&f;k++){
				if (h[i][k]+h[j][k]>m) f=0;
			}
			if (f) merge(i,j);
		}
	}
	for (int i=1;i<=n;i++) size[find(i)]++;
	for (int i=1;i<=n;i++) {
		if (fa[i]!=i) continue;
		ans*=jc[size[i]];ans%=mod;
	}
	for (int i=1;i<=n;i++) fa[i]=i,size[i]=0;
	for (int i=1;i<=n;i++){
		for (int j=i+1;j<=n;j++){
			bool f=1;
			for (int k=1;k<=n&&f;k++){
				if (h[k][i]+h[k][j]>m) f=0;
			}
			if (f) merge(i,j);
		}
	}
	for (int i=1;i<=n;i++) size[find(i)]++;
	for (int i=1;i<=n;i++) {
		if (fa[i]!=i) continue;
		ans*=jc[size[i]];ans%=mod;
	}
	printf("%lld",ans%mod);
	
	return 0;
}

单调队列优化DP

介绍

如果当前状态的所有值能从上一个状态的一段中转移，且需要对这一段状态进行RMQ，就可以用单调队列优化。

例题

股票交易

设 \(dp_{i,j}\) 表示第 \(i\) 天有 \(j\) 张股票时最多能赚的钱数，有4种转移的方式。

1.空手买

\(dp_{i,j}=-ap_i \times j(0\le j\le as_i)\)

2.无操作

\(dp_{i,j}=\max (dp_{i,j},dp_{i-1},j)\)

3.在以前的基础上买股票

\(dp_{i,j}=\max (dp_{i,j},dp_{i-w-1,k}-(j-k)\times ap_i)(j-as_i\le k<j)\)

4.在以前的基础上卖股票

\(dp_{i,j}=\max(dp_{i,j},dp_{i-w-1,k}+(k-j)\times bp_i)(j<k \le j+bs_i)\)

可以看出3、4可以用单调队列优化。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2007;

int n,maxp,w,dp[maxn][maxn],ap[maxn],bp[maxn],as[maxn],bs[maxn];
int q[maxn],hh,tt;

int main(){
	memset(dp,-0x3f,sizeof dp);
	scanf("%d%d%d",&n,&maxp,&w);
	for (int i=1;i<=n;i++){
		scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
		for (int j=0;j<=as[i];j++){
			dp[i][j]=j*ap[i]*-1;
		}
	}
	for (int i=1;i<=n;i++){
		for (int j=0;j<=maxp;j++){
			dp[i][j]=max(dp[i][j],dp[i-1][j]);
		}
		if (i<=w) continue;
		hh=0,tt=-1;
		for (int j=0;j<=maxp;j++){
			while (hh<=tt&&q[hh]<j-as[i]) hh++;
			while (hh<=tt&&dp[i-w-1][q[tt]]+q[tt]*ap[i]<=dp[i-w-1][j]+j*ap[i]) tt--;
			q[++tt]=j;
			if (hh<=tt) dp[i][j]=max(dp[i][j],dp[i-w-1][q[hh]]+q[hh]*ap[i]-j*ap[i]);
		}
		hh=0;tt=-1;
		for (int j=maxp;j>=0;j--){
			while (hh<=tt&&q[hh]>j+bs[i]) hh++;
			while (hh<=tt&&dp[i-w-1][q[tt]]+q[tt]*bp[i]<=dp[i-w-1][j]+j*bp[i]) tt--;
			q[++tt]=j;
			if (hh<=tt) dp[i][j]=max(dp[i][j],dp[i-w-1][q[hh]]+q[hh]*bp[i]-j*bp[i]);
		}
	}
	int ans=0;
	for (int i=0;i<=maxp;i++) ans=max(ans,dp[n][i]);
	printf("%d",ans);
	
	
	return 0;
}

最近打atcoder看到一道线段树优化dp，顺便把题放到这儿

线段树

定义

线段树是一种常用来维护区间信息的数据结构，可以在 \(O(log n)\) 的时间复杂度内实现单点修改、区间修改、区间查询等操作。

模版

以下模版维护查询区间和与进行区间加操作。

using ll=long long;
const int maxn=1e5+7;

ll a[maxn],tree[maxn<<2],tag[maxn<<2];
int lson(int x){
    return (x<<1);
}
int rson(int x){
    return (x<<1|1);
}
void addtag(int p,int l,int r,ll d){
    tag[p]+=d;
    tree[p]+=(r-l+1)*d;
}
void pushup(int x){
    tree[x]=tree[lson(x)]+tree[rson(x)];
}
void pushdown(int p,int l,int r){
    if (tag[p]){
        int mid=(l+r)>>1;
        addtag(lson(p),l,mid,tag[p]);
        addtag(rson(p),mid+1,r,tag[p]);
        tag[p]=0;
    }
}
void build(int p,int l,int r){
    if (l==r){
        tree[p]=a[l];return ;
    }
    int mid=(l+r)>>1;
    build(lson(p),l,mid);
    build(rson(p),mid+1,r);
    pushup(p);
}
void update(int p,int pl,int pr,int l,int r,ll d){
    if (l<=pl&&pr<=r){
        addtag(p,pl,pr,d);return ;
    }
    pushdown(p,pl,pr);
    int mid=(pl+pr)>>1;
    if (l<=mid) update(lson(p),pl,mid,l,r,d);
    if (r>mid) update(rson(p),mid+1,pr,l,r,d);
    pushup(p);
}
ll query(int p,int pl,int pr,int l,int r){
    if (l<=pl&&pr<=r) return tree[p];
    pushdown(p,pl,pr);
    ll res=0;
    int mid=(pl+pr)>>1;
    if (l<=mid) res+=query(lson(p),pl,mid,l,r);
    if (r>mid) res+=query(rson(p),mid+1,pr,l,r);
    return res;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while (m--){
        int op;cin>>op;
        if (op==1){
            int l,r;ll k;cin>>l>>r>>k;
            update(1,1,n,l,r,k);
        }else{
            int l,r;cin>>l>>r;
            cout<<query(1,1,n,l,r)<<'\n';
        }
    }

    return 0;
}
例题

咕咕咕。

标签：总结,tmp,cnt,int,++,寒假,maxn,ans,集训
From： https://www.cnblogs.com/code953/p/18007034

相关文章

  • 2024.2.4寒假每日总结26
    算法题：292.Nim游戏-力扣（LeetCode）LeetCodeNim游戏292.Nim游戏-力扣（LeetCode）题目描述你和你的朋友，两个人一起玩Nim游戏：桌子上有一堆石头。你们轮流进行自己的回合，你作为先手。每一回合，轮到的人拿掉1-3块石头。拿掉最后一块石头的人就是获胜者。......
  • 2.4寒假每日总结25
    误详情：使用IDEA直接连接数据库报错：Serverreturnsinvalidtimezone.Goto'Advanced'tabandset'serverTimezone'propertymanually.错误原因：MySQL驱动中默认时区是UTC，与本地时间有时差。解决方案：点开最右侧导航栏Advanced，找到serverTimezone，在value处填写GMT保存 ......
  • 寒假第二周——训练总结
    题解1A题，给n个英文字母，你可以组成最长的回文串长度是多少？现在，请你利用程序帮助算出他能构成的最长回文串的长度是多少。用桶排的方法，记录字母的数量，然后把双数的数量×2，加上超过二的单数/2的奇数加1即可，需要判断只需要有一个超过2的奇数就在结果加一就行。A——A点击查看......
  • 2024牛客寒假算法基础集训营1 K 牛镇公务员考试 题解
    Question2024牛客寒假算法基础集训营1K牛镇公务员考试给出一张试卷有\(n\)道单选题，每道题用一个整数\(a_i\)和一个长度为\(5\)的字符串\(s_i\)表示，其中第\(i\)道题的题面为：第\(a_i\)道题的答案是（）A.\(s_1\)B.\(s_2\)C.\(s_3\)D.\(s_4\)E.\(s_5\)问：正......
  • 如何做好一个信息系统项目经理，一个项目经理的个人体会和经验总结（四）
    前言说完了在项目开发阶段我的一些个人体会和经验总结，最后我们聊聊在项目验收阶段我们需要关注哪些方面的内容……项目验收阶段系统开发告一段落后，就进入客户培训、系统验收阶段，这个阶段，我一般会注意以下几个问题：1.给客户做培训前，多注意一些表面功夫大多数客户其实并不......
  • 东北师大附中 集训游记
    update文笔稚嫩谨慎观看。东北师大附中集训游记但是去的时候到处都在翻修（小声bb）。Day1早上一来就要先考试，太离谱了。根本没准备\(qaq\)。于是就开始刚题，第一题写了半天，感觉推出来的结论超级无敌对，但是却只拿了10分。第二题没思路，放弃了。第三题读完题也挺离谱，写了个......
  • 冯梓轩图论总结2
    图论学习总结2拓补排序当给定的一张图是一张DAG（有向无环图）时，可以对该图进行拓补排序，在\(O(n+m)\)的时间内转移一些信息。通常用队列进行实现。拓补排序经常与其他算法进行结合，如DP。例题[POI2015]PUS(Pustynia)当一些数之间只给定了大小关系，要求一组可行解时，可以考虑......
  • 我的公众号2023运营总结
    转眼间已经2024了，我的公众号架构成长指南运营也算是有一年了，在这里感谢各位粉丝朋友们的关注，文末有封面红包领取，下面分享一下我这一年运营结果为什么写公众号？因为平时写笔记，同时在公司内部也会进行一些技术分享，想着在哪分享不是分享，能帮助更多人不是挺好，因此在2022年8月就开......
  • Python 基于pymongo操作Mongodb学习总结
    实践环境Python3.6.4pymongo4.1.1pymongo-3.12.3-cp36-cp36m-win_amd64.whl下载地址：https://pypi.org/simple/pymongo/代码实践#!/usr/bin/envpython#-*-coding:utf-8-*-importdatetimeimportrandomimportpymongofrompymongoimportMongoClientfrombson.objecti......
  • 寒假day3 2.4
    讲师：钟皓曦，NOI2012Au，from成都七中听课能听懂30%就算成功**dp关键：状态、转移、初始化转移：状态与状态之间的关系初始化：状态的边界条件数字三角形状态：\(f_{i,j}\)表示走到\(a_{i,j}\)这个位置的最大价值。如何设计状态？题目要你干什么——从第一行走到最后一行该过程......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99