题解|算法竞赛团队培训第一次考核

[TOC]

A.小红的签到题

解析

题目描述了一个情景，其中 ( a ) 是题目的总数，( b ) 是参赛人数，而 ( c ) 是所有人通过题目的总数。要找出最多有多少人“ak”，即通过了所有题目。

在这种情况下，如果每个人至少通过了一道题，那么最多可以通过 ( a * b ) 道题。但题目只告诉我们总共通过了 ( c ) 道题。所以，要找出最多有多少人通过了所有题目，我们可以将 ( c ) 除以 ( a )，因为每个人要“ak”就需要通过 ( a ) 道题。

为什么不需要计算余数呢？因为题目问的是最多有多少人“ak”，这意味着我们是在寻找一个整数解，即最多有多少完整地通过了所有题目的人。如果 ( c ) 不能被 ( a ) 整除，那么就意味着不可能有更多的人完全通过所有题目，因为余数代表的是不足以构成一个完整“ak”的人数。

例如，如果 ( c = 123 ) 且 ( a = 6 )，那么 ( 123 / 6 = 20 ) 余 3。这表示最多有 20 个人可以完全通过所有题目，因为剩下的 3 道题不足以让更多的人完成“ak”。

因此，直接用 ( c ) 除以 ( a ) 得到的整数部分就是答案。

Code

1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
	cout<<c/a<<endl;
	return 0;
}
1
2
a,b,c=map(int,input().split())
print(int(c/a))

B.判断闰年

解析

公历闰年的简单计算方法（符合以下条件之一的年份即为闰年）：

1.能被4整除而不能被100整除

2.能被400整除

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	if((n%4==0 && n%100!=0) || (n%400==0)){
		cout<<"yes"<<endl;
	}
	else{
		cout<<"no"<<endl;
	}
	return 0;
}
1
2
3
4
5
n=int(input())
if(((n%4==0) and (n%100!=0)) or (n%400==0)):
    print("yes")
else:
    print("no")

C.[NOIP2010]数字统计

解析

见代码

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

int main() {
	int L, R;
	cin >> L >> R;
	int countTwos = 0;  // 重命名变量以避免冲突
	
	for (int i = L; i <= R; ++i) {
		string num_str = to_string(i);
		countTwos += count(num_str.begin(), num_str.end(), '2');  
	}
	
	cout << countTwos << endl;
	return 0;
}

1
2
3
4
5
L,R=map(int,input().split())
count=0
for i in range(L,R+1):
    count+=str(i).count("2")
print(count)

D.[ NOIP2017]图书管理员

解析

见代码

Code

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
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int find(const vector<int>& library, const pair<int, string>& tupleX) {
    for (int i : library) {
        string num_str = to_string(i);
        if (num_str.length() >= tupleX.second.length()) {
            string suffix = num_str.substr(num_str.length() - tupleX.first);
            if (suffix == tupleX.second) {
                return i;
            }
        }
    }
    return -1;
}

