Pluto_Rabbit's Blog

蒟蒻妹纸一枚，轻拍

【蒟蒻】NOIP的各种

Jacinth posted @ 2015年9月03日 09:16 in NOIP with tags Learning NOIP , 728 阅读

好久不见，那啥在做一些可能很**的联赛题哎。。。怪我？

NOIP2014 DAY1 T3 飞扬的小鸟

题目： https://vijos.org/p/1907

唔，其实比赛的时候想到了标算，但至今不知道当时怎么死在了75分

然而重新写一遍就A了是smg！！！（咆哮

#include <iostream> 
#include <cstring>
#include <cstdio>
#include <cstdlib> 
#include <algorithm>
#define INF 0x7fffffff
#define NN 10010
#define MM 1010
using namespace std;

int n,m,k,tot,ans,p;
int x[NN],y[NN],l[NN],r[NN],dp[NN][MM];
bool f[NN][MM],ff,fl[NN];

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	memset(l,0,sizeof(l));
	memset(r,0,sizeof(r));
	memset(fl,0,sizeof(fl));
	for (int i=1;i<=n;++i) 
	{
		scanf("%d%d",&x[i],&y[i]);
	}
	for (int i=1;i<=k;++i) 
	{
		scanf("%d",&p);
		scanf("%d%d",&l[p],&r[p]);
		fl[p]=1;
	}
	memset(f,0,sizeof(f));
	memset(dp,0x3f,sizeof(dp));
	tot=0;
	for (int i=1;i<=m;++i)  f[0][i]=1,dp[0][i]=0;
	for (int i=1;i<=n;++i) 
	{
		for (int j=x[i]+1;j<=m;++j)
			if (f[i-1][j-x[i]]) f[i][j]=1,dp[i][j]=min(dp[i][j],dp[i-1][j-x[i]]+1);
		for (int j=x[i]+1;j<=m;++j)
			if (f[i][j-x[i]])  f[i][j]=1,dp[i][j]=min(dp[i][j],dp[i][j-x[i]]+1);
		for (int j=1;j<=m-y[i];++j) 
			if (f[i-1][j+y[i]]) f[i][j]=1,dp[i][j]=min(dp[i][j],dp[i-1][j+y[i]]);
		for (int j=m-x[i]+1;j<=m;++j)
		{
			if (f[i-1][j]) dp[i][m]=min(dp[i][m],dp[i-1][j]+1),f[i][m]=1;
			if (f[i][j]) dp[i][m]=min(dp[i][m],dp[i][j]+1),f[i][m]=1;
		}
		if (fl[i]) 
		{
			for (int j=1;j<=l[i];++j)  f[i][j]=0;
			for (int j=r[i];j<=m;++j) f[i][j]=0;
		}
		ff=0;
		for (int j=1;j<=m;++j) if (f[i][j]) { ff=1; break;}
		if (!ff)
		{
			puts("0");
			printf("%d\n",tot);
			return 0;
		}
		else
		if (fl[i]) tot++;
	}
	ans=INF;
	for (int i=1;i<=m;++i) if (f[n][i]) ans=min(ans,dp[n][i]);
	puts("1"); printf("%d\n",ans);
	return 0;
}

NOIP2013 DAY1 T3 货车运输

题目： http://vijos.org/p/1843

冰茶几+LCA+DFS+乱搞什么的肯定能做出

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

struct REC {int x,y,v;};
REC a[50010];
int head[20010],ne[20010],u[20010],w[20010],father[20010],fa[10010][20],dis[10010][20],deep[10010];
bool used[10010];
int n,m,xx,yy,total,tot,q,qx,qy;

void Insert(int xx,int yy,int zz)
{
	ne[++total]=head[xx]; head[xx]=total; u[total]=yy; w[total]=zz;
	ne[++total]=head[yy]; head[yy]=total; u[total]=xx; w[total]=zz;
}

int find_father(int xx)
{
	return father[xx]==xx?xx:father[xx]=find_father(father[xx]);
}

