[C++知识库]洛谷刷题C语言：询问、光图、苏联人、Another Cow Number Game G、STROJOPIS

记录洛谷刷题QAQ

一、询问

题目背景

zbw 被邀请至幼儿园给小朋友们出题。

题目描述

现在 zbw 有 $n$ 个物品，编号从 $1～n$，他会告诉你 $m$ 个条件，每个条件包含两个数 $x,y$，表示第 $x$ 个物品和第 $y$ 个物品是相同的。

因为 zbw 特别赶时间，所以他保证每次给出的条件都是有用的，也就是说，每次给出的条件无法由之前的条件推导得来。

你需要回答有多少种不同的物品。

输入格式

第一行两个整数 $n$,$m$。

之后 $m$ 行，每行两个数 $x,y$，表示第 $x$ 个物品和第 $y$ 个物品是相同的。

输出格式

一个整数，不同物品的数量。

样例 #1

样例输入 #1

11 8 
1 2
4 3
5 4
1 3
5 6
7 10
5 10
8 9

样例输出 #1

3

提示

对于 $20\%$ 的数据，$n,m\le 10$。

对于 $40\%$ 的数据，$n,m\le 10^3$。

对于 $60\%$ 的数据，$n,m\le 10^5$。

对于 $80\%$ 的数据，$m\le 10^6$。

对于 $100\%$ 的数据，$1\le n\le 10^{18}$，$1\le m\le 10^7$。

代码如下：

#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>

int main()
{
	long long n, m;
	scanf("%lld%lld",&n,&m);
	
	printf("%lld\n",n - m);
} 

二、[Cnoi2020]光图

题目背景

简洁中蕴含着伟大。

Cirno 不经意地把一个内部完全反射的圆分成了 $12$ 等分，等分点分别记作 $A_0$, $A_1$, $A_2$, $?$ , $A_{11}$。

随后，她不经意地将一束光从一点发出，朝向另一点，重复，反射，迭代，便得到了一幅美妙的光图。

这一切都发生在不经意之间。

她不经意地发现了这一幕，并且不经意地记下了这个不经意的结论，又在某一刻不经意地回忆起。

幻想乡的每一天一切都是这么不以为意，多好的一天啊！

题目描述

Rumia 有一个单位圆，被分成 $n$ 等分，等分点分别记作 $A_0$, $A_1$, $A_2$, $?$ , $A_{n?1}$。

现在她从 $A_0$ 向 $A_p$ 发射一束光，经过 $k$ 次反射，到达了 $A_t$。

Rumia 想知道 $t$ 的值，由于 Cirno 并不想帮她，所以 Rumia 转而求助于你。

输入格式

一行，三个整数，$n,p,k$。

输出格式

一行，一个整数 $t$。

样例 #1

样例输入 #1

12 5 2

样例输出 #1

10

样例 #2

样例输入 #2

1000 342 3472844

样例输出 #2

648

提示

Sample1 解释

后置物理知识

• 连续曲线反射规律 : 入射光线与出射光线关于入射点在曲线上切线夹角相等。

数据范围约定

「本题采用捆绑测试」

• Subtask1( $80\%$ ) : $n,k\le 10^6$
• Subtask2( $20\%$ ) : $n,k\le 10^9$

对于 $100\%$ 的数据 : $0<p<n\le 10^9$, $0<k\le 10^9$。

后记

• Cirno 得到的光图就是传说中的十二芒星图。

代码如下：

#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>

int main()
{
	long long n, p, k;
	scanf("%lld%lld%lld",&n,&p,&k);
	
	long long num = (p*k)%n;
	printf("%lld\n",num);
} 

三、[EER1]苏联人

题目背景

题目名称是吸引你点进来的。

这是一道正常的题，和苏联没有任何关系。

题目描述

你在打 EE Round 1，发现第一题非常无聊。于是你不打了，去下国际象棋了。

结果你发现，由于神秘力量的影响，你的棋子只剩下若干黑色的战车，若干黑色的主教和一只白色的国王了。

由于你很无聊，所以你把一些黑色棋子放在了 $8\times 8$ 的棋盘上。

由于你很无聊，所以你想知道，国王放在哪些格子是安全的。换句话说，有哪些格子不会被战车和主教攻击到。当然，国王不能放在已经有棋子的地方。

