Pluto_Rabbit's Blog

蒟蒻妹纸一枚,轻拍

【蒟蒻】NOIP的各种

Jacinth posted @ 2016年11月14日 20:20 in NOIP with tags Learning NOIP , 243 阅读

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

(重新拉到首页,Timeline有些错乱,轻拍)

UPDATE 20161114: 增加了NOIP2015&NOIP2013华容道&NOIP2011mayan游戏&更改部分格式

之前的链接:http://lujiaxin.is-programmer.com/posts/181542.html

NOIP2015:http://lujiaxin.is-programmer.com/posts/187893.html

广告时间~%%%xmc:http://scarlet.is-programmer.com/posts/207004.html

NOIP2015 DAY1 T1 神奇的幻方

题目:https://vijos.org/p/1978

暴力模拟

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define LL long long
#define D double 
using namespace std;
struct REC
{
	int x,y;
};
int n;
REC a[2500];
int ans[50][50];
int main()
{
	freopen("magic.in","r",stdin); freopen("magic.out","w",stdout);
	scanf("%d",&n);
	memset(a,0,sizeof(a)); memset(ans,0,sizeof(ans));
	a[1].x=1; a[1].y=(n+1)>>1; ans[a[1].x][a[1].y]=1;
	for (int i=2;i<=n*n;++i)
	{
		if (a[i-1].x==1 && a[i-1].y!=n)
		{
			a[i].x=n; a[i].y=a[i-1].y+1; ans[a[i].x][a[i].y]=i; continue;
		} else
		if (a[i-1].y==n && a[i-1].x!=1)
		{
			a[i].x=a[i-1].x-1; a[i].y=1; ans[a[i].x][a[i].y]=i; continue;
		} else
		if (a[i-1].x==1 && a[i-1].y==n) 
		{
			a[i].x=a[i-1].x+1; a[i].y=a[i-1].y; ans[a[i].x][a[i].y]=i; continue;
		}
		else
		{
			if (ans[a[i-1].x-1][a[i-1].y+1]==0)
			{
				a[i].x=a[i-1].x-1; a[i].y=a[i-1].y+1; ans[a[i].x][a[i].y]=i; continue;
			}
			else
			{
				a[i].x=a[i-1].x+1; a[i].y=a[i-1].y; ans[a[i].x][a[i].y]=i; continue;
			}
		}
	}
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<n;++j) printf("%d ",ans[i][j]);
		printf("%d\n",ans[i][n]);
	}
	fclose(stdin); fclose(stdout);
	return 0;
}

NOIP2015 DAY1 T2 信息传递

题目:https://vijos.org/p/1979

大力BFS

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <ctime>
#define LL long long
#define D double 
#define NN 200020
using namespace std;
struct REC
{
	int p,fa;
};
int num[NN],ne[NN<<1],head[NN],v[NN<<1];
int n,x,tot,minn,tott;
int vis[NN];
queue<REC> que;
REC tmp;
void Build(int xx,int yy)
{
	ne[++tot]=head[xx]; v[tot]=yy; head[xx]=tot;
}
void BFS(int xx)
{
	while (!que.empty()) que.pop();
	vis[xx]=tott; num[xx]=1;
	tmp.p=xx; tmp.fa=0;
	que.push(tmp);
	while (!que.empty())
	{
		REC h=que.front(); que.pop();
		for (int i=head[h.p];i;i=ne[i])
		{
			if (vis[v[i]]==tott)
			{
				minn=min(minn,num[h.p]+1-num[v[i]]); continue;
			}
			else
			if (!vis[v[i]])
			{
				vis[v[i]]=tott;
				tmp.p=v[i]; tmp.fa=h.p; num[v[i]]=num[h.p]+1;
				que.push(tmp);
			}
		}
	}
	return;
}
int main()
{
	freopen("message.in","r",stdin); freopen("message.out","w",stdout);
	scanf("%d",&n); tot=0; minn=0x7fffffff;
	memset(ne,0,sizeof(ne)); memset(head,0,sizeof(head)); memset(v,0,sizeof(v));
	for (int i=1;i<=n;++i) 
	{
		scanf("%d",&x);
		Build(i,x);
	}
	memset(vis,0,sizeof(vis));
	tott=0;
	for (int i=1;i<=n;++i)
		if (!vis[i]) 
		{
			tott++; BFS(i);
		}
	printf("%d\n",minn);
	fclose(stdin); fclose(stdout);
	return 0;
}

NOIP2015 DAY1 T3 斗地主

题目:https://vijos.org/p/1980

考场上大暴力爆炸,难过

