洛谷刷题C语言：I wanna a feasitor（化验器）、天才⑨与天才拆分、RIJEČI、王国比赛、MORTADELA

记录洛谷刷题C语言qaq

---

[WFOI - 02] I wanna a feasitor（化验器）

题目背景

比赛时在做什么？有没有空？可以来开 longlong 吗？

kid 一脸疑惑地看着 Elgo87，Elgo87 说，通关就告诉你 …

题目描述

kid 发现了一个函数 $f(x)$，它表示除 $x$ 本身之外，$x$ 的最大约数（$x$ 为大于 $1$ 正整数）。

下面是一些例子：

• $f(8)=4$，因为 $8$ 的约数有 $1,2,4,8$，除 $8$ 本身之外显然最大的约数为 $4$，所以 $f(8)=4$；
• $f(15)=5$，因为 $15$ 的约数有 $1,3,5,15$，除 $15$ 本身之外显然最大的约数为 $5$，所以 $f(15)=5$；

kid 还发现了两个数 $L,R$，你需要帮他求对于 $L\sim R$ 中的每一个数 $x$，$f(x)$ 的最大值，作为通关密码。

注意，$L\sim R$ 包括 $L$ 和 $R$。

你只需要告诉他答案，剩下的操作就交给 Elgo87 吧！

输入格式

一行两个整数 $L,R$，意义如题目描述。

输出格式

一行，表示对于 $L\sim R$ 中每个数 $x$，$f(x)$ 的最大值。

样例 #1

样例输入 #1

12 17
1

样例输出 #1

8
1

提示

【样例解释】

在 $12\sim 17$，也就是 $12,13,14,15,16,17$ 这几个数中，除这些数本身之外的最大因数分别是 $6,1,7,5,8,1$，故最大值为 $8$。

【数据范围】

本题采用 $\mathtt{Subtask}$ 捆绑测试。 即你需要通过一个 $\mathtt{Subtask}$ 中的所有测试点才能得到这部分的分数。