bool cmp(const REC xx,const REC yy)
{
	return xx.v>yy.v;
}

void DFS(int xx)
{
	used[xx]=1;
	for (int i=1;i<=16;++i)
	{
		if (deep[xx]<(1<<i)) break;
		fa[xx][i]=fa[fa[xx][i-1]][i-1];
		dis[xx][i]=min(dis[xx][i-1],dis[fa[xx][i-1]][i-1]);
	}
	for (int i=head[xx];i;i=ne[i])
	{
		if (used[u[i]]) continue;
		fa[u[i]][0]=xx;
		dis[u[i]][0]=w[i];
		deep[u[i]]=deep[xx]+1;
		DFS(u[i]);
	}
	return;
}

int LCA(int xx,int yy)
{
	if (deep[xx]<deep[yy]) swap(xx,yy);
	int tmp=deep[xx]-deep[yy];
	for (int i=0;i<=16;++i) if ((1<<i)&tmp) xx=fa[xx][i];
	for (int i=16;i>=0;--i)
		if (fa[xx][i]!=fa[yy][i])
		{
			xx=fa[xx][i]; yy=fa[yy][i];
		}
	if (xx==yy) return xx;
	return fa[xx][0];
}

int ASK(int xx,int yy)
{
	int minn=0x7fffffff;
	int tmp=deep[xx]-deep[yy];
	for (int i=0;i<=16;++i)
	{
		if (tmp&(1<<i))
		{
			minn=min(minn,dis[xx][i]);
			xx=fa[xx][i];
		}
	}
	return minn;
}

int main()
{
	memset(dis,127/3,sizeof(dis));
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) father[i]=i;
	for (int i=1;i<=m;++i)	scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
	sort(a+1,a+1+m,cmp);
	total=0;
	for (int i=1;i<=m;++i)
	{
		int xx=find_father(a[i].x),yy=find_father(a[i].y);
		if (xx!=yy)
		{
			father[xx]=yy;
			Insert(a[i].x,a[i].y,a[i].v);
			++tot;
			if (tot==n-1) break;
		}
	}
	for (int i=1;i<=n;++i) if (!used[i]) DFS(i);
	scanf("%d",&q);
	for (int i=1;i<=q;++i)
	{
		scanf("%d%d",&qx,&qy);
		if (find_father(qx)!=find_father(qy)) puts("-1");
		else
		{
			int tmp=LCA(qx,qy);
			printf("%d\n",min(ASK(qx,tmp),ASK(qy,tmp)));
		}
	}
	return 0;
}

NOIP2013 DAY2 T1 同余方程

题目： http://vijos.org/p/1781

数学题，%%%Scarlet数论大神

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;

LL a,b,x,y,ans;

LL GCD(LL a,LL b,LL &xx,LL &yy)
{
	if (!b)
	{
		xx=1; yy=0; return a;
	}
	else
	{
		LL sum=GCD(b,a%b,xx,yy);
		LL tmp=xx;
		xx=yy; yy=tmp-(a/b)*yy;
		return sum;
	}
}

int main()
{
	scanf("%lld%lld",&a,&b);
	LL tmp=GCD(a,b,x,y);
	ans=x%b;
	while (x<0) x+=b;
	printf("%lld\n",x);
	return 0;
}

NOIP2013 DAY2 T2 花匠

题目： http://vijos.org/p/1845

