看心情填坑

感觉前9题和后两题画风完全不一样。

所以我就偷懒只写最后两题好了。反正前面都是大傻题。

H bridges

题意：给你一个图，现在要在图上加一条边，使得这个图的割边尽可能少。

SOL：一开始想什么生成树上树剖，我想多了。先TARJAN把所有割边弄出来，然后随便构一个生成树出来，然后就是求权值最大的树链，这个东西可以O(n)扫出来，总复杂度O(n+m)

#include<cstdio>
#include<algorithm>
using namespace std;
struct edge{
	int u,v;
	bool b;
}E[100005];
struct Edge{
	int to,next,k;
}e[200005];
int test,head[100005],n,m,cnt,low[100005],dfn[100005],vis[100005],fa[100005],ans,dp[100005];
void add(int x,int y,int k){
	cnt++;
	e[cnt].next=head[x];
	e[cnt].to=y;
	e[cnt].k=k;
	head[x]=cnt;
}
void Tarjan(int root,int fa,int dep){
	dfn[root]=low[root]=dep;
	vis[root]=1;
	for(int i=head[root];i;i=e[i].next)if(e[i].to!=fa){
		if(vis[e[i].to]==1)low[root]=min(low[root],dfn[e[i].to]);
		if(vis[e[i].to]==0){
			Tarjan(e[i].to,root,dep+1);
			low[root]=min(low[root],low[e[i].to]);
		}
	}
	vis[root]=2;
}
void dfs(int root,int fa){
	int max1=0,max2=0;
	for(int i=head[root];i;i=e[i].next)if(e[i].to!=fa){
		dfs(e[i].to,root);
		dp[e[i].to]+=E[e[i].k].b;
		if(dp[e[i].to]>=max1){max2=max1;max1=dp[e[i].to];}
		else if(dp[e[i].to]>max2){max2=dp[e[i].to];}
	}
	for(int i=head[root];i;i=e[i].next)if(e[i].to!=fa){
		if(dp[e[i].to]==max1)ans=max(max2+dp[e[i].to],ans);
		else ans=max(max1+dp[e[i].to],ans);
	}
	dp[root]=max1;
}
int find(int k){
	if(fa[k]==k)return k;
	fa[k]=find(fa[k]);
	return fa[k];
}
int main(){
	scanf("%d",&test);
	while(test--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++)head[i]=0,vis[i]=0;
		cnt=0;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&E[i].u,&E[i].v);E[i].b=false;
			add(E[i].u,E[i].v,i);
			add(E[i].v,E[i].u,i);
		}
		Tarjan(1,0,1);
		int s=0;
		for(int i=1;i<=m;i++){
			if(low[E[i].u]>dfn[E[i].v])E[i].b=true;
			if(low[E[i].v]>dfn[E[i].u])E[i].b=true;
			if(E[i].b){
				s++;
			}
		}
		cnt=0;
		for(int i=1;i<=n;i++)head[i]=0,fa[i]=i;
		for(int i=1;i<=m;i++){
			int U=find(E[i].u),V=find(E[i].v);
			if(U!=V){
				fa[U]=V;
				add(E[i].u,E[i].v,i);
				add(E[i].v,E[i].u,i);
			}
		}
		ans=0;
		dfs(1,0);
		printf("%d\n",s-ans);
	}
}

L:Alternating Strings II

题意：定义一种01串叫交替串：

1、长度>1

2、0和1交替出现。

现在要你把一个长度为n的串分成若干份，使得每一份长度不超过K且不是交替串。求最少分成几份-1

SOL：一眼dp,dp方程显然是O(n)转移的，n^2*n(交替串验证）想都不用想会T，考虑优化，显然对于dp[i]可以转移的是一个区间l-r（有可能不存在）以及i-1,且l满足l>=i-m，r满足r+1到i这一段是01交替出现，01交替出现可以O(1)处理掉（看代码）然后用堆维护这个区间即可，每个元素进堆一次出堆一次。总复杂度O(nlog)

#include<cstdio>
#include<algorithm>
using namespace std;
int dp[100005],e[100005],heap[100005];
char s[100005];
int test,n,m,top,l,r;
void del(){
	heap[1]=heap[top];top--;
	int k=1;
	while(k*2<=top){
		int v=k*2;
		if(dp[heap[v]]>dp[heap[v+1]])v++;
		if(dp[heap[k]]>dp[heap[v]]){
			swap(heap[k],heap[v]);
			k=v;
		}else break;
	}
}
void ins(int x){
	top++;heap[top]=x;
	int k=top;
	while(k>1){
		if(dp[heap[k>>1]]>dp[heap[k]]){
			swap(heap[k],heap[k>>1]);
			k>>=1;
		}else break;
	}
}
int main(){
	scanf("%d",&test);
	while(test--){
		scanf("%d%d",&n,&m);
		scanf("%s",s+1);
		int k=0;
		dp[0]=0;r=-1;l=0;top=0;
		for(int i=1;i<=n;i++){
			dp[i]=dp[i-1]+1;
			while((i-heap[1]>m)&&(top))del(),l++;
			if(top)dp[i]=min(dp[i],dp[heap[1]]+1);
			if(s[i]==s[i+1]){
				for(int j=r+1;j<i;j++)ins(j);
				r=i-1;
			}
		}
		printf("%d\n",dp[n]-1);
	}
}