第十二届蓝桥杯决赛JavaC组真题——详细答案对照(全网唯一：异或变换100%数据)
第十二届蓝桥杯决赛JavaC组真题——详细答案对照(全网唯一：异或变换100%数据)
目录
A、整数范围
本题总分：5 分
问题描述
用 8 位二进制（一个字节）来表示一个非负整数，表示的最小值是 0 ，则一般能表示的最大值是多少？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
package action;
public class demo {
public static void main(String[] args) {
System.out.println(Integer.parseInt("11111111", 2));
}
}B 带宽
本题总分：5 分
问题描述
小蓝家的网络带宽是 200 Mbps，请问，使用小蓝家的网络理论上每秒钟最多可以从网上下载多少 MB 的内容。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
package action;
public class demo {
public static void main(String[] args) {
System.out.println(200/8);
}
}C、纯质数
本题总分：10 分
问题描述
如果一个正整数只有 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 中，有多少个纯质数？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
package action;
public class demo {
public static void main(String[] args) {
long out = 0;// 记录总个数
for (int i = 1; i <= 20210605; i++) {
if ((i + "").indexOf("1") == -1 && (i + "").indexOf("4") == -1 && (i + "").indexOf("6") == -1 && // 首先判断当前数字中不能包含非质数数字
(i + "").indexOf("8") == -1 && (i + "").indexOf("9") == -1 && (i + "").indexOf("0") == -1) {
if (f(i)) { // 判断是否是质数
out++;
// System.out.println(i);
}
}
if (i % 10000 == 0) {
System.out.println(i);// 观察程序运行进度
}
}
System.out.println(out);// 最后结果
}
// 判断是否是质数
private static boolean f(int num) {
for (int i = 2; i < num / 2; i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}D 完全日期
本题总分：10 分
问题描述
如果一个日期中年月日的各位数字之和是完全平方数，则称为一个完全日期。 例如：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 日中，一共有多少个完全日期？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
package action;
import java.util.Calendar;
public class demo {
public static void main(String[] args) {
long out = 0;// 记录总个数
Calendar n = Calendar.getInstance();
n.clear();
for (int i = 2001; i < 2022; i++) {// 年份
for (int j = 1; j <= 12; j++) {// 月份
n.set(i, j - 1, 1);
int max = n.getActualMaximum(Calendar.DAY_OF_MONTH);// 获取当前月份最大天数
for (int k = 1; k <= max; k++) {// 日
// System.out.println(i+""+j+""+k);
if (f(Integer.parseInt(i + "" + j + "" + k))) {
out++;
}
}
}
}
System.out.println(out);// 最后结果
}
// 判断是否是完全日期
private static boolean f(int num) {
int n = 0;
while (num > 0) {
n += num % 10;
num /= 10;
}
if (n == 4 || n == 9 || n == 16 || n == 25) {// 满足当前范围内日期的完全平方数只有4 9 16 25无需判断其余数字
return true;
}
return false;
}
}E、最小权值
本题总分：15 分
问题描述
对于一棵有根二叉树 T ，小蓝定义这棵树中结点的权值 W(T) 如下： 空子树的权值为 0 。 如果一个结点 v 有左子树 L , 右子树 R ，分别有 C(L) 和 C(R) 个结点，则 W(v)=1+2W(L)+3W(R)+(C(L))^2C(R)。(^2代表平方) 树的权值定义为树的根结点的权值。 小蓝想知道，对于一棵有 2021 个结点的二叉树，树的权值最小可能是多少？
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
package action;
public class demo {
static int n = 2021;
public static void main(String[] args) {
f();
}
public static void f() {
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]);
}
}
F、大写
时间限制: 1.0s 内存限制: 512.0MB 本题总分：15 分
问题描述
给定一个只包含大写字母和小写字母的字符串，请将其中所有的小写字母转换成大写字母后将字符串输出。
输入格式
输入一行包含一个字符串。
输出格式
输出转换成大写后的字符串。 测试样例1 Input： LanQiao
Output： LANQIAO 评测用例规模与约定
对于所有评测用例，字符串的长度不超过100。
package action;
import java.util.Scanner;
public class demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(sc.next().toUpperCase());
}
}G、123
时间限制: 5.0s 内存限制: 512.0MB 本题总分：20 分
问题描述
小蓝发现了一个有趣的数列，这个数列的前几项如下： 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 行，每行包含一个整数表示对应询问的答案。
测试样例1 Input： 3 1 1 1 3 5 8
Output： 1 4 8 评测用例规模与约定
对于 10 1010% 的评测用例，1 ≤ T ≤ 30 , 1 ≤ l i ≤ r i ≤ 100。 对于 20 2020% 的评测用例，1 ≤ T ≤ 100 , 1 ≤ l i ≤ r i ≤ 1000。 对于 40 4040% 的评测用例，1 ≤ T ≤ 1000 , 1 ≤ l i ≤ r i ≤ 10^6 。 对于 70 7070% 的评测用例，1 ≤ T ≤ 10000 , 1 ≤ l i ≤ r i ≤ 10^9。 对于 80 8080% 的评测用例，1 ≤ T ≤ 1000 , 1 ≤ l i ≤ r i ≤ 10^12。 对于 90 9090% 的评测用例，1 ≤ T ≤ 10000 , 1 ≤ l i ≤ r i ≤ 10^12。 对于所有评测用例，1 ≤ T ≤ 100000 , 1 ≤ l i ≤ r i ≤ 1 0^12。
package action;
import java.util.Scanner;
public class demo {
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;
}
}H、异或变换（源码提供者：学生【郭尚】）
时间限制: 3.0s 内存限制: 512.0MB 本题总分：20 分
问题描述
小蓝有一个 01 串 s = s1s2s3 ⋅ ⋅ ⋅ sn。 以后每个时刻，小蓝要对这个 01 串进行一次变换。每次变换的规则相同。 对于 01 串 s = s1s2s3 ⋅ ⋅ ⋅ sn，变换后的 01 串s' = s'1s'2s'3 ⋅ ⋅ ⋅ s'n为： s'1=s1; s'i=si-1⊕si。 其中 a ⊕ b 表示两个二进制的异或，当 a 和 b 相同时结果为 0 ，当 a 和 b 不同时结果为 1。 请问，经过 t 次变换后的 01 串是什么？
输入格式
输入的第一行包含两个整数 n,t，分别表示 01 串的长度和变换的次数。 第二行包含一个长度为 n 的 01 串。
输出格式
输出一行包含一个 01 串，为变换后的串。
测试样例1 Input： 5 3 10110
Output： 11010
Explanation： 初始时为 10110，变换 1 次后变为 11101，变换 2 次后变为 10011，变换 3 次后变为 11010。
评测用例规模与约定
对于 40% 的评测用例，1 ≤ n ≤ 100 , 1 ≤ t ≤ 1000。 对于 80% 的评测用例，1 ≤ n ≤ 1000 , 1 ≤ t ≤ 10^9。 对于所有评测用例，1 ≤ n ≤ 10000 , 1 ≤ t ≤ 10^18。
package action;
import java.util.Scanner;
public class demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long t = sc.nextInt();// 变换次数
StringBuilder as = new StringBuilder();// 输出得变量
char[] c = sc.next().toCharArray();// 一个长度为n得字符串转数组
sc.close();
for (int i = 0; i < n; i++) {
boolean a = c[i] == '0';// true是0
// 在n里面判断是否相等
for (int j = 1; i - j >= 0 && j <= t; j++)
if ((t & j) == j && c[i - j] == '1')
a = !a;
as.append(a ? 0 : 1);// 三目运算，相等是0，不相等是1
}
System.out.println(as);
}
}测试数据：1 ≤ n ≤ 10000 , 1 ≤ t ≤ 10^18
1000 100000000
/*
* 提示：该行代码过长，系统自动注释不进行高亮。一键复制会移除系统注释
* 1011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111
*/结果：
1000 100000000 1011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100011000110001100001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001110011100111001011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111 1011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101011010110101101110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011110111101111011100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000100001000010000101010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010100101001010010
I、冰山
时间限制: 5.0s 内存限制: 512.0MB 本题总分：25 分
问题描述
一片海域上有一些冰山，第 i ii 座冰山的体积为 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 mm 天对这片海域进行了观察，并准确记录了冰山的变化。小蓝想知道，每天结束时所有冰山的体积之和（包括新漂来的）是多少。 由于答案可能很大，请输出答案除以 998244353 的余数。
输入格式
输入的第一行包含三个整数 n,m,k，分别表示初始时冰山的数量、观察的天数以及冰山的大小限制。 第二行包含 n nn 个整数 V1, V2 , ⋅⋅⋅ , Vn，表示初始时每座冰山的体积。 接下来 m 行描述观察的 m 天的冰山变化。其中第 i 行包含两个整数 Xi , Yi，意义如前所述。
输出格式
输出 m 行，每行包含一个整数，分别对应每天结束时所有冰山的体积之和除以 998244353 的余数。
测试样例1 Input： 1 3 6 1 6 1 2 2 -1 1
Output： 8 16 11
Explanation： 在本样例说明中，用 [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 4040% 的评测用例，n,m,k≤2000； 对于 60 6060% 的评测用例，n,m,k≤20000； 对于所有评测用例，1 ≤ n , m ≤ 100000 , 1 ≤ k ≤ 10^9 , 1 ≤ Vi ≤ k , 0 ≤ Yi ≤ k , − k ≤ Xi ≤ k。
package action;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class demo {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long k = sc.nextInt();
Queue<Long> que = new LinkedList<Long>();
for (int i = 0; i < n; i++) {// 初始时冰山状态
que.add(sc.nextLong());
}
for (int i = 0; i < m; i++) {//
long x = sc.nextLong();
long y = sc.nextLong();
long sum = y;
if (x != 0) {
int len = que.size();// 队列循环时长度会变化 单独记录一下
for (int j = 0; j < len; j++) {
long temp = que.poll() + x;// 计算当前冰山状态 大于0再加入回去
if (temp > 0) {
sum += temp;
if (temp > k) {
que.add(k);// 体积大于k添加一个k 其余为1
for (int l = 0; l < temp - k; l++) {
que.add(1l);
}
} else {
que.add(temp);
}
}
}
}
if (y != 0) {// 判断有没有新冰山
que.add(y);
}
System.out.println(sum % 998244353l);
}
}
}J、二进制问题
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
问题描述
小蓝最近在学习二进制。他想知道 1 到 N 中有多少个数满足其二进制表示中恰好有 K 个 1。你能帮助他吗？
输入格式
输入一行包含两个整数 N 和 K。
输出格式
输出一个整数表示答案。
测试样例1 Input： 7 2
Output： 3 评测用例规模与约定
对于 30 3030% 的评测用例，1 ≤ N ≤ 10^6 , 1 ≤ K ≤ 10。 对于 60 6060% 的评测用例，1 ≤ N ≤ 2 × 10^9 , 1 ≤ K ≤ 30。 对于所有评测用例，1 ≤ N ≤ 1 0^18 , 1 ≤ K ≤ 50。
package action;
import java.util.Scanner;
public class demo {
public static long out = 0;
public static int[] aa;
public static long n;
public static int k;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextLong();
k = sc.nextInt();
sc.close();
aa = new int[Long.toString(n, 2).length()];
f(k, 0);
System.out.println(out);
}
private static void f(int kk, int index) {
if (kk == 0) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < aa.length; i++) {
sb.append(aa[i]);
}
if (Long.valueOf(sb.toString(), 2) <= n) {
out++;
}
} else {
if (aa.length - index < kk) {
return;
} else {
aa[index] = 1;
f(kk - 1, index + 1);
aa[index] = 0;
f(kk, index + 1);
}
}
}
}腾讯云开发者
