- #A 求余
- #B 双阶乘
- #C 格点
- 朴素枚举
- 稍微优化
- #D 整数分解
- 排列组合
- 动态规划
- 组合数
- #E 城邦
- 最小树生成
- Kruskal
- Prim
- 贪心 + Trie
- #F 特殊年份
- 朴素解法
- BCD码
- #G 小平方
- #H 完全平方数
- 睡觉
第一场最后一题做自闭了，换场子了
#A 求余
本题总分： 5 5 5 分
问题描述
在 C / C + + / J a v a / P y t h o n mathrm{C/C++/Java/Python} C/C++/Java/Python 等语言中，使用 % mathrm{%} % 表示求余，请问 2021 % 20 mathrm{2021%20} 2021%20 的值是多少？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
1
唉
#B 双阶乘
本题总分： 5 5 5 分
问题描述
一个正整数的双阶乘，表示不超过这个正整数且与它有相同奇偶性的所有正整数乘积。
n
n
n 的双阶乘用
n
!
!
n!!
n!! 表示。
例如：
3
!
!
=
3
×
1
=
3
3!! = 3 × 1 = 3
3!!=3×1=3。
8
!
!
=
8
×
6
×
4
×
2
=
384
8!! = 8 × 6 × 4 × 2 = 384
8!!=8×6×4×2=384。
11
!
!
=
11
×
9
×
7
×
5
×
3
×
1
=
10395
11!! = 11 × 9 × 7 × 5 × 3 × 1 = 10395
11!!=11×9×7×5×3×1=10395。
请问，
2021
!
!
2021!!
2021!! 的最后
5
5
5 位（这里指十进制位）是多少？
注意：
2021
!
!
=
2021
×
2019
×
⋅
⋅
⋅
×
5
×
3
×
1
2021!! = 2021 × 2019 × · · · × 5 × 3 × 1
2021!!=2021×2019×⋅⋅⋅×5×3×1。
提示：建议使用计算机编程解决问题。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
59375
calcCode
public class Test {
public static void main(String[] args) { new Test().run(); }
void run() {
int n = 2021 + 2, ans = 1;
while (n > 1)
ans = (ans * (n -= 2)) % 100000;
System.out.println(ans);
}
}
( a × b ) % p = ( a % p × b % p ) % p (a × b) % p = (a % p × b % p) % p (a×b) %p=(a % p×b % p) %p， p ∈ Z p in mathbb{Z} p∈Z
没啥好讲的。
#C 格点
本题总分： 10 10 10 分
问题描述
如果一个点
(
x
,
y
)
(x, y)
(x,y) 的两维坐标都是整数，即
x
∈
Z
x ∈ Z
x∈Z 且
y
∈
Z
y ∈ Z
y∈Z，则称这个点为一个格点。
如果一个点
(
x
,
y
)
(x, y)
(x,y) 的两维坐标都是正数，即
x
>
0
x > 0
x>0 且
y
>
0
y > 0
y>0，则称这个点在第一象限。
请问在第一象限的格点中，有多少个点
(
x
,
y
)
(x, y)
(x,y) 的两维坐标乘积不超过
2021
2021
2021，即
x
⋅
y
≤
2021
x · y ≤ 2021
x⋅y≤2021。
提示：建议使用计算机编程解决问题。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
15698
朴素枚举
public class Test {
public static void main(String[] args) { new Test().run(); }
int n = 2021;
void run() {
int ans = 0;
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
if (x * y <= n) ans++;
System.out.println(ans);
}
}
不谈。
稍微优化
题目解读一下就是多少个正整数二元组的乘积等于 k k k， k ∈ [ 1 , 2021 ] k in [1,2021] k∈[1,2021]，我们可以用欧拉筛线性的分解出区间内每个数的质因数，用其质数计算出组合方案的种数。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Test {
public static void main(String[] args) { new Test().run(); }
int n = 2021, ans = 0;
void run() {
Map[] nums = new Map[n + 1];
nums[1] = new HashMap(){{ put(0, 0); }};
List primes = new ArrayList();
for (int i = 2; i <= n; i++) {
if (nums[i] == null) {
(nums[i] = new HashMap()).put(i, 1);
primes.add(i);
}
for (int p : primes) {
if (i * p > n) break;
nums[i * p] = new HashMap(nums[i]);
nums[i * p].put(p, nums[i].getOrDefault(p, 0) + 1);
if (i % p == 0)break;
}
}
for (int i = 1; i <= n; i++) {
int count = 1;
for (int k : nums[i].values())
count *= k + 1;
ans += count;
}
System.out.println(ans);
}
}
要是以后出个题，计算 20222222 的格点，记得给我打钱。
#D 整数分解
本题总分： 10 10 10 分
问题描述
将
3
3
3 分解成两个正整数的和，有两种分解方法，分别是
3
=
1
+
2
3 = 1 + 2
3=1+2 和
3
=
2
+
1
3 = 2 + 1
3=2+1。注意顺序不同算不同的方法。
将
5
5
5 分解成三个正整数的和，有
6
6
6 种分解方法，它们是
1
+
1
+
3
=
1
+
2
+
2
=
1
+
3
+
1
=
2
+
1
+
2
=
2
+
2
+
1
=
3
+
1
+
1
1 + 1 + 3 = 1 + 2 + 2 = 1 + 3 + 1 = 2 + 1 + 2 = 2 + 2 + 1 = 3 + 1 + 1
1+1+3=1+2+2=1+3+1=2+1+2=2+2+1=3+1+1。
请问，将
2021
2021
2021 分解成五个正整数的和，有多少种分解方法？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
691677274345
排列组合
O ( n 5 ) O(n^{5}) O(n5) 指定是不行了，不过这里可以将算式分解成 k + ( a 1 + a 2 ) + ( b 1 + b 2 ) k + (a_1 + a_2) + (b_1 + b_2) k+(a1+a2)+(b1+b2) 三部分， 然后枚举每一个 k k k，暴力的求出 ( a 1 + a 2 ) (a_1 + a_2) (a1+a2)、 ( b 1 + b 2 ) (b_1 + b_2) (b1+b2) 可能的组合数，并将它们累加。
public class Test {
public static void main(String[] args) { new Test().run(); }
int n = 2021;
void run() {
long ans = 0;
for (int k = 1, a, b; k <= n - 2 - 2; k++) {
for (a = 2, b = n - 2 - k; b >= 2; a++, b--)
ans += (a - 1) * (b - 1);
}
System.out.println(ans);
}
}
当然也可以推一下组合公式，
有问题，将 N N N 分解成 k k k 个无序的正整数之和， N ≥ k N ge k N≥k，求方案数 A ( N , k ) A(N,k) A(N,k)。
显然 k = 2 k = 2 k=2 时， A ( N , 2 ) = N − 1 A(N,2)=N-1 A(N,2)=N−1;
k = 3 k = 3 k=3 时，显然 A ( N , 3 ) = A ( N − 1 , 2 ) + A ( N − 2 , 2 ) + ⋯ + A ( 2 , 2 ) = ( N − 1 ) ( N − 2 ) 2 A(N,3)=A(N-1,2) + A(N-2,2) + cdots + A(2,2) = cfrac{(N-1)(N-2)}{2} A(N,3)=A(N−1,2)+A(N−2,2)+⋯+A(2,2)=2(N−1)(N−2);
k = 5 k = 5 k=5 时，我们整理一下 ∑ i = 2 N − 3 A ( i , 2 ) A ( N − i , 3 ) = ∑ i = 2 N − 3 i 3 + ( 2 − 2 N ) i 2 + ( N 2 − N − 1 ) i − N 2 + 3 N − 2 2 displaystylesum_{i = 2}^{N-3}A(i,2)A(N-i,3) = displaystylesum_{i = 2}^{N-3}cfrac{i^3+(2−2N)i^2+(N^2−N−1)i−N^2+3N−2}{2} i=2∑N−3A(i,2)A(N−i,3)=i=2∑N−32i3+(2−2N)i2+(N2−N−1)i−N2+3N−2，又臭又长的一堆就不写了，总之等于 ( N − 1 ) ( N − 2 ) ( N − 3 ) ( N − 4 ) 4 × 3 × 2 cfrac{(N-1)(N-2)(N-3)(N-4)}{4 × 3 × 2} 4×3×2(N−1)(N−2)(N−3)(N−4)。
public class Test {
public static void main(String[] args) { new Test().run(); }
long n = 2021;
void run() {
System.out.println((n - 1) * (n - 2) * (n - 3) * (n - 4) / 4 / 3 / 2);
}
}
只会用笨方法，没上过高中体谅一下。
动态规划
设有状态 d p ( k , i ) dp(k,i) dp(k,i) 为 i i i 分解成 k k k 个正整数的方案数。
在上述解法里，容易得出 A ( N , 3 ) = A ( N − 1 , 3 − 1 ) + A ( N − 1 , 3 ) A(N,3)=A(N-1,3-1) + A(N-1,3) A(N,3)=A(N−1,3−1)+A(N−1,3)，具体的细节留给读者自行思考，这里直接给出状态转移方程： d p ( k , i ) = { 1 k = 1 d p ( k − 1 , i − 1 ) + d p ( k , i − 1 ) dp(k,i) = left{begin{array}{lr}1&k=1\dp(k-1,i-1) + dp(k,i-1)&end{array}right. dp(k,i)={1dp(k−1,i−1)+dp(k,i−1)k=1
import java.util.Arrays;
public class Test {
public static void main(String[] args) { new Test().run(); }
int n = 2021, k = 5;
void run() {
long[][] dp = new long[k + 1][n + 1];
Arrays.fill(dp[1], 1);
for (int i = 2; i <= k; i++)
for (int j = i; j <= n; j++)
dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1];
System.out.println(dp[k][n]);
}
}
组合数
两种方法无不在暗示结果等于 C 2020 4 C_{2020}^{4} C20204。
开个坑，不一定填。
#E 城邦
本题总分： 15 15 15 分
问题描述
小蓝国是一个水上王国，有
2021
2021
2021 个城邦，依次编号
1
1
1 到
2021
2021
2021。在任意两个城邦之间，都有一座桥直接连接。
为了庆祝小蓝国的传统节日，小蓝国政府准备将一部分桥装饰起来。对于编号为
a
a
a 和
b
b
b 的两个城邦，它们之间的桥如果要装饰起来，需要的费用如下计算：找到
a
a
a 和
b
b
b 在十进制下所有不同的数位，将数位上的数字求和。
例如，编号为
2021
2021
2021 和
922
922
922 两个城邦之间，千位、百位和个位都不同，将这些数位上的数字加起来是
(
2
+
0
+
1
)
+
(
0
+
9
+
2
)
=
14
(2 + 0 + 1) + (0 + 9 + 2) = 14
(2+0+1)+(0+9+2)=14。注意
922
922
922 没有千位，千位看成
0
0
0。
为了节约开支，小蓝国政府准备只装饰
2020
2020
2020 座桥，并且要保证从任意一个城邦到任意另一个城邦之间可以完全只通过装饰的桥到达。
请问，小蓝国政府至少要花多少费用才能完成装饰。
提示：建议使用计算机编程解决问题。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
4046
最小树生成
送分。
具体地说就是：完全图上的最小树生成。
也就是说该图具有 m = n ( n − 1 ) 2 m=cfrac{n(n-1)}{2} m=2n(n−1)，在这里是一个超过 2 E 6 2E6 2E6 的数字。
这里使用 K r u s k a l O ( m log m ) mathrm{Kruskal} O(m log m) Kruskal O(mlogm) 的去求解，不如朴素的做 P r i m mathrm{Prim} Prim，它的复杂度在 O ( n 2 ) O(n^2) O(n2)。
通常，使用优先队列可以简单将 P r i m mathrm{Prim} Prim 优化至 O ( m log m ) O(mlog m) O(mlogm)，但在 完全图 上，
不如不做。
下面给大打两个板子。
Kruskal
import java.util.ArrayList;
import java.util.List;
public class Test {
public static void main(String[] args) { new Test().run(); }
int n = 2021;
int[] link = new int[n + 1];
void run() {
List edges = new ArrayList();
for (int v = 1; v < n; v++) {
link[v] = v;
for (int w = v + 1; w <= n; w++)
edges.add(new Edge(v, w, calc(v, w)));
}
edges.sort((e1, e2)->(e1.weight - e2.weight));
int ans = 0, k = 1;
for (Edge edge : edges) {
int v = find(edge.v);
int w = find(edge.w);
if (v != w) {
link[v] = w;
ans += edge.weight;
if (++k == n) break;
}
}
System.out.println(ans);
}
int find(int k) { return k == link[k] ? k : (link[k] = find(link[k])); }
int calc(int v, int w) {
int res = 0;
for (int i = 0; i < 4; i++) {
if (v % 10 != w %10)
res += v % 10 + w % 10;
v /= 10; w /= 10;
}
return res;
}
class Edge {
int v, w, weight;
Edge(int v, int w, int weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
}
}
Prim
import java.util.Arrays;
public class Test {
public static void main(String[] args) { new Test().run(); }
int n = 2021;
void run() {
boolean[] marked = new boolean[n + 1];
int[] dist = new int[n + 1];
Arrays.fill(dist, 0x7FFFFFFF);
int ans = 0;
dist[1] = 0;
for (int k = 0; k < n; k++) {
int V = 0;
for (int i = 1; i <= n; i++)
if (!marked[i] && dist[i] < dist[V]) V = i;
marked[V] = true;
ans += dist[V];
for (int i = 1; i <= n; i++)
if (!marked[i])
dist[i] = min(dist[i], calc(i, V));
}
System.out.println(ans);
}
int min(int a, int b) { return a < b ? a : b; }
int calc(int v, int w) {
int res = 0;
for (int i = 0; i < 4; i++) {
if (v % 10 != w %10)
res += v % 10 + w % 10;
v /= 10; w /= 10;
}
return res;
}
}
贪心 + Trie
K r u s k a l mathrm{Kruskal} Kruskal 的策略是，每次连接权值最小，且两边没有连通的边，
在题目给定的权值计算方法下，权值最小的边显然为后缀(方便计算)重叠最多的两个节点构成的边，
好像行不通，开坑，一定不填。
#F 特殊年份
时间限制: 1.0 1.0 1.0s 内存限制: 512.0 512.0 512.0MB 本题总分： 15 15 15 分
问题描述
今年是
2021
2021
2021 年，
2021
2021
2021 这个数字非常特殊，它的千位和十位相等，个位比百位大
1
1
1，我们称满足这样条件的年份为特殊年份。
输入
5
5
5 个年份，请计算这里面有多少个特殊年份。
输入格式
输入 5 5 5 行，每行一个 4 4 4 位十进制数（数值范围为 1000 1000 1000 至 9999 9999 9999），表示一个年份。
输出格式
输出一个整数，表示输入的 5 5 5 个年份中有多少个特殊年份。
测试样例1
Input： 2019 2021 1920 2120 9899 Output： 2 Explanation： 2021 和 9899 是特殊年份，其它不是特殊年份。
朴素解法
import java.util.Scanner;
public class Main {
public static void main(String[] args) { new Main().run(); }
void run() {
Scanner in = new Scanner(System.in);
int ans = 0, k = 5;
while (k-- > 0)
if (check(in.nextInt())) ans++;
System.out.println(ans);
}
boolean check(int year) { return (year / 1000 == (year % 100) / 10) && ((year % 10) - 1 == (year % 1000) / 100); }
}
签到。
BCD码
虽然是签到题，但总想玩点花样，
固然我们可以用一串字符来表示一个十进制的数，但在多数情况下，空间和运行效率都不理想。
如果在需要频繁按位处理十进制上的位的问题的时候(当然不是只这个问题)，我们可以引入 B C D mathrm{BCD} BCD 码 ( B i n a r y − C o d e d D e c i m a l ) (mathrm{Binary-Coded Decimal}) (Binary−Coded Decimal)，
用四位二进制来表示一位十进制数，而非二的四次幂也就是十六进制数。
用若干位运算来替代取余和除法。
import java.util.Scanner;
public class Main {
public static void main(String[] args) { new Main().run(); }
void run() {
Scanner in = new Scanner(System.in);
int ans = 0, k = 5;
while (k-- > 0)
if (check(in.nextInt(16))) ans++;
System.out.println(ans);
}
boolean check(int year) { return (year >> 12 == ((year >> 4) & 0xf)) && ((year & 0xf) - 1 == ((year >> 8) & 0xf)); }
}
虽然不是这里，但总有用得上的时候。
#G 小平方
时间限制: 1.0 1.0 1.0s 内存限制: 512.0 512.0 512.0MB 本题总分： 20 20 20 分
问题描述
小蓝发现，对于一个正整数
n
n
n 和一个小于
n
n
n 的正整数
v
v
v，将
v
v
v 平方后对
n
n
n 取余可能小于
n
n
n 的一半，也可能大于等于
n
n
n 的一半。
请问，在
1
1
1 到
n
−
1
n − 1
n−1 中，有多少个数平方后除以
n
n
n 的余数小于
n
n
n 的一半。
例如，当
n
=
4
n = 4
n=4 时，
1
,
2
,
3
1, 2, 3
1,2,3 的平方除以
4
4
4 的余数都小于
4
4
4 的一半。
又如，当
n
=
5
n = 5
n=5 时，
1
,
4
1, 4
1,4 的平方除以
5
5
5 的余数都是
1
1
1，小于
5
5
5 的一半。而
2
,
3
2, 3
2,3 的平方除以
5
5
5 的余数都是
4
4
4，大于等于
5
5
5 的一半。
输入格式
输入一行包含一个整数 n n n。
输出格式
输出一个整数，表示满足条件的数的数量。
测试样例1
Input： 5 Output： 2
评测用例规模与约定
对于所有评测用例， 1 ≤ n ≤ 10000 1 ≤ n ≤ 10000 1≤n≤10000。
没什么花里胡哨，套两 f o r mathrm{for} for 比什么都好使。
import java.util.Scanner;
public class Main {
public static void main(String[] args) { new Main().run(); }
void run() {
int n = new Scanner(System.in).nextInt(), ans = 0;
for (int i = 1; i < n; i++)
if (i * i % n < n + 1 >> 1) ans++;
System.out.println(ans);
}
}
双签到了，属于是。
#H 完全平方数
时间限制: 2.0 2.0 2.0s 内存限制: 512.0 512.0 512.0MB 本题总分： 20 20 20 分
问题描述
一个整数
a
a
a 是一个完全平方数，是指它是某一个整数的平方，即存在一个整数
b
b
b，使得
a
=
b
2
a = b^{2}
a=b2。
给定一个正整数
n
n
n，请找到最小的正整数
x
x
x，使得它们的乘积是一个完全平方数。
输入格式
输入一行包含一个正整数 n n n。
输出格式
输出找到的最小的正整数 x x x。
测试样例1
Input： 12 Output： 3
测试样例2
Input： 15 Output： 15
评测用例规模与约定
对于
30
30
30% 的评测用例，
1
≤
n
≤
1000
1 ≤ n ≤ 1000
1≤n≤1000，答案不超过
1000
1000
1000。
对于
60
60
60% 的评测用例，
1
≤
n
≤
1
0
8
1 ≤ n ≤ 10^{8}
1≤n≤108，答案不超过
1
0
8
10^{8}
108。
对于所有评测用例，
1
≤
n
≤
1
0
12
1 ≤ n ≤ 10^{12}
1≤n≤1012，答案不超过
1
0
12
10^{12}
1012。
就蓝桥的难度，显然只是一道算术基本定理，
琢磨一下有没有能应付 n n n 是个极大的质数的策略。
睡觉