据说可以DP,蒟蒻只能DFS辣

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define LL long long
#define D double 
using namespace std;
struct REC
{
	int num,ne,cs;
};
REC sum[50];
bool f[50],huojian;
int x,y,tot,T,n,a[50],minn,one,two,three,four,maxx3,maxx4,checker[10];

void DFS(int pr,int tot)
{
	if (tot-maxx3>minn) return;
	if (pr>17)
	{
		int ans=tot;
		checker[1]=one,checker[2]=two,checker[3]=three,checker[4]=four;
		//去4 带走尽量多的2个对子 若不足带走两个单牌
		for (int w=1;w<=checker[4];++w)
		{
			if (checker[2]>=2) ans++,checker[2]-=2;
			else
			if (checker[1]>=2) ans++,checker[1]-=2;
			else
			if (checker[2]==1) ans++,checker[2]-=1;
			else ans++;
		}
		//去3 先带光对子,然后带光单牌
		for (int w=1;w<=checker[3];++w) 
		{
			if (checker[2]>0) ans++,checker[2]--;
			else
			if (checker[1]>0) ans++,checker[1]--;
			else ans++;
		}
		if (checker[1]>=2&&huojian) ans++,checker[1]-=2;
		ans+=checker[1]+checker[2];
		minn=min(ans,minn);
		return;
	}
	if (a[pr]==0)	{DFS(pr+1,tot);		return;}
	if (pr<=14)
	{
		bool flag;
		int t;
		if (pr+4<=14)
		{
			flag=1,t=0;
			for (int w=pr;w<=pr+4;++w) if (a[w]<1) {flag=0; break;}
			if (flag)
			{
				for (int w=pr;w<=pr+3;++w) a[w]--;
				for (int w=pr+4;w<=14;++w)
				if (a[w]>=1)
				{
					a[w]--; t=w; DFS(pr,tot+1);
				}
				else break;
				for (int w=pr;w<=t;++w) a[w]++;
			}
		} //单顺子 
		if (pr+2<=14)
		{
			flag=1,t=0;
			for (int w=pr;w<=pr+2;++w) if (a[w]<2) { flag=0; break;}
			if (flag)
			{
				for (int w=pr;w<=pr+1;++w) a[w]-=2;
				for (int w=pr+2;w<=14;++w)
				if (a[w]>=2)
				{
					a[w]-=2; t=w; DFS(pr,tot+1);
				}
				else break;
				for (int w=pr;w<=t;++w) a[w]+=2;
			}
		} //双顺子
		if (pr+1<=14)
		{
			flag=1,t=0;
			for (int w=pr;w<=pr+2;++w) if (a[w]<3) { flag=0; break;}
			if (flag)
			{
				a[pr]-=3;
				for (int w=pr+1;w<=14;++w)
				if (a[w]>=3)
				{
					a[w]-=3; t=w; DFS(pr,tot+1);
				}
				else break;
				for (int w=pr;w<=t;++w) a[w]+=3;
			}
		}  //三顺子 
	}
	if (a[pr]>=4)	{	++four; a[pr]-=4; DFS(pr,tot); --four; a[pr]+=4;	}//4
	if (a[pr]>=3)	{	++three; a[pr]-=3; DFS(pr,tot); --three; a[pr]+=3;}//3
	if (a[pr]>=2)	{	++two; a[pr]-=2; DFS(pr,tot); --two; a[pr]+=2;	}//2
	if (a[pr]>=1)	{	++one; a[pr]-=1; DFS(pr,tot); --one; a[pr]+=1;	}//1
	return;
}

int main()
{
	freopen("landlords.in","r",stdin); freopen("landlords.out","w",stdout);
	scanf("%d%d",&T,&n);
	while (T--)
	{
		memset(a,0,sizeof(a)); memset(sum,0,sizeof(sum)); minn=0x7fffffff;
		for (int i=1;i<=n;++i)
		{
			scanf("%d%d",&x,&y);
			if (x>=3) a[x]++;
			else
			{
				if (x==0) 	{		if (y==1) a[16]++; else a[17]++;}
				else a[x+13]++;
			}
		}
		for (int i=3;i<=17;++i)
		{
			if (a[i]>=3) ++maxx3;
			if (a[i]>=4) ++maxx4;
		}
		maxx3+=maxx4*2;
		one=two=three=four=0;
		if (a[16]==1 && a[17]==1) huojian=1; else huojian=0;
		DFS(3,0);
		printf("%d\n",minn);
	}
	fclose(stdin); fclose(stdout);
	return 0;
}

NOIP2015 DAY2 T1 跳石头

题目:https://vijos.org/p/1981

