国庆专项题解集.md · 阿丽优/BUAA-21级信类萌新和朋友们的题解集

# A - 改革春风吹满地

| 难度  |         考点          |
| :---: | :-------------------: |
|   0   | 签到 |

## 题目分析1

签到题；  我就要每行写一个printf，诶，就是玩。

## 示例程序1

```c
//Author: Noctis
#include <stdio.h>
int main()
{
    printf("      **                        **         **               ******\n");
    printf("      **                        **       *******          **\n");
    printf("      **                        ***        ** **         **   **\n");
    printf("**************  ************   *** *  ************       ***********\n");
    printf("      **                      * **        ****            **  **   **\n");
    printf("      **                        **       **   **         **   **    **\n");
    printf("      **                        **      **      ****        * **\n");
    printf("      **                        **     **       ****         ***");
    return 0;
}//祝祖国繁荣昌盛，顺祝各位国庆快乐！
```
## 题目分析2

打printf打累了？  
希望找个更简单的方法？  
那你算是找对地方啦！  
示例程序2.1为你提供只打一个printf的方法！

PS：示例程序2.2提供了一种更花哨的写法

## 示例程序2.1
```c
//Author: Toby Shi
#include <stdio.h>

int main()
{
	printf("\
      **                        **         **               ******\n\
      **                        **       *******          **\n\
      **                        ***        ** **         **   **\n\
**************  ************   *** *  ************       ***********\n\
      **                      * **        ****            **  **   **\n\
      **                        **       **   **         **   **    **\n\
      **                        **      **      ****        * **\n\
      **                        **     **       ****         ***"
	);
    return 0;
}

/*
让我来解释一下这是什么意思：
想必大家都能理解为什么每行（最后一行除外）都有一个\n吧。
所以我只解释行末单独的一个\是什么意思。
首先大家都知道，在C语言中字符串是不能提行写的，
但是，为了使程序好看我们又需要提行写。
怎么办呢？其实只需要在行末打一个单独的\即可！
这就是上面的代码的由来。
*/

```

## 示例程序2.2

```c
//Author: Toby Shi
#include <stdio.h>
#define Wish int main(){
#define the printf("      **                        **         **               ******\n");
#define motherland printf("      **                        **       *******          **\n");
#define prosperity printf("      **                        ***        ** **         **   **\n");
#define And printf("**************  ************   *** *  ************       ***********\n");
#define happy printf("      **                      * **        ****            **  **   **\n");
#define National printf("      **                        **       **   **         **   **    **\n");
#define Day printf("      **                        **      **      ****        * **\n");
#define to printf("      **                        **     **       ****         ***");
#define you return 0;
#define all }

Wish the motherland prosperity
And happy National Day to you all

//宏定义为您送上最好的国庆礼物！

```

## 题目分析3

感觉这签到题太没意思了？  
做签到题就是在侮辱我们的智商？  
那你可以尝试下面的做法！  
什么样的程序最好呢？  
当然是能写程序的程序！

