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