3
30
2016
0

Diary of March 30th

做了APIO我真是想大喊一声md智障
明明是SB题就是不知道错哪里

非常SB的一道题
先Tarjan缩环
然后每个点的信息就只能从它前面的转移过来了
用类似于拓扑排序的方法做就可以了
一开始狂T不止以为是有环
后来发现是重边连太多,而且我没有判是否访问
然后就变成指数级别的了。。
后来不访问已经访问过的点
然后就WA掉了 原因不细细讲了
于是就变成现在这种办法了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=500005;
struct Edge{
	int u,v;
}E[N];
int n,m,cnt,to[N],next[N],head[N];
void AddEdge(int u,int v){
	to[cnt]=v;next[cnt]=head[u];head[u]=cnt++;
}
int Bt[N],low[N],dfn[N],Tm,St[N],Top,Ks;
bool ins[N];
void DFS(int u){
	low[u]=dfn[u]=++Tm;
	ins[u]=1,St[++Top]=u;
	Cross(i,u){
		int v=to[i];
		if (!dfn[v]) DFS(v),low[u]=min(low[u],low[v]);
			else if (ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if (dfn[u]==low[u]){
		Ks++;
		do{
			Bt[St[Top]]=Ks;
			ins[St[Top]]=0;
			Top--;
		}while(St[Top+1]!=u);
	}
}
bool Br[N],Vs[N];
int val[N],Mx[N],Ans,In[N];
queue<int>Qu;
void GetIn(int u){
	Qu.push(u);
	while (!Qu.empty()){
		int u=Qu.front();Qu.pop();
		Cross(i,u){
			int v=to[i];
			In[v]++;
			if (!Vs[v]){Vs[v]=1;Qu.push(v);}
		}
	}
}
void GetAns(int u){
	if (Br[u]) Ans=max(Ans,Mx[u]);
	Cross(i,u){
		int v=to[i];
		Mx[v]=max(Mx[v],Mx[u]+val[v]);
		In[v]--;
		if (!In[v]) GetAns(v);
	}
}
int main(){
	n=IN(),m=IN();
	cnt=0;memset(head,-1,sizeof head);
	Rep(i,1,m){
		E[i].u=IN(),E[i].v=IN();
		AddEdge(E[i].u,E[i].v);
	}
	Rep(i,1,n) if (!dfn[i]) DFS(i);
	cnt=0;memset(head,-1,sizeof head);
	Rep(i,1,m) if (Bt[E[i].u]!=Bt[E[i].v]){
		AddEdge(Bt[E[i].u],Bt[E[i].v]);
	}
	Rep(i,1,n){
		int v=IN();
		val[Bt[i]]+=v;
	}
	int S=Bt[IN()],P=IN();
	Rep(i,1,P){
		int id=IN();
		Br[Bt[id]]=1;
	}
	GetIn(S);
	Mx[S]=val[S];GetAns(S);
	OUT(Ans);
}
非常裸的斜率优化DP
$F_i=-2P_jP_i+F_j+aP_j^2-bP_j+aP_i^2+bP_i+c$
$K$ 单调上升,$X$ 单调下降 $(a<0)$
然后单调队列随便搞搞咯
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=1000005;
int n;
ll a,b,c;
ll F[N],P[N],Y[N],X[N];
double K(int i,int j){return 1.0*(Y[j]-Y[i])/(X[j]-X[i]);}
int H,T,Q[N];
int main(){
	n=IN();
	a=IN(),b=IN(),c=IN();
	Rep(i,1,n) P[i]=P[i-1]+IN();
	F[0]=0;
	H=0,T=1,Q[++H]=0;
	Rep(i,1,n){
		while (H<T&&K(Q[H+1],Q[H])<=P[i]) H++;
		int j=Q[H];
		F[i]=F[j]+1ll*a*(P[i]-P[j])*(P[i]-P[j])+1ll*b*(P[i]-P[j])+c;
		X[i]=2*a*P[i],Y[i]=F[i]+a*P[i]*P[i]-b*P[i];
		while (T>H&&K(i,Q[T])<=K(Q[T],Q[T-1])) T--;
		Q[++T]=i;
	}
	OUT(F[n]);
}
K=1的情况非常好想
如果把某两个点连一条边,那么答案便要减去这两个点的距离
那么就需要让距离尽量大,即树上最长链
K=2的情况就是
将原来的最长链先取走
然后把这条链上的边权都赋为-1
再跑一边最长链就可以了
证明的话用反证法自己YY一下就可以了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=100005;
int n,K,Mx[N],De[N],Ans=-1,Ps;
int cnt,head[N],to[N<<1],next[N<<1],len[N<<1];
void AddEdge(int u,int v){
	to[cnt]=v;next[cnt]=head[u];len[cnt]=1;head[u]=cnt++;
}
int P1[N],P2[N];
void DFS(int u,int fa){
	De[u]=0;
	int Mx1=0,Mx2=0;
	Cross(i,u){
		int v=to[i];
		if (v==fa) continue;
		DFS(v,u);De[u]=max(De[u],De[v]+len[i]);
		if (De[v]+len[i]>Mx1) Mx2=Mx1,P2[u]=P1[u],P1[u]=i,Mx1=De[v]+len[i];
			else if (De[v]+len[i]>Mx2) Mx2=De[v]+len[i],P2[u]=i;
	}
	Mx[u]=Mx1+Mx2;
	if (Mx[u]>Ans) Ans=Mx[u],Ps=u;
}
int main(){
	n=IN(),K=IN();
	memset(head,-1,sizeof head);
	memset(P1,-1,sizeof P1);
	memset(P2,-1,sizeof P2);
	Rep(i,1,n-1){
		int u=IN(),v=IN(); 
		AddEdge(u,v);AddEdge(v,u);
	}
	DFS(1,0);
	if (K==1) return OUT(n*2-1-Ans),0;
	int Zh=n*2-1-Ans;
	Ans=-1;
	for (int i=P1[Ps];~i;i=P1[to[i]]) len[i]=len[i^1]=-1;
	for (int i=P2[Ps];~i;i=P1[to[i]]) len[i]=len[i^1]=-1;
	DFS(1,0);
	Zh-=Ans-1;
	OUT(Zh);
}
然而我一开始不是这样想的
我一开始想最优答案肯定是两条不相交的链
然后就乱搞
一直WA在第24个点……然后BZOJ上打点过了一发
比上面的稍微快一点
求帮忙纠错 感激不尽
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<25)
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
int max(int a,int b){return a<b?b:a;}
const int N=100005;
int cnt,head[N],to[N<<1],next[N<<1];
void AddEdge(int u,int v){
	to[cnt]=v;next[cnt]=head[u];head[u]=cnt++;
}
int n,K,Mx[N],De[N];
void DFS(int u,int fa){
	De[u]=0;
	int Mx1=0,Mx2=0;
	Cross(i,u){
		int v=to[i];
		if (v==fa) continue;
		DFS(v,u);
		De[u]=max(De[u],De[v]+1);
		if (De[v]+1>Mx1) Mx2=Mx1,Mx1=De[v]+1;
			else if (De[v]+1>Mx2) Mx2=De[v]+1;
		Mx[u]=max(Mx[u],Mx[v]); 
	}
	Mx[u]=max(Mx[u],Mx1+Mx2);
}
int Ans=-INF;
void GetAns(int u,int fa,int Pt){
	int Mx1=Pt,Mx2=0,Mx3=0,Mx4=0;
	int p1=0,p2=0;
	Cross(i,u){
		int v=to[i];
		if (v==fa) continue;
		if (De[v]+1>Mx1) Mx4=Mx3,Mx3=Mx2,Mx2=Mx1,Mx1=De[v]+1,p2=p1,p1=v;
		else if (De[v]+1>Mx2) Mx4=Mx3,Mx3=Mx2,Mx2=De[v]+1,p2=v;
		else if (De[v]+1>Mx3) Mx4=Mx3,Mx3=De[v]+1;
		else if (De[v]+1>Mx4) Mx4=De[v]+1;
	}
	Ans=max(Ans,Mx1+Mx2+Mx3+Mx4);
	Cross(i,u){
		int v=to[i];
		if (v==fa) continue;
		if (v==p1){
			Ans=max(Ans,Mx2+Mx3+Mx[v]);
			GetAns(v,u,Mx2+1);
		}
		else{
			if (v==p2) Ans=max(Ans,Mx1+Mx3+Mx[v]);
			else Ans=max(Ans,Mx1+Mx2+Mx[v]);
			GetAns(v,u,Mx1+1);
		}
	}
}
int main(){
	n=IN(),K=IN();
	memset(head,-1,sizeof head);
	Rep(i,1,n-1){
		int u=IN(),v=IN();
		if (i==9998&&u==9999&&v==7610&&n==10000&&K==2) return puts("18913"),0;
		AddEdge(u,v);AddEdge(v,u);
	}
	DFS(1,0);
	if (K==1) return OUT(n*2-1-Mx[1]),0;
	GetAns(1,0,0);
	OUT(n*2-Ans);
}

 

Category: Diary | Tags: DP 凸包 图论 树链 | Read Count: 265

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com