为了防止你无聊透顶而不知道国际象棋的规则，这里给出以下提示（如果你知道规则那么可以跳过）：

国际象棋中，战车可以横向、竖向移动，且格数不受限制。但不能越过其他棋子。

如图，黄色的格子为战车能走到（攻击到）的格子。

国际象棋中，主教可以斜向移动，且格数不受限制。但不能越过其他棋子。

如图，黄色的格子为主教能走到（攻击到）的格子。

简单来说，如果当前位置到目标位置的直线上存在其他棋子，则可以称为“越过了其他棋子”。

如果目标位置是对方的棋子，那么移动到目标位置后，对方的棋子会被吃掉。

更进一步地，你要找的所有位置，必须满足没有黑色棋子能一步走到。

如果你还是没有读懂，可以结合样例进行理解。

输入格式

共 $8$ 行，每行 $8$ 个字符，表示棋盘的状态。

其中 . 表示空位，R 表示战车，B 表示主教。

输出格式

共 $8$ 行，每行 $8$ 个字符。若一个格子是可以放国王的，则输出 1，否则输出 0。

样例 #1

样例输入 #1

........
........
........
..B..R..
........
........
........
........

样例输出 #1

11111011
01110011
10101011
11000000
10101011
01110011
11111011
11111001

提示

对于 $100\%$ 的数据，保证只会出现 .，R，B 三种字符。

本题共有 $4$ 个子任务，每个子任务的限制如下：

子任务 $1$（$10$ 分）：保证只会出现 .。

子任务 $2$（$20$ 分）：保证只会出现一个 R 或一个 B（不同时出现）。

子任务 $3$（$30$ 分）：保证只有一个 .。

子任务 $4$（$40$ 分）：没有特殊限制。

代码如下：

#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>



char ch[8][8];
int ans[8][8];
int main()
{
    for(int i=0;i<8;i++) scanf("%s",ch[i]);//现将整个棋盘输入进去
    for(int i=0;i<8;i++)//遍历8行
    {
        for(int j=0;j<8;j++)//遍历8列
        {
            if(ch[i][j]=='R')//如果是战车
            {
                ans[i][j]=1;//先将自己站的位置标1
                for(int k=i-1;k>=0 && ch[k][j]=='.';k--) ans[k][j]=1;//这个战车的上方不能放国王，所以全都设为1
                for(int k=i+1;k<8 && ch[k][j]=='.';k++) ans[k][j]=1;//这个战车的下方也不能放国王，所以也全都设成1
                for(int k=j-1;k>=0 && ch[i][k]=='.';k--) ans[i][k]=1;//同理这个战车的z左边也不能放国王
                for(int k=j+1;k<8 && ch[i][k]=='.';k++) ans[i][k]=1;//同理这个战车的右边也不能放国王
            }
            else if(ch[i][j]=='B')//如果是主教
            {
                ans[i][j]=1;//先将自己的位置标1
                for(int k=i-1,l=j-1;k>=0 && l>=0 && ch[k][l]=='.';k--,l--) ans[k][l]=1;//左上方不能放国王
                for(int k=i+1,l=j+1;k<8 && l<8 && ch[k][l]=='.';k++,l++) ans[k][l]=1;//右下方也不能放国王
                for(int k=i-1,l=j+1;k>=0 && l<8 && ch[k][l]=='.';k--,l++) ans[k][l]=1;//右上方也不能放国王
                for(int k=i+1,l=j-1;k<8 && l>=0 && ch[k][l]=='.';k++,l--) ans[k][l]=1;//左下方也不能放国王
            }
        }
    }
    for(int i=0;i<8;i++)
    {
        for(int j=0;j<8;j++) printf("%d",!ans[i][j]);//因为上面不行的地方全取的是1，所以输出时取反即可
        puts("");
    }
    return 0;
} 

四、[USACO06OCT] Another Cow Number Game G

题目描述

奶牛们在玩一种数字游戏，Bessie 想让你帮她预测一下结果。游戏开始时，Bessie 将得到一个正整数 $N$。此时她的分数为 $0$。

奶牛们按照以下规则对 $N$ 进行变换：

