第十二届蓝桥杯决赛JavaC组真题——详细答案对照(全网唯一:异或变换100%数据)-3

简介: 第十二届蓝桥杯决赛JavaC组真题——详细答案对照(全网唯一:异或变换100%数据)

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);
      }
    }
  }
}
相关文章
|
2月前
第十四届蓝桥杯集训——JavaC组第十三篇——for循环
第十四届蓝桥杯集训——JavaC组第十三篇——for循环
44 0
|
2月前
|
算法
第十四届蓝桥杯集训——JavaC组第十二篇——while循环(循环四要素)
第十四届蓝桥杯集训——JavaC组第十二篇——while循环(循环四要素)
50 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-439 算法训练 简单字符变换
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-439 算法训练 简单字符变换
46 1
|
2月前
|
网络安全 数据安全/隐私保护 计算机视觉
2024蓝桥杯网络安全-图片隐写-缺失的数据(0基础也能学会-含代码解释)
2024蓝桥杯网络安全-图片隐写-缺失的数据(0基础也能学会-含代码解释)
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 数列排序(四种语言对照)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 数列排序(四种语言对照)
32 0
|
2月前
|
Java C语言
第十四届蓝桥杯集训——JavaC组第十四篇——嵌套循环
第十四届蓝桥杯集训——JavaC组第十四篇——嵌套循环
42 0
|
2月前
|
C语言
第十四届蓝桥杯集训——JavaC组第十一篇——switch
第十四届蓝桥杯集训——JavaC组第十一篇——switch
40 0
|
2月前
第十四届蓝桥杯集训——JavaC组第十篇——分支语句
第十四届蓝桥杯集训——JavaC组第十篇——分支语句
39 0
|
2月前
|
算法
第十四届蓝桥杯集训——JavaC组第九篇——三元运算符
第十四届蓝桥杯集训——JavaC组第九篇——三元运算符
36 0
|
2月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
73 0