题解 | 算法竞赛团队培训第一次考核
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
#include<iostream>
using namespace std;
int main(){
int a,b,c;
cin>>a>>b>>c;
cout<<c/a<<endl;
return 0;
}
a,b,c=map(int,input().split())
print(int(c/a))
B.判断闰年
解析
公历闰年的简单计算方法（符合以下条件之一的年份即为闰年）：
1.能被4整除而不能被100整除
2.能被400整除
Code
#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;
}
n=int(input())
if(((n%4==0) and (n%100!=0)) or (n%400==0)):
print("yes")
else:
print("no")
C.[NOIP2010]数字统计
解析
见代码
Code
#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;
}
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
#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;
}
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)
解析
辗转相除法求最大公因数：
#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;
}
def gcd(m,n):
while m%n != 0:
oldm = m
oldn = n
m = oldn
n = oldm%oldn
return n
最小公倍数（LCM）等于两个数的乘积除以它们的最大公因数（GCD）
Code
#include <bits/stdc++.h>
using namespace std;
int main()
{
unsigned long long a,b;
cin>>a>>b;
cout<<lcm(a,b);
return 0;
}
import math
a,b=map(int,input().split())
print(math.lcm(a,b))
F. 简单的整除
解析
见代码
Code
#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;
}
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米，但是小沙还是可以跳跃两米）例如：
可以看到虽然墙壁之间的距离只有一米，但是小沙还是可以跳两米远
Code
牛客513205243号 提交的代码
#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;
}
砍个价沈 提交的代码
x,n=map(int,input().split())
if x>=n:
print(int(x*n))
else:
print(int(x))
J. 猜拳游戏
题目
你正在与长途玩石头剪刀布的猜拳游戏。
请回忆石头剪刀布的游戏规则：两个人同时伸出手，分别出示石头（用 shitou 表示）、剪刀（用 jiandao 表示）或布（用 bu 表示）的手势。石头胜剪刀，剪刀胜布，布胜石头。如果两个人出示的手势相同，则是平局，需要重新进行游戏。
在开始游戏之前，长途会告诉你他要出石头、剪刀还是布。
然而实际上，长途是在欺骗你。他认为你会相信他的话，并且认为你一定会根据他说的话选择能战胜他的手势（例如，他说他会出石头，他便认为你会出布）。
所以最终，长途不会按照他告诉你的手势出拳，而是选择自己所认为一定能战胜你的手势。
现在你已经看透了他的小心思。请问，在知道他告诉你他要出什么手势的情况下，你应该出什么手势才能取胜？
Code
牛客513205243号 提交的代码
#include<stdio.h>
int main(){
char n[100];
scanf("%s",&n);
printf("%s",n);
return 0;
}
砍个价沈 提交的代码
i=str(input())
if i=="shitou":
print("shitou")
elif i=="jiandao":
print("jiandao")
else:
print("bu")
print(input())
G.小苯的石子游戏
解析
博弈的定义：
博弈的基本要素包括参与人（players）、行动（actions）、信息（information）、策略（strategies）、收益（payoffs）和均衡（equilibria）。
标准表达式（normal form）：
设在有 ( ) 个参与者的博弈中，令 (
) 表示参与者 (
) 可选择的战略集合（战略空间），其中任意一个特定的战略用 (
) 表示（
）。当每个参与者都选定一个策略后，形成了博弈的一个战略组合 ( (s_1, s_2, \ldots, s_n) )。令 (
) 表示第 (
) 个参与者选择对应策略后的收益函数。由此可定义博弈的标准表达式：(
)。
收益矩阵：
两人博弈的标准表达式通常可以使用收益矩阵来表示。例如，经典的囚徒困境问题。两个犯罪嫌疑人被逮捕并被分别隔离审问，他们不同的行动将带来不同的后果。如果两人都不坦白（沉默），将被判入狱1个月；如果双方都坦白（招认），两人都将判处6个月；如果一人招认而另一人拒不坦白，则招认一方将马上释放，而不坦白的另一人将判处9个月。两人博弈的收益矩阵可表示为如下形式，其中每一单元格有两个数字，分别表示囚徒1和囚徒2的收益：
策略：
参与人关于其行动的完备集合，即考虑每一种可预见情况下选择的行动，即使那种情况出现不一定会出现。例如，如果参与人在1989年自杀，他的策略里也应当包括如果他在1990年还活着应该采取的对应行动。
策略和行动是有区别的，而在一些简单的博弈中，两者的表现可能是一致的，如上述的囚徒困境中博弈双方的策略和行动可选集都是 ()。
均衡：
由博弈中的 ( n ) 个参与人选取的最佳策略所组成的一个策略组合 ( )。
巴什博弈（Bash Game）：
有 个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取
个（
）。最后取光者得胜。
分析：
显然，如果 (
)，那么由于一次最多只能取 (
) 个物品，所以无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，故后者必然取胜。根据这样的规律，我们发现了如何取胜的法则。
如果 (
) r 为任意自然数，(
)，那么先取者首先拿走 (
) 个物品，接下来若后取者拿走 (
)（(
)）个，那么先取者再拿走 (
) 个，结果剩下 (
) 个，以后都保持这样的取法，那么后取者最终会面临 (
) 的局面，而先取者则必然获胜。总之，要保持给对手留下 (
) 的倍数，最后就一定能获胜。
Code
#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;
}
}
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")
H.小红勇闯地下城
解析
【【算法】最短路径查找—Dijkstra算法】 https://www.bilibili.com/video/BV1zz4y1m7Nq/?share_source=copy_web&vd_source=440c7ec5d64e62c0d02675282b15de02
Code
#include <bits/stdc++.h>
#define int long long //将所有的int替换成long long 防止爆
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
void dijkstra(int n, int m, int u, int v, vector<string> &mp, vector< vector<int> > &d, vector< vector<bool> > &st) // 对地图跑dijkstra算法
{
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> q; // 存储三个变量的优先队列
q.push({0, u, v});
// 第一个表示(u, v)到当前位置的当前最短距离为 0
// 第二个和第三个变量表示当前位置的行和列
// 从(u, v)开始遍历地图
st[u][v] = true; // 将(u, v)标记为已来过
d[u][v] = 0; // (u, v)到(u, v)的最短距离为 0
while(q.size()) // 如果优先队列不为空
{
auto [dis, x, y] = q.top(); // 取出队头
q.pop(); // 弹出队头
for(int i = 0; i < 4; i++) // 移动
{
int tx = x + dx[i], ty = y + dy[i]; // 移动后的位置
if(tx >= 0 && tx < n && ty >= 0 && ty < m && !st[tx][ty]) // 移动后的位置没来过且合法
{
st[tx][ty] = true; // 将移动后的位置标记为已来过
d[tx][ty] = min(d[tx][ty], d[x][y] + (mp[tx][ty] - '0')); // 更新最短距离
q.push({d[tx][ty], tx, ty}); // 加入优先队列
}
}
}
}
void solve()
{
int q;
cin >> q;
while(q--)
{
int n, m, h;
cin >> n >> m >> h;
vector<string> mp(n); // 存储地图
vector< vector<int> > d(n, vector<int>(m, INF)); // 记录从(u, v)到(i, j)的最短距离
vector< vector<bool> > st(n, vector<bool>(m, false)); // 标记当前位置有没有来过
for(int i = 0; i < n; i++) // 读入地图
cin >> mp[i];
int u, v, x, y;
for(int i = 0; i < n; i++) // 找到起点和终点
{
for(int j = 0; j < m; j++)
{
if(mp[i][j] == 'S') // S 为起点
{
u = i;
v = j;
mp[i][j] = '0'; // 起点没有怪，故此处为 0
}
if(mp[i][j] == 'T') // T 为终点
{
x = i;
y = j;
mp[i][j] = '0'; // 终点没有怪，故此处为 0
}
}
}
dijkstra(n, m, u, v, mp, d, st); // 跑一遍最短路
// 如果最低血量消耗 大于等于 已有血量，则无法安全到达终点
if(d[x][y] >= h) cout << "No" << endl;
else cout << "Yes" << endl;
}
}
signed main()
{
int T = 1;
// cin >> T; // 根据具体情况注释
while(T--)
solve();
return 0;
}
import heapq
from typing import List, Tuple
# 定义方向数组
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
# Dijkstra算法实现
def dijkstra(n, m, u, v, mp, d, st):
# 使用heapq作为优先队列
q = []
heapq.heappush(q, (0, u, v)) # 初始节点的距离是0
st[u][v] = True
d[u][v] = 0
while q:
dis, x, y = heapq.heappop(q)
for i in range(4):
tx, ty = x + dx[i], y + dy[i]
if 0 <= tx < n and 0 <= ty < m and not st[tx][ty]:
st[tx][ty] = True
new_dis = d[x][y] + (int(mp[tx][ty]) - int('0'))
if new_dis < d[tx][ty]:
d[tx][ty] = new_dis
heapq.heappush(q, (new_dis, tx, ty))
# 主解决问题函数
def solve():
q = int(input())
for _ in range(q):
n, m, h = map(int, input().split())
mp = [input() for _ in range(n)]
d = [[float('inf')] * m for _ in range(n)]
st = [[False] * m for _ in range(n)]
u, v, x, y = None, None, None, None
for i in range(n):
for j in range(m):
if mp[i][j] == 'S':
u, v = i, j
mp[i] = mp[i][:j] + '0' + mp[i][j + 1:] # 将起点标记为'0'
elif mp[i][j] == 'T':
x, y = i, j
mp[i] = mp[i][:j] + '0' + mp[i][j + 1:] # 将终点标记为'0'
dijkstra(n, m, u, v, mp, d, st)
if d[x][y] >= h:
print("No")
else:
print("Yes")
# 主函数入口
if __name__ == "__main__":
T = 1
# T = int(input()) # 如果需要处理多个测试用例，可以取消注释此行
for _ in range(T):
solve()
京公网安备 11010502036488号