首页 > 代码库 > 10.7 noip模拟试题
10.7 noip模拟试题
楼
【问题背景】
zhx 为他的妹子造了一幢摩天楼。
【问题描述】
zhx 有一幢摩天楼。 摩天楼上面有 M 个观光电梯，每个观光电梯被两个整
数???? " ,???? " 描述。每个电梯只有两个按钮， （针对第 i 个电梯）两个按钮分别可以使
电梯向上???? " 层向下???? " 层。摩天楼的高度是无限的，但是电梯不可以钻入地下，
也就是说是有下限的。每层楼用整数标记， 以 0 作为地面这一层的标记。
zhx 去陪他妹子了，留你一个人在摩天楼的 0 层，现在你想知道，仅可以选
择 M 个电梯中的一个乘坐（不可以中途换电梯） ，按电梯中的按钮 N 次后（每
次两个按钮选一个按） ，可以到达的最低楼层数。按电梯的过程中请注意，如果
当前所在楼层数小于你选择的???? " ，你将无法选择电梯向下运行。
【输入格式】
第一行两个数 N 和 M，如题目描述。
接下来 M 行，每行两个整数???? " 和???? " 。
【输出格式】
仅一行一个整数，包含所求的答案。
【样例输入】
10 3
15 4
15 12
7 12
【样例输出】
13
【数据范围与规定】
对于50%的数据，所有1 ≤ ????,???? ≤ 1000。
对于100%的数据，所有1 ≤ ???? ≤ 10 , ,1 ≤ ???? ≤ 2000,1 ≤ ???? " ,???? " ≤ 10 . 。
P69 读
数学题...
/*数学公式算一下就好了 */#include<iostream>#include<cstdio>#define maxn 2010#define ll long longusing namespace std;ll n,m,a,b,x,y,ans=0x7fffffff;ll init(){ ll x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}ll min(ll a,ll b){ return a<b?a:b;}int main(){ freopen("building.in","r",stdin); freopen("building.out","w",stdout); n=init();m=init(); while(m--){ a=init();b=init(); y=b*n%(a+b); x=b*n/(a+b)+(y!=0); y=n-x; ans=min(ans,a*x-b*y); } cout<<ans<<endl; return 0;}
读
【问题背景】
zhx 为他的妹子制造了一个特别的图灵机（的磁带） 。
【问题描述】
有一个两端无限长的磁带，有 N 个读取指针在某些位置，需要读取 M 个
位置上的数据。每一个单位时间每个读取指针都可以向左或向右移动一格。如
果存在某个时刻某个读取指针在某一个位置上（包括 0 时刻） ，那么这个位置上
的数据就会被读取。 （注意，不需要读取的位置也能被指针经过）
zhx 去陪妹子了，现在你需要帮他解决一个问题，最少经过多少时间，M
个需要读取的位置都能被读取？
【输入格式】
第一行两个整数 N，M，表示指针数和需要读取的位置数。
接下来一行 N 个整数，???? " 表示第 i 个指针初始位置。
接下来一行 M 个整数，???? " 表示第 i 个需要读取的位置。
【输出格式】
一行一个整数，代表需要的最小时间。
【样例输入】
3 4
2 5 6
1 3 6 8
【样例输出】
2
【样例输入】
3 3
1 2 3
1 2 3
【样例输出】
0
【数据规模与约定】
对于10%的数据，满足???? = 1。
对于另外30%的数据，满足????,???? ≤ 4,???? " ,???? " ≤ 15。
对于100%的数据， 满足1 ≤ ????,???? ≤ 10 . , 0 ≤ ???? " ,???? " ≤ 10 45 , 输入给出的???? " ,???? "
为递增顺序。
暴力50
#include<iostream>#include<cstdio>#include<cstring>#define maxn 1010#define ll long longusing namespace std;ll n,m,a[maxn],b[maxn],c[maxn][maxn],ans=1000000000000000;ll init(){ ll x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}ll Abs(ll x){ return x<0?-x:x;}ll Cal(){ ll r=0,L,R,p; for(int i=1;i<=n;i++){ if(c[i][0]==0)continue; L=b[c[i][1]];R=b[c[i][c[i][0]]]; p=a[i];r=max(r,min(Abs(R-p),Abs(p-L))+R-L); } return r;}void Dfs(int now){ if(now==m+1){ ans=min(ans,Cal()); return; } for(int i=1;i<=n;i++){ c[i][++c[i][0]]=now; Dfs(now+1);c[i][0]--; }}int main(){ freopen("read.in","r",stdin); freopen("read.out","w",stdout); n=init();m=init(); for(int i=1;i<=n;i++)a[i]=init(); for(int i=1;i<=m;i++)b[i]=init(); Dfs(1);cout<<ans<<endl; return 0;}
正解二分
/*正解二分 但是考试的时候直接没有往这想....QAQ每次judge的时候就判断每个指针移动x的距离最多覆盖到哪因为输入是有序的 所以越靠右越优 对于每个指针 假设前面的指针们已经搞完了j-1个位置两种情况 1.b[j]<a[i] 也就是说i要左移先把j覆盖了 这个时候有两种方法 先左移或者先右移 这里max一下2.b[j]>a[i] 这是一定是直接右移最优最后判一下是不是所有的都覆盖了 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 100010#define ll long longusing namespace std;int n,m;ll a[maxn],b[maxn],ans;ll init(){ ll x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}bool Judge(ll x){ for(int j=1,i=1;i<=n;i++){ if(a[i]-b[j]>x)return 0; ll R=0; if(b[j]<a[i])R=max(x-(a[i]-b[j])+b[j],(x+a[i]+b[j])/2); else R=a[i]+x; while(j<=m+1&&R>=b[j])j++; if(j>m)return 1; } return 0;}int main(){ freopen("read.in","r",stdin); freopen("read.out","w",stdout); n=init();m=init(); for(int i=1;i<=n;i++)a[i]=init(); for(int i=1;i<=m;i++)b[i]=init(); ll l=0,r=(ll)1<<60; while(l<=r){ ll mid=l+r>>1; if(Judge(mid)){ r=mid-1;ans=mid; } else l=mid+1; } cout<<ans<<endl; return 0;}
柜
【问题背景】
zhx 用一个保险柜藏私房钱。
【问题描述】
zhx 有一个高级的保险柜，是一个使用激光穿过一个有几面镜子的矩形网格
的光学封闭机械。
当激光被激活后，从矩形网格的最上方一行的左侧水平射入。每当激光束击
中一面镜子，/和\二者之一，就会以 45 度角被反射。如果激光束从矩形网格底
部一行的右侧水平射出（见上图左） ，那么安全检测成功，保险箱打开。否则保
险箱发出警报。
保险箱有一面镜子丢失来防止激光束成功穿过网格（见上图右） 。zhx 需要
开启保险箱时，就将 一 面 镜 子 放到某一个 空 的 网 格 上。因为他知道正确的放镜子
的位置和放置镜子的正确方向（上图右是第 4 行第 3 列，方向是/） ，因此可以打
开保险箱。 而其他人即使拥有那面镜子也会因为不知道如何安放而无法打开保险
箱。
zhx 去陪妹子了，现在需要你帮他确定保险箱是安全的。一个安全的保险箱
不会再不插入镜子的情况下打开， 并 至 少 存 在 一 个 位置和正确方向的镜子在插入
后保险箱能正确打开。
【输入格式】
文件包含多组数据，请读到文件末尾（EOF）结束。
每组数据描述了一个单独的保险箱，开头一行包含了四个整数 R,C,M,N。该
机械的网格有 R 行 C 列。
接下来有 M 行，每行包含两个整数???? " ,???? " ，指明有一个/镜子在第???? " 行，???? " 列。
接下来 N 行以相同方式指明 N 面\镜子的位置。输入数据保证 M+N 面镜子的位
置两两不同。
【输出格式】
每组数据对应一行输出，分下列三种情况：
1. 如果不插入镜子保险箱就能被直接打开，输出 0。
2. 如果插入或不插入镜子保险箱都不能被打开，输出-1。
3. 如果保险箱不插入一面镜子就不会被打开，K 是恰好能打开保险箱的插
入位置的数量，R,C 是字典序最小的正确插入位置。如果一个位置插入/
或\都能正确打开，只算一次。输出三个数，K R C（空格分隔）
【样例输入】
5 6 1 4
2 3
1 2
2 5
4 2
5 5
100 100 0 2
1 77
100 77
100 100 0 0
【样例输出】
2 4 3
0
-1
【数据规模与约定】
对于 5%的数据，满足????,???? ≤ 4,????,???? ≤ 4。
对于 25%的数据，满足????,???? ≤ 100，数据组数≤ 7。
对于另 5%的数据，满足????,???? ≤ 100。
对于另 5%的数据，满足???? + ???? ≤ 4, 合法位置最多为2，数据组数≤ 32。
对于另15%的数据，满足????,???? ≤ 7000。
对于另15%的数据，满足????,???? ≤ 7000。
对于 100%的数据, 满足1 ≤ ????,???? ≤ 10 B ,1 ≤ ????,???? ≤ 2 ∗ 10 . 。 除单独声明的
测试点外，数据组数≤ 2，数据有梯度。
这题有点无语....
/*暴力 ....开始wa了 很傻逼的错误就是把之前有的镜子算上了....这样暴力可以60正解嘛..没写大体看了看std(因为没有题解~)用了各种数据结构+stl总之就是简化了模拟时一步一步走的过程每次从镜子跳到镜子然后起点权值+1 终点-1然后查区间和大体就是这么个思路 反正就是简化了不必要的过程 */#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 10010using namespace std;int n,m,A,B,cnt,X,Y;short g[maxn][maxn];bool vis[maxn][maxn];int xx[4]={0,0,1,-1};int yy[4]={1,-1,0,0};struct node{ int x,y;}K[maxn*1000];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}int cmp(const node &aa,const node &bb){ if(aa.x==bb.x)return aa.y<bb.y; return aa.x<bb.x;}void Clear(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) g[i][j]=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) vis[i][j]=0; X=Y=0;cnt=0;}void Go(){ int x=1,y=1,p=0; for(;;){ if(g[x][y]==1)p=3-p; if(g[x][y]==2)p=(p+2)%4; vis[x][y]=1; x+=xx[p];y+=yy[p]; if(x>n||y>m||x<1||y<1){ X=x;Y=y;break; } }}void GO(){ int x=n,y=m,p=1; for(;;){ if(g[x][y]==1)p=3-p; if(g[x][y]==2)p=(p+2)%4; if(vis[x][y]&&g[x][y]==0){ cnt++;K[cnt].x=x;K[cnt].y=y;vis[x][y]=0; } x+=xx[p];y+=yy[p]; if(x>n||y>m||x<1||y<1){ X=x;Y=y;break; } }}int main(){ freopen("safe.in","r",stdin); freopen("safe.out","w",stdout); while(scanf("%d",&n)!=EOF){ m=init();A=init();B=init(); int x,y;Clear(); for(int i=1;i<=A;i++){ x=init();y=init();g[x][y]=1; } for(int i=1;i<=B;i++){ x=init();y=init();g[x][y]=2; } Go(); if(X==n&&Y==m+1){printf("0\n");continue;} GO(); if(cnt==0){printf("-1\n");continue;} sort(K+1,K+1+cnt,cmp); printf("%d %d %d\n",cnt,K[1].x,K[1].y); } return 0;}
10.7 noip模拟试题