DP一眼题，然后想着把O(n^2）弄到O(n）就可以了

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define NN 100100
using namespace std;

int f[NN][3],a[NN];
int n;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	f[1][0]=f[1][1]=1;  
	for (int i=1;i<n;++i)
	{
		if (a[i]>a[i+1])
		{
			f[i+1][0]=f[i][0];
			f[i+1][1]=max(f[i][1],f[i][0]+1);
		}
		else
		if (a[i]<a[i+1])
		{
			f[i+1][1]=f[i][1];
			f[i+1][0]=max(f[i][1]+1,f[i][0]);
		}
		else
		{
			f[i+1][1]=f[i][1];
			f[i+1][0]=f[i][0];
		}
	}
	printf("%d\n",max(f[n][1],f[n][0]));
	return 0;
}

NOIP2012 DAY1 T3 开车旅行

题目： http://vijos.org/p/1780

嗯，就是倍增

先用set预处理出每个城市的最近与次近

然后令g[i][j]为从i点走2^j个轮回（注意是轮回，不是步）后的位置，f[i][j][0]为从i点走2^j个轮回后A走过的距离，f[i][j][1]为从i点走2^j个轮回后B走过的距离。

那么很容易推出：

g[i][j]=g[g[i][j-1]][j-1];

f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];

f[i][j][1]=f[i][j-1][0]+f[g[i][j-1]][j-1][1];

然后我会告诉你这样就好了哒？

#include <iostream>
#include <cstdio>
#include <set>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define LL long long
#define NN 100010
using namespace std;

struct REC
{
	int h,num;
	bool operator <(const REC xx) const{
		return h<xx.h;
	}
};
REC a[NN];
set <REC> s;
set <REC> ::iterator it;
LL f[NN][21][2];
int ne[NN][2],dis[NN][2],g[NN][21];
int n,m,x0,s0,ans=0;

void Update(REC xx, REC yy)
{
	if (!ne[xx.num][0])
	{
		ne[xx.num][0]=yy.num;
		dis[xx.num][0]=abs(xx.h-yy.h);
	}
	else
	if (abs(xx.h-yy.h)<dis[xx.num][0] || (abs(xx.h-yy.h)==dis[xx.num][0] && yy.h<a[ne[xx.num][0]].h))
	{
		ne[xx.num][1]=ne[xx.num][0];
		dis[xx.num][1]=dis[xx.num][0];
		ne[xx.num][0]=yy.num;
		dis[xx.num][0]=abs(xx.h-yy.h);
	}
	else
	if (abs(xx.h-yy.h)<dis[xx.num][1] || (abs(xx.h-yy.h)==dis[xx.num][1] && yy.h<a[ne[xx.num][1]].h))
		ne[xx.num][1]=yy.num,dis[xx.num][1]=abs(xx.h-yy.h);
	else
	if (!ne[xx.num][1]) ne[xx.num][1]=yy.num,dis[xx.num][1]=abs(xx.h-yy.h);
	return ;
}

void Query(int ss,int xx,LL &disa,LL &disb)
{
	for (int j=20;j>=0;--j)
	{
		if (f[ss][j][0]+f[ss][j][1]<=xx && g[ss][j])
		{
			disa+=f[ss][j][0]; disb+=f[ss][j][1];
			xx-=(f[ss][j][0]+f[ss][j][1]); ss=g[ss][j];
		}
	}
	if (ne[ss][1] && dis[ss][1]<=xx) disa+=dis[ss][1];
}

int main() 
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i].h),a[i].num=i;
	for (int i=n;i>=1;i--)
	{
		s.insert(a[i]); it=s.find(a[i]);
		if (it!=s.begin())
		{
			it--;
			Update(a[i],*it);
			if (it!=s.begin())
			{
				it--;
				Update(a[i],*it);
				it++;
			}
			it++;
		}
		if ((++it)!=s.end())
		{
			Update(a[i],*it);
			it++;
			if (it!=s.end())
				Update(a[i],*it);
			it--;
		}
		it--;
	}
	for (int i=1;i<=n;++i)
	{
		g[i][0]=ne[ne[i][1]][0];
		f[i][0][0]=dis[i][1];
		f[i][0][1]=dis[ne[i][1]][0];
	}
	for (int j=1;j<=20;++j)
		for (int i=1;i<=n;++i)
		{
			g[i][j]=g[g[i][j-1]][j-1];
			f[i][j][0]=f[i][j-1][0]+f[g[i][j-1]][j-1][0];
			f[i][j][1]=f[i][j-1][1]+f[g[i][j-1]][j-1][1];
		}
	scanf("%d",&x0);
	LL ansa=1e15,ansb=0;
	for (int i=1;i<=n;++i)
	{
		LL disa=0,disb=0;
		Query(i,x0,disa,disb);
		if (disb&&(!ans||ansa*disb>ansb*disa))
		{
			ans=i;
			ansa=disa,ansb=disb;
		}
	}
	printf("%d\n",ans);
	scanf("%d",&m);
	while (m--)
	{
		scanf("%d%d",&s0,&x0);
		LL disa=0,disb=0;
		Query(s0,x0,disa,disb);
		printf("%lld %lld\n",disa,disb);
	}
	return 0;
}

