【海亮集训&&题解】普及组noip2018赛前练习题解

专辑：海亮集训&&题解

一、小X与位运算
题目描述
自从上次小X 搞定了完美数之后，他最近在研究一项和计算机密切相关的黑科技。要知道在计算机的内部，数据都是以二进制的形式来进行存储的，而它使用的计算方法也和我们平时的加减乘除四则运算 有所不同，它使用的是位运算。那什么是位运算呢？ 基础位运算有三种符号，分别是 and，or，xor（分别对应 pascal 中的 and，or，xor 三种运算符 号）。
以 and 为例，两个二进制数在做 and 运算时，分别对两个二进制数的每一位做 and 运算。而对每一 位做and 运算时，遵守以下规则：只有当两个数的这一位都是 1 时，运算结果才为 1，否则就是 0。例如 1101 和10101 做and 运算之后结果为101（高位不足用0 补齐，最后结果忽略前导0）。 通俗点讲 and 运算就是按位做乘法，即将两个二进制数从高位到低位依次对齐，然后每一位上对齐 的两个数相乘即得到这一位的结果 。我们可以列一个简单的例子来说明个and运算：01101 and 10101 = 00101。
而or，xor 的运算方法类似，唯一不同的是在对每一位做运算时遵循的方法不同。 or 运算遵守以下规则：只有当两个数的这一位都是 0 时，运算结果才为 0，否则就是 1。例如1101or10101=11101。
xor 运算遵守以下规则：只有当两个数的这一位相同时，运算结果才为0，否则就是1。例如1101xor10101=11000 。
小 X想知道两个很大很大的二进制数，在做完位运算之后， 最后的结果是什么。而小X 自己无法知道正确答案是什么，他只好求助于你来帮助他解决这个问题。

输入格式
输入数据第一行是一个字符串，由字符0 和1组成，表示一个二进制数。 第二行也是一个字符串，由字符0 和1组成，同样表示一个二进制数。 第三行还是一个字符串，一定是and，or，xor三个中一种，表示运算符号。 注意输入的二进制数没有前导零，字符个数可能会超过255 个。

输出格式
输出一行一个字符串，由字符0和1 组成，表示最后运算得到的二进制数。 注意输出的二进制数不能带有前导零，即输出的第一个字符不能为0。

样例数据

input
110100
11001
or

output

111101

分析
这道题没有什么算法可言，知识存粹的模拟题，只要细心点按照题目意思模拟下去问题不大。不过需要注意的是前导零的处理以及零的补充.

那么具体代码如下：

#include<bits/stdc++.h>
using namespace std;
string s3;
string s1,s2;
string s;
void swapp(){
    string t;
    t=s1;s1=s2;s2=t;
}
int main(){
    freopen("bignum.in","r",stdin);
    freopen("bignum.out","w",stdout);
      cin>>s1>>s2;
      cin>>s;
      if (s1.size()<s2.size()) swapp();
      int len=s1.size()-s2.size();
      bool f1=1;
      for (int i=0;i<=len-1;i++){
	      if (s=="and") if (!f1) cout<<'0';else;
	      if (s=="or") if (s1[i]=='1') cout<<'1',f1=0;else if (!f1) cout<<'0';else;
	      if (s=="xor") if (s1[i]=='1') cout<<'1',f1=0;else if (!f1) cout<<'0';else;
	  }
      for (int i=len;i<=s1.size()-1;i++){
	      if (s=="and"){if (s1[i]=='1'&&s2[i-len]=='1') cout<<'1',f1=0;else if (!f1) cout<<'0';else;}
		  else if (s=="or") {if (s1[i]=='1'||s2[i-len]=='1') cout<<'1',f1=0;else if (!f1) cout<<'0';else;}
		  else if (s=="xor"){if (s1[i]!=s2[i-len]) cout<<'1',f1=0;else if (!f1) cout<<'0';else;}
	  }
      fclose(stdin);
      fclose(stdout);
	  return 0;
}

二、小X与机器人
题目描述
小 X 最近对战胜韩国围棋大神李世石的 AlphaGo 很感兴趣，所以小 X 自己写了一个叫做 BetaGo 的人工智能程序(简称 AI)，这个 BetaGo 会做什么呢？ 小 X 首先想要让 BetaGo 做到自己在棋盘上落子，这一点 AlphaGo 是由程序员来完成的。

小 X 的 设想是这样的：在棋盘的边框上放置一个小机器人，这个小机器人会沿着棋盘的边框移动到最接近落子点的位置，然后伸出它的机械臂将棋子放到棋盘上。这里面最关键的一步是如何让小机器人在棋盘的边框上沿着最短的路径移动，小 X 想请你帮他编个程序解决这个问题。众所周知，围棋棋盘大小为 19 × 19(如下图所示),图中加粗的一圈即为边框。我们用一对整数 (x, y) 来表示棋盘上第 x 条横线（从下往上数）与第 y 条竖线（从左往右数）的交叉点，如上图中边框上的 A 点用（6，1）表示，B 点用(10，19)表示，小机器人初始时放置在 (x1, y1) 这个位置上，它想要移动到 (x2, y2) 这个位置上。

