[Contest] IOI2011 day1 題目彙總

跟着ZZY神犇刷ioi題

garden

不會做，隻會做倍增69分

以後再填坑

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

inline char nc()
{
	static char buf[100000],*p1=buf,*p2=buf;
	if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
	return *p1++;
}

inline void read(int &x){
	char c=nc(),b=1;
	for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
	for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

int N,M,P,Q;
int G[2005];
int R[150005][2];
int size[150005];
int f1[150005],f2[150005];
int F1[150005][35],F2[150005][35];
int Enf1[150005][35],Enf2[150005][35];
int tot;

inline int Query(int s,int K){
	int flag=0;
	for (int k=30;k>=0;k--)
		if (K&(1<<k))
		{
			if (!flag || size[s]==1)
				flag=Enf1[s][k],s=F1[s][k];
			else
				flag=Enf2[s][k],s=F2[s][k];
		}
	return s;
}

int main()
{
	freopen("t.in","r",stdin);
	freopen("t.out","w",stdout);
	read(N); read(M); read(P); P++;
	for (int i=1;i<=M;i++)
		read(R[i][0]),read(R[i][1]),R[i][0]++,R[i][1]++;
	for (int i=1;i<=M;i++)
	{
		int u=R[i][0],v=R[i][1];
		size[u]++; size[v]++;
		if (!f1[u]) f1[u]=v; else if (!f2[u]) f2[u]=v;
		if (!f1[v]) f1[v]=u; else if (!f2[v]) f2[v]=u;
	}
	for (int i=1;i<=N;i++)
	{
		F1[i][0]=f1[i]; if (f1[f1[i]]==i) Enf1[i][0]=1;
		F2[i][0]=f2[i]; if (f1[f2[i]]==i) Enf2[i][0]=1;
	}
	for (int k=1;k<=30;k++)
		for (int i=1;i<=N;i++)
		{
			if (Enf1[i][k-1] && size[F1[i][k-1]]!=1)
			{
				F1[i][k]=F2[F1[i][k-1]][k-1];
				Enf1[i][k]=Enf2[F1[i][k-1]][k-1];
			}
			else
			{
				F1[i][k]=F1[F1[i][k-1]][k-1];
				Enf1[i][k]=Enf1[F1[i][k-1]][k-1];
			}
			if (Enf2[i][k-1] && size[F2[i][k-1]]!=1)
			{
				F2[i][k]=F2[F2[i][k-1]][k-1];
				Enf2[i][k]=Enf2[F2[i][k-1]][k-1];
			}
			else
			{
				F2[i][k]=F1[F2[i][k-1]][k-1];
				Enf2[i][k]=Enf1[F2[i][k-1]][k-1];
			}
		}
	read(Q);
	for (int i=1;i<=Q;i++)
		read(G[i]);
	for (int i=1;i<=Q;i++)
	{
		int ans=0;
		for (int j=1;j<=N;j++)
			if (Query(j,G[i])==P)
				ans++;
		printf("%d\n",ans);
	}
	return 0;
}
           

ricehub

單調的維護一下中位數和sum

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;

inline char nc()
{
	static char buf[100000],*p1=buf,*p2=buf;
	if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
	return *p1++;
}

inline void read(ll &x){
	char c=nc(),b=1;
	for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
	for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

ll n,M,B,ans;
ll X[100005];
ll L,R,Mid,Sum,Road;

inline bool TryRight(){
	if (R==n) return 0;
	ll last=Sum;
	Sum+=X[++R]-X[Mid];
	if (Mid!=(L+R)>>1)
	{
		Mid++;
		Road=X[Mid]-X[Mid-1];
		Sum+=(Mid-1-L+1)*Road;
		Sum-=(R-Mid+1)*Road;
	}
	if (Sum>B) 
	{
		Sum=last; R--; Mid=(L+R)>>1;
		return 0;
	}
	return 1;
}

int main()
{
	freopen("t.in","r",stdin);
	freopen("t.out","w",stdout);
	read(n); read(M); read(B);
	for (int i=1;i<=n;i++) read(X[i]);
	R=1; L=1; Mid=1; Sum=0;
	while (TryRight());
	ans=max(ans,R-L+1);
	for (;L<n;)
	{
		if (L==R)
		{
			L++; R++; Sum=0; Mid=(L+R)>>1;
		}
		else
		{
			if (Mid==L)
			{
				Mid++;
				Road=X[Mid]-X[Mid-1];
				Sum+=(Mid-1-L+1)*Road;
				Sum-=(R-Mid+1)*Road;
			}
			Sum-=X[Mid]-X[L++];
			if (Mid!=(L+R)>>1)
			{
				Mid++;
				Road=X[Mid]-X[Mid-1];
				Sum+=(Mid-1-L+1)*Road;
				Sum-=(R-Mid+1)*Road;
			}
		}
		while (TryRight());
		ans=max(ans,R-L+1);
	}
	printf("%lld\n",ans);
	return 0;
}
           

Race

很早做過的一道題 樹分治裸題

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<queue>
#define V G[p].v
using namespace std;
typedef pair<int,int> abcd;

inline char nc()
{
	static char buf[100000],*p1=buf,*p2=buf;
	if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
	return *p1++;
}

inline void read(int &x)
{
	char c=nc(),b=1;
	for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
	for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

struct edge{
	int u,v,w;
	int next;
};

edge G[400005];
int head[200005],num=1;

inline void add(int u,int v,int w,int p)
{
	G[p].u=u; G[p].v=v; G[p].w=w; G[p].next=head[u]; head[u]=p;
}

inline void link(int u,int v,int w)
{
	add(u,v,w,++num); add(v,u,w,++num);
}

int n,K;
int del[200005];
int sum,size[200005];

int minimum,rt;

inline void Root(int u,int fa)
{
	int maximum=0;
	size[u]=1;
	for (int p=head[u];p;p=G[p].next)
		if (V!=fa && !del[V])
		{
			Root(V,u);
			size[u]+=size[V];
			maximum=max(maximum,size[V]);
		}
	maximum=max(maximum,sum-size[u]);
	if (maximum<minimum) minimum=maximum,rt=u;
}

int f[2000005];
int ans;

inline void dp(int u,int fa,int d,int len)
{
	if (K<d) return; 
	ans=min(ans,f[K-d]+len);
	for (int p=head[u];p;p=G[p].next)
		if (!del[V] && V!=fa)
			dp(V,u,d+G[p].w,len+1);
}

inline void update(int u,int fa,int d,int len,int flag)
{
	if (K<d) return;
	if (flag)
		f[d]=min(f[d],len);
	else 
		f[d]=n;
	for (int p=head[u];p;p=G[p].next)
		if (!del[V] && V!=fa)
			update(V,u,d+G[p].w,len+1,flag);
}

inline void solve(int u)
{
	del[u]=1; f[0]=0;
	for (int p=head[u];p;p=G[p].next)
		if (!del[V])
		{
			dp(V,u,G[p].w,1);
			update(V,u,G[p].w,1,1);
		}
	for (int p=head[u];p;p=G[p].next)
		if (!del[V])
			update(V,u,G[p].w,1,0);
	for (int p=head[u];p;p=G[p].next)
		if (!del[V])
		{
			minimum=n; sum=size[V]; Root(V,u);
			solve(rt);
		}
}

int main()
{
	int _u,_v,_w;
	freopen("t.in","r",stdin);
	freopen("t.out","w",stdout);
	read(n); read(K);
	for (int i=1;i<n;i++)
		read(_u),read(_v),read(_w),link(_u+1,_v+1,_w);
	for (int i=1;i<=K;i++) f[i]=n; f[0]=0;
	ans=n;
	minimum=n; sum=n; Root(1,0);
	solve(rt);
	if (ans==n)
		printf("-1\n");
	else 
		printf("%d\n",ans);
	return 0;
}