devbox
编程领航者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Codeforces Round 912 (Div. 2) --- D1题和D2题 -- 题解_maximum and queries

作者：编程领航者 | 2024-02-02 11:45:45

赞

踩

maximum and queries

目录

Maximum And Queries

题目大意：

思路：

D1：

D2：

D1代码：

D2代码：

 

Maximum And Queries

Problem - D1 - Codeforces

Problem - D2 - Codeforces

题目大意：

现在给你n个数，然后你可以进行q次查询，每一次查询你都可以进行k次操作，操作的定义为选择任意一个数字让其加一，在进行小于等于k次操作后，这n个数字能得到最大的与和是多少。

D1 ：数据范围 n<=10^6, q<=10^6, n*q<=10^6，a<=10^6

D2:  数据范围  n<=10^6 q<=10^6,a<=10^6

思路：

D1：

因为n*q是小于等于10^6，所以我们可以不用在意查询代价，因为一次计算代价就是 60，所以时间复杂度最高为O(6*10^7)是可以接受的。

然后计算答案应该从二进制的高位开始计算，因为如果从低位开始计算，下一次计算的时候我们这一位填1会影响计算k的大小，但是如果从高位开始计算，如果这一位需要通过操作让其变为1，那么他的低位就会变为0，并且这样的变化并不会影响低位操作次数的统计。

D2：

这里的n*q最大为10^12，这里我们在意查询代价了，所以我们应该做到查询代价为O(1)。

k最大为10^18,约等于2^60,并且2^20大于10^6（所以2^20以上的与和只能通过操作得到，所以可以直接快速求），那么我可以把2^20作为n的临界值，如果k能将ai全部提升至2^20以上，那么就直接让他全部变为最大值。

否则通过预处理ai，这里用到SOSDP（可以自行了解）

  1.         // dpSum[i][j] 表示i的超集，从0到j位的值的和
  2.         long[][] dpSum = new long[1 << 20][20];
  3.         // dpCnt[i] 表示 i的超集有多少个
  4.         long[] dpCnt = new long[1 << 20];
  5.         for (int i = 0; i < n; i++) {
  6.             arr[i] = input.nextLong();
  7.             total += arr[i];
  8.             s += (t - arr[i]);
  9.             dpCnt[(int) arr[i]]++;
  10.             int sum = 0;
  11.             for (int j = 0; j < 20; j++) {
  12.                 sum += (arr[i] & (1 << j));
  13.                 dpSum[(int) arr[i]][j] += sum;
  14.             }
  15.         }
  16.         
  17.         // 预处理dpCnt
  18.         for (int i = 0; i < 20; i++) {
  19.             for (int j = 0; j < 1 << 20; j++) {
  20.                 if ((j & (1 << i)) == 0)
  21.                     dpCnt[j] += dpCnt[j | (1 << i)]; 
  22.             }
  23.         }
  24.  
  25.         //预处理 dpSum
  26.         for (int i = 0; i < 20; i++) {
  27.             for (int j = 0; j < 1 << 20; j++) {
  28.                 for (int k = 0; k < 20; k++) {
  29.                     if ((j & (1 << i)) == 0)
  30.                         dpSum[j][k] += dpSum[j | (1 << i)][k];
  31.                 }
  32.             }
  33.         }
  34.  
  35.         for (int i = 0; i < q; i++) {
  36.             long k = input.nextLong();
  37.             long ans = 0;
  38.             if (k >= s) { // 如果能直接提升到2^20及以上则直接计算。
  39.                 ans = t + (k - s) / n;
  40.                 out.println(ans);
  41.                 continue;
  42.             }
  43.  
  44.             for (int j = 19; j >= 0; j--) {
  45.                 // dpCnt[i] 表示i的超集的个数， 如果当前答案是 110000，目标答案是 110010，
  46.                 // dpCnt[110010]已经有这个110010二进制的数，不需要进行操作，
  47.                 // 所以目标答案需要进行(n - dpCnt[(int) (ans | (1 << j))]) * (1L << j)，
  48.                 // 这里假设除了110010的超集剩余的数字从0位到第j位都为0，但是他可能不为0，
  49.                 // 所以需要减去[ans ， ans | (1 << j)] 这个范围之间的数字他的贡献
  50.                 long x = (n - dpCnt[(int) (ans | (1 << j))]) * (1L << j);
  51.                 x -= dpSum[(int) ans][j] - dpSum[(int) (ans | (1<<j))][j];
  52.                 if (x <= k){
  53.                     k -= x;
  54.                     ans |= (1L << j);
  55.                 }
  56.             }
  57.             out.println(ans);
  58.         }

D1代码：

  1. import java.util.Scanner;
  2.  
  3. /**
  4.  * @ProjectName: study3
  5.  * @FileName: Ex35
  6.  * @author:HWJ
  7.  * @Data: 2023/12/2 11:37
  8.  */
  9. public class Ex35 {
  10.     public static void main(String[] args) {
  11.         Scanner input = new Scanner(System.in);
  12.         int n = input.nextInt();
  13.         int q = input.nextInt();
  14.         long[] arr = new long[n];
  15.         for (int i = 0; i < n; i++) {
  16.             arr[i] = input.nextInt();
  17.         }
  18.         for (int i = 0; i < q; i++) {
  19.             long k = input.nextLong();
  20.             long ans = 0;
  21.             long[] a = new long[n];
  22.             for (int j = 0; j < n; j++) {
  23.                 a[j] = arr[j];
  24.             }
  25.             for (int j = 62; j >= 0; j--) {
  26.                 long sum = 0;
  27.                 long num = 1L << j;
  28.                 for (int l = 0; l < n; l++) {
  29.                     if ((ans & a[l]) != ans){
  30.                         a[l] = ans;
  31.                     }
  32.                     if ((a[l] & num) == num) continue;
  33.                     sum += num - (a[l] & (num - 1));
  34.                     if (sum > k) break;
  35.                 }
  36.                 if (sum > k) continue;
  37.                 k -= sum;
  38.                 ans += num;
  39.             }
  40.             System.out.println(ans);
  41.         }
  42.     }
  43. }

