以下均为个人想法和解题思路,如有错误或不足,欢迎指正。如果本篇文章对您有所帮助,不妨点个赞,您的认可是我继续创作的动力,蟹蟹♪(・ω・)ノ
试题 A: 纯质数
本题总分:5 分
如果一个正整数只有 1 和它本身两个约数,则称为一个质数(又称素数)。
前几个质数是:2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · · 。
如果一个质数的所有十进制数位都是质数,我们称它为纯质数。例如:2, 3, 5, 7, 23, 37 都是纯质数,而 11, 13, 17, 19, 29, 31 不是纯质数。当然 1, 4, 35也不是纯质数。
请问,在 1 到 20210605 中,有多少个纯质数?
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
个人答案:1903
个人代码:
public class _纯质数 {
public static void main(String[] args) {
ffa(20210605);
}
/**
* 使用的是欧拉筛选法对质数进行筛选
* @param n
*/
public static void ffa(int n) {
int[] arr = new int[n + 1];
boolean[] pin = new boolean[n + 1];
int cnt = 0;
for (int i = 2; i <= n; ++i) {
if (!pin[i])
arr[++cnt] = i;
for (int j = 1; arr[j] * i <= n && j <= cnt; ++j) {
pin[arr[j] * i] = true;
if (i % arr[j] == 0)
break;
}
}
int ans = 0;
for (int i = 1; i <= cnt; ++i) {
if (arr[i] < 10 || check(arr[i]))
++ans;
}
System.out.println(ans);
}
public static boolean check(int x) {
while (x != 0) {
int p = x % 10;
if (p != 2 && p != 3 && p != 5 && p != 7)
return false;
x /= 10;
}
return true;
}
}
解题思路:暴力
试题 B: 完全日期
本题总分:5 分
如果一个日期中年月日的各位数字之和是完全平方数,则称为一个完全日期。
例如:2021 年 6 月 5 日的各位数字之和为 2 + 0 + 2 + 1 + 6 + 5 = 16,而16 是一个完全平方数,它是 4 的平方。所以 2021 年 6 月 5 日是一个完全日期。
例如:2021 年 6 月 23 日的各位数字之和为 2 + 0 + 2 + 1 + 6 + 2 + 3 = 16,是一个完全平方数。所以 2021 年 6 月 23 日也是一个完全日期。
请问,从 2001 年 1 月 1 日到 2021 年 12 月 31 日中,一共有多少个完全日期?
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
个人答案:977
个人代码:
public class _完全日期 {
static int[] dir = new int[] { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
public static void main(String[] args) {
int cur_Y = 2001, cur_M = 1, cur_D = 1;
int ans = 0;
while (cur_Y != 2022) {
if (check(cur_Y, cur_M, cur_D))
++ans;
boolean isR = isRun(cur_Y);
if (isR)
dir[2] = 29;
else
dir[2] = 28;
++cur_D;
if (cur_D > dir[cur_M]) {
cur_D = 1;
++cur_M;
if (cur_M == 13) {
cur_M = 1;
++cur_Y;
}
}
}
System.out.println(ans);
}
public static boolean isRun(int year) {
if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
return true;
return false;
}
public static boolean check(int year, int month, int day) {
int p = 0;
while (year != 0) {
p += year % 10;
year /= 10;
}
while (month != 0) {
p += month % 10;
month /= 10;
}
while (day != 0) {
p += day % 10;
day /= 10;
}
int r = (int) Math.sqrt(p);
if (r * r == p) {
return true;
}
return false;
}
}
解题思路:暴力
试题 C: 最小权值
本题总分:10 分
对于一棵有根二叉树 T,小蓝定义这棵树中结点的权值 W(T) 如下:
空子树的权值为 0。
如果一个结点 v 有左子树 L, 右子树 R,分别有 C( L ) 和 C( R ) 个结点,则W (v ) = 1 + 2W( L ) + 3W( R ) + ( C( L ) ^ 2 ) * C( R )。
树的权值定义为树的根结点的权值。
小蓝想知道,对于一棵有 2021 个结点的二叉树,树的权值最小可能是多少?
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
个人答案:2653631372
个人代码:
public class _最小权值{
static int n = 2021;
public static void main(String[] args) {
ffa();
}
public static void ffa() {
long[] dp = new long[n + 1];
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
long min = Long.MAX_VALUE;
for (int l = 0; l <= i - 1; ++l) {
int r = i - l - 1;
long p = 1 + 2 * dp[l] + 3 * dp[r] + l * l * r;
min = Math.min(min, p);
}
dp[i] = min;
}
System.out.println(dp[n]);
}
}
解题思路:一维动态规划,要注意数据类型要用long
试题 D: 覆盖
本题总分:10 分
小蓝有一个国际象棋的棋盘,棋盘的大小为 8 × 8,即由 8 行 8 列共 64 个方格组成。棋盘上有美丽的图案,因此棋盘旋转后与原来的棋盘不一样。
小蓝有很多相同的纸片,每张纸片正好能覆盖棋盘的两个相邻方格。小蓝想用 32 张纸片正好将棋盘完全覆盖,每张纸片都覆盖其中的两个方格。
小蓝发现,有很多种方案可以实现这样的覆盖。如果棋盘比较小,方案数相对容易计算,比如当棋盘是 2 × 2 时有两种方案,当棋盘是 4 × 4 时有 36 种方案。但是小蓝算不出他自己的这个 8 × 8 的棋盘有多少种覆盖方案。
请帮小蓝算出对于这个 8 × 8 的棋盘总共有多少种覆盖方案。
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
个人答案:12988816
个人代码:
public class _覆盖 {
static boolean[][] pin = new boolean[8][8];
static int ans = 0;
public static void main(String[] args) {
ffa(0, 0);
System.out.println(ans);
}
public static void ffa(int x, int y) {
if (x == 8) {
++ans;
return;
}
if (!pin[x][y]) {
pin[x][y] = true;
if (y != 7) {
if (!pin[x][y + 1]) {
pin[x][y + 1] = true;
ffa(x, y + 1);
pin[x][y + 1] = false;
}
}
if (x != 7) {
if (!pin[x + 1][y]) {
pin[x + 1][y] = true;
if (y == 7)
ffa(x + 1, 0);
else
ffa(x, y + 1);
pin[x + 1][y] = false;
}
}
pin[x][y] = false;
} else {
if (y == 7)
ffa(x + 1, 0);
else
ffa(x, y + 1);
}
}
}
解题思路:深搜模拟
试题 E: 123
时间限制: 5.0s 内存限制: 512.0MB 本题总分:15 分
小蓝发现了一个有趣的数列,这个数列的前几项如下:
1, 1, 2, 1, 2, 3, 1, 2, 3, 4, …
小蓝发现,这个数列前 1 项是整数 1,接下来 2 项是整数 1 至 2,接下来 3 项是整数 1 至 3,接下来 4 项是整数 1 至 4,依次类推。
小蓝想知道,这个数列中,连续一段的和是多少。
输入的第一行包含一个整数 T,表示询问的个数。
接下来 T 行,每行包含一组询问,其中第 i 行包含两个整数 li 和 ri,表示
询问数列中第 li 个数到第 ri 个数的和。
输出 T 行,每行包含一个整数表示对应询问的答案。
【样例输入】
3
1 1
1 3
5 8
1
4
8
对于 10% 的评测用例,1 ≤ T ≤ 30, 1 ≤ li ≤ ri ≤ 100。
对于 20% 的评测用例,1 ≤ T ≤ 100, 1 ≤ li ≤ ri ≤ 1000。
对于 40% 的评测用例,1 ≤ T ≤ 1000, 1 ≤ li ≤ ri ≤ 106。
对于 70% 的评测用例,1 ≤ T ≤ 10000, 1 ≤ li ≤ ri ≤ 109。
对于 80% 的评测用例,1 ≤ T ≤ 1000, 1 ≤ li ≤ ri ≤ 1012。
对于 90% 的评测用例,1 ≤ T ≤ 10000, 1 ≤ li ≤ ri ≤ 1012。
对于所有评测用例,1 ≤ T ≤ 100000, 1 ≤ li ≤ ri ≤ 1012。
个人代码:
import java.util.Scanner;
public class _123{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for (int i = 0; i < t; ++i) {
long l = sc.nextLong(), r = sc.nextLong();
long ans_l = ffa(l - 1), ans_r = ffa(r);
System.out.println(ans_r - ans_l);
}
}
public static long ffa(long r) {
long ind = 1, cnt = 1, ans = 0;
while (ind <= r) {
ans += cnt * (cnt + 1) / 2;
++cnt;
ind += cnt;
}
if (ind > r) {
ind -= cnt;
cnt = r - ind;
ans += cnt * (cnt + 1) / 2;
}
return ans;
}
}
解题思路:类似阶梯思想
试题 F: 二进制问题
时间限制: 1.0s 内存限制: 512.0MB 本题总分:15 分
小蓝最近在学习二进制。他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗?
输入一行包含两个整数 N 和 K。
输出一个整数表示答案。
7 2
3
对于 30% 的评测用例,1 ≤ N ≤ 10^6, 1 ≤ K ≤ 10。
对于 60% 的评测用例,1 ≤ N ≤ 2 × 10^9, 1 ≤ K ≤ 30。
对于所有评测用例,1 ≤ N ≤ 10^18, 1 ≤ K ≤ 50。
个人代码:
import java.math.BigInteger;
import java.util.Scanner;
public class MainF {
static long n;
static int k;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextLong();
k = sc.nextInt();
System.out.println(ffa());
}
/**
* 这里用到了高中的排列组合C(n, r),意思是在n个位置中放r个元素共有多少种放置方式
* @return
*/
public static long ffa() {
long res = 0;
int y = k;
char[] cn = Long.toBinaryString(n).toCharArray();
for (int i = 0; i < cn.length && y != 0; ++i) {
int x = cn.length - i - 1;
if (cn[i] == '1' && y <= x) {
long resx = 1, resy = 1;
for (int j = 1; j <= y; ++j) {
resx *= x - j + 1;
resy *= j;
}
res += resx / resy;
--y;
}
}
if (y == 0)
++ res;
if (new BigInteger(String.valueOf(n)).bitCount() == k && cn[cn.length - 1] == '1')
++ res;
return res;
}
}
解题思路:(有需要再补)
试题 G: 冰山
时间限制: 5.0s 内存限制: 512.0MB 本题总分:20 分
一片海域上有一些冰山,第 i 座冰山的体积为 Vi。
随着气温的变化,冰山的体积可能增大或缩小。第 i 天,每座冰山的变化量都是 Xi。当 Xi > 0 时,所有冰山体积增加 Xi;当 Xi < 0 时,所有冰山体积减少 −Xi;当 Xi = 0 时,所有冰山体积不变。
如果第 i 天某座冰山的体积变化后小于等于 0,则冰山会永远消失。
冰山有大小限制 k。如果第 i 天某座冰山 j 的体积变化后 Vj 大于 k,则它会分裂成一个体积为 k 的冰山和 Vj − k 座体积为 1 的冰山。
第 i 天结束前(冰山增大、缩小、消失、分裂完成后),会漂来一座体积为Yi 的冰山(Yi = 0 表示没有冰山漂来)。
小蓝在连续的 m 天对这片海域进行了观察,并准确记录了冰山的变化。小蓝想知道,每天结束时所有冰山的体积之和(包括新漂来的)是多少。
由于答案可能很大,请输出答案除以 998244353 的余数。
输入的第一行包含三个整数 n, m, k,分别表示初始时冰山的数量、观察的天数以及冰山的大小限制。
第二行包含 n 个整数 V1, V2, · · · , Vn,表示初始时每座冰山的体积。
接下来 m 行描述观察的 m 天的冰山变化。其中第 i 行包含两个整数 Xi, Yi,意义如前所述。
输出 m 行,每行包含一个整数,分别对应每天结束时所有冰山的体积之和除以 998244353 的余数。
1 3 6
1
6 1
2 2
-1 1
8
16
11
在本样例说明中,用 [a1, a2, · · · , an] 来表示每座冰山的体积。
初始时的冰山为 [1]。 第 1 天结束时,有 3 座冰山:[1, 1, 6]。 第 2 天结束时,有 6 座冰山:[1, 1, 2, 3, 3, 6]。 第 3 天结束时,有 5 座冰山:[1, 1, 2, 2, 5]。
对于 40% 的评测用例,n, m, k ≤ 2000;
对于 60% 的评测用例,n, m, k ≤ 20000;
对于所有评测用例,1 ≤ n, m ≤ 100000, 1 ≤ k ≤ 10^9, 1 ≤ Vi ≤ k, 0 ≤ Yi ≤ k, −k ≤ Xi ≤ k。
个人代码:
解题思路:
试题 H: 和与乘积
时间限制: 1.0s 内存限制: 512.0MB 本题总分:20 分
给定一个数列 A = (a1, a2, · · · , an),问有多少个区间 [L, R] 满足区间内元素
的乘积等于他们的和,即 aL · aL+1 · · · aR = aL + aL+1 + · · · + aR 。
输入第一行包含一个整数 n,表示数列的长度。
第二行包含 n 个整数,依次表示数列中的数 a1, a2, · · · , an。
输出仅一行,包含一个整数表示满足如上条件的区间的个数。
4
1 3 2 2
6
符合条件的区间为 [1, 1], [1, 3], [2, 2], [3, 3], [3, 4], [4, 4]。
对于 20% 的评测用例,n, m ≤ 3000;
对于 50% 的评测用例,n, m ≤ 20000;
对于所有评测用例,1 ≤ n, m ≤ 200000, 1 ≤ ai ≤ 200000。
个人代码:
解题思路:
试题 I: 异或三角
时间限制: 5.0s 内存限制: 512.0MB 本题总分:25 分
给定 T 个数 n1, n2, · · · , nT,对每个 ni 请求出有多少组 a, b, c 满足:
- 1 ≤ a, b, c ≤ ni;
- a ⊕ b ⊕ c = 0,其中 ⊕ 表示二进制按位异或;
- 长度为 a, b, c 的三条边能组成一个三角形。
输入的第一行包含一个整数 T。
接下来 T 行每行一个整数,分别表示 n1, n2, · · · , nT。
输出 T 行,每行包含一个整数,表示对应的答案。
2
6
114514
6
11223848130
对于 10% 的评测用例,T = 1, 1 ≤ ni ≤ 200;
对于 20% 的评测用例,T = 1, 1 ≤ ni ≤ 2000;
对于 50% 的评测用例,T = 1, 1 ≤ ni ≤ 2^20;
对于 60% 的评测用例,1 ≤ T ≤ 100000, 1 ≤ ni ≤ 2^20;
对于所有评测用例,1 ≤ T ≤ 100000, 1 ≤ ni ≤ 2^30。
个人代码:
解题思路:
试题 J: 积木
时间限制: 10.0s 内存限制: 512.0MB 本题总分:25 分
小蓝有大量正方体的积木(所有积木完全相同),他准备用积木搭一个巨大的图形。
小蓝将积木全部平铺在地面上,而不垒起来,以便更稳定。他将积木摆成一行一行的,每行的左边对齐,形成最终的图形。
第一行小蓝摆了 H1 = w 块积木。从第二行开始,第 i 行的积木数量 Hi 都至少比上一行多 L,至多比上一行多 R(当 L = 0 时表示可以和上一行的积木数量相同),即Hi−1 + L ≤ Hi ≤ Hi−1 + R。
给定 x, y 和 z,请问满足以上条件的方案中,有多少种方案满足第 y 行的积木数量恰好为第 x 行的积木数量的 z 倍。
输入一行包含 7 个整数 n,w, L, R, x, y,z,意义如上所述。
输出一个整数, 表示满足条件的方案数,答案可能很大,请输出答案除以998244353 的余数。
5 1 1 2 2 5 3
4
符合条件的积木如图所示
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210619115621671.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MDI2MA==,size_16,color_FFFFFF,t_70#pic_left)
233 5 1 8 100 215 3
308810105
对于 10% 的评测用例,1 ≤ n ≤ 10, 1 ≤ w ≤ 10, 0 ≤ L ≤ R ≤ 3;
对于 20% 的评测用例,1 ≤ n ≤ 20, 1 ≤ w ≤ 10, 0 ≤ L ≤ R ≤ 4;
对于 35% 的评测用例,1 ≤ n ≤ 500, 0 ≤ L ≤ R ≤ 10;
对于 50% 的评测用例,1 ≤ n ≤ 5000, 0 ≤ L ≤ R ≤ 10;
对于 60% 的评测用例,1 ≤ n ≤ 20000, 0 ≤ L ≤ R ≤ 10;
对于 70% 的评测用例,1 ≤ n ≤ 50000, 0 ≤ L ≤ R ≤ 10;
对于 85% 的评测用例,1 ≤ n ≤ 300000, 0 ≤ L ≤ R ≤ 10;
对于所有评测用例,1 ≤ n ≤ 500000, 1 ≤ w ≤ 109, 0 ≤ L ≤ R ≤ 40, 1 ≤ x < y ≤ n, 0 ≤ z ≤ 109。
个人代码:
解题思路:
~ 如果本篇文章对您有所帮助,不妨点个赞,您的认可是我继续创作的动力,蟹蟹♪(・ω・)ノ