• $\text{Subtask \#0 (10pts)}$：$2\le L<R\le 100$；
• $\text{Subtask \#1 (30pts)}$：$2\le L<R\le 10^4$；
• $\text{Subtask \#2 (30pts)}$：$2\le L<R\le 10^9$，$R-L\le 10^6$；
• $\text{Subtask \#3 (30pts)}$：$2\le L<R\le 10^{18}$。

代码如下：

C语言

#include
#include
#include
#include 


long long l, r;
int main(){
	scanf ("%lld%lld", &l, &r);
	for (long long i = r; i >= l; i--){
		if (i % 2 == 0){
			printf ("%lld\n", i / 2);
			return 0;
		}
	}
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

尝试使用C++

#include 
using namespace std;

int main()
{
	long long a, b;
	cin >> a >> b;
	cout << b / 2;
	system("pause");

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

「Wdoi-5」天才⑨与天才拆分

题目背景

\kern{75pt}

萌萌琪露诺在寺子屋的教室里面见到了哆来咪·苏伊特。心怀好意的哆来咪告诉了她期末考试的题目，只要解出这些题目就能免于被慧音老师头槌。兴奋的琪露诺告别了哆来咪，猛然发现自己已经身处在期末考试的考场之上！但是琪露诺实在是太笨了，醒来就把哆来咪告诉她的题目忘得一干二净，只记得试卷上有大量的⑨。

现在琪露诺已经在考试啦，你可以使用⑨的妖精链接回答她的问题，以平复她忘记了考试答案的悲痛。你能帮帮她吗？

温馨提示：考试作弊是不对的哦。

题目描述

琪露诺定义一个十进制正整数为「$k$ 阶天才数」，当且仅当该整数的位数为 $k$ 的倍数，且每一个数位均为 $9$。例如，$9999$ 是 $2$ 阶天才数，而 $999$ 不是 $2$ 阶天才数，但是它是 $1$ 阶天才数，也是 $3$ 阶天才数。

琪露诺给定你 $t$ 个询问，每个询问有两个整数 $n$ 和 $k$，希望你能帮帮她，告诉她能不能把 $n$ 拆分成若干个 $k$ 阶天才数的和。

输入格式

• 第一行是一个整数 $t$，代表询问的个数。
• 接下来 $t$ 行，每行两个整数 $k$ 和 $n$，代表一个询问。

输出格式

• 输出共 $t$ 行。如果对应的询问答案是可以，输出一行一个字符串 aya，否则输出一行一个字符串 baka。

样例 #1

样例输入 #1

2
1 999
2 999
1
2
3

样例输出 #1

aya
baka
1
2

提示

本题共有 $20$ 个测试点，每个测试点 $5$ 分。最终分数为所有测试点分数之和。

KaTeX parse error: Expected a control sequence at position 6: \def{̲\n}{\text{无特殊限制…

对于全部数据，满足 $1\le t\le 10^3$，$1\le n_i\le 10^{18}$，$1\le k_i\le 10$。

代码如下：

C语言

#include
#include
#include
#include 

int main(){
	long long t,n,k;
	scanf("%lld",&t);
	while(t--){
		scanf("%lld %lld",&k,&n);
		long long x = 0;
		for(long long i = 1;i <= k;i++){
			x = x*10 + 9;
		}
		if(n % x != 0) puts("baka");
		else puts("aya");
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

尝试使用C++

#include 
using namespace std;

int main()
{
	long long t, n, k;
	cin >> t;
	while (t--)
	{
		cin >> k >> n;
		long long num = 0;
		for (long long i = 1; i <= k; i++)
		{
			num = num * 10 + 9;
		}
		if (n % num != 0)
			cout << "baka"<<endl;
		else
			cout << "aya"<<endl;
	}
	system("pause");

	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

[COCI2013-2014#3] RIJEČI

题目描述

一天，Mirko 发现了一个非常大的屏幕，这个屏幕上一开始只有一个字母 $\text{A}$。Mirko 在这个屏幕旁边找到了一个按钮。当他按一次时，屏幕上的字母变成了 $\text{B}$。随后他又按了若干次，屏幕上依次显示 $\text{BA}$、$\text{BAB}$、$\text{BABBA}$、……这时他才发现，每当他按一次按钮，屏幕上的字母 $\text{B}$ 变为 $\text{BA}$，而字母 $\text{A}$ 变为 $\text{B}$。

现在，Mirko 已经按了 $k$ 次按钮，他想知道屏幕上分别有多少个字母 $\text{A}$ 和字母 $\text{B}$。

输入格式

输入一个整数 $k$，表示 Mirko 按下按钮的次数。

输出格式

输出两个整数，以空格间隔，分别表示字母 $\text{A}$ 的个数和字母 $\text{B}$ 的个数。

样例 #1

样例输入 #1

1
1

样例输出 #1

0 1
1

样例 #2

样例输入 #2

4
1

样例输出 #2

2 3
1

样例 #3

样例输入 #3

10
1

样例输出 #3

34 55
1

提示

【数据范围与限制】

对于 $20\%$ 的数据，保证 $k⩽10$。
对于所有数据，$1⩽k⩽45$。

【题目来源】

本题来源自 COCI 2013-2014 CONTEST 3 T1 RIJEČI，按照原题数据配置，满分 $50$ 分。

由 Eason_AC 翻译整理提供。

代码如下：

C语言

#include
#include
#include
#include 

int main()
{
    int k, a[50];
    scanf("%d",&k);
    a[0] = 0;
    a[1] = 1;
    a[2] = 1;
    for (int i = 3;i <= k;i++)
        a[i] = a[i - 1] + a[i - 2];
    printf("%d %d",a[k-1],a[k]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

尝试使用C++

#include 
using namespace std;

int main()
{
    int k, a[50];
    cin >> k;
    a[0] = 0;
    a[1] = 1;
    a[2] = 1;
    for (int i = 3; i <= k; i++)
        a[i] = a[i - 1] + a[i - 2];
    cout << a[k - 1] << " " << a[k];

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

[NOI Online 2022 入门组] 王国比赛

题目背景

经过管理员的考虑，我们打算将民间数据单独存放在最后一个 Subtask 中。这些测试点分数均为 0 分，但是没有通过其中的任何测试点将会视为此题不通过。

民间数据提供者：@一扶苏一。

题目描述

智慧之王 Kri 统治着一座王国。

这天 Kri 决定举行一场比赛，来检验自己大臣的智慧。

比赛由 $n$ 道判断题组成，有 $m$ 位大臣参加。现在你已经知道了所有大臣的答题情况，但尚未拿到答案，于是你决定先行预测。

具体来说，对于第 $i$ 道题，有 $x$ 个大臣选对，$y$ 个大臣选错（显然有 $x+y=m$），如果 $x>y$，那么你预测这题答案为对，否则为错。为了方便，我们保证 $m$ 是奇数。

在统计完成后，你拿到了答案，你想知道通过你的预测方式你最后有几道题预测正确。

输入格式

第一行两个正整数 $n,m$，保证 $m$ 是奇数。

接下来 $m$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个整数代表第 $i$ 位大臣对第 $j$ 道题的答案，$1$ 表示他选对，$0$ 表示他选错。

接下来 $1$ 行 $n$ 个整数， 表示比赛答案，第 $i$ 个数 $b_i$ 若为 $1$ 表示第 $i$ 道题答案是对，若为 $0$ 表示答案是错。

输出格式

输出一个整数，表示你最后有几题预测正确。

样例 #1

样例输入 #1

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

样例输出 #1

2
1

样例 #2

样例输入 #2

6 5
1 0 1 1 1 0
0 1 0 1 1 1
0 0 1 0 1 0
1 0 1 0 1 0
0 1 0 1 0 0
1 0 1 0 1 0
1
2
3
4
5
6
7

样例输出 #2

4
1

样例 #3

样例输入 #3

见附件中的 kingdom3.in
1

样例输出 #3

见附件中的 kingdom3.out
1

提示

【样例 1 解释】

• 第一题 $x=1,y=2$ 你预测答案为错（即 $0$），实际答案为1，预测错误。
• 第二题 $x=2,y=1$ 你预测答案为对（即 $1$），实际答案为1，预测正确。
• 第三题 $x=2,y=1$ 你预测答案为对（即 $1$），实际答案为1，预测正确。

所以预测正确的题数为 $2$。

【数据范围】

对于 $20\%$ 的数据，$n\le 5$，$m=1$。

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

对于 $100\%$ 的数据，$1\le n\le 1000$，$1\le m\le 1000$，$m$ 为奇数。

代码如下：

C语言

#include
#include
#include
#include 



int read(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x;
}


int n, m, cnt[1000001], ans;

int main(){
 
    n = read(), m = read();
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            cnt[j] += read();
        }
    }
    for(int i = 1; i <= n; i++){
        ans += read()?(cnt[i]<<1>m):(cnt[i]<<1<m);
    }
    printf("%d\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

C++

#include 
using namespace std;



int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return x;
}


int n, m, cnt[1000001], ans;

int main() {

    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cnt[j] += read();
        }
    }
    for (int i = 1; i <= n; i++) {
        ans += read() ? (cnt[i] << 1 > m) : (cnt[i] << 1 < m);
    }
    printf("%d\n", ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

[COCI2012-2013#2] MORTADELA

题目背景

本题分值按 COCI 原题设置，满分 $50$。

题目描述

全国连锁超市（NSC）喜欢吹嘘它们的意式肉肠是全国最低的。

实际上，如果顾客打算在其他连锁超市里找到更便宜的肉肠，那么 NSC 会向其补上差价。

Matej 和 Filip 决定接受这个挑战。他们将会挨个走访 $N$ 家不同连锁店，来找到不仅比 NSC 便宜的熟香肠，而且在市场上最便宜的。如果他们成功了，他们就可以在他们学校附近的 NSC 分店买到最便宜的香肠。

NSC 希望没有人能找到更便宜的香肠，因为所有所有连锁超市（包括 NSC）都以一种复杂的方式表示香肠的价格：$X$ 元 $Y$ 克香肠。

请编写一个程序，给定 NSC 与其余 $N$ 家连锁店中的香肠价格，求 Matej 和 Filip 必须为靠近学校的 NSC 中的 $1000$ 克熟香肠支付的价格。

输入格式

第一行两个正整数 $X_{\text{NSC}}(1\le X_{\text{NSC}}\le 100)$ 和 $Y_{\text{NSC}}(1\le Y_{\text{NSC}}\le 10^3)$，表示 $X_{\text{NSC}}$ 是在 NSC 连锁店中 $Y_{\text{NSC}}$ 克香肠的价格。

第二行一个正整数 $N(1\le N\le 100)$，表示连锁店的数目（不包括 NSC）。

接下来 $N$ 行，每行两个正整数 $X_i,Y_i(X_i\le 100,Y_i\le 10^3)$，表示 $X_i$ 是在第 $i$ 家连锁店中 $Y_i$ 克香肠的价格。

输出格式

输出仅一行，一个实数，表示结果，保留 $2$ 位小数。

样例 #1

样例输入 #1

5 100
3
4 100
3 100
7 100
1
2
3
4
5

样例输出 #1

30.00
1

样例 #2

样例输入 #2

13 6
5
56 679
35 120
99 999
56 73
37 532
1
2
3
4
5
6
7

样例输出 #2

69.55
1

样例 #3

样例输入 #3

100 5
3
99 8
65 14
78 10
1
2
3
4
5

样例输出 #3

4642.86
1

代码如下：

C语言

#include
#include
#include
#include 

int main()
{
	double n, m;
	scanf("%lf%lf",&n,&m);
	
	int t;
	scanf("%d",&t);
	double sum = 1000/m*n;

	while(t--)
	{
		double a,b;
		scanf("%lf%lf",&a,&b);
		double num = 1000 / b*a;
		if(num <= sum)
		{
			sum = num;
		}
	}
	printf("%.2lf",sum);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

C++

#include 
#include
using namespace std;

int main()
{
	double n, m;
	cin >> n >> m;

	int t;
	cin >> t;
	double sum = 1000 / m * n;

	while (t--)
	{
		double a, b;
		cin >> a >> b;
		double num = 1000 / b * a;
		if (num <= sum)
		{
			sum = num;
		}
	}
	cout << fixed << setprecision(2) << sum<< endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26