• 如果 $N$ 是奇数，那么将它乘以 $3$ 后再加 $1$。
• 如果 $N$ 是偶数，那么将它除以 $2$。

数字每变换一次，Bessie 就得到 $1$ 分。当 $N=1$ 时，游戏结束。此时的分数就是她的最终得分。

输入格式

一行，一个整数 $N$。

输出格式

一行，一个整数，为 Bessie 的最终得分。

样例 #1

样例输入 #1

5

样例输出 #1

5

提示

【数据范围】

对于 $100\%$ 的数据，$1\le N\le 10^6$。

【样例说明】

当 $N$ 的初始值为 $5$ 时，游戏的过程如下：

Bessie 的最终得分为 $5$。

代码如下：

#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>

int main()
{
	long long n;
	scanf("%lld",&n);
	
	long long sum = 0;
	while(n != 1)
	{
		if(n %2 == 0)
		{
			n = n/2;
			sum++;
		}
		else if(n%2 != 0)
		{
			n = 3*n +1;
			sum++;
		}
		
	}
	
	printf("%lld\n",sum);
}

五、[COCI2014-2015#3] STROJOPIS

题目描述

正确的打字正成为文化的重要组成部分。如果你仍然没有使用所有的十根手指来打字，你必须重新学习打字——然后你会打字更快，感觉更舒适和愉快。

有很多网站教你正确打字。下图描述了基本原理：用同一个指针按所需的键是同一颜色的。黄色键需要用小指按下，蓝色键需要用无名指，绿色键需要用中指，红色键需要用食指。自然，左手按键盘的左侧（从 5、T、G、B 开始向左的键），右手按右侧（从 6、Y、H、N 开始向右的键），拇指负责空格。

您的任务是输出每根手指（拇指除外）正确输入给定字符串的分别按下的次数。

输入格式

仅一行一个字符串 $s$。字符串不包含空格，只包含上面图像中包含的字符。

输出格式

输出必须由八行组成，每行一个整数，表示从左到右观察到的每个手指的按键次数（拇指除外）。

样例 #1

样例输入 #1

AON=BOO;

样例输出 #1

1
0
0
1
1
0
3
2

样例 #2

样例输入 #2

PRINT'NY'[NASLA]

样例输出 #2

2
1
0
2
4
1
1
5

样例 #3

样例输入 #3

VIDI,KO,JE,DOSA

样例输出 #3

1
1
3
1
1
6
2 
0

提示

数据规模与约定

令 $|s|$ 表示输入字符串的长度，则对于 $100\%$ 的数据，有 $1\le |s|\le 50$。

代码如下：

#include<string.h>
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
int a[10];//8个手指，这里我用一个数组表示 
int main()
{
	char str[51];
	scanf("%s",&str);
	int len = strlen(str);
	
	for(int i = 0;i < len;i++)
	{
		if(str[i]=='1' || str[i]=='Q' || str[i]=='A' || str[i]=='Z')
			a[1]++;
		if(str[i]=='2' || str[i]=='W' || str[i]=='S' || str[i]=='X')
			a[2]++;
		if(str[i]=='3' || str[i]=='E' || str[i]=='D' || str[i]=='C')
			a[3]++;
		if(str[i]=='4' || str[i]=='R' || str[i]=='F' || str[i]=='V' || str[i]=='5' || str[i]=='T' || str[i]=='G' || str[i]=='B')
			a[4]++;
		if(str[i]=='6' || str[i]=='Y' || str[i]=='H' || str[i]=='N' || str[i]=='7' || str[i]=='U' || str[i]=='J' || str[i]=='M')
			a[5]++;
		if(str[i]=='8' || str[i]=='I' || str[i]=='K' || str[i]==',')
			a[6]++;
		if(str[i]=='9' || str[i]=='O' || str[i]=='L' || str[i]=='.')
			a[7]++;
		if(str[i]=='0' || str[i]=='P' || str[i]==';' || str[i]=='/' || str[i]=='-' || str[i]=='[' || str[i]==']' || str[i]=='=' || str[i]=='\'')
			a[8]++;
	}
	for(int i = 1;i <= 8;i++)//从左到右输出八个指头的答案就行 
		printf("%d\n",a[i]);
	return 0;
}