首页 > 代码库 > 9.30 noip模拟试题
9.30 noip模拟试题
时限均为1s，内存 256MB
1、某种密码(password.*)
关于某种密码有如下描述：某种密码的原文A是由N个数字组成，而密文B是一个长度为N的01数串，原文和密文的关联在于一个钥匙码KEY。若KEY=∑?〖Ai*Bi〗，则密文就是原文的一组合法密码。
现在有原文和钥匙码，请编一个程序来帮助他统计到底有多少个符合条件的密文。
【输入数据】
第一行两个数N，KEY，意义同题目描述；
第二行N个数表示原文A，意义同题目描述。
【输出数据】
一个数ANS，表示对于原文A和KEY，有多少组可行的密文B。
【输入样例】
3 2
1 1 2
【输出样例】
2
【样例说明】
密文110，1*1+1*1+0*2=2
密文001，0*1+0*1+1*2=2
一共两组可行的密文。
【数据约定】
60%数据满足N<=25
100%数据满足N<=40，-maxlongint<=∑?Ai<=maxlongint
暴力+hash
/*蒟蒻用map*/#include<iostream>#include<cstdio>#include<cstring>#include<map>#define ll long longusing namespace std;long long n,k,N,a[50],falg,ans;map<long long,long long>p;void Dfs(long long now,long long s){ if(now==N+1){ if(!falg)p[s]++; else ans+=p[k-s]; return; } Dfs(now+1,s); Dfs(now+1,s+a[now]);}int main(){ freopen("password.in","r",stdin); freopen("password.out","w",stdout); cin>>n>>k; for(long long i=1;i<=n;i++)cin>>a[i]; N=n/2;Dfs(1,0); falg=1;N=n;Dfs(n/2+1,0); cout<<ans; return 0;}
2、球的序列(formation.*)
N个编号为1-n的球，每个球都有唯一的编号。这些球被排成两种序列，分别为A、B序列，现在需要重新寻找一个球的序列l，对于这个子序列l中任意的两个球，要求j,k(j<k)，都要求满足lj在A中位置比lk在A中位置靠前，却lj在B中位置比lk在B中位置靠前，请你计算这个子序列l的最大长度。
输入:
第一行一个整数，表示N。
第二行N个整数，表示A序列。
第三行N个整数，表示B序列。
样例输入
5
1 2 4 3 5
5 2 3 4 1
//5 2 4 3 1
样例输出
2
样例说明
L可以是{2,3}，也可以是{2,4}
数据范围:
40% N<=5000
100% N<=50000
暴力LCS 40
#include<cstdio>#define maxn 10010using namespace std;int n,a[maxn],b[maxn];short f[maxn][maxn];int init(){ int x=0;char s=getchar(); while(s<‘0‘||s>‘9‘)s=getchar(); while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x;}short max(short x,short y){ return x>y?x:y;}int main(){ freopen("formation.in","r",stdin); freopen("formation.out","w",stdout); n=init(); for(int i=1;i<=n;i++)a[i]=init(); for(int i=1;i<=n;i++)b[i]=init(); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(a[i]==b[j])f[i][j]=f[i-1][j-1]+1; else f[i][j]=max(f[i-1][j],f[i][j-1]); printf("%d\n",f[n][n]); return 0;}
转化成LIS
/*并不难的题没好好想想~~*/#include<cstdio>#include<algorithm>#define maxn 50010using namespace std;int n,a[maxn],b[maxn],c[maxn],r;int init(){ int x=0;char s=getchar(); while(s<‘0‘||s>‘9‘)s=getchar(); while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x;}int max(int x,int y){ return x>y?x:y;}void LIS(){ for(int i=1;i<=n;i++){ int x=b[i]; if(x>c[r]){ c[++r]=x; continue; } int p=lower_bound(c+1,c+1+r,x)-c; c[p]=x; }}int main(){ //freopen("formation.in","r",stdin); //freopen("formation.out","w",stdout); n=init();int x; for(int i=1;i<=n;i++){ x=init();a[x]=i; } for(int i=1;i<=n;i++){ x=init();b[i]=a[x]; } LIS(); printf("%d\n",r); return 0;}
3、大逃亡(escape.*)
给出数字N（1<=N<=10000），X（1<=x<=1000），Y（1<=Y<=1000）,代表有N个敌人分布一个X行Y列的矩阵上，矩形的行号从0到X-1,列号从0到Y-1再给出四个数字x1,y1,x2,y2,代表你要从点(x1,y1)移到(x2,y2)。在移动的过程中你当然希望离敌人的距离的最小值最大化，现在请求出这个值最大可以为多少,以及在这个前提下，你最少要走多少步才可以回到目标点。注意这里距离的定义为两点的曼哈顿距离，即某两个点的坐标分为(a,b),(c,d),那么它们的距离为|a-c|+|b-d|。
输入：
第一行给出数字N，X，Y
第二行给出x1,y1,x2,y2
下面将有N行，给出N个敌人所在的坐标
输出：
在一行内输出你离敌人的距离及在这个距离的限制下，你回到目标点最少要移动多少步。
Sample input
2 5 6
0 0 4 0
2 1
2 3
Sample output
2 14
/*本来能A的 但写wa了 这种题又没法拍 哎QAQ*/#include<iostream>#include<cstdio>#include<cstring>#include<queue>#define maxn 1010using namespace std;int n,m,k,f[maxn][maxn],dis[maxn][maxn];int x1,x2,y1,y2,ans,step;struct node{ int x,y,s;};int xx[4]={0,0,1,-1};int yy[4]={1,-1,0,0};queue<node>q;void Bfs(){ while(!q.empty()){ node t=q.front();q.pop(); dis[t.x][t.y]=t.s; for(int i=0;i<4;i++){ int nx=t.x+xx[i]; int ny=t.y+yy[i]; if(nx>0&&nx<=n&&ny>0&&ny<=m&&f[nx][ny]==0){ f[nx][ny]=1;dis[nx][ny]=t.s+1; q.push((node){nx,ny,t.s+1}); } } }}int Judge(int S){ if(dis[x1][y1]<S)return -1;//这里没考虑到 memset(f,0,sizeof(f)); f[x1][y1]=1; while(!q.empty())q.pop(); q.push((node){x1,y1,0}); while(!q.empty()){ node t=q.front();q.pop(); if(t.x==x2&&t.y==y2) return t.s;//开始wa的时候是返回01 并且直接改 for(int i=0;i<4;i++){ int nx=t.x+xx[i]; int ny=t.y+yy[i]; if(nx>0&&nx<=n&&ny>0&&ny<=m&&f[nx][ny]==0&&dis[nx][ny]>=S){ f[nx][ny]=1; q.push((node){nx,ny,t.s+1}); } } } return -1;}int main(){ freopen("escape.in","r",stdin); freopen("escape.out","w",stdout); scanf("%d%d%d",&k,&n,&m); scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1++;x2++;y1++;y2++; int x,y; memset(dis,127/3,sizeof(dis)); for(int i=1;i<=k;i++){ scanf("%d%d",&x,&y); x++;y++; q.push((node){x,y,0}); f[x][y]=1;dis[x][y]=0; } Bfs(); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) printf("%d ",dis[i][j]); printf("\n"); } int l=0,r=maxn*maxn; while(l<=r){ int mid=(l+r)/2; int tmp=Judge(mid); if(tmp!=-1){ l=mid+1;ans=mid; step=tmp; } else r=mid-1; } printf("%d %d\n",ans,step); return 0;}
9.30 noip模拟试题