NOIP2012 DAY2 T2 借教室

题目： http://vijos.org/p/1782

鬼畜用了二分答案，其实还是8错滴~~~感觉比线段树好写一点哎

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define NN 1000100
using namespace std;

int n,m,l,r,sum;
int rr[NN],d[NN],s[NN],t[NN],a[NN];
bool f,ff;

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%d",&rr[i]);
	for (int i=1;i<=m;++i) scanf("%d%d%d",&d[i],&s[i],&t[i]);
	l=1; r=m+1;
	f=1;
	while (l<r)
	{
		ff=0;
		int mid=(l+r)>>1;
		for (int i=l;i<=mid;++i)
		{
			a[s[i]]+=d[i];
			a[t[i]+1]-=d[i];
		}
		sum=0;
		for (int i=1;i<=n;++i)
		{
			sum+=a[i];
			if (sum>rr[i]) 
			{
				f=0;
				ff=1;
				break;
			}
		}
		if (ff)
		{
			r=mid;
			for (int i=l;i<=mid;++i)
			{
				a[s[i]]-=d[i];
				a[t[i]+1]+=d[i];
			}
		} 
		else l=mid+1;
	}
	if (f) puts("0");
	else
	{
		puts("-1");
		printf("%d\n",l);
	}
	return 0;
}

NOIP2012 DAY2 T3 疫情控制

题目：http://vijos.org/p/1783

呀，noip膜你赛竟然考真·noip题，不过不然不会这么早去做它了QAQ

二分+贪心判断

先向上移动到首都下一层的几个点，然后某个点有好几个军队的话，就要考虑到首都下一层可能有几个点还是空着的，就是要通过首都移动过去，排序贪心什么的

（↑_↑上面的好混乱）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define NN 50010
#define LL long long
using namespace std;

int head[NN*2],ne[NN*2],u[NN*2],w[NN*2];
bool leaf[NN],tmpp[NN],used[NN];
LL times[NN],diss[NN],dis[NN];
int mark[NN],army[NN],ances[NN],n,m,fa[NN],Q[NN],tmp1[NN],tmp2[NN];
int x,y,z,t,hh,tott;
LL r,tot,l;

void Build(int x,int y,int z)
{
	ne[++tott] = head[x]; head[x] = tott; u[tott] = y; w[tott] = z;
	ne[++tott] = head[y]; head[y] = tott; u[tott] = x; w[tott] = z;
}

bool cmp1(const int xx,const int yy)
{
	return diss[xx]<diss[yy];
}

bool cmp2(const int xx,const int yy)
{
	return dis[army[xx]]>dis[army[yy]];
}

