模拟和高精度

[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

WWWWWWWWWWWWWWWWWWWW
WWLWE

样例输出 #1

11:0
11:0
1:1

21:0
2:1

提示

每行至多 $25$ 个字母，最多有 $2500$ 行。

（注：事实上有一个测试点有 $2501$ 行数据。）

【题目来源】

NOIP 2003 普及组第一题

题解

思路

在两个规模下比赛，一个是11分，另一个是21分，其中只要当遍历到字母E的时候才会结束比赛信息。当双方比分都超过11或者21时，需要双方分差大于等于2时才会结束，那么就需要abs函数给绝对值然后返回。由于题目要求每行至多 $25$ 个字母，最多有 $2500$ 行。则在建立字符串数组时需要很大，来测试数据。

代码

#include<iostream>
#include<cmath>
using namespace std;

char str[100010];
int cnt=0;

void show(int n){

    int a=0,b=0;
    for(int i=0;i<cnt;i++){
        if(str[i]=='W') a++;
        if(str[i]=='L') b++;

        if((a>=n||b>=n)&&abs(a-b)>=2){
            cout<<a<<":"<<b<<endl;
            a=b=0;
        }
    }

    cout<<a<<":"<<b<<endl;
}

int main(){
    char ch;

    while(cin>>ch&&ch!='E'){
        if(ch=='W'||ch=='L'){
          str[cnt++]=ch;
        }
    }

    show(11);
    cout<<endl;
    show(21);
}

---

[NOIP2015 普及组] 扫雷游戏

题目背景

NOIP2015 普及组 T2

题目描述

扫雷游戏是一款十分经典的单机小游戏。在 $n$ 行 $m$ 列的雷区中有一些格子含有地雷（称之为地雷格），其他格子不含地雷（称之为非地雷格）。玩家翻开一个非地雷格时，该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下，找出所有的非地雷格。

现在给出 $n$ 行 $m$ 列的雷区中的地雷分布，要求计算出每个非地雷格周围的地雷格数。

注：一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。

输入格式

第一行是用一个空格隔开的两个整数 $n$ 和 $m$，分别表示雷区的行数和列数。

接下来 $n$ 行，每行 $m$ 个字符，描述了雷区中的地雷分布情况。字符 $\texttt{*}$ 表示相应格子是地雷格，字符 $\texttt{?}$ 表示相应格子是非地雷格。相邻字符之间无分隔符。

输出格式

输出文件包含 $n$ 行，每行 $m$ 个字符，描述整个雷区。用 $\texttt{*}$ 表示地雷格，用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。

样例 #1

样例输入 #1

3 3
*??
???
?*?

样例输出 #1

*10
221
1*1

样例 #2

样例输入 #2

2 3
?*?
*??

样例输出 #2

2*1
*21

提示

对于 $100\%$的数据，$1≤n≤100, 1≤m≤100$。

题解

思路

这题重点是如何判断上、下、左、右、左上、右上、左下、右下八个方向，可以先创建一个二维数组，然后因为他是n行m列的数组，利用i、j分别去控制二维数组中某一个位置的上下左右来达到实现判断上、下、左、右、左上、右上、左下、右下八个方向。然后是要先定义网格大小，同时只考虑’?’字符的输出情况，不去考虑’‘字符时的输出，因为题中’‘字符输出不变。

代码

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int MAX_N = 105; // 定义网格的最大尺寸

char grid[MAX_N][MAX_N];

void show(int n, int m) {
    // 定义检查相邻单元格的方向
    int dx[] = {1, 1, 1, 0, 0, -1, -1, -1};
    int dy[] = {1, 0, -1, 1, -1, 1, 0, -1};
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] != '*') {
                int mines = 0;
                // 检查相邻单元格
                for(int k = 0; k < 8; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == '*')
                        mines++;
                }
                grid[i][j] = mines + '0'; // 将计数转换为字符
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    
    show(n, m);
    
    // 打印网格
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cout << grid[i][j];
        }
        cout << endl;
    }
    
    return 0;
}

---

