NOIP2014 飞翔的小鸟【DP】+解方程【取模】

tonyfang posted @ 2015年9月07日 17:33 in NOIP with tags c++ OI , 703 阅读

飞翔的小鸟:用类似完全背包的方法DP下即可。

 

# include <stdio.h>
# include <algorithm>
using namespace std;
int n,m,k;
const int inf=21000000;
int f[10010][1010];
int x[10010],y[10010];
int up[10010],down[10010];
int main() {
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;++i) {
		scanf("%d%d",&x[i],&y[i]);
		up[i]=m+1,down[i]=0;
	}
	for (int i=1,P,L,H;i<=k;++i) {
		scanf("%d%d%d",&P,&L,&H);
		up[P]=H,down[P]=L;
	}
	for (int i=1;i<=n;++i)
		for (int j=0;j<=m;++j) f[i][j]=inf;
	f[0][0]=inf;
	for (int i=1;i<=n;++i) {
		for (int j=1;j<=m;++j) {
			if(j>=x[i]) 
				f[i][j]=min(f[i][j],min(f[i-1][j-x[i]]+1,f[i][j-x[i]]+1));
			if(j==m) {
				for (int k=j-x[i];k<=m;++k) 
					f[i][j]=min(f[i][j],min(f[i-1][k]+1,f[i][k]+1));
			}
		} 
		for (int j=down[i]+1;j<=up[i]-1;++j)
			if(j+y[i]<=m)
				f[i][j]=min(f[i][j],f[i-1][j+y[i]]);
		for (int j=1;j<=down[i];++j) f[i][j]=inf;
		for (int j=up[i];j<=m;++j) f[i][j]=inf;
	}
	int fail = k, ans = inf;
	for (int i=n; i>=1; --i) {
		for (int j=down[i]+1;j<=up[i]-1;++j)
			if(f[i][j]<inf) 
				ans=min(ans,f[i][j]);
		if(ans!=inf) break;
		if(up[i]<=m) fail --;
	}
	if(fail == k) printf("1\n%d\n",ans);
	else printf("0\n%d\n",fail);
	return 0;
}

解方程:取4个10000多的质数$p_1,p_2,p_3,p_4$,在模意义下判断。

我们会发现,在某一个模意义下,若$x$在答案内,那么$x+k \times p_i$也在答案内。

那么我们就可以把$0~p_{i}-1$的预处理出来即可,然后$O(gn+km)$判断,$k=4,g \leq 10050$。

# include <stdio.h>
using namespace std;
int n,m;
const int prime[5]={0,10037,10039,10003,10009};
int num[110][7];
bool f[10050][5];
int cnt[1000010];
int x1,x2,x3,x4,ff;
char ch;
bool js(int prim,int valu) {
	long long t=0,xx=1;
	for (int ii=n;ii>=0;--ii) 
		t=(t*valu+num[ii][prim])%prime[prim];
	return t!=0;
}
inline void scan(int i) {
	x1=x2=x3=x4=0,ff=1;ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-') ff=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x1=(x1<<3)+(x1<<1)+ch-'0';
		x1%=prime[1];
		x2=(x2<<3)+(x2<<1)+ch-'0';
		x2%=prime[2];
		x3=(x3<<3)+(x3<<1)+ch-'0';
		x3%=prime[3];
		x4=(x4<<3)+(x4<<1)+ch-'0';
		x4%=prime[4];
		ch=getchar();
	}
	num[i][1]=ff*x1;
	num[i][2]=ff*x2;
	num[i][3]=ff*x3;
	num[i][4]=ff*x4;
	if(ff==-1) {
		num[i][1]+=prime[1];
		num[i][2]+=prime[2];
		num[i][3]+=prime[3];
		num[i][4]+=prime[4]; 
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for (int i=0;i<=n;++i) scan(i);
	for (int i=1;i<=4;++i) 
		for (int j=0;j<prime[i];++j) 
			f[j][i]=js(i,j);
	for (int i=1;i<=m;++i) {
		bool flag=1;
		for (int j=1;j<=4;++j)
			if(f[i%prime[j]][j]){
				flag=0;
				break;
			}
		if(flag) cnt[++cnt[0]]=i;
	}
	printf("%d\n",cnt[0]);
	for (int i=1;i<=cnt[0];++i) printf("%d\n",cnt[i]);
}


 

PSEB 11th Question P 说:
2022年8月22日 02:17

There are several public and private schools in Punjab that are associated with this board; all of these schools operate under its supervision and are also controlled by it. Many students from this state took the class 11th exams this year as well, and they are all currently waiting for the Punjab +1 PSEB 11th Question Paper 2023 of these exams. PSEB 11th Question Paper 2023 Punjab Board will as soon as possible announce the Punjab +1 Important Question Paper 2023 for class 11th via their official website. Numerous pupils took the class 11th exams that were administered by this board in the previous academic year, which was done in the past. In this test, girls performed better than guys.


登录 *


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