【蒟蒻】NOIP的各种

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

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

（重新拉到首页，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;
}

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

[回复]

AP 1st Inter Economi 说:
2022年9月08日 21:41

The AP Intermediate students can download the Economics question bank with solved study material with practice questions in chapter wise to every TM, EM, UM student, and the economics subject paper-1 AP 1st Inter Economics Model Paper and paper-2 important questions with suggestions are available through AP Jr and Sr inter Economics Model Paper 2023 Pdf with guess paper.

Pluto_Rabbit's Blog

蒟蒻妹纸一枚，轻拍