[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

7 3
0 singer
0 reader
0 mengbier 
1 thinker
1 archer
0 writer
1 mogician 
0 3
1 1
0 2

样例输出 #1

writer

样例 #2

样例输入 #2

10 10
1 C
0 r
0 P
1 d
1 e
1 m
1 t
1 y
1 u
0 V
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4

样例输出 #2

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。最后输出该字符串

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

struct node 
{
    int head;
    string name;
}a[100005];
int n,m,x,y;
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>a[i].head>>a[i].name;
    }
    int now=0;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        if(a[now].head==0&&x==0)now=(now+n-y)%n;
        else if(a[now].head==0&&x==1)now=(now+y)%n;
        else if(a[now].head==1&&x==0)now=(now+y)%n;
        else if(a[now].head==1&&x==1)now=(now+n-y)%n;
    }
    cout<<a[now].name<<endl;
    return 0;
}

---

A+B Problem（高精）

题目描述

高精度加法，相当于 a+b problem，不用考虑负数。

输入格式

分两行输入。$a,b \leq 10^{500}$。

输出格式

输出只有一行，代表 $a+b$ 的值。

样例 #1

样例输入 #1

1
1

样例输出 #1

2

样例 #2

样例输入 #2

1001
9099

样例输出 #2

10100

提示

$20\%$ 的测试数据，$0\le a,b \le10^9$；

$40\%$ 的测试数据，$0\le a,b \le10^{18}$。

题解

思路

首先这道题是高精度的题目，它的数据超过int和longlong型的数据大小，因此需要先输入成字符串然后将字符串转变为整型数组，然后相加。字符串变成整型数组后，需要将数组反转，让个位对齐，然后相加，注意因为有进位的存在，需要有个标识符，然后还要判断当两个数组长度一样时，相加有可能超过数组的长度，需要加上进位的标识符。

代码

#include<bits/stdc++.h>
using namespace std;

int aplusb(string a,string b,int *c){
	int j1[505]={0},j2[505]={0},jw=0;
	int lena=a.length(),lenb=b.length(),len=max(lena,lenb);
	for(int i=0;i<lena;i++) j1[i]=a[lena-i-1]-'0';
	for(int i=0;i<lenb;i++) j2[i]=b[lenb-i-1]-'0';
	for(int i=0;i<len;i++)
	{
		c[i]=j1[i]+j2[i]+jw;
		jw=c[i]/10;
		c[i]=c[i]%10;
	}
	if(jw>0){
		c[len]=jw;
		len++;
	}
	return len;
}

int main(){
	string a,b;
	int c[505],n;
	cin>>a>>b;
	n=aplusb(a,b,c);
	for(int i=n-1;i>=0;i--){
		cout<<c[i];
	}
	return 0;
}

---

A*B Problem

题目描述

给出两个非负整数，求它们的乘积。

输入格式

输入共两行，每行一个非负整数。

输出格式

输出一个非负整数表示乘积。

样例 #1

样例输入 #1

1 
2

样例输出 #1

2

提示

每个非负整数不超过 $10^{2000}$。

题解

思路

