3
30
2016
1

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: 918
Small_feed 评论 (1)
1
[回复]
CBSE 10th Model Pape 说:
Aug 27, 2022 03:31:19 PM

CBSE 10th Guess Paper 2023 Published by Central Board Secondary School Examination (CBSE) Board only. CBSE 10th Student you can Download Question Paper for Secondary School Examination 2023 from Our websites also.CBSE 10th Model Paper Central Board 10th class Students have been in Search of the Previous Papers over the Internet. as Exams are Approaching Authorities have Released all the CBSE 10th Model Test Paper 2023 in the form of Pdf for all the subjects in their official site. Students can Download those uploaded Class X Model Papers to Check out the Complete Pattern of the Paper, Marking Scheme etc.


登录 *


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