Ianwusb's Blog

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;
}

1 2	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")

解析

见代码

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;
}

1
2
3

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))

题目

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

请回忆石头剪刀布的游戏规则：两个人同时伸出手，分别出示石头（用 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")

1	print(input())

G.小苯的石子游戏

解析

博弈的定义：

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

标准表达式（normal form）：

设在有 ( $n$ ) 个参与者的博弈中，令 ( $S_i$ ) 表示参与者 ( $i$ ) 可选择的战略集合（战略空间），其中任意一个特定的战略用 ( $s_i^*$ ) 表示（$s_i^* \in S_i $）。当每个参与者都选定一个策略后，形成了博弈的一个战略组合 ( (s_1, s_2, \ldots, 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

#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")

Ianwusb's Blog

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

A.小红的签到题

解析

Code

B.判断闰年

解析

Code

C.[NOIP2010]数字统计

解析

Code

D.[ NOIP2017]图书管理员

解析

Code

E.最大公约数(lcm)

解析

Code

F. 简单的整除

解析

Code

I.悬崖

题目

Code

牛客513205243号提交的代码

砍个价沈提交的代码

J. 猜拳游戏

题目

Code

牛客513205243号提交的代码

砍个价沈提交的代码

G.小苯的石子游戏

解析

博弈的定义：

标准表达式（normal form）：

收益矩阵：

策略：

均衡：

巴什博弈（Bash Game）：

Code

埃拉托斯特尼筛法

A.小红的签到题

解析

Code

B.判断闰年

解析

Code

C.[NOIP2010]数字统计

解析

Code

D.[ NOIP2017]图书管理员

解析

Code

E.最大公约数(lcm)

解析

Code

F. 简单的整除

解析

Code

I.悬崖

题目

Code

牛客513205243号 提交的代码

砍个价沈 提交的代码

J. 猜拳游戏

题目

Code

牛客513205243号 提交的代码

砍个价沈 提交的代码

G.小苯的石子游戏

解析

博弈的定义：

标准表达式（normal form）：

收益矩阵：

策略：

均衡：

巴什博弈（Bash Game）：

Code

牛客513205243号提交的代码

砍个价沈提交的代码

牛客513205243号提交的代码

砍个价沈提交的代码