上计会青少年算法竞赛3月月赛

3月月赛丙组题 https://iai.sh.cn/contest/3

打鱼还是晒网

• 5天一个周期，如果 n 除以5的余数是4或者0，就是晒网；否则就是打鱼

• 注意：任何正整数除以 r 的余数的范围是 0 ~ (r-1)

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	
	if (n%5==0 || n%5==4) cout << "Lying" << endl;
	else cout << "Fishing" << endl;
	
	return 0;
}

数字加密

• 这题方法很多，可以把输入当做一个整型变量，也可以把输入当做字符串

整型变量

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	
	cout << 9 - n%10;
	cout << 9 - n/10%10;
	cout << 9 - n/100%10;
	cout << 9 - n/1000;

	return 0;
}

字符数组

#include <iostream>
using namespace std;

int main() {
	char c[4];
	cin >> c;
	
	for (int i = 3; i >= 0; i--) {
		c[i] = char('0' + '9' - c[i]);
		cout << c[i]; 
	}
	
	return 0;
}

双质数

• 没什么好说的，判断质数的模板题。一定要把判断质数的函数熟练默写出来
• 主程序要枚举的数字不超过$2\ast 10^5$。判断质数的代码时间复杂度是$O(\sqrt{n})$，表面上看会超时，但大部分数字是合数，很快就会找出因子，函数中实际循环次数很少
• 掌握这道题里布尔变量的用法：
  • 设置布尔变量 flag，并初始化为“真”
  • 在循环过程中，如果某条件成立，则将 flag 修改为“假”
  • 循环结束后，如果 flag 仍然为假，就说明循环里的条件没有成立过

#include <iostream>
using namespace std;

bool isPrime(int x) {
	if (x < 2) return false;
	for (int i = 2; i <= x/i; i ++ ) {
		if (x % i == 0) {
			return false;
		}
	}
	return true;
}

int main() {
	int a, b;
	cin >> a >> b;
	
	bool flag = true;
	
	for (int i = a; i <= b; i ++ ) {
		if (isPrime(i) && isPrime(i/10)) {
			flag = false;
			cout << i << endl;
		}
	}
		
	if (flag) cout << "None" << endl;
	
	return 0;
}

连乘问题

• 很多同学会先用循环计算$a_1\ast a_2\ast a_3...a_n\%10000$，再除以$a_i$，这样计算的结果是不对的，我们来看下面的例子
  • $\frac{123\ast 456}{12}\%10000=4674$
  • $\frac{123\ast 456\%10000}{12}=507$
• 观察下式，我们可以得出第一个方法：
  • $从第1项循环到第i-1项$
  • $再从第i+1项循环到第n$项
  • $由于题目要计算A_1到A_n，时间复杂度是O(n^2)$，适用于前60%的数据，该代码可以得到60分
    $$\begin{array}{rl}{A}_i& =\frac{a_1\ast a_2\ast ...\ast a_n}{a_i}\%10000\\ & =(a_1\ast a_2\ast ...\ast a_{i-1})\ast (a_{i+1}\ast a_{i+2}\ast ...\ast a_n)\%10000\end{array}$$

#include <cstdio>
#include <iostream>
using namespace std;

const int N = 1e5+10, mod = 1e4;
int n, a[N];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i];
	}
	
	for (int i = 1; i <= n; i ++ ) {
		int ans = 1;
		for (int j = 1; j < i; j ++ ) {
			ans = (ans * a[j]) % mod;
		}
		for (int j = i + 1; j <= n; j ++ ) {
			ans = (ans * a[j]) % mod;
		}
		cout << ans << endl;
	}

	return 0;
}

• 对于另外40%的数据，$n的上限是10^5$，不能用嵌套循环求解；我们可以预处理出前缀积与后缀积，再通过前缀积与后缀积计算$A_1到A_n$，时间复杂度是$O(n)$，可以得到满分代码
  • $前缀积的第i项：front[i]=front[i-1]\ast a[i]$
  • $后缀积的第i项：back[i]=back[i+1]\ast a[i]$
  • 例如数列3 1 4 1 5 9 2 6中
    – 前缀积：3，3，12，12，60，540，1080，6480
    – 后缀积：6480，2160，2160，540，540，108，12，6
    $$\begin{array}{rl}{A}_i& =\frac{a_1\ast a_2\ast ...\ast a_n}{a_i}\%10000\\ & =(a_1\ast a_2\ast ...\ast a_{i-1})\ast (a_{i+1}\ast a_{i+2}\ast ...\ast a_n)\%10000\\ & =front[i-1]\ast back[i+1]\%10000\end{array}$$

#include <cstdio>
#include <iostream>
using namespace std;

const int N = 1e5+10, mod = 1e4;
int n, a[N], front[N], back[N];

int main() {
	cin >> n;
	
	for (int i = 1; i <= n; i ++ ) {
		cin >> a[i];
	}
	
	front[0] = 1;
	for (int i = 1; i <= n; i ++ ) {
		front[i] = (front[i-1] * a[i]) % mod;
	}
	back[n+1] = 1;
	for (int i = n; i >= 1; i -- ) {
		back[i] = (back[i+1] * a[i]) % mod;
	}
	
	for (int i = 1; i <= n; i ++ ) {
		int ans = 1;
		ans = front[i-1] * back[i+1] % mod;
		cout << ans << endl;
	}

	return 0;
}

救援争先

• 把出发时间和到达时间转化为距离00:00的分钟数，接下来排序就可以了
• 未学过结构体和sort函数的同学看这段代码

#include <cstdio>
#include <iostream>
using namespace std;

int n, depart[1005], arrive[1005], id[1005];

int main() {
	cin >> n;
	
	int x, y;
	char ch;
	for (int i = 1; i <= n; i ++ ) {
		cin >> x >> ch >> y;
		depart[i] = x * 60 + y;
		
		cin >> x >> ch >> y;
		arrive[i] = depart[i] + x * 60 + y;
		
		id[i] = i;
	}

	for (int i = 1; i < n; i ++ ) {
		int k = i;
		for (int j = k + 1; j <= n; j ++ ) {
			if (arrive[j] < arrive[k]) k = j;
			else if (arrive[j] == arrive[k]) {
				if (depart[j] < depart[k]) k = j;
				else if (depart[j] == depart[k]) {
					if (id[j] < id[k]) k = j;
				}
			}
		}
		swap(depart[k], depart[i]);
		swap(arrive[k], arrive[i]);
		swap(id[k], id[i]);
	}

	for (int i = 1; i <= n; i ++ ) cout << id[i] << endl;

	return 0;
}

• 学过结构体和sort函数的同学看这段代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int n;
struct team{
	int depart, arrive, id;
}t[1005];

bool cmp(team a, team b) {
	if (a.arrive < b.arrive) return true;
	if (a.arrive == b.arrive) {
		if (a.depart < b.depart) return true;
		if (a.depart == b.depart) {
			if (a.id < b.id) return true;			
		}
	}
	return false;
}

int main() {
	cin >> n;
	
	int x, y;
	char ch;
	for (int i = 1; i <= n; i ++ ) {
		cin >> x >> ch >> y;
		t[i].depart = x * 60 + y;
		
		cin >> x >> ch >> y;
		t[i].arrive = t[i].depart + x * 60 + y;
		
		t[i].id = i;
	}

	sort(t+1, t+1+n, cmp);

	for (int i = 1; i <= n; i ++ ) cout << t[i].id << endl;

	return 0;
}

最后

以上就是欣慰洋葱为你收集整理的上计会青少年算法竞赛3月月赛的全部内容，希望文章能够帮你解决上计会青少年算法竞赛3月月赛所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。