bool Check(LL mid)
{
	memset(times,-1,sizeof(times));
	memset(used,0,sizeof(used));
	memcpy(tmpp,leaf,sizeof(tmpp));
	for (int i=n;i>=1;--i)
	{
		int h=Q[i];
		if (mark[h]&&dis[h]>mid) times[h]=mid;
		times[fa[h]]=max(times[fa[h]],times[h]-diss[h]);
		if (times[h]>=0) tmpp[h]=1;
		if (!tmpp[h]) tmpp[fa[h]]=0;
	}
	for (int i=1;i<=m;++i)
		if (dis[army[i]]<=mid) used[i]=1;
	tmp1[0]=tmp2[0]=0;
	for (int i=head[1];i;i=ne[i])
		if (!tmpp[u[i]]) tmp1[++tmp1[0]]=u[i];
	for (int i=1;i<=m;++i)
		if (used[i]) tmp2[++tmp2[0]]=i;
	sort(tmp1+1,tmp1+1+tmp1[0],cmp1);
	sort(tmp2+1,tmp2+1+tmp2[0],cmp2);
	int jj=1;
	for (int i=1;i<=tmp2[0];++i)
	{
		if (!tmpp[ances[army[tmp2[i]]]]) tmpp[ances[army[tmp2[i]]]]=1;
		else if (diss[tmp1[jj]]+dis[army[tmp2[i]]]<=mid) tmpp[tmp1[jj]]=1;
		while (jj<=tmp1[0] && tmpp[tmp1[jj]]) jj++;
		if (jj>tmp1[0]) return 1;
	}
	return 0;
}

queue <int> que;
void BFS(int xx)
{
	hh=1; t=0; Q[++t]=xx;
	while (hh<=t)
	{
		int h=Q[hh++];
		leaf[h]=0;
		for (int i=head[h];i;i=ne[i])
		{
			int v=u[i];
			if (v==fa[h]) continue;
			fa[v]=h;
			dis[v]=dis[h]+w[i];
			diss[v]=w[i];
			if (h!=xx) ances[v]=ances[h];
			else ances[v]=v;
			leaf[h]=1; Q[++t]=v;
		}
	}
}

int main()
{
	scanf("%d",&n); 
	tott = 0;
	tot=1;
	for (int i=1;i<n;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		Build(x,y,z);
		tot+=(LL)z;
	}
	scanf("%d",&m);
	memset(mark,0,sizeof(mark));
	for (int i=1;i<=m;++i) scanf("%d",&army[i]),mark[army[i]]=1;
	BFS(1);
	l=0; r=tot;
	while (l<r-1)
	{
		LL mid=(l+r)>>1;
		if (Check(mid)) r=mid; else l=mid;
	}
	if (r==tot) puts("-1"); else printf("%lld\n",r);
	return 0;
}

NOIP2011 DAY1 T2 选择客栈

题目： http://codevs.cn/problem/1135/

这真是斯波题啊，O（nk）乱搞表示毫无压力

就是倒着处理一遍，然后正着摞一遍

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define NN 200010
using namespace std;

int n,k,p;
int a[NN],b[NN],po[NN],f[NN][55];
long long ans;

int main()
{
	scanf("%d%d%d",&n,&k,&p);
	for (int i=1;i<=n;++i)
		scanf("%d%d",&a[i],&b[i]);
	memset(f,0,sizeof(f));
	po[n+1]=n+1;
	for (int i=n;i>=1;--i)
	{
		if (b[i]<=p) po[i]=i; else po[i]=po[i+1];
		for (int j=0;j<k;++j) f[i][j]=f[i+1][j];
		f[i][a[i]]++;
	}
	ans=0;
	for (int i=1;i<=n;++i)
	{
		if (po[i]!=i)
		{
			ans+=f[po[i]][a[i]];
		}
		if (po[i]==i)
		{
			ans+=f[i+1][a[i]];
		}
	}
	printf("%lld\n",ans);
	return 0;
}

NOIP2011 DAY2 T1 计算系数

题目：http://vijos.org/p/1739

其实就是C(k,n)*a^n*b*m就好了

然后求C(k,n)的时候其实挺简单的啊。。。（逆元其实挺好玩的辣）

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define mod 10007
using namespace std;

long long ans;
int a,b,k,n,m;
long long ny[1010];

long long ksm(int xx,int yy)
{
	long long tmp=1,x=xx;
	while (yy)
	{
		if (yy&1) tmp=tmp*x%mod;
		yy>>=1; x=x*x%mod;
	}
	return tmp;
}