int main() {
    int n, q;
    cin >> n >> q;
    
    vector<int> library(n);
    for (int i = 0; i < n; ++i) {
        cin >> library[i];
    }
    
    vector<pair<int, string>> needed(q);
    for (int i = 0; i < q; ++i) {
        int x;
        string s;
        cin >> x >> s;
        needed[i] = make_pair(x, s);
    }
    
    sort(library.begin(), library.end());
    
    for (const auto& i : needed) {
        cout << find(library, i) << 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
n,q=map(int,input().split())
library=[int(input()) for _ in range(n)]
#和下面代码是一个意思:
# for _ in range(n):
#     library.append(int(input()))
needed=[tuple(map(int,input().split())) for _ in range(q)]
#和下面代码是一个意思:
# for _ in range(q):
#     needed.append(tuple(map(int,input().split())))
#test:
# print(library)
# print(needed)
library.sort()
def find(tupleX):
    for i in library:
        a=-tupleX[0]
        if str(i)[a:]==str(tupleX[1]):
            return i
    return -1
for i in needed:
    print(find(i))

E.最大公约数(lcm)

解析

辗转相除法求最大公因数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
    if (a % b==0) return b;
    else return gcd(b, a % b);
}
int x, y; 
int main(){
	
	cin >> x >> y;
	cout << gcd(x, y);
	
	return 0;
}
1
2
3
4
5
6
7
8
def gcd(m,n):
    while m%n != 0:
        oldm = m
        oldn = n

        m = oldn
        n = oldm%oldn
    return n

最小公倍数（LCM）等于两个数的乘积除以它们的最大公因数（GCD）

Code

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;

int main()
{
	unsigned long long a,b;
    cin>>a>>b;
    cout<<lcm(a,b);
    return 0;
}
1
2
3
import math
a,b=map(int,input().split())
print(math.lcm(a,b))

F.简单的整除

解析

见代码

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
using namespace std;
int main() {
	int x;
	cin >> x;
	vector<int> li = {2, 3, 5, 7};
	
	for (int i : li) {
		if (x % i == 0) {
			cout << "YES" << endl;
			break;
		}
	}
	if (x % 2 != 0 && x % 3 != 0 && x % 5 != 0 && x % 7 != 0) {
		cout << "NO" << endl;
	}
	
	return 0;
}

1
2
3
4
5
6
7
8
x=int(input())
li=[2,3,5,7]
for i in li:
    if x%i==0:
        print("YES")
        break
else:
    print("NO")

I.悬崖

题目

小沙被困在两个巨大的墙壁之中快要被压死了，但是两个墙壁中间就是万丈悬崖，小沙想要多活一会，他脚底下有一个非常强大的弹跳鞋，每一次跳跃可以使他向着对面的墙壁飞行x米，但是他必须要踩上墙壁才能进行下一次跳跃，现已知两个墙壁中间间隔n米，并且每次跳跃两个墙壁之间的距离会减少1米，也就是说小沙在n秒后就会被压死，如果不考虑跳跃期间墙壁的移动，请问小沙最多能跳(飞)多少米。

两面墙壁都没有什么物品可以让小沙能够抓住从而挂在墙壁上，所以小沙要保证一直的跳跃才能不摔下悬崖

说明：小沙第一次跳跃两米，到对面墙壁，然后两个墙壁的距离变成1米，小沙继续跳到对面墙壁（此时虽然两个墙壁之间只有1米，但是小沙还是可以跳跃两米）例如：

img

可以看到虽然墙壁之间的距离只有一米，但是小沙还是可以跳两米远

Code

牛客513205243号 提交的代码

1
2
3
4
5
6
7
8
9
10
11
#include<iostream>
using namespace std;
int main(){
	long long x, n;
	cin >> x >> n;
	if(x>=n)
		cout << n * x;
	else 
		cout << x ;
	return 0;
}

砍个价沈 提交的代码

1
2
3
4
5
x,n=map(int,input().split())
if x>=n:
    print(int(x*n))
else:
    print(int(x))

J.猜拳游戏

题目

你正在与长途玩石头剪刀布的猜拳游戏。

请回忆石头剪刀布的游戏规则：两个人同时伸出手，分别出示石头（用 shitou 表示）、剪刀（用 jiandao 表示）或布（用 bu 表示）的手势。石头胜剪刀，剪刀胜布，布胜石头。如果两个人出示的手势相同，则是平局，需要重新进行游戏。

在开始游戏之前，长途会告诉你他要出石头、剪刀还是布。

然而实际上，长途是在欺骗你。他认为你会相信他的话，并且认为你一定会根据他说的话选择能战胜他的手势（例如，他说他会出石头，他便认为你会出布）。

所以最终，长途不会按照他告诉你的手势出拳，而是选择自己所认为一定能战胜你的手势。

现在你已经看透了他的小心思。请问，在知道他告诉你他要出什么手势的情况下，你应该出什么手势才能取胜？

Code

牛客513205243号 提交的代码

1
2
3
4
5
6
7
#include<stdio.h>
int main(){
	char n[100];
	scanf("%s",&n);
	printf("%s",n);
	return 0;
}

砍个价沈 提交的代码

1
2
3
4
5
6
7
i=str(input())
if i=="shitou":
    print("shitou")
elif i=="jiandao":
    print("jiandao")
else:
    print("bu")
1
print(input())

G.小苯的石子游戏

解析

博弈的定义：

博弈的基本要素包括参与人（players）、行动（actions）、信息（information）、策略（strategies）、收益（payoffs）和均衡（equilibria）。

标准表达式（normal form）：

设在有 ( \(n\) ) 个参与者的博弈中，令 ( \(S_i\) ) 表示参与者 ( \(i\) ) 可选择的战略集合（战略空间），其中任意一个特定的战略用 ( \(s_i^*\) ) 表示（$s_i^* S_i $）。当每个参与者都选定一个策略后，形成了博弈的一个战略组合 ( (s_1, s_2, , s_n) )。令 ( \(u_i\) ) 表示第 ( \(i\) ) 个参与者选择对应策略后的收益函数。由此可定义博弈的标准表达式：( \(G = \{S_1, \ldots, S_n, u_1, \ldots, u_n\}\) )。

收益矩阵：

两人博弈的标准表达式通常可以使用收益矩阵来表示。例如，经典的囚徒困境问题。两个犯罪嫌疑人被逮捕并被分别隔离审问，他们不同的行动将带来不同的后果。如果两人都不坦白（沉默），将被判入狱1个月；如果双方都坦白（招认），两人都将判处6个月；如果一人招认而另一人拒不坦白，则招认一方将马上释放，而不坦白的另一人将判处9个月。两人博弈的收益矩阵可表示为如下形式，其中每一单元格有两个数字，分别表示囚徒1和囚徒2的收益： 囚徒困境

策略：

参与人关于其行动的完备集合，即考虑每一种可预见情况下选择的行动，即使那种情况出现不一定会出现。例如，如果参与人在1989年自杀，他的策略里也应当包括如果他在1990年还活着应该采取的对应行动。 策略和行动是有区别的，而在一些简单的博弈中，两者的表现可能是一致的，如上述的囚徒困境中博弈双方的策略和行动可选集都是 (\(\{沉默, 招认\}\))。

均衡：

由博弈中的 ( n ) 个参与人选取的最佳策略所组成的一个策略组合 ( \(s^* = (s_1^*, \ldots, s_n^*)\) )。

巴什博弈（Bash Game）：

有\(n\) 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取 \(m\) 个（\(m < n\) ）。最后取光者得胜。 分析： 显然，如果 ( \(n = m + 1\) )，那么由于一次最多只能取 ( \(m\) ) 个物品，所以无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，故后者必然取胜。根据这样的规律，我们发现了如何取胜的法则。 如果 ( \(n = (m + 1)r + s\) ) r 为任意自然数，( \(0 \leq s \leq m\) )，那么先取者首先拿走 ( \(s\) ) 个物品，接下来若后取者拿走 ( \(k\) )（( \(1 \leq k \leq m\) )）个，那么先取者再拿走 ( \(m + 1 - k\) ) 个，结果剩下 ( \((m + 1) \times (r - 1)\) ) 个，以后都保持这样的取法，那么后取者最终会面临 ( \(m + 1\) ) 的局面，而先取者则必然获胜。总之，要保持给对手留下 ( \(m + 1\) ) 的倍数，最后就一定能获胜。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
void solve() {
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	} 
	// sort(a.begin() + 1, a.end()); // 题目已经保证a有序，可以不写这句
	int s1 = 0, s2 = 0;
	int f = 0;
	for(int i = n; i; i--) {
		if(!f) s1 += a[i];
		else s2 += a[i];
		f ^= 1;
	}
	if(s1 > s2) {
		cout << "Alice" << endl;
	}
	else {
		cout << "Bob" << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
t=int(input())
for _ in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    #player=["Alice","Bob"]
    player=[0,0]
    count=0
    while a!=[]:
        player[count%2]+=a.pop(-1)
        count+=1
    if player[0]>player[1]:
        print("Alice")
    else:
        print("Bob")
题解|算法竞赛团队培训第一次考核
http://example.com/2024/10/27/题解-算法竞赛团队培训第一次考核/
作者
Ianwusb
发布于
2024年10月27日
许可协议