二分+$O(n)$贪心判断

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#define NN 50010
using namespace std;
int tot,l,r,len,n,m,a[NN],g[NN],ans;
bool Check(int xx)
{
	tot=0; 
	int i=0;
	while (i<n+1)
	{
		i++;
		int sum=g[i];
		while (sum<xx)
		{
			sum+=g[++i],tot++;
			if (tot>m) return 0;
			if (i>n+1) return 1;
		}
	}
	return 1;
}
int main()
{
	freopen("stone.in","r",stdin); freopen("stone.out","w",stdout);
	scanf("%d%d%d",&len,&n,&m);
	a[0]=0; a[n+1]=len;
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=n+1;++i) g[i]=a[i]-a[i-1];
	l=0; r=len; ans=0;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (Check(mid)) l=mid+1,ans=mid; else r=mid-1;
	}
	printf("%d\n",ans);
	fclose(stdin); fclose(stdout);
	return 0;
}

NOIP2015 DAY2 T2 子串

题目:https://vijos.org/p/1982

DP,但是要加滚动数组防MLE

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

LL f[3][1010][210],ans[3][1010][210];
int t,n,m,k;
char a[1010],b[210];

int main()
{
	freopen("substring.in","r",stdin); freopen("substring.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	scanf("%s",a+1); scanf("%s",b+1);
	t=0;
	for (int i=0;i<=n;++i) ans[0][i][0]=1;
	for (int w=1;w<=k;++w)
	{
		t^=1;
		for (int i=1;i<=n;++i)
			for (int j=1;j<=m;++j)
			if (a[i]==b[j])
			{
				f[t][i][j]=(f[t][i-1][j-1]+ans[t^1][i-1][j-1])%mod;
				ans[t][i][j]=(f[t][i][j]+ans[t][i-1][j])%mod;
			}
			else	f[t][i][j]=0,ans[t][i][j]=ans[t][i-1][j];
		for (int i=0;i<=n;++i) ans[t^1][i][0]=0;
	}
	printf("%lld\n",ans[t][n][m]);
	fclose(stdin); fclose(stdout);
	return 0;
}

NOIP2015 DAY2 T3 运输计划

题目:https://vijos.org/p/1983

树上乱搞+二分答案判断

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
#define NN 300100
int read()
{
	int xx=0,ff=1; char ch;
	for (ch=getchar();ch<'0'||ch>'9';ch=getchar()) if (ch == '-') ff=-1;
	for (;ch>='0';ch=getchar()) xx=xx*10+ch-'0'; xx*=ff;
	return xx;
}
int sz=0, fa[NN][20], deep[NN], pos[NN], dis[NN], tot=0, head[NN], n, m;
int sum=0, x[NN], y[NN], z[NN], l, r, ans, maxx2=0, val[NN];
struct E
{
	int v,w,ne;
}e[NN<<1];
struct S
{
	int u,v,d,lca;
}s[NN];
void Build(int xx,int yy,int zz)
{
	e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;
	e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].w=zz;
}

void DFS(int xx)
{
	pos[++sz]=xx;
	for (int i=1;i<=17;++i)
		if ((1<<i)<=deep[xx]) fa[xx][i]=fa[fa[xx][i-1]][i-1];
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].v != fa[xx][0])
	{
		deep[e[i].v] = deep[xx]+1, fa[e[i].v][0] = xx, dis[e[i].v] = dis[xx] + e[i].w, val[e[i].v] = e[i].w;
		DFS(e[i].v);
	}
}
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<=17;++i) if (tmp>>i&1) xx=fa[xx][i];
	for (int i=17;i>=0;--i) if (fa[xx][i] != fa[yy][i]) xx=fa[xx][i], yy=fa[yy][i];
	return xx==yy?xx:fa[xx][0];
}
int tmp[NN];
bool Check(int xx)
{
	int cnt=0, lim=0;
	memset(tmp,0,sizeof(tmp));
	for (int i=1;i<=m;++i)
		if (s[i].d > xx)
		{
			++tmp[s[i].u], ++tmp[s[i].v], tmp[s[i].lca]-=2;
			lim = max(s[i].d-xx, lim);
			cnt++;
		}
	if (!cnt) return 1;
    for (int i=n;i>1;--i) tmp[fa[pos[i]][0]]+=tmp[pos[i]];
    for (int i=2;i<=n;++i)
    	if (val[i] >= lim && tmp[i]==cnt) return 1;
    return 0;
}
int main()
{
	n=read(), m=read();
	for (int i=1;i<n;++i)
	{
		x[i]=read(), y[i]=read(), z[i]=read(), sum+=z[i];
		Build(x[i],y[i],z[i]);
	}
	dis[1]=0, deep[1]=1, fa[1][0]=0;
	DFS(1);
	for (int i=1;i<=m;++i)
	{
		s[i].u=read(), s[i].v=read();
		s[i].lca=LCA(s[i].u, s[i].v);
		s[i].d=dis[s[i].u] + dis[s[i].v] - 2*dis[s[i].lca];
	}
	l=0, r=sum;
	while (l<=r)
	{
		int mid=(l+r)>>1;
		if (Check(mid)) ans=mid, r=mid-1; else l=mid+1;
	}
	printf("%d\n", ans);
	return 0;
}

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;
}

