【NOIP2014】真题回顾

生活大爆炸版石头剪刀布就是个模拟，不说了

联合权值枚举每个点，统计它任意两个儿子的联合权值，统计的时候维护sum和max就行了

飞扬的小鸟比较好的DP题，不难想到用dp[i][j]表示到达第i列，高度j的最小点击次数，直接枚举i,j转移到下一列的位置会TLE，需要优化

#include<iostream>

#include<cstring>

#include<cstdio>

#define min(x,y) ((x)<(y)?(x):(y))

#define max(x,y) ((x)>(y)?(x):(y))

using namespace std;

const int N=10010;

const int M=2010;

const int INF=100000;

const int ch_top=4e7+3;

char ch[ch_top],*now_r=ch-1;

inline int read(){

    while(*++now_r<'0');

    register int x=*now_r-'0';

    while(*++now_r>='0')x=x*10+*now_r-'0';

    return x;

}

int n,m,k,X[N],Y[N],cnt[N],s[N],num;

int dp[N][M],low[N],high[N],Max;

int main()

{

//	freopen("a.in","r",stdin);

	fread(ch,1,ch_top,stdin);

	n=read(); m=read(); k=read();

	for(int i=0;i<n;++i){

		X[i]=read(); Y[i]=read();

		low[i]=1; high[i]=m;

	}

	low[n]=1; high[n]=m;

	int P,L,H;

	while(k--){

		P=read(); L=read(); H=read();

		low[P]=L+1; high[P]=H-1;

		++cnt[P];

	}

	for(int i=1;i<=n;++i)

		cnt[i]+=cnt[i-1];

	for(int i=0;i<=n;++i)

		for(int j=0;j<=m;++j)

			dp[i][j]=INF;

	for(int i=1;i<=m;++i)

		dp[0][i]=0;

	for(int i=0;i<n;++i){

		num=0;

		for(int j=high[i];j>=low[i];--j)//从上往下依次转移，有利于后面优化时间

		  if(dp[i][j]<INF){//先转移向上跳的情况

		  	s[++num]=j;

		  	Max=max(Max,i);

			int g=(low[i+1]-j)/X[i];//直接计算需要向上跳几次达到low[i+1]

			if(g<1) g=1;

			int h=j+g*X[i];

			if(h<low[i+1]) ++g,h+=X[i];

			while(h<=high[i+1]){

				if(dp[i+1][h]>dp[i][j]+g)

					dp[i+1][h]=dp[i][j]+g;

				else break;//优化时间，如果dp[i+1][h]已经有了更好的方案，一定是向上跳了若干步后转移过来的，那么dp[i+1][h+k*X[i]]也可以被跳到

				++g; h+=X[i];

			}

			if(high[i+1]==m)

				dp[i+1][m]=min(dp[i+1][m],dp[i][j]+(m-j)/X[i]+1);//计算到天花板的步数并转移

		}

		for(int l=1,j=s[l];l<=num;j=s[++l])	//后转移向下落的情况

		  if(dp[i][j]<INF){

			int t=j-Y[i];

			if(low[i+1]<=t&&t<=high[i+1])

				dp[i+1][t]=min(dp[i+1][t],dp[i][j]);

		}

	}

	int ans=INF;

	for(int i=low[n];i<=high[n];++i)

		if(dp[n][i]<INF)

			ans=min(ans,dp[n][i]);

	if(ans<INF){

		puts("1");

		printf("%d\n",ans);

		return 0;

	}

	puts("0");

	printf("%d\n",cnt[Max]);

	return 0;

}

无线网络发射器选址想怎么暴力就怎么暴力

寻找道路按照题意，先标记所有能到终点的点，然后标记所有出边指向的点都与终点连通的点，最后找一条最短的就行了

解方程这题直接用高精干会爆炸，我们发现，如果原先式子的结果为0，对一个大质数取模后仍为0，原先式子的结果为你用的大质数的倍数，取模得到的结果也是0，这样的话你就被卡了，但是出题人怎么知道你是用19260817还是998244353或者19491001再或者是2147483647

还有，计算的时候用不用秦九韶都是O(n)的，也不知道这玩意有什么用处..

#include<iostream>

#include<cstring>

#include<cstdio>

#define int long long

using namespace std;

const int MAXN=110;

const int MAXM=1000010;

const int MOD=2147483647;

int n,m,a[MAXN];

inline int read(){

	int x=0,f=1; char c=getchar();

	while(c<'0') { if(c=='-') f=-1; c=getchar();}

	while(c>='0') x=(x*10+c-'0')%MOD,c=getchar();

	return x*f;

}

int cnt,ans[MAXM];

inline bool check(int x){

	int ans=0,y=1;

	for(int i=0;i<=n;++i){

		ans=(ans+a[i]*y)%MOD;

		y=y*x%MOD;

	}

	return ans==0;

}

signed main()

{

	scanf("%lld%lld",&n,&m);

	for(int i=0;i<=n;++i)

		a[i]=read();

	for(int i=1;i<=m;++i)

		if(check(i)) ans[++cnt]=i;

	printf("%lld\n",cnt);

	for(int i=1;i<=cnt;++i)

		printf("%lld\n",ans[i]);

	puts("");

	return 0;

}

巴特西

【NOIP2014】真题回顾

最新文章

热门文章