高精度的数相乘，相当于列式计算，（与高精度加法类似），首先输入字符串然后转变成整型数组再反转，让个位对齐，再相乘，当某一位的数超过9的时候，需要将这个数除以10作为进位，然后该数的位置再求10的余数。然后将两个数的长度相加，如果首位有0的情况需要将长度-1，最后反向输出这个数。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
char a1[10001],b1[10001];
int a[10001],b[10001],i,len,j,c[10001];
int main ()
{
    cin>>a1>>b1;
    int lena=strlen(a1);
	int lenb=strlen(b1);
    for(i=1;i<=lena;i++)a[i]=a1[lena-i]-'0';
    for(i=1;i<=lenb;i++)b[i]=b1[lenb-i]-'0';
	for(i=1;i<=lenb;i++)
	for(j=1;j<=lena;j++)
	c[i+j-1]+=a[j]*b[i];
    for(i=1;i<lena+lenb;i++)
	if(c[i]>9)
	{
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	len=lena+lenb;
    while(c[len]==0&&len>1)len--;
    for(i=len;i>=1;i--)cout<<c[i];
    return 0;
}

---

[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

3

样例输出 #1

9

提示

【数据范围】

对于 $100 \%$ 的数据，$1 \le n \le 50$。

【其他说明】

注，《深入浅出基础篇》中使用本题作为例题，但是其数据范围只有 $n \le 20$，使用书中的代码无法通过本题。

如果希望通过本题，请继续学习第八章高精度的知识。

NOIP1998 普及组 第二题

题解

思路

首先高精度的话，用两个数组，一个表示输入的数组，另一个表示计算结果。
首先主函数里先输入n表示需要计算的阶乘和的变量，然后由于最后是要相加的，直接返回数组的最后一位的初值，且初值设置为1，然后循环从i=2开始。在阶乘函数中，数组的值需要进行高精度算法运算，然后再到求和函数中进行高精度算法运算，最后再反转求和的数组，然后输出。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,a[101]={0},s[101]={0};
void change(int x)
{
	int g=0;
	for(int i=100;i>=0;i--)
	{
		a[i]=a[i]*x+g;
		g=a[i]/10;
		a[i]=a[i]%10;
	}
}
void qh()
{
	int g=0;
	for(int i=100;i>=0;i--)
	{
		s[i]=s[i]+a[i]+g;
		g=s[i]/10;
		s[i]=s[i]%10;
	}
}
void sc()
{
	int w;
	for(int i=0;i<=100;i++)
	{
		if(s[i]!=0)
		{
			w=i;
			break;
		}
	}
	for(int i=w;i<=100;i++)
	   printf("%d",s[i]);
}
int main()
{
	scanf("%d",&n);
	s[100]=a[100]=1;
	for(int i=2;i<=n;i++)
	{
		change(i);
		qh();
	}
	sc();
	return 0;
}

---

[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

3
1 0 2 3
0 2 3 3
2 1 3 3
2 2

样例输出 #1

3

样例 #2

样例输入 #2

3
1 0 2 3
0 2 3 3
2 1 3 3
4 5

样例输出 #2

-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作为第一个地毯，以此来确定最上方的的地毯。

代码

#include<bits/stdc++.h> 

using namespace std;

const int MAX=10000+5;
int a[MAX],b[MAX],g[MAX],k[MAX];

int main(){
	int n,x,y;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d%d%d",&a[i],&b[i],&g[i],&k[i]);
	}
	scanf("%d%d",&x,&y);
	
	int ans=-1;
	for(int i=0;i<n;i++){
		if(x>=a[i]&&y>=b[i]&&x<=a[i]+g[i]&&y<=b[i]+k[i]){
			ans=i+1;
		}
	}
	
	printf("%d\n",ans);
	return 0;
}

---

[NOIP2009 普及组] 多项式输出

题目描述

一元 $n$ 次多项式可用如下的表达式表示：

$$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots +a_1x+a_0,a_n\ne 0$$

其中，$a_ix^i$ 称为 $i$ 次项，$a_i$ 称为 $i$ 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：

1. 多项式中自变量为 $x$，从左到右按照次数递减顺序给出多项式。

2. 多项式中只包含系数不为 $0$ 的项。

3. 如果多项式 $n$ 次项系数为正，则多项式开头不出 + 号，如果多项式 $n$ 次项系数为负，则多项式以 - 号开头。

4. 对于不是最高次的项，以 + 号或者 - 号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于 $0$ 次的项，其系数的绝对值为 $1$，则无需输出 $1$）。如果 $x$ 的指数大于 $1$，则接下来紧跟的指数部分的形式为“$x^b$”，其中 $b$ 为 $x$ 的指数；如果 $x$ 的指数为 $1$，则接下来紧跟的指数部分形式为 $x$；如果 $x$ 的指数为 $0$，则仅需输出系数即可。

5. 多项式中，多项式的开头、结尾不含多余的空格。

输入格式

输入共有 $2$ 行

第一行 $1$ 个整数，$n$，表示一元多项式的次数。

第二行有 $n+1$ 个整数，其中第 $i$ 个整数表示第 $n-i+1$ 次项的系数，每两个整数之间用空格隔开。

输出格式

输出共 $1$ 行，按题目所述格式输出多项式。

样例 #1

样例输入 #1

5 
100 -1 1 -3 0 10

样例输出 #1

100x^5-x^4+x^3-3x^2+10

样例 #2

样例输入 #2

3 
-50 0 0 1

样例输出 #2

-50x^3+1

提示

NOIP 2009 普及组 第一题

对于100%数据，$0 \le n \le 100$，$-100 \le $系数$ \le 100$

---

$\text{upd 2022.8.1}$：新增加一组 Hack 数据。

题解

思路

这道题主要有很多点需要注意：

1. 系数为0不输出
2. 第一项系数为正，不输出+，但是如果为负，就输出-
3. 其他项正负号输出需要注意，如果指数为1的话直接输出“x”，其他情况需要输出“x^”

代码

#include<bits/stdc++.h> 

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;
}

[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

2 22

样例输出 #1

6

样例 #2

样例输入 #2

2 100

样例输出 #2

20

提示

$1 ≤ L ≤R≤ 100000$。

NOIP2010 普及组 第一题

题解

思路

这道题的重点就是将数每次取完余数后再降位数，然后在for循环中i不能直接用，因为后面会被赋值，所有要用n去代替i赋值。

代码

#include<bits/stdc++.h> 

using namespace std; 

int main(){
	long long L,R,k=0,n;
	cin>>L>>R;

	for(int i=L;i<=R;i++){
		n=i;
		while(n!=0){
			if(n%10==2)
				k++;
			n/=10;	
		}
			
	}
	
	cout<<k<<endl;
	return 0;
}

---

[NOIP2015 提高组] 神奇的幻方

题目背景

NOIp2015 提高组 Day1T1

题目描述

幻方是一种很神奇的 $N\times N$ 矩阵：它由数字 $1,2,3,\cdots \cdots ,N \times N$ 构成，且每行、每列及两条对角线上的数字之和都相同。

当 $N$ 为奇数时，我们可以通过下方法构建一个幻方：

首先将 $1$ 写在第一行的中间。

之后，按如下方式从小到大依次填写每个数 $K \ (K=2,3,\cdots,N \times N)$ ：

1. 若 $(K-1)$ 在第一行但不在最后一列，则将 $K$ 填在最后一行， $(K-1)$ 所在列的右一列；
2. 若 $(K-1)$ 在最后一列但不在第一行，则将 $K$ 填在第一列， $(K-1)$ 所在行的上一行；
3. 若 $(K-1)$ 在第一行最后一列，则将 $K$ 填在 $(K-1)$ 的正下方；
4. 若 $(K-1)$ 既不在第一行，也不在最后一列，如果 $(K-1)$ 的右上方还未填数，则将 $K$ 填在 $(K-1)$ 的右上方，否则将 $K$ 填在 $(K-1)$ 的正下方。

现给定 $N$ ，请按上述方法构造 $N \times N$ 的幻方。

输入格式

一个正整数 $N$，即幻方的大小。

输出格式

共 $N$ 行，每行 $N$ 个整数，即按上述方法构造出的 $N \times N$ 的幻方，相邻两个整数之间用单空格隔开。

样例 #1

样例输入 #1

3

样例输出 #1

8 1 6
3 5 7
4 9 2

样例 #2

样例输入 #2

25

样例输出 #2

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
353 380 407 434 461 488 515 542 569 596 623 25 27 54 81 108 135 162 189 216 243 270 297 324 326
379 406 433 460 487 514 541 568 595 622 24 26 53 80 107 134 161 188 215 242 269 296 323 350 352
405 432 459 486 513 540 567 594 621 23 50 52 79 106 133 160 187 214 241 268 295 322 349 351 378
431 458 485 512 539 566 593 620 22 49 51 78 105 132 159 186 213 240 267 294 321 348 375 377 404
457 484 511 538 565 592 619 21 48 75 77 104 131 158 185 212 239 266 293 320 347 374 376 403 430
483 510 537 564 591 618 20 47 74 76 103 130 157 184 211 238 265 292 319 346 373 400 402 429 456
509 536 563 590 617 19 46 73 100 102 129 156 183 210 237 264 291 318 345 372 399 401 428 455 482
535 562 589 616 18 45 72 99 101 128 155 182 209 236 263 290 317 344 371 398 425 427 454 481 508
561 588 615 17 44 71 98 125 127 154 181 208 235 262 289 316 343 370 397 424 426 453 480 507 534
587 614 16 43 70 97 124 126 153 180 207 234 261 288 315 342 369 396 423 450 452 479 506 533 560
613 15 42 69 96 123 150 152 179 206 233 260 287 314 341 368 395 422 449 451 478 505 532 559 586
14 41 68 95 122 149 151 178 205 232 259 286 313 340 367 394 421 448 475 477 504 531 558 585 612
40 67 94 121 148 175 177 204 231 258 285 312 339 366 393 420 447 474 476 503 530 557 584 611 13
66 93 120 147 174 176 203 230 257 284 311 338 365 392 419 446 473 500 502 529 556 583 610 12 39
92 119 146 173 200 202 229 256 283 310 337 364 391 418 445 472 499 501 528 555 582 609 11 38 65
118 145 172 199 201 228 255 282 309 336 363 390 417 444 471 498 525 527 554 581 608 10 37 64 91
144 171 198 225 227 254 281 308 335 362 389 416 443 470 497 524 526 553 580 607 9 36 63 90 117
170 197 224 226 253 280 307 334 361 388 415 442 469 496 523 550 552 579 606 8 35 62 89 116 143
196 223 250 252 279 306 333 360 387 414 441 468 495 522 549 551 578 605 7 34 61 88 115 142 169
222 249 251 278 305 332 359 386 413 440 467 494 521 548 575 577 604 6 33 60 87 114 141 168 195
248 275 277 304 331 358 385 412 439 466 493 520 547 574 576 603 5 32 59 86 113 140 167 194 221
274 276 303 330 357 384 411 438 465 492 519 546 573 600 602 4 31 58 85 112 139 166 193 220 247
300 302 329 356 383 410 437 464 491 518 545 572 599 601 3 30 57 84 111 138 165 192 219 246 273
301 328 355 382 409 436 463 490 517 544 571 598 625 2 29 56 83 110 137 164 191 218 245 272 299

提示

对于 $100\%$ 的数据，对于全部数据， $1 \leq N \leq 39$ 且 $N$ 为奇数。

题解

思路

这道题是纯模拟题，就是纯暴力解决，在while循环中不断判断条件然后进行处理。

代码

#include<bits/stdc++.h> 
using namespace std; 

int a[40][40] = { 0 };

int main() {
    int n;
    cin >> n;            
    int step = 1;    
    int posx, posy; 
    while (step <= n * n) {
        if (step == 1) 
            a[posx = 1][posy = n / 2 + 1] = step++;
        else if (posx == 1 && posy != n) 
            a[posx = n][++posy] = step++;
        else if (posx != 1 && posy == n) 
            a[--posx][posy = 1] = step++;
        else if (posx == 1 && posy == n) 
            a[++posx][posy] = step++;
        else if (posx != 1 && posy != n)
            if (a[posx - 1][posy + 1] == 0)
                a[--posx][++posy] = step++;
            else
                a[++posx][posy] = step++;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j)
            cout << a[i][j] << " ";
        cout <<endl;
    }
}

#include<bits/stdc++.h> 
using namespace std; 

int n,a[40][40],x,y;
int main(){
	scanf("%d",&n);
	x=1,y=(n+1)/2;
	for(int i=1;i<=n*n;i++){
		a[x][y]=i;
		if(!a[(x-2+n)%n+1][y%n+1]) x=(x-2+n)%n+1,y=y%n+1;
		else x=x%n+1;//数学运算
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
}