NOIP2013 DAY2 T3 华容道

题目:https://vijos.org/p/1846

大力BFS

#include <bits/stdc++.h>
using namespace std;
const int NN = 40, INF = 0x3f3f3f3f;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
struct STK
{
	int x,y,d;
}stk[15];
struct P
{
	int x,y;
};
queue <P> que;
queue <STK> QUE;
int n,m,EX,EY,SX,SY,TX,TY,Q,stk_n;
int mp[NN][NN],dis[NN][NN],st[NN][NN][5][5],dp[NN][NN][5];
bool vis[NN][NN][5];
void Pre(int sx,int sy)
{
	stk_n=0;
	for (int i=0;i<4;++i)
	{
		int tx=sx+dx[i],ty=sy+dy[i];
		if (tx>0 && ty>0 && tx<=n && ty<=m && mp[tx][ty])
			stk[++stk_n].x=tx, stk[stk_n].y=ty, stk[stk_n].d=i;
	}
	for (int _=stk_n;_;--_)
	{
		while(!que.empty()) que.pop();
		memset(dis,0x3f,sizeof(dis));
		int ttx=stk[_].x,tty=stk[_].y,ttd=stk[_].d;
		dis[ttx][tty] = 0;
		que.push((P){ttx,tty});
		while (!que.empty())
		{
			int tx=que.front().x,ty=que.front().y; que.pop();
			for (int i=0;i<4;++i)
			{
				int xx=tx+dx[i],yy=ty+dy[i];
				if (xx>0 && yy>0 && xx<=n && yy<=m)
					if (mp[xx][yy] && (xx!=sx||yy!=sy) && dis[xx][yy] == INF)
					{
						dis[xx][yy] = dis[tx][ty] + 1;
						que.push((P){xx,yy});
					}
			}
		}
		for (int i=0;i<4;++i)
		{
			int xx = sx+dx[i], yy = sy+dy[i];
			if (xx>0 && yy>0 && xx<=n && yy<=m)
				if (mp[xx][yy] && (xx!=ttx||yy!=tty) && dis[xx][yy] != INF)
					st[sx][sy][ttd][i] = dis[xx][yy];
		}
	}
}

void Pre_BFS()
{
	memset(dis,0x3f,sizeof(dis));
	while (!que.empty()) que.pop();
	dis[EX][EY] = 0;
	que.push((P){EX,EY});
	while (!que.empty())
	{
		int tx = que.front().x, ty = que.front().y; que.pop();
		for (int i=0;i<4;++i)
		{
			int xx = tx+dx[i], yy = ty+dy[i];
			if (xx>0 && yy>0 && xx<=n && yy<=m && (xx!=SX || yy!=SY))
				if (mp[xx][yy] && dis[xx][yy] == INF)
				{
					dis[xx][yy] = dis[tx][ty] + 1;
					que.push((P){xx,yy});
				}
		}
	}
	
}
int BFS()
{
	int ans = 0;
	if (TX==SX && TY==SY) return 0;
	Pre_BFS();
	memset(dp,0x3f,sizeof(dp));
	while (!QUE.empty()) QUE.pop();
	for (int i=0;i<4;++i)
	{
		int xx = SX+dx[i], yy = SY+dy[i];
		if (xx>0 && yy>0 && xx<=n && yy<=m && mp[xx][yy] && dis[xx][yy] != INF)
		{
			dp[SX][SY][i] = dis[xx][yy];
			QUE.push((STK){SX,SY,i});
			vis[SX][SY][i] = 1;
		}
	}
	while (!QUE.empty())
	{
		int tx=QUE.front().x, ty=QUE.front().y, td=QUE.front().d; QUE.pop();
		vis[tx][ty][td] = 0;
		int xx=tx+dx[td], yy=ty+dy[td];
		if (dp[xx][yy][(td+2)%4] > dp[tx][ty][td] + 1)
		{
			dp[xx][yy][(td+2)%4] = dp[tx][ty][td] + 1;
			if (!vis[xx][yy][(td+2)%4])
			{
				vis[xx][yy][(td+2)%4] = 1;
				QUE.push((STK){xx,yy,(td+2)%4});
			}
		}
		for (int i=0;i<4;++i)
		{
			xx=tx+dx[i],yy=ty+dy[i];
			if (i!=td && xx>0 && yy>0 && xx<=n && yy<=m && mp[xx][yy] && st[tx][ty][td][i] != INF)
				if (dp[tx][ty][i] > dp[tx][ty][td] + st[tx][ty][td][i])
				{
					dp[tx][ty][i] = dp[tx][ty][td] + st[tx][ty][td][i];
					if (!vis[tx][ty][i]) vis[tx][ty][i] = 1, QUE.push((STK){tx,ty,i});
				}
		}
	}
	ans = INF;
	for (int i=0;i<4;++i) ans = min(ans,dp[TX][TY][i]);
	return (ans == INF)?-1:ans;
}