D2代码：

  1. import java.io.*;
  2. import java.math.BigInteger;
  3. import java.util.StringTokenizer;
  4.  
  5. /**
  6.  * @ProjectName: study3
  7.  * @FileName: Ex36
  8.  * @author:HWJ
  9.  * @Data: 2023/12/2 11:37
  10.  */
  11. public class Ex36 {
  12.     public static void main(String[] args) throws IOException {
  13.         int n = input.nextInt();
  14.         int q = input.nextInt();
  15.         long[] arr = new long[n];
  16.         long s = 0;
  17.         long t = 1L << 20;
  18.         long total = 0;
  19.         long[][] dpSum = new long[1 << 20][20];
  20.         long[] dpCnt = new long[1 << 20];
  21.         for (int i = 0; i < n; i++) {
  22.             arr[i] = input.nextLong();
  23.             total += arr[i];
  24.             s += (t - arr[i]);
  25.             dpCnt[(int) arr[i]]++;
  26.             int sum = 0;
  27.             for (int j = 0; j < 20; j++) {
  28.                 sum += (arr[i] & (1 << j));
  29.                 dpSum[(int) arr[i]][j] += sum;
  30.             }
  31.         }
  32.  
  33.         for (int i = 0; i < 20; i++) {
  34.             for (int j = 0; j < 1 << 20; j++) {
  35.                 if ((j & (1 << i)) == 0)
  36.                     dpCnt[j] += dpCnt[j | (1 << i)];
  37.             }
  38.         }
  39.  
  40.         for (int i = 0; i < 20; i++) {
  41.             for (int j = 0; j < 1 << 20; j++) {
  42.                 for (int k = 0; k < 20; k++) {
  43.                     if ((j & (1 << i)) == 0)
  44.                         dpSum[j][k] += dpSum[j | (1 << i)][k];
  45.                 }
  46.             }
  47.         }
  48.  
  49.         for (int i = 0; i < q; i++) {
  50.             long k = input.nextLong();
  51.             long ans = 0;
  52.             if (k >= s) {
  53.                 ans = t + (k - s) / n;
  54.                 out.println(ans);
  55.                 continue;
  56.             }
  57.             for (int j = 19; j >= 0; j--) {
  58.                 // dpCnt[i] 表示i的超集的个数， 如果当前答案是 110000，目标答案是 110010，
  59.                 // dpCnt[110010]已经有这个110010二进制的数，不需要进行操作，
  60.                 // 所以目标答案需要进行(n - dpCnt[(int) (ans | (1 << j))]) * (1L << j)，
  61.                 // 这里假设除了110010的超集剩余的数字从0位到第j位都为0，但是他可能不为0，
  62.                 // 所以需要减去[ans ， ans | (1 << j)] 这个范围之间的数字他的贡献
  63.                 long x = (n - dpCnt[(int) (ans | (1 << j))]) * (1L << j);
  64.                 x -= dpSum[(int) ans][j] - dpSum[(int) (ans | (1<<j))][j];
  65.                 if (x <= k){
  66.                     k -= x;
  67.                     ans |= (1L << j);
  68.                 }
  69.             }
  70.             out.println(ans);
  71.         }
  72.         out.flush();
  73.         out.close();
  74.         br.close();
  75.     }
  76.     static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
  77.     static Input input = new Input(System.in);
  78.     static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  79.     static class Input {
  80.         public BufferedReader reader;
  81.         public StringTokenizer tokenizer;
  82.  
  83.         public Input(InputStream stream) {
  84.             reader = new BufferedReader(new InputStreamReader(stream), 32768);
  85.             tokenizer = null;
  86.         }
  87.  
  88.         public String next() {
  89.             while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  90.                 try {
  91.                     tokenizer = new StringTokenizer(reader.readLine());
  92.                 } catch (IOException e) {
  93.                     throw new RuntimeException(e);
  94.                 }
  95.             }
  96.             return tokenizer.nextToken();
  97.         }
  98.  
  99.         public String nextLine() {
  100.             String str = null;
  101.             try {
  102.                 str = reader.readLine();
  103.             } catch (IOException e) {
  104.                 // TODO 自动生成的 catch 块
  105.                 e.printStackTrace();
  106.             }
  107.             return str;
  108.         }
  109.  
  110.         public int nextInt() {
  111.             return Integer.parseInt(next());
  112.         }
  113.  
  114.         public long nextLong() {
  115.             return Long.parseLong(next());
  116.         }
  117.  
  118.         public Double nextDouble() {
  119.             return Double.parseDouble(next());
  120.         }
  121.  
  122.         public BigInteger nextBigInteger() {
  123.             return new BigInteger(next());
  124.         }
  125.     }
  126. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/55175
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号