PS：关于这个程序怎么用，请看[这个视频](https://www.bilibili.com/video/BV1S64y187iu?share_source=copy_web)。

## 示例程序3

```c
//Author: Toby Shi
#include <stdio.h>

//告诉你一个小秘密，以后凡是看到没有输入，只要求输出一段文字的题目，都可以使用本程序！

int main()
{
	freopen("a.txt", "r", stdin); //请在运行本程序前，将欲输出的内容复制粘贴到a.txt的文件下，且这个文件应与此程序位于同一个目录下
	freopen("ac.c", "w", stdout); //这个程序将向一个叫做ac.c的文件里写入内容，而写入的内容是一个程序！
	printf("#include <stdio.h>\n\n");
	printf("int main()\n");
	printf("{\n");
	char s[100];
	while(gets(s))
		printf("\tprintf(\"%s\\n\");\n", s);
	printf("\treturn 0;\n");
	printf("}\n");
	return 0;
}

```

# B - 闰年

| 难度  |         考点          |
| :---: | :-------------------: |
|   0   | 签到 |

## 题目分析

签到题；  小学数学还是要学好的。

## 示例程序

```c
//Author: Noctis
#include <stdio.h>
int main ()
{
    int a;
    scanf("%d",&a);
    if(((a%4==0)&&(a%100!=0))||(a%400==0)) printf("leap year!");
	else printf("common year!");
    return 0;
}
```

# C - 暴食之王

| 难度  |         考点          |
| :---: | :-------------------: |
|   1   | 对题干的阅读理解 |

## 题目分析

需注意此题题干中对数据范围有一定要求，暴食之王的总体重完全可能超过int范围。  
此外，王获得的是被吃的生物体积一半而不是自身（"x"）的体积一半。

## 示例程序

```c
//Author: Noctis
#include <stdio.h>
int main ()
{
    long long n,x,i;//这里我偷懒了，但其实只有x需要用到long long，像我这样写会占用不必要的内存 (Toby注：还会多花时间(笑))
    scanf("%lld%lld\n",&n,&x);
    for (int j=0;j<n;j++)
    {
        scanf("%lld",&i);
        getchar();
        if (i<=x/2) x+=i;
        if (i>x/2&&i<=x) x+=i/2;
    }
    printf("%lld",x);
    return 0;
}
```

# D - MYX的函数续

| 难度  |         考点          |
| :---: | :-------------------: |
|   1   | 对问题的一定分析能力 |

## 题目分析

作为《MYX的函数》续集，这题的输入部分和前者一模一样；  
这次仔细读题后不难发现只要x[i]<z[i]就找不到到对应的y[i]了。  
最后，经典的"N0"了（笑）

## 示例程序

```c
//Author: Noctis, with the help of Toby
#include <stdio.h>
int main ()
{
    int n;
    char ch1,ch2;
    scanf("%d\n",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%c%c",&ch1,&ch2);
        if (ch1<ch2)//感谢Toby的指正
        {
            printf("N0");//一旦有一组不行整个都不行了，类似于上次存钱
            return 0;
        }
    }
    printf("YES!");
    return 0;
}
```

# E - 菱形

| 难度  |         考点          |
| :---: | :-------------------: |
|   1   | 有点小学数学题的味儿 |

## 题目分析

其实这道题在程设《导引》上面有几乎一样的，参见应该是第一章。  
这题是Noctis第一次写自定义函数，对他来说算是个记录吧。

## 示例程序

```c
//Author: Noctis
#include <stdio.h>
void drawline(int space,int length,char fill)//先定义一个画线函数
{                                            //这个函数没有返回值，所以写void
    int q=1;                                 //如果要有返回值就得写int drawline这样，并且要把return 一个返回值放进函数里面
    for (q=1;q<=space;q++) printf(" ");      //这个函数实现了给定前面的空格数、长度和填充用的字符来画一条线的功能
    for (q=1;q<=length;q++) printf("%c",fill);
    printf("\n");
}//大家可以翻翻书或者上网查一查，毕竟Noctis也是零基础刚学                   
int main()//其实这也是个函数
{
    int n,i;
    scanf("%d",&n);
    for (i=1;i<=n/2;i++) drawline(n/2-(2*i-1)/2,2*i-1,'*');//我先画一个正三角形
    for (;i>=1;i--) drawline(n/2-(2*i-1)/2,2*i-1,'*');//再画一个倒三角形
    return 0;
}
```

# F - STEINS;GATE

| 难度  |         考点          |
| :---: | :-------------------: |
|   2   | 还是一个数学题 |

## 题目分析

列出各个数字需要的极管数之后不难发现只有两根的1和三根的7是有意义的（前者连着写很多位，后者用来处理奇数）；  
因此其实只要用1和7就可以了。  
另外，听说《命运石之门》很好看。

## 示例程序

```c
//Author: Noctis
#include <stdio.h>
int main()
{
    int t,n,i,u;
    scanf("%d\n",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%d",&n);
        if (n<=1) printf("-1\n");//单独处理过小的
        else
        {
            if (n%2==0)//偶数用1
            {
                for (u=1;u<=n/2;u++) printf("1");
                printf("\n");//记得换行
            }
            else//奇数拿7顶最高位，剩下放1
            {
                printf("7");
                for (u=1;u<=n/2-1;u++) printf("1");
                printf("\n");
            }
        }
    }
    return 0;
}
```
# G - 双关键字最值

| 难度  |         考点          |
| :---: | :-------------------: |
|   1.5   | 基础编程能力 |

## 题目分析

如题 就是想让你按a,b双关键字寻找最大值 有基础编程能力就可顺利切题

懒一点的话也可以写qsort+自定义结构体排序

当然我认为直接扫描一遍O(n）的做法就很优了

## 示例程序

```c
//From: Srch_Paris丶
#include<stdio.h>
int a[100002],b[100002],n,d[100002],p;
int main(){
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&b[i]);
    int z=-1e8;
    for(i=1;i<=n;i++){
        if(a[i]==z) d[++p]=i;//如果和当前最大值相同就记下位置来
        if(a[i]>z){//发现有更大的就更新z并清空之前的记录
            p=0;d[++p]=i;
            z=a[i];
        }
    }
    z=-1e8;
    int k=0;
    for(i=1;i<=p;i++){
        if(b[d[i]]>=z){//对第二关键字扫描 这里必须是大于等于哦 为了保证取下标最大的要求
            z=b[d[i]];
            k=d[i];
        }
    }
    printf("%d\n%d %d\n",k,a[k],b[k]);
    return 0;
}//挺签到的反正
```
# N - Monica的星空

| 难度 | 考点 |
| :-----: | :-----: |
| 6 | 概率统计 |

## 题目分析

这题有亿点难度，尽管有4个Hint，但是这些Hint说的都很隐晦，生怕你知道了什么秘密  
所以我们首先来解读这些Hint：  
- Hint 1：如何使用小费马定理求乘法逆元，这个应该都能看懂吧，不解释。
- Hint 2：方差怎么计算，这个非常重要，大家也能看懂，不解释。
- Hint 3：统计每个棋子的贡献，因为本题矩形很大但棋子很少，所以我们不能穷举棋盘只能穷举棋子，结合Hint 2，实际上，考虑每个棋子的贡献的时候就不能考虑其对方差的贡献，必须考虑其对期望以及平方的期望的贡献。
- Hint 4：这个就很迷，但是众所周知，一个棋子对期望的贡献好求，对平方的期望不易求，所以势必需要某个方法，Hint 4显然是一个方法，但是怎么用呢？

别急，做题要一步一步的来，这道题有如下要点需要考虑：
- 一共究竟有多少个矩形？
- $E(x)$究竟怎么维护？
- $E(x^2)$又要怎么维护？

------------------------

关于一共有多少个矩形，我们这样考虑：

首先，考虑棋盘只有一行（即$n=1$），此时显然有$m$个$1\times1$的矩形，$m-1$个$1\times2$的矩形，$m-2$个$1\times3$的矩形，……，$1$个$1\times m$的矩形。因此矩形总数是$\frac{m(m+1)}{2}$。  
然后，考虑棋盘只有两行（即$n=2$），此时每一行都有$\frac{m(m+1)}{2}$个矩形，但是两行还可以加起来，这就又有$\frac{m(m+1)}{2}$个矩形。因此矩形总数是$3\times\frac{m(m+1)}{2}$。  
最后，我们直接考虑棋盘有n行m列，此时显然每行都有$\frac{m(m+1)}{2}$个矩形，但是有多少行呢？实际上，每行可以单独成行，也可以和邻近的行连在一起，因此计算方法和一行有多个矩形一致。所以一共就有$\frac{m(m+1)}{2}\times\frac{n(n+1)}{2}$个矩形。

求出总数后，由于总数是分母，所以不要忘记用Hint 1取乘法逆元哦！

-----------------------

关于$E(x)$究竟怎么维护，我们这样考虑：

首先明确一点，$E(x)$的分母就是矩形总数，分子是每个矩形里的棋子数的和，所以我们显然只需要维护分子。  
注意到，想要求每个矩形里的棋子数的和，但枚举每个矩形是不可能的，我们只能枚举棋子。  
实际上，Hint 3说了，考虑每个棋子的贡献。实际上，要求每个棋子为$E(x)$的分子贡献的数目，就是求这个棋子在多少个矩形中，它每在一个矩形中，这个矩形里的棋子数就+1，$E(x)$的分子就+1。  
现在我们已经把问题转化为求某个棋子在多少个矩形中了。如何计算呢？  
我们依然先只考虑棋子所在行，包括这个棋子的矩形，可以向左延伸若干列，也可以向右延伸若干列。更准确地说，对于棋子(x,y)，向左可延伸0\~y-1列，向右可延伸0\~m-y列，而且向左延伸和向右延伸互不干扰，因此这一行中，包含这个棋子的矩形共有$y\times(m-y+1)$个。  
好的，现在同样思路考虑列，这样一来，我们就知道了，包含这个棋子(x,y)的矩形共有$x\times(n-x+1)\times y\times(m-y+1)$个。

写成代码就是：（千万不要忘记随时取模，以及使用long long）
```c
scanf("%d%d", &x[i], &y[i]);
x_1 += 1ll * x[i] * (n - x[i] + 1) % P * y[i] % P * (m - y[i] + 1) % P;
x_1 %= P;
x_2 += 1ll * x[i] * (n - x[i] + 1) % P * y[i] % P * (m - y[i] + 1) % P;
x_2 %= P;
```

----------------------

关于$E(x^2)$究竟怎么维护，我们这样考虑：

这个比较困难，因此我们需要仔细思考Hint 4。实际上，Hint 4的意思是 $((1+1+...+1)+1)^2=(1+1+...+1)^2+1^2+2\times1\times1+2\times1\times1+...+2\times1\times1$，我为什么要这样写呢？  
因为我们发现，$((1+1+...+1)+1)^2$是我们需要计算的式子，而$(1+1+...+1)^2$是已经计算的式子（这是我们一直要维护的$E(x^2)$的分子），接下来，就只需要计算$1^2 + 2\times1\times1 + 2\times1\times1 + ... + 2\times1\times1$了。如何计算呢？  
我们发现，首先，对于任何包含棋子(x,y)的矩形，都应该获得+1；其次，对于那些已经拥有棋子的矩形，当前棋子的贡献就会更高，确切地说，如果一个矩形同时包含当前棋子和另一棋子，则当前棋子额外贡献+2。  
有了这个想法，其实我们只需要枚举当前棋子的同时枚举我们已经计算好了的棋子，然后考虑能同时包含这两个棋子的矩形，至此，大功告成！

写成代码就是下面这样：
```c
x_2 += 1ll * x[i] * (n - x[i] + 1) % P * y[i] % P * (m - y[i] + 1) % P; //这个就是单独的贡献，同x_1
x_2 %= P;
for(int j = 0; j < i; j++)
{
	int a1 = MIN(x[i], x[j]), a2 = MAX(x[i], x[j]);
	int b1 = MIN(y[i], y[j]), b2 = MAX(y[i], y[j]);
	x_2 += 1ll * a1 * (n - a2 + 1) % P * b1 % P * (m - b2 + 1) % P * 2 % P; //不要忘记这里是要乘以2的
	x_2 %= P;
}
```

## 示例代码

```c
//Author: Toby Shi
#include <stdio.h>
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define MAX(x, y) ((x) > (y) ? (x) : (y))

const int P = 998244353;
int n, m, x[5005], y[5005], k;
int x_1, x_2, cnt;

int power(int base, int exp) //快速幂，详见E3-D题
{
	if(exp == 0) return 1;
	if(exp == 1) return base;
	if(exp & 1) return base * 1ll * power(base * 1ll * base % P, exp >> 1) % P;
	return power(base * 1ll * base % P, exp >> 1);
}

int main()
{
	scanf("%d%d%d", &n, &m, &k);
	cnt = (1ll * n * (n+1) / 2 % P) * (1ll * m * (m+1) / 2 % P) % P;
	cnt = power(cnt, P - 2);
	for(int i = 0; i < k; i++)
	{
		scanf("%d%d", &x[i], &y[i]);
		x_1 += 1ll * x[i] * (n - x[i] + 1) % P * y[i] % P * (m - y[i] + 1) % P;
		x_1 %= P;
		x_2 += 1ll * x[i] * (n - x[i] + 1) % P * y[i] % P * (m - y[i] + 1) % P;
		x_2 %= P;
		for(int j = 0; j < i; j++)
		{
			int a1 = MIN(x[i], x[j]), a2 = MAX(x[i], x[j]);
			int b1 = MIN(y[i], y[j]), b2 = MAX(y[i], y[j]);
			x_2 += 1ll * a1 * (n - a2 + 1) % P * b1 % P * (m - b2 + 1) % P * 2 % P;
			x_2 %= P;
		}
	}
	long long ans = x_1 * 1ll * cnt % P; //E(x)
	ans = ans * ans % P; //E^2(x)
	ans = x_2 * 1ll * cnt % P - ans; //E(x^2) - E^2(x)
	ans = (ans + P) % P; //可能是负的，我们+P再%P
	printf("%lld\n", ans);
	return 0;
}
```

# P - 亦真亦假

| 难度  |         考点          |
| :---: | :-------------------: |
|   0   | 最大公约数 |

## 题目分析

看起来每天国庆练习都会更新一道水题和一道不水的题，这题是和Q一起出来的。  
这道题作为水题只需要记得求最大公约数约分就行了（我用的辗转相除）。

## 示例程序

```c
//Author: Noctis
//结束之后就有了，不过你多半用不上
```

# Q - 奇怪的团建增加了.jpg

| 难度  |         考点          |
| :---: | :-------------------: |
|   5   | 图 论（噔噔咚） |

## 题目分析

这一题只是单纯的数学题啦  
代码部分的难度几近于0（这比签到题的代码还短吧）   
证明如下：  
2![Transcribed by Clay.](https://images.gitee.com/uploads/images/2021/1005/094047_ffaefdfd_9742051.png "National Day_Q.png")
有任何不明白的地方欢迎提问，我会对证明步骤进行改进的。

## 示例程序

```c
//Author：Projekt Red
#include<stdio.h>

int main()
{
    int n,a,b;
    while(scanf ("%d%d%d",&n,&a,&b)!=EOF){
    if ((a-1)*(n-1)+b)
    printf ("Impossible\n");
    else
    printf ("Possible\n");
    }
    return 0;
}
```

第一次写题解，希望没有什么意外（逃  
Noctis:制约写题解的因素是解题能力而不是markdown语法（笑），所以日后主要靠各位大佬啦

# R - 转 反 字 数

| 难度  |         考点          |
| :---: | :-------------------: |
|   2   | 仔细程度 |

## 题目分析

看起来每天国庆练习都会更新一道水题和一道不水的题，这题是和S一起出来的。  
这道题作为水题有那么一点考验耐心，各种情况都要考虑到，在我心里有着接近E3-C的地位。  
如果你和我一样菜而需要帮助的话可以考虑先处理反转前的数字（抹掉结尾的0等）再反转。

## 示例程序

```c
//Author: Noctis
/*
结束之后就有了，不过你多半用不上
这里提供一组测试数据吧，方便你debug：
0
10
-10
5.0
-5.0
5.00
-5.00
50.0
-50.0
500.00
-500.00
500.000
-500.000
记得看数据范围，数组越界导致错误就很亏了
*/
```

阿丽优/BUAA-21级信类萌新和朋友们的题解集

简介

发行版

贡献者

近期动态

阿丽优/BUAA-21级信类萌新和朋友们的题解集 .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

阿丽优/BUAA-21级信类萌新和朋友们的题解集