int main()
{
	scanf("%d%d%d",&n,&m,&Q);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j) scanf("%d",&mp[i][j]);
	memset(st,0x3f,sizeof(st));
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			if (mp[i][j]) Pre(i,j);
	while (Q--)
	{
		scanf("%d%d%d%d%d%d",&EX,&EY,&SX,&SY,&TX,&TY);
		printf("%d\n",BFS());
	}
	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 选择客栈

题目:https://vijos.org/p/1737

这真是斯波题啊,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 DAY1 T3 Mayan游戏

题目:https://vijos.org/p/1738

DFS

注意Fall 和 Remove两个函数就可以了

NOIP竟然还给了-1两个点,自己还是too young,一开始都不看好题目

#include <bits/stdc++.h>
using namespace std;
const int NN = 10;
int C[NN][NN],cnt[15],n,lin[NN][5];
bool FLAG=0;
bool Remove(int c[][NN])
{
	bool pos[10][10]={0},flag = 0;
	for (int i=1;i<=5;++i)
		for (int j=1;j<=7;++j)
		if (c[i][j])
		{
			if (i<=3 && c[i][j] == c[i+1][j] && c[i][j] == c[i+2][j])
				pos[i][j] = pos[i+1][j] = pos[i+2][j] = 1;
			if (j<=5 && c[i][j] == c[i][j+1] && c[i][j] == c[i][j+2])
				pos[i][j] = pos[i][j+1] = pos[i][j+2] = 1;
		}
	for (int i=1;i<=5;++i)
		for (int j=1;j<=7;++j)
			if (pos[i][j]) c[i][j] = 0, flag = 1;
	return flag;
}

void Fall(int c[][NN])
{
	int k,tmp;
	for (int i=1;i<=5;++i)
	{
		k=0;
		for (int j=1;j<=7;++j)
		{
			tmp=c[i][j], c[i][j] = 0;
			if (tmp) c[i][++k] = tmp;
		}
	}
}

bool Check(int c[][NN])
{
	for (int i=1;i<=5;++i)
		for (int j=1;j<=7;++j)
			if (c[i][j]) return 0;
	return 1;
}

void DFS(int k,int c[][NN])
{
	if (k>n)
	{
		if (Check(c))
		{
			for (int i=1;i<=n;++i)
			{
				if (lin[i][2]) printf("%d %d -1\n",lin[i][0],lin[i][1]-1);
				else printf("%d %d 1\n",lin[i][0]-1,lin[i][1]-1);
			}
			FLAG = 1;
		}
		return;
	}
    int tmp[10][10]={0};
    memset(cnt,0,sizeof cnt);
    for (int i=1;i<=5;++i)
		for (int j=1;j<=7;++j) ++ cnt[c[i][j]];
	for (int i=1;i<=10;++i)
		if (cnt[i] == 1 || cnt[i] == 2) return;
	for (int i=1;i<5;++i)
		for (int j=1;j<=7;++j)
		{
			if (c[i][j] != c[i+1][j])
			{
				memcpy(tmp,c,sizeof(tmp));
				lin[k][0]=i, lin[k][1]=j, lin[k][2]=!c[i][j];
				swap(tmp[i][j],tmp[i+1][j]);
				Fall(tmp);
				while (Remove(tmp)) Fall(tmp);
				DFS(k+1,tmp);
				if (FLAG) return;
			}
		}
}

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=5;++i)
		for (int j=1;;++j)
		{
			scanf("%d",&C[i][j]);
			if (!C[i][j]) break;
		}
	DFS(1,C);
	if (!FLAG) puts("-1");
	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;
}

(感觉好像未完待续。。。)


登录 *


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