【题解】acwing第118场周赛

比赛题目链接

5140. 循环串

给定两个整数 $n,a$，请你用前 $a$ 个小写字母为循环节，构成一个无限长的循环字符串，然后输出该循环字符串的前 $n$ 个字符。

例如，当 $a=2$ 时，循环字符串为 ababab...，当 $a=3$ 时，循环字符串为 abcabcabc...。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据占一行，包含两个整数 $n,a$。

输出格式

每组数据输出一行结果，一个长度为 $n$ 的字符串，表示循环字符串的前 $n$ 个字符。

数据范围

前 $3$ 个测试点满足 $1 \le T \le 5$，$1 \le n \le 10$，$1 \le a \le 10$。
所有测试点满足 $1 \le T \le 1000$，$1 \le n \le 1000$，$1 \le a \le 26$。

输入样例：

4
7 3
6 1
6 4
5 2

输出样例：

aaaaaa
abcdab
ababa

算法（模拟）

没什么好说的，按题意模拟即可

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int T;
int main(){
	cin>>T;
	while(T--){
		int n,a;
		cin>>n>>a;
		for(int i=0;i<n;i++){
			cout<<(char)(i%a+'a');
		}
		cout<<endl;
	}
}

5141. 操作轮数

给定两个正整数 $a,b$（$a > b$）。

对两数执行以下操作，在每一轮操作中：

• 令较大数变为较大数减较小数之差，令较小数保持不变。（注意，如果两数相等，则任意指定其中一数为较大数即可。）

当两数之中至少有一个数变为 $0$ 时，操作停止。

请你计算，一共需要进行多少轮操作。

输入格式

共一行，包含两个整数 $a,b$。

输出格式

一个整数，表示所需进行的操作轮数。

数据范围

所有测试点满足 $1 \le b < a \le 10^{12}$。

输入样例1：

2 1

输出样例1：

2

输入样例2：

10 7

输出样例2：

6

输入样例3：

1000000000000 1

输出样例3：

1000000000000

算法1（暴力）

最开始一眼丁真写了暴力代码，吃了一发罚时，暴力的思路是模拟题意，这里给出代码

#include <bits/stdc++.h>
using namespace std;
int T;
int main(){
	long long  a,b,cnt=0;
	cin>>a>>b;
	while(a&&b){
		cnt++;
		if(a>b) a-=b;
		else b-=a;
	}
	cout<<cnt;
}

算法2（取模）

如果数据给了个$10^9$和$1$，就会tle，所以我们考虑优化，可以用取模的方式

#include <bits/stdc++.h>
using namespace std;
int T;
int main(){
	long long  a,b,cnt=0;
	cin>>a>>b;
	while(a&&b){
		if(a<b) swap(a,b);
		cnt+=a/b,a%=b;
	}
	cout<<cnt;
}

5142. 移动棋子

在一个无限大的二维平面中有一颗棋子。

初始时，棋子位于点 $(x_0,y_0)$。

现在，我们希望将棋子移动至点 $(x_1,y_1)$。

每次移动时，你需要首先选择一个与棋子距离恰好为 $r$ 的点，然后令棋子以该点为旋转中心旋转任意角度，使得棋子到达适当的位置。

请计算，为了使棋子到达最终目的地，至少需要进行多少次移动。

输入格式

共一行，包含 $5$ 个整数 $r,x_0,y_0,x_1,y_1$。

输出格式

一个整数，表示所需的最少移动次数。

数据范围

前 $3$ 个测试点满足 $1 \le r \le 10$，$-10 \le x_0,y_0,x_1,y_1 \le 10$。
所有测试点满足 $1 \le r \le 10^5$，$-10^5 \le x_0,y_0,x_1,y_1 \le 10^5$。

输入样例1：

2 0 0 0 4

输出样例1：

1

输入样例2：

1 1 1 4 4

输出样例2：

3

输入样例3：

4 5 6 5 6

输出样例3：

0

算法（人类智慧）

题目大意是把一个点挪到另一个点，挪动方式的是绕一个点以半径为$r$旋转。

我们知道，两点之间线段最短，所以给出代码（我不会证）

#include <bits/stdc++.h>
using namespace std;
double r,x,y,x2,y2;
int main(){
	cin>>r>>x>>y>>x2>>y2;
	double d=sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2));
	cout<<ceil(d/(2*r));
}