int main()
{
	scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
	ans=1;
	for (int i=1;i<=k;++i) ny[i]=ksm(i,mod-2);
	for (int i=k;i>=(k-n+1);--i) ans=(ans*i)%mod;
	for (int i=1;i<=n;++i) ans=(ans*ny[i])%mod;
	ans=(ans*ksm(a,n)%mod)*ksm(b,m)%mod;
	printf("%lld\n",ans);
	return 0;
}

NOIP2010 T3 关押罪犯

题目： http://vijos.org/p/1776

并查集水题

排序的时候n和m打反了，调了老久都没调出，感觉可以自爆了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NN 20010
#define MM 100010
using namespace std;

struct REC
{
	int x,y,w;
};

int father[NN],e[NN];
REC a[MM];
int n,m;

bool cmp(const REC xx,const REC yy)
{
	return xx.w>yy.w;
}

int find_father(int xx)
{
	if (father[xx]==xx) return xx;
	int fx=father[xx];
	father[xx]=find_father(fx);
	return father[xx];
}

void doing(int xx,int yy)
{
	int xa=find_father(xx),ya=find_father(yy);
	father[xa]=ya;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;++i) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
	for (int i=1;i<=n;++i) father[i]=i;
	memset(e,0,sizeof(e));
	sort(a+1,a+1+m,cmp);
	for (int i=1;i<=m;++i)
	{
		int xa=find_father(a[i].x),ya=find_father(a[i].y);
	 	if (xa==ya) 
		{
			printf("%d\n",a[i].w); return 0;
		}
		if (e[a[i].x]==0 && e[a[i].y]==0){ e[a[i].x]=a[i].y; e[a[i].y]=a[i].x; continue;}
		if (e[a[i].x]==0) e[a[i].x]=a[i].y;
		if (e[a[i].y]==0) e[a[i].y]=a[i].x;
		doing(e[a[i].x],a[i].y);
		doing(e[a[i].y],a[i].x);
	}
	puts("0");
	return 0;
}

NOIP2008 T4 双栈排序

题目： http://vijos.org/p/1605

DFS染色一下什么的，然后就乱搞

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <stack>
#define NN 1010
using namespace std;

stack<int> stacka,stackb;
bool ff;
int f[NN],a[NN],colour[NN];
bool e[NN][NN];
int n,k;

void work(int xx,int yy)
{
	colour[xx]=yy;
	for (int i=1;i<=n;++i)
	if (e[xx][i])
	{
		if (yy==colour[i]) { ff=1; return; }
		if (colour[i]==0) work(i,3-yy);
		if (ff) return;
	}
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	f[n+1]=0x7fffffff;
	for (int i=n;i>=1;--i) f[i]=min(a[i],f[i+1]);
	for (int i=1;i<=n;++i)
		for (int j=i+1;j<=n;++j)
		{
			if (a[i]<a[j] && f[j+1]<a[i])
			e[i][j]=e[j][i]=1;
		}
	memset(colour,0,sizeof(colour));
	ff=0;
	for (int i=1;i<=n;++i)
		if (colour[i]==0) work(i,1);
	if (ff)
	{
		puts("0"); return 0;
	}
	k=1;
	for (int i=1;i<=n;++i)
	{
		if (colour[i]==1)
		{
			stacka.push(a[i]);
			printf("a ");
		}
		else
		{
			stackb.push(a[i]);
			printf("c ");
		}
		while (((!stacka.empty())&&stacka.top()==k) || ((!stackb.empty())&&stackb.top()==k))
		{
			if ((!stacka.empty())&&stacka.top()==k)
			{
				printf("b ");
				stacka.pop();
			}
			else
			{
				printf("d ");
				stackb.pop();
			}
			k++;
		}
	}
	puts("");
	return 0;
}

（感觉好像未完待续。。。）

Small_feed 评论 (0)

登录 *


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