(x1, y1)和(x2, y2) 一定是棋盘边框上的交叉 点 每一步小机器人可以从当前位置移动到相邻（上下左右）的某个位置上，即每次可以从 (x, y) 移 动到 (x - 1, y)、(x + 1, y)、(x, y - 1)、(x, y + 1) 四个位置中的一个，但是它不能走出或走进棋盘， 也就是说它只能沿着棋盘的边框移动到相邻位置，这就意味着任一时刻相邻位置都恰好只有两个。 BetaGo 会告诉小机器人最少需要走多少步，但小 X 还是很担心 BetaGo 有的时候会失控，从而告诉他一个错误值。为此小 X 只好求助你，希望你编一个程序计算从 (x1, y1) 沿着棋盘的边框移动到 (x2, y2) 最少需要走多少步。上图中从 A 点（6，1）移动到 B 点(10，19)最少需要走 32 步，移动路线是： （6，1）→（5，1）→（4，1）→（3，1）→（2，1）→（1，1）→(1，2)→(1，3)→…… →(1，19)→(2，19)→……→(10，19)。

分析
两种方法，一种是数学手推，很好理解，这里不再赘述；另一种就是BFS（虽然显得很奢侈），这题是可以被当作一题BFS模板题写的，知识注意的是能走的知识棋盘的一圈，注意vis数组的赋值
具体代码如下：

#include<bits/stdc++.h>
using namespace std;
int st,en,st1,en1;
struct node{
    int x,y;
};
node q[100001];
bool f[101][101];
int ans[101][101];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int main(){
	freopen("betago.in","r",stdin);
	freopen("betago.out","w",stdout);
	int head=1,tail=0;
	scanf("%d %d %d %d",&st,&st1,&en,&en1);
	memset(ans,30,sizeof(ans));
	ans[st][st1]=0;
	q[++tail].x=st;
	q[tail].y=st1;
	memset(f,0,sizeof(f));
	for (int i=1;i<=19;i++) f[i][1]=f[i][19]=f[1][i]=f[19][i]=1;
	for (;head<=tail;head++){
	    node t=q[head];
	    for (int i=0;i<4;i++){
		    int xx=t.x+dx[i],yy=t.y+dy[i];
		    if (!f[xx][yy]) continue;
		    if (ans[xx][yy]>ans[t.x][t.y]+1) ans[xx][yy]=ans[t.x][t.y]+1,q[++tail].x=xx,q[tail].y=yy;
		    if (xx==en&&yy==en1){cout<<ans[en][en1];fclose(stdin);fclose(stdout);return 0;}
		}
	}
	fclose(stdin);
	fclose(stdout);
    return 0;
}

三、赛车
题目描述
小x为了平复自己悲愤的心情，参加了F7赛车决赛的解说工作。作为一位优秀的主持人，他想要了解一下参加决赛的N位选手的情况。经过一番努力，他找到了各位选手前几站比赛的成绩。

决赛就要开始了，比赛规定：第一个到达终点的得到N分，第二个到达终点的得到N-1分，以此类推…最后一个到达终点的得到1分。而且不会有两位选手同时到达终点。

小x非常忙，所以他想请你帮他统计一下有多少选手有可能成为总冠军（之前的成绩+决赛成绩=总成绩，总成绩最高者为总冠军，总冠军可能有多位）。

输入格式
第一行一个正整数N(3≤N≤300000)，代表参加决赛的选手个数。

接下来N行，每行一个正整数Bi，代表第i位选手之前比赛的成绩。

输出格式
一行一个正整数，代表有可能成为总冠军的选手个数。

样例数据
input1
3
8
10
9

output1
3

input2
5
15
14
15
12
14

output2
4

#include<bits/stdc++.h>
using namespace std;
int maxx[10000001];
int n;
int a[10000001];
inline bool mycmp(int x,int y){
    return x>y;
}
int main(){
	freopen("racing.in","r",stdin);
	freopen("racing.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1,mycmp);
    maxx[1]=a[1]+1;
    for (int i=2;i<=n;i++)
      maxx[i]=max(maxx[i-1],a[i]+i);
    int ans=1;
    for (int i=2;i<=n;i++) if (a[i]+n>=maxx[i-1]) ans++;
    cout<<ans;
    fclose(stdin);
    fclose(stdout);
    return 0;
}

最后

以上就是舒服大山为你收集整理的【海亮集训&&题解】普及组noip2018赛前练习题解的全部内容，希望文章能够帮你解决【海亮集训&&题解】普及组noip2018赛前练习题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。