模拟和高精度
[NOIP2003 普及组] 乒乓球
题目背景
国际乒联现在主席沙拉拉自从上任以来就立志于推行一系列改革,以推动乒乓球运动在全球的普及。其中 $11$ 分制改革引起了很大的争议,有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位,他退役之后走上了乒乓球研究工作,意图弄明白 $11$ 分制和 $21$ 分制对选手的不同影响。在开展他的研究之前,他首先需要对他多年比赛的统计数据进行一些分析,所以需要你的帮忙。
题目描述
华华通过以下方式进行分析,首先将比赛每个球的胜负列成一张表,然后分别计算在 $11$ 分制和 $21$ 分制下,双方的比赛结果(截至记录末尾)。
比如现在有这么一份记录,(其中 $\texttt W$ 表示华华获得一分,$\texttt L$ 表示华华对手获得一分):
$\texttt{WWWWWWWWWWWWWWWWWWWWWWLW}$
在 $11$ 分制下,此时比赛的结果是华华第一局 $11$ 比 $0$ 获胜,第二局 $11$ 比 $0$ 获胜,正在进行第三局,当前比分 $1$ 比 $1$。而在 $21$ 分制下,此时比赛结果是华华第一局 $21$ 比 $0$ 获胜,正在进行第二局,比分 $2$ 比 $1$。如果一局比赛刚开始,则此时比分为 $0$ 比 $0$。直到分差大于或者等于 $2$,才一局结束。
你的程序就是要对于一系列比赛信息的输入($\texttt{WL}$ 形式),输出正确的结果。
输入格式
每个输入文件包含若干行字符串,字符串有大写的 $\texttt W$ 、 $\texttt L$ 和 $\texttt E$ 组成。其中 $\texttt E$ 表示比赛信息结束,程序应该忽略 $\texttt E$ 之后的所有内容。
输出格式
输出由两部分组成,每部分有若干行,每一行对应一局比赛的比分(按比赛信息输入顺序)。其中第一部分是 $11$ 分制下的结果,第二部分是 $21$ 分制下的结果,两部分之间由一个空行分隔。
样例 #1
样例输入 #1
1 | WWWWWWWWWWWWWWWWWWWW |
样例输出 #1
1 | 11:0 |
提示
每行至多 $25$ 个字母,最多有 $2500$ 行。
(注:事实上有一个测试点有 $2501$ 行数据。)
【题目来源】
NOIP 2003 普及组第一题
题解
思路
在两个规模下比赛,一个是11分,另一个是21分,其中只要当遍历到字母E的时候才会结束比赛信息。当双方比分都超过11或者21时,需要双方分差大于等于2时才会结束,那么就需要abs函数给绝对值然后返回。由于题目要求每行至多 $25$ 个字母,最多有 $2500$ 行。则在建立字符串数组时需要很大,来测试数据。
代码
1 |
|
[NOIP2015 普及组] 扫雷游戏
题目背景
NOIP2015 普及组 T2
题目描述
扫雷游戏是一款十分经典的单机小游戏。在 $n$ 行 $m$ 列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下,找出所有的非地雷格。
现在给出 $n$ 行 $m$ 列的雷区中的地雷分布,要求计算出每个非地雷格周围的地雷格数。
注:一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。
输入格式
第一行是用一个空格隔开的两个整数 $n$ 和 $m$,分别表示雷区的行数和列数。
接下来 $n$ 行,每行 $m$ 个字符,描述了雷区中的地雷分布情况。字符 $\texttt{*}$ 表示相应格子是地雷格,字符 $\texttt{?}$ 表示相应格子是非地雷格。相邻字符之间无分隔符。
输出格式
输出文件包含 $n$ 行,每行 $m$ 个字符,描述整个雷区。用 $\texttt{*}$ 表示地雷格,用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。
样例 #1
样例输入 #1
1 | 3 3 |
样例输出 #1
1 | *10 |
样例 #2
样例输入 #2
1 | 2 3 |
样例输出 #2
1 | 2*1 |
提示
对于 $100\%$的数据,$1≤n≤100, 1≤m≤100$。
题解
思路
这题重点是如何判断上、下、左、右、左上、右上、左下、右下八个方向,可以先创建一个二维数组,然后因为他是n行m列的数组,利用i、j分别去控制二维数组中某一个位置的上下左右来达到实现判断上、下、左、右、左上、右上、左下、右下八个方向。然后是要先定义网格大小,同时只考虑’?’字符的输出情况,不去考虑’‘字符时的输出,因为题中’‘字符输出不变。
代码
1 |
|
[NOIP2016 提高组] 玩具谜题
题目背景
NOIP2016 提高组 D1T1
题目描述
小南有一套可爱的玩具小人,它们各有不同的职业。
有一天,这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈,它们有的面朝圈内,有的面朝圈外。如下图:
这时 singer 告诉小南一个谜题:“眼镜藏在我左数第 $3$ 个玩具小人的右数第 $1$ 个玩具小人的左数第 $2$ 个玩具小人那里。”
小南发现,这个谜题中玩具小人的朝向非常关键,因为朝内和朝外的玩具小人的左右方向是相反的:面朝圈内的玩具小人,它的左边是顺时针方向,右边是逆时针方向;而面向圈外的玩具小人,它的左边是逆时针方向,右边是顺时针方向。
小南一边艰难地辨认着玩具小人,一边数着:
singer 朝内,左数第 $3$ 个是 archer。
archer 朝外,右数第 $1$ 个是 thinker。
thinker 朝外,左数第 $2$ 个是 writer。
所以眼镜藏在 writer 这里!
虽然成功找回了眼镜,但小南并没有放心。如果下次有更多的玩具小人藏他的眼镜,或是谜题的长度更长,他可能就无法找到眼镜了。所以小南希望你写程序帮他解决类似的谜题。这样的谜題具体可以描述为:
有 $n$ 个玩具小人围成一圈,已知它们的职业和朝向。现在第 $1$ 个玩具小人告诉小南一个包含 $m$ 条指令的谜題,其中第 $z$ 条指令形如“向左数/右数第 $s$ 个玩具小人”。你需要输出依次数完这些指令后,到达的玩具小人的职业。
输入格式
输入的第一行包含两个正整数 $n,m$,表示玩具小人的个数和指令的条数。
接下来 $n$ 行,每行包含一个整数和一个字符串,以逆时针为顺序给出每个玩具小人的朝向和职业。其中 $0$ 表示朝向圈内,$1$ 表示朝向圈外。保证不会出现其他的数。字符串长度不超过 $10$ 且仅由英文字母构成,字符串不为空,并且字符串两两不同。整数和字符串之间用一个空格隔开。
接下来 $m$ 行,其中第 $i$ 行包含两个整数 $a_i,s_i$,表示第 $i$ 条指令。若 $a_i=0$,表示向左数 $s_i$ 个人;若 $a_i=1$,表示向右数 $s_i$ 个人。 保证 $a_i$ 不会出现其他的数,$1 \le s_i < n$。
输出格式
输出一个字符串,表示从第一个读入的小人开始,依次数完 $m$ 条指令后到达的小人的职业。
样例 #1
样例输入 #1
1 | 7 3 |
样例输出 #1
1 | writer |
样例 #2
样例输入 #2
1 | 10 10 |
样例输出 #2
1 | y |
提示
样例 1 说明
这组数据就是【题目描述】中提到的例子。
子任务
子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难,可以尝试只解决一部分测试数据。
每个测试点的数据规模及特点如下表:
其中一些简写的列意义如下:
全朝内:若为 $\surd$,表示该测试点保证所有的玩具小人都朝向圈内;
全左数:若为 $\surd$,表示该测试点保证所有的指令都向左数,即对任意的 $1\leq z\leq m, a_i=0$;
$s=1$:若为 $\surd$,表示该测试点保证所有的指令都只数 $1$ 个,即对任意的 $1\leq z\leq m,s_i=1$;
职业长度为 $1$:若为 $\surd$,表示该测试点保证所有玩具小人的职业一定是一个长度为 $1$ 的字符串。
题解
思路
这道题首先要构造结构体,将n行中的整数和字符串放到结构体的数组中,这个数组要设置得大些,以免超出测试数据,然后在指令的循环体里判断,如果朝内时,向左就是加n-s,向右就是加s,如果朝外时,则向左就是加s,向右就是加n-s。最后输出该字符串
代码
1 |
|
A+B Problem(高精)
题目描述
高精度加法,相当于 a+b problem,不用考虑负数。
输入格式
分两行输入。$a,b \leq 10^{500}$。
输出格式
输出只有一行,代表 $a+b$ 的值。
样例 #1
样例输入 #1
1 | 1 |
样例输出 #1
1 | 2 |
样例 #2
样例输入 #2
1 | 1001 |
样例输出 #2
1 | 10100 |
提示
$20\%$ 的测试数据,$0\le a,b \le10^9$;
$40\%$ 的测试数据,$0\le a,b \le10^{18}$。
题解
思路
首先这道题是高精度的题目,它的数据超过int和longlong型的数据大小,因此需要先输入成字符串然后将字符串转变为整型数组,然后相加。字符串变成整型数组后,需要将数组反转,让个位对齐,然后相加,注意因为有进位的存在,需要有个标识符,然后还要判断当两个数组长度一样时,相加有可能超过数组的长度,需要加上进位的标识符。
代码
1 |
|
A*B Problem
题目描述
给出两个非负整数,求它们的乘积。
输入格式
输入共两行,每行一个非负整数。
输出格式
输出一个非负整数表示乘积。
样例 #1
样例输入 #1
1 | 1 |
样例输出 #1
1 | 2 |
提示
每个非负整数不超过 $10^{2000}$。
题解
思路
高精度的数相乘,相当于列式计算,(与高精度加法类似),首先输入字符串然后转变成整型数组再反转,让个位对齐,再相乘,当某一位的数超过9的时候,需要将这个数除以10作为进位,然后该数的位置再求10的余数。然后将两个数的长度相加,如果首位有0的情况需要将长度-1,最后反向输出这个数。
代码
1 |
|
[NOIP1998 普及组] 阶乘之和
题目描述
用高精度计算出 $S = 1! + 2! + 3! + \cdots + n!$($n \le 50$)。
其中 !
表示阶乘,定义为 $n!=n\times (n-1)\times (n-2)\times \cdots \times 1$。例如,$5! = 5 \times 4 \times 3 \times 2 \times 1=120$。
输入格式
一个正整数 $n$。
输出格式
一个正整数 $S$,表示计算结果。
样例 #1
样例输入 #1
1 | 3 |
样例输出 #1
1 | 9 |
提示
【数据范围】
对于 $100 \%$ 的数据,$1 \le n \le 50$。
【其他说明】
注,《深入浅出基础篇》中使用本题作为例题,但是其数据范围只有 $n \le 20$,使用书中的代码无法通过本题。
如果希望通过本题,请继续学习第八章高精度的知识。
NOIP1998 普及组 第二题
题解
思路
首先高精度的话,用两个数组,一个表示输入的数组,另一个表示计算结果。
首先主函数里先输入n表示需要计算的阶乘和的变量,然后由于最后是要相加的,直接返回数组的最后一位的初值,且初值设置为1,然后循环从i=2开始。在阶乘函数中,数组的值需要进行高精度算法运算,然后再到求和函数中进行高精度算法运算,最后再反转求和的数组,然后输出。
代码
1 |
|
[NOIP2011 提高组] 铺地毯
题目描述
为了准备一个独特的颁奖典礼,组织者在会场的一片矩形区域(可看做是平面直角坐标系的第一象限)铺上一些矩形地毯。一共有 $n$ 张地毯,编号从 $1$ 到 $n$。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设,后铺的地毯覆盖在前面已经铺好的地毯之上。
地毯铺设完成后,组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意:在矩形地毯边界和四个顶点上的点也算被地毯覆盖。
输入格式
输入共 $n + 2$ 行。
第一行,一个整数 $n$,表示总共有 $n$ 张地毯。
接下来的 $n$ 行中,第 $i+1$ 行表示编号 $i$ 的地毯的信息,包含四个整数 $a ,b ,g ,k$,每两个整数之间用一个空格隔开,分别表示铺设地毯的左下角的坐标 $(a, b)$ 以及地毯在 $x$ 轴和 $y$ 轴方向的长度。
第 $n + 2$ 行包含两个整数 $x$ 和 $y$,表示所求的地面的点的坐标 $(x, y)$。
输出格式
输出共 $1$ 行,一个整数,表示所求的地毯的编号;若此处没有被地毯覆盖则输出 -1
。
样例 #1
样例输入 #1
1 | 3 |
样例输出 #1
1 | 3 |
样例 #2
样例输入 #2
1 | 3 |
样例输出 #2
1 | -1 |
提示
【样例解释 1】
如下图,$1$ 号地毯用实线表示,$2$ 号地毯用虚线表示,$3$ 号用双实线表示,覆盖点 $(2,2)$ 的最上面一张地毯是 $3$ 号地毯。
【数据范围】
对于 $30\%$ 的数据,有 $n \le 2$。
对于 $50\%$ 的数据,$0 \le a, b, g, k \le 100$。
对于 $100\%$ 的数据,有 $0 \le n \le 10^4$, $0 \le a, b, g, k \le {10}^5$。
noip2011 提高组 day1 第 $1$ 题。
题解
思路
首先因为数据很大需要设置数组,然后规定数组的最大值,接着输入a,b,g,k,然后初始化标志ans为-1,当没有地毯的时候直接输出ans。当循环体中满足x>=a[i]&&y>=b[i]&&x<=a[i]+g[i]&&y<=b[i]+k[i]的条件时,由于i是从0开始的需要+1作为第一个地毯,以此来确定最上方的的地毯。
代码
1 |
|
[NOIP2009 普及组] 多项式输出
题目描述
一元 $n$ 次多项式可用如下的表达式表示:
其中,$a_ix^i$ 称为 $i$ 次项,$a_i$ 称为 $i$ 次项的系数。给出一个一元多项式各项的次数和系数,请按照如下规定的格式要求输出该多项式:
多项式中自变量为 $x$,从左到右按照次数递减顺序给出多项式。
多项式中只包含系数不为 $0$ 的项。
如果多项式 $n$ 次项系数为正,则多项式开头不出
+
号,如果多项式 $n$ 次项系数为负,则多项式以-
号开头。对于不是最高次的项,以
+
号或者-
号连接此项与前一项,分别表示此项系数为正或者系数为负。紧跟一个正整数,表示此项系数的绝对值(如果一个高于 $0$ 次的项,其系数的绝对值为 $1$,则无需输出 $1$)。如果 $x$ 的指数大于 $1$,则接下来紧跟的指数部分的形式为“$x^b$”,其中 $b$ 为 $x$ 的指数;如果 $x$ 的指数为 $1$,则接下来紧跟的指数部分形式为 $x$;如果 $x$ 的指数为 $0$,则仅需输出系数即可。多项式中,多项式的开头、结尾不含多余的空格。
输入格式
输入共有 $2$ 行
第一行 $1$ 个整数,$n$,表示一元多项式的次数。
第二行有 $n+1$ 个整数,其中第 $i$ 个整数表示第 $n-i+1$ 次项的系数,每两个整数之间用空格隔开。
输出格式
输出共 $1$ 行,按题目所述格式输出多项式。
样例 #1
样例输入 #1
1 | 5 |
样例输出 #1
1 | 100x^5-x^4+x^3-3x^2+10 |
样例 #2
样例输入 #2
1 | 3 |
样例输出 #2
1 | -50x^3+1 |
提示
NOIP 2009 普及组 第一题
对于100%数据,$0 \le n \le 100$,$-100 \le $系数$ \le 100$
$\text{upd 2022.8.1}$:新增加一组 Hack 数据。
题解
思路
这道题主要有很多点需要注意:
- 系数为0不输出
- 第一项系数为正,不输出+,但是如果为负,就输出-
- 其他项正负号输出需要注意,如果指数为1的话直接输出“x”,其他情况需要输出“x^”
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
int main(){
int n;
cin>>n;
int a;
for(int i=n;i>=0;i--){
cin>>a;
if(a){
if(i!=n&&a>0) cout<<"+";
if(abs(a)>1||i==0) cout<<a;
if(a==-1&&i) cout<<"-";
if(i>1) cout<<"x^"<<i;
if(i==1) cout<<"x";
}
}
return 0;
}
1 |
|
[NOIP2010 普及组] 数字统计
题目描述
请统计某个给定范围 $[L, R]$ 的所有整数中,数字 $2$ 出现的次数。
比如给定范围 $[2, 22]$,数字 $2$ 在数 $2$ 中出现了 $1$ 次,在数 $12$ 中出现 $1$ 次,在数 $20$ 中出现 $1$ 次,在数 $21$ 中出现 $1$ 次,在数 $22$ 中出现 $2$ 次,所以数字 $2$ 在该范围内一共出现了 $6$ 次。
输入格式
$2$ 个正整数 $L$ 和 $R$,之间用一个空格隔开。
输出格式
数字 $2$ 出现的次数。
样例 #1
样例输入 #1
1 | 2 22 |
样例输出 #1
1 | 6 |
样例 #2
样例输入 #2
1 | 2 100 |
样例输出 #2
1 | 20 |
提示
$1 ≤ L ≤R≤ 100000$。
NOIP2010 普及组 第一题
题解
思路
这道题的重点就是将数每次取完余数后再降位数,然后在for循环中i不能直接用,因为后面会被赋值,所有要用n去代替i赋值。
代码
1 |
|
[NOIP2015 提高组] 神奇的幻方
题目背景
NOIp2015 提高组 Day1T1
题目描述
幻方是一种很神奇的 $N\times N$ 矩阵:它由数字 $1,2,3,\cdots \cdots ,N \times N$ 构成,且每行、每列及两条对角线上的数字之和都相同。
当 $N$ 为奇数时,我们可以通过下方法构建一个幻方:
首先将 $1$ 写在第一行的中间。
之后,按如下方式从小到大依次填写每个数 $K \ (K=2,3,\cdots,N \times N)$ :
- 若 $(K-1)$ 在第一行但不在最后一列,则将 $K$ 填在最后一行, $(K-1)$ 所在列的右一列;
- 若 $(K-1)$ 在最后一列但不在第一行,则将 $K$ 填在第一列, $(K-1)$ 所在行的上一行;
- 若 $(K-1)$ 在第一行最后一列,则将 $K$ 填在 $(K-1)$ 的正下方;
- 若 $(K-1)$ 既不在第一行,也不在最后一列,如果 $(K-1)$ 的右上方还未填数,则将 $K$ 填在 $(K-1)$ 的右上方,否则将 $K$ 填在 $(K-1)$ 的正下方。
现给定 $N$ ,请按上述方法构造 $N \times N$ 的幻方。
输入格式
一个正整数 $N$,即幻方的大小。
输出格式
共 $N$ 行,每行 $N$ 个整数,即按上述方法构造出的 $N \times N$ 的幻方,相邻两个整数之间用单空格隔开。
样例 #1
样例输入 #1
1 | 3 |
样例输出 #1
1 | 8 1 6 |
样例 #2
样例输入 #2
1 | 25 |
样例输出 #2
1 | 327 354 381 408 435 462 489 516 543 570 597 624 1 28 55 82 109 136 163 190 217 244 271 298 325 |
提示
对于 $100\%$ 的数据,对于全部数据, $1 \leq N \leq 39$ 且 $N$ 为奇数。
题解
思路
这道题是纯模拟题,就是纯暴力解决,在while循环中不断判断条件然后进行处理。
代码
1 |
|
1 |
|