第十二届蓝桥杯 2021年国赛真题 (Java 大学B组)
蓝桥杯 2021年国赛真题（Java 大学 B 组 ）
-
#A 整数范围
-
#B 纯质数
-
- 预备知识
- 朴素解法
- 按位枚举
-
#C 完全日期
-
- Java党的完全胜利
- 朴素解法
- 朴素改进
- 不依赖 API 的实现
-
#D 最小权值
-
- 记忆化搜索
- 动态规划
-
#E 大写
-
#F 123
-
- 前缀和
-
#G 和与乘积
-
- 优雅骗分
- 前缀和
-
#H 巧克力
-
- 贪心算法
- 并查集优化
- 贪心 + 大根堆
-
#I 翻转括号序列
-
- 线段树
-
#J 异或三角
-
- 线性递推
- 组合数学
认真整下，不嘻嘻哈哈了。
#A 整数范围
本题总分：5 分
问题描述
用 8 位二进制形式（即一个字节）来用于表示非负整数时，则其最小可能取值为 0。那么通常能表示的最大数值是多少？
答案提交
这是一道结果填空型的题目；答题者只需计算出正确答案并提交即可完成作答过程；本题的答案是一个整数值；回答时只需提供该整数值即可；在提交答案时只填写这个整数值将被接受；填写多余的内容可能导致评分扣分或被忽略。
255
calcCode：
public class Test {
public static void main(String[] args) {
System.out.print(0xFF);
}
}?
#B 纯质数
本题总分：5 分
问题描述
被称为质数（素数）的正整数仅限于那些只有 1 和自身两个约数的数字。
前面提到的一些质数值包括：
\{2,\;3,\;5,\;7,\;{\\!}^{+}\!+\!+\!+\!+\!+\!+\!+\!}
等等。
被称为纯质數的是那些所有十進制位上的數字均为單一位素數值的質数值。
具體來說：
等都属于純質數，
而像 等则不属于純質數；
當然啦，
在區間 [?] 到 [?] 內共有多少個這樣的素數值呢？
答案提交
这种类型的题目需要考生仅计算得出答案并提交。题目要求考生只需计算出最终结果后进行提交操作即可完成作答过程。本题的答案是一个整数，在作答时应仅填写该数值而不添加其他内容以避免影响最终得分
1903
预备知识
如果不会一种合数筛法的，估计跑到比赛结束结果都出不来。
质数打表，
就是为了这点题解，
我才写的这篇博客。
就是为了这篇博客，
我才立的这个标题。
朴素解法
一个简单直接的想法，在列表中 [1,20210605] 内的质数时段内，补充性地执行纯质数检验，并将检验结果累加起来。
import java.util.ArrayList;
import java.util.List;
public class Test {
public static final int N = 20210605;
public static void main(String[] args) {
boolean[] marked = new boolean[N + 1];
List<Integer> primes = new ArrayList();
marked[0] = marked[1] = true;
int ans = 0;
for (int i = 2; i <= N; i++) {
if (!marked[i]) {
primes.add(i);
boolean flag = false;
for (int k = i; k > 0; k /= 10)
if (flag = marked[k % 10]) break;
if (!flag) ans++;
}
for (int p : primes) {
if (p * i > N) break;
marked[p * i] = true;
if (i % p == 0) break;
}
}
System.out.println(ans);
}
}按位枚举
由于传统方法存在许多不必要的步骤，在区间 [0,10) 内仅存在 2、3、5 和 7 这四个质数。如果我们专注于由这四个数字组成的数值进行质数验证，则算法性能是否有进一步优化的空间？
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Test {
public static final int N = 20210605;
public static int[][] digits = new int[8][4];
public static void main(String[] args) {
boolean[] primes = new boolean[N + 1];
List<Integer> helper = new ArrayList();
Arrays.fill(primes, 2, N, true);
int ans = 0;
for (int i = 2; i <= N; i++) {
if (primes[i]) helper.add(i);
for (int p : helper) {
if (p * i > N) break;
primes[p * i] = false;
if (i % p == 0) break;
}
}
digits[0] = new int[]{2, 3, 5, 7};
for (int k = 1; k < 7; k++)
for (int i = 0; i < 4; i++)
digits[k][i] = digits[k - 1][i] * 10;
digits[7] = new int[]{ digits[6][0] * 10 };
System.out.println(dfs(primes, 0, 0));
}
public static int dfs(boolean[] primes, int k, int depth) {
if (depth == 8) return k <= N && primes[k] ? 1 : 0;
int ans = primes[k] ? 1 : 0;
for (int a : digits[depth])
ans += dfs(primes, k + a, depth + 1);
return ans;
}
}实际上性能并没有进一步的提升，并且代码量还有所增加。
因为质数在区间 (1,N] 内的大致数量为 \cfrac{N}{\ln N} 个，在这种情况下由位组成的可能构成纯质数的数量约为 4^{\ln N} 个。这一数量显然不属于显著增长的范畴。
这段代码被放置在这里，是为了进一步帮助未进行充分刷题的读者拓展解题思路，并掌握解决类似问题的方法。
#C 完全日期
本题总分：10 分
问题描述
我们称，在某一天（由年、月、日组成的）其各数字之和若为一完美平方数，则称该天为一个完美日子。
答案提交
此题为一种只需计算得出结果并进行上交操作的任务；该任务的答案是一个整数；在回答时只需提供该整数值；任何附加信息均无法获得分数
977
Java党的完全胜利
LocalDate好用。
朴素解法
枚举 [2001-01-01，2021-12-31] 这个区间间内的时间，判断然后累加。
import java.time.LocalDate;
public class Test {
public static final int maxPerfect = 2 + 0 + 1 + 9 + 0 + 9 + 2 + 9;
public static final boolean[] perfect = new boolean[maxPerfect + 1];
public static LocalDate start = LocalDate.of(2001, 01, 01);
public static LocalDate end = LocalDate.of(2021, 12, 31);
public static void main(String[] args) {
int count = 0;
for (int i = 1; i * i<= maxPerfect; i++)
perfect[i * i] = true;
while (end.compareTo(start) >= 0) {
if (perfect[calc(start)])
count++;
start = start.plusDays(1);
}
System.out.println(count);
}
public static int calc(LocalDate date) {
String dateStr = date.toString();
int res = 0;
for (int i = dateStr.length() - 1; i >= 0; i--)
if (Character.isDigit(dateStr.charAt(i)))
res += Character.digit(dateStr.charAt(i), 10);
return res;
}
}朴素改进
在时间段[2001-01-01至2021-12-31]内，在这段时间内各数字之和不仅有极大值（计算结果为）：即每一位数字相加得到的结果的最大总和是32；还有极小值（计算结果为）：即每一位数字相加得到的结果的最小总和是4；这表明可能的完全平方数仅限于以下三种情况：即完全平方数只能是边长为3、4、5的情况；基于这一点我们可以简化我们的代码逻辑。
import java.time.LocalDate;
public class Test {
public static LocalDate start = LocalDate.of(2001, 01, 01);
public static LocalDate end = LocalDate.of(2021, 12, 31);
public static void main(String[] args) {
int count = 0;
while (end.compareTo(start) >= 0) {
if (isPerfect(start)) count++;
start = start.plusDays(1);
}
System.out.println(count);
}
public static boolean isPerfect(LocalDate date) {
String dateStr = date.toString();
int sum = 0;
for (int i = dateStr.length() - 1; i >= 0; i--)
if (Character.isDigit(dateStr.charAt(i)))
sum += Character.digit(dateStr.charAt(i), 10);
return sum == 3 * 3 || sum == 4 * 4 || sum == 5 * 5;
}
}不依赖 API 的实现
统计各数位之和在每年各个月份中出现的次数，在每年份中进行相应的判断以确定该年份是否为闰年
public class Test {
public static void main(String[] args) {
int[] bigMonth = { 1, 3, 5, 7, 8, 1 + 0, 1 + 2 };
int[] smallMonth = { 4, 6, 9, 1 + 1 };
int[] calendar = new int[9 + 2 + 9 + 1];
int ans = 0;
for (int day = 1; day <= 31; day++)
for (int month : bigMonth)
calendar[month + calc(day)]++;
for (int day = 1; day <= 30; day++)
for (int month : smallMonth)
calendar[month + calc(day)]++;
for (int day = 1; day <= 28; day++)
calendar[2 + calc(day)]++;
for (int year = 2001; year <= 2021; year++) {
if (isLeapYear(year))
if (isLeapYear(year + 2 + 2 + 9)) ans++;
for (int i = 0; i < calendar.length; i++) {
if (calendar[i] == 0) continue;
if (isPerfect(calc(year) + i))
ans += calendar[i];
}
}
System.out.println(ans);
}
public static int calc(int n) {
int res = 0;
do
res += n % 10;
while ((n /= 10) > 0);
return res;
}
public static boolean isPerfect(int num) { return num == 3 * 3 || num == 4 * 4 || num == 5 * 5; }
public static boolean isLeapYear(int year) { return year % 100 == 0 ? year % 400 == 0 : year % 4 == 0; }
}#D 最小权值
本题总分：10 分
问题描述
考虑具有根节点的一棵二叉树 T，在其结构中各节点被赋予一种称为"权值"（weight）的数量指标 W(T)，其定义如下：当某棵子树为空时其对应的权值定义为零；而对于拥有左子树 L 和右子_tree R 的任一节点 v 来说，在此情况下其权重计算公式将基于以下参数进行综合考量：具体而言，
W(v)=1+2W(L)+3W(R)+(C(L))²×C(R)，其中 C(X) 表示 X 子_tree 中所包含的具体节点数量。
其中该节点对应的整体权值即为其数值。
为了探究这一问题的答案
答案提交
此题属于结果填空类题目，请答题者只需计算得出答案后进行提交操作。该题目所得的结果是一个单一的整数值，在作答完成后的提交流程中，请仅输出该整数值。任何附加的信息或内容均不会被计入最终评分体系中。
2653631372
记忆化搜索
那可真蠢
这题就是把动规两个字放在了题面上，没什么好说的。
public class Test {
public static final int N = 2021;
public static long[] map = new long[N + 1];
public static void main(String[] args) { System.out.println(dfs(N)); }
public static long dfs(int TSize) {
if (TSize == 0 || map[TSize] != 0) return map[TSize];
long TWeight = Long.MAX_VALUE;
for (int LC = 0; LC < TSize; LC++) {
int RC = TSize - LC - 1;
long weight =
1 + 2 * dfs(LC) + 3 * dfs(RC) + LC * LC * RC;
TWeight = Math.min(TWeight, weight);
}
return map[TSize] = TWeight;
}
}动态规划
根据题意，显然有 N = 2021，W(0) = 0，W(N) = \min \{1 + 2W(L) + 3W(R) + (C(L))^{2}C(R)\}，其中 L + R = N - 1，0 \leq L \leq R \leq N。
状态转移方程显而易见：dp(y)=\left\{ begin{array}{lr} 0 & 当i=0时\\ 求解过程涉及最小化{,1 + 2dp(l) + 3dp(r) + l^{2}r,} & 其中满足条件l+r=i-1且0 ≤ l ≤ r ≤ i时的值。 end{array} ight. 明确无疑。
public class Test {
public static final int N = 2021;
public static void main(String[] args) {
long[] dp = new long[N + 1];
for (int i = 1; i <= N; i++) {
dp[i] = Long.MAX_VALUE;
for (int l = i >> 1; l >= 0; l--)
dp[i] = Math.min(dp[i],
1 + 2 * dp[l] + 3 * dp[i - l - 1] + l * l * (i - l - 1));
}
System.out.println(dp[N]);
}
}#E 大写
时间限制: 1.0s 内存限制: 512.0MB 本题总分：15分
问题描述
对于仅包含大小写字母的一个字符串，请将其所有的小写字母转译为大写字母并输出该字符串。
输入格式
输入一行包含一个字符串。
输出格式
输出转换成大写后的字符串。
测试样例 1
Input：
LanQiao
Output：
LANQIAO评测用例规模与约定
对于所有评测用例，字符串的长度不超过 100。
code：
public class Main {
public static void main(String[] args) {
System.out.println(new java.util.Scanner(System.in).next().toUpperCase());
}
}送分。
#F 123
时间限制: 5.0s 内存限制: 512.0MB 本题总分：15分
问题描述
小蓝发现了有趣的一个数列。观察到该数列最初的几项排列如下：
1,\quad 1,\;2,\quad 1,\;2,\;3,\quad 1,\;2,\;3,\;4,\quad \dots
进一步分析可得：
随后每n组包含从数字\mathbf{1}递增到n+（\mathbf{第n}组）。
例如：
随后每组的第一位都是数字\mathbf{1}；
随后每组包含从数字\mathbf{1}递增到n的序列；
以此类推。
为了计算该序列中任意一段连续数值之和，
需要明确具体的求和区间范围。
输入格式
第一行输入一个整数值T用于表示询问的总数量。随后有T组数据每组数据包含两个整数值l_i和r_i分别用于表示询问区间起点位置和区间终点位置
输出格式
输出 T 行，每行包含一个整数表示对应询问的答案。
测试样例 1
Input：
3
1 1
1 3
5 8
Output：
1
4
8评测用例规模与约定
占总测试用例的 1\% 的情况下，
其中变量 T 满足 T ∈ [1, 3]，
同时满足条件的变量 l_i 和 r_i 满足 l_i ≤ r_i ≤ 5^2 =25
；
占总测试用例的 5\%
的情况下，
其中变量 T 满足 T ∈ [4,7]，
同时满足条件的变量 l_i 和 r_i 满足
l_i ≤ r_i ≤5^4=625
；
其余情况均需满足
l_{i}≤r_{i}。
前缀和
处理区间和的问题时，默认会采用前缀和的方法。然而，在本题中所给的区间范围极为宽广以至于用全部的内存来存放前缀和这会导致内存占用过高能满足条件的有效用例数量仅有一半左右因此这里要将原序列\pmb[1,1,2,1,2,3,1,\ \cdots,n-1,n\pmb]变形为矩阵\begin{bmatrix}1\\ 1&2\\ 1&2&3\\ \vdots&\vdots&\vdots&\ddots\\ 1&2&3&\cdots&n\end{bmatrix}这样我们就可以高效地处理从[1, 10^{12}]之间的各种查询需求n取n = \sqrt{2E}.
对于经过变形处理后的序列矩阵，在计算每一列及最后一行的前缀和后并进行组合，在对数时间复杂度内就可以快速得到区间 [1,k] 内所有元素的总和（其中k属于[1,10^12]这个范围）。针对任意区间求和问题 \sum_{i = l}^{r} a_{i} ，我们可以通过转换为 \sum_{i = 1}^{r} a_{i} - \sum_{i = 1}^{l - 1} a_{i} 来解决该问题。
还有就是溢出问题，形如这种矩阵，在最大元素为 n 时，其矩阵元素和为 n + 2(n - 1) + 3(n - 2) + \cdots + n 。
=n(1 +2+3+\cdots+n)-n(1×2+2×3+3×4+\cdots+(n - 1)n)
=\cfrac{n^{2}(n-1)}{2} - (1^2+1 + 2^2 + 2 + 3^2 +\cdots +(n - 1)^2 + n - 1)
=\cfrac{n^{2}(n-1)}{2} - \{(1^2 + 2^2 + 3^2 +\cdots +(n - 1)^2) + (1 + 2 + 3 + \cdots + n - 1)\}
=\cfrac{n^{2}(n-1)}{2} - \cfrac{n(n - 1)(2n - 1)}{6}-\cfrac{n(n-1)}{2}
取 n 为 \sqrt{2E12}，矩阵元素和约为 4.7E17，长整形够用。
code:
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) { new Main().run(); }
int N = (int)Math.sqrt(2E12) + 1;
long[] row = new long[N + 1], col = new long[N + 1];
void run() {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
for (int i = 1; i <= N; i++) {
row[i] = i + row[i - 1];
col[i] = col[i - 1] + row[i];
}
int T = in.readInt();
long l, r;
while (T-- > 0) {
l = in.readLong();
r = in.readLong();
out.println(sum(r) - sum(l - 1));
}
out.flush();
}
long sum(long r) {
int k = lowerBound(r);
return r == row[k] ? col[k] : col[k - 1] + row[(int)(r - row[k - 1])];
}
int lowerBound(long k) {
int offset = 0, length = N + 1;
while (length > 0) {
int half = length >> 1;
if (k > row[offset + half]) {
offset += half + 1;
length -= half + 1;
} else length = half;
}
return offset;
}
class InputReader {
BufferedReader reader;
StringTokenizer token;
InputReader(InputStream in) {
this.reader = new BufferedReader(new InputStreamReader(in));
}
String read() {
while (token == null || !token.hasMoreTokens()) {
try {
token = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return token.nextToken();
}
int readInt() { return Integer.parseInt(read()); }
long readLong() { return Long.parseLong(read()); }
}
}#G 和与乘积
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20分
问题描述
设有一个数列 A = (a_1, a_2, \dots, a_n)。探讨有多少个区间 [L, R] 满足该区间的元素乘积等于其元素之和即 a_L \cdot a_{L+1} \cdots \cdot a_R = a_L + a_{L+1} + \cdots + a_R。
输入格式
在输入的第一行中存在一个整数值 n ，该值代表序列的长度。在第二行中有n个整数值。这些整数值按照顺序排列为a_{1}, a_{2}, \cdots, a_{n}。
输出格式
输出仅一行，包含一个整数表示满足如上条件的区间的个数。
测试样例 1
Input：
4
1 3 2 2
Output：
6
Explanation：
符合条件的区间为 [1, 1], [1, 3], [2, 2], [3, 3], [3, 4], [4, 4]。评测用例规模与约定
针对 2\%_{}^{}\textsuperscript{注：此处应为"2%"}的评测样本集n\textsubscript{}}_{}{}$\textsuperscript{注：此处应为"n"}中$n\textsubscript{}}_{}{}\textless=\textgreater=3,!{\rm k}（即n\textless=\textgreater=3\times{1{\rm e}+3}），以及另一组规模更大的测试集n\textless=\textgreater=5\times{1{\rm e}+4}$等情形下进行评估
优雅骗分
推了一天，啥也没推出来，放弃了。
当我们遇到基于简单思路导致的时间复杂度为O(n^2)的问题时，一种可能的方法是选择一个不可能存在的元素来进行二分操作。假设该关键点位于序列中的第m个位置，则进行二分操作后的时间复杂度将变为O(m^2 + (n - m)^2)。
从理论上讲，在m值最小且各点分布极其均匀的情况下，采用该方法进行拆分能够使计算复杂度降至O(n \log n)水平或更低。
在 a_{L} · a_{L+1} \cdots · a_{R} = a_{L} + a_{L+1} + \cdots + a_{R} 这个表达式中，若 R - L >1 的情况，两边必为合数。
对于任意区间 a_{L} · a_{L+1} \cdots · a_{R} 中存在一个足够大的质数 p 的情况而言，在这种情况下其可能性接近于零的情况即对于任意选取的一些 (0,2×10^{5}] 间的自然数来说这些自然数之和被该质数 p 整除的概率趋近于零
难以计算啊！即便如此也不足为惧！我们有此等分法可将原序列划分为若干个互不干扰的子序列。
运气好就A了。
import java.io.*;
import java.util.List;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) { new Main().run(); }
final int N = 200000, p = 131;
void run() {
InputReader in = new InputReader(System.in);
int n = in.readInt(), ans = n;
int[] A = new int[n];
for (int i = 0; i < n; i++)
A[i] = in.readInt();
if (n > 0xC60) {
boolean[] compos = new boolean[N + 1];
List<Integer> prime = new ArrayList();
compos[1] = true;
for (int i = 2; i <= N; i++) {
if (!compos[i]) prime.add(i);
for (int p : prime) {
if (p * i > n) break;
compos[p * i] = true;
if (i % p == 0)break;
}
}
for (int i = 0, j = 0; i < n; i = j++) {
while (j < n && (compos[A[i]] || A[i] >= p)) j++;
ans += calc(A, i, j - i);
}
} else ans += calc(A, 0, n);
System.out.println(ans);
}
int calc(int[] A, int offset, int length) {
int ans = 0;
long sum, product;
for (int i = 0; i < length; i++) {
sum = product = A[offset + i];
for (int j = i + 1; j < length; j++) {
product = multi(product, A[offset + j]);
if (product < 0) break;
sum += A[offset + j];
if (sum == product)
ans++;
}
}
return ans;
}
long multi(long arg0, long arg1) {
long product = arg0 * arg1;
return product / arg1 == arg0 ? product : -1;
}
class InputReader {
BufferedReader reader;
StringTokenizer token;
InputReader(InputStream in) {
this.reader = new BufferedReader(new InputStreamReader(in));
}
String read() {
while (token == null || !token.hasMoreTokens()) {
try {
token = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return token.nextToken();
}
int readInt() { return Integer.parseInt(read()); }
}
}给这题锤的神志不清了，有无大哥指点一下迷津。
前缀和
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) { new Main().run(); }
void run() {
InputReader in = new InputReader(System.in);
int n = in.readInt(), ans = n, N = 1, a;
long[] A = new long[n + 1];
long[] S = new long[n + 1];
int[] O = new int[n + 2];
for (int i = 0; i < n; i++) {
a = in.readInt();
if (a == 1) {
S[N]++;
O[N]++;
} else {
S[N] += S[N - 1] + a;
A[N++] = a;
}
}
long max = S[N - 1] + O[N];
for (int i = 1; i < N; i++) {
long pro = A[i];
for (int j = i + 1; j < N; j++) {
pro *= A[j];
if (pro > max) break;
long dif = pro - S[j] + S[i - 1] + O[i];
if (dif == 0) ans++;
else if (dif > 0 && O[i] + O[j + 1] >= dif) {
long l = Math.min(dif, O[i]);
long r = Math.min(dif, O[j + 1]);
ans += l + r - dif + 1;
}
}
}
System.out.println(ans);
}
class InputReader {
BufferedReader reader;
StringTokenizer token;
InputReader(InputStream in) { this.reader = new BufferedReader(new InputStreamReader(in)); }
String read() {
while (token == null || !token.hasMoreTokens())
try {
token = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return token.nextToken();
}
int readInt() { return Integer.parseInt(read()); }
}
}#H 巧克力
时间限制: 1.0s 内存限制: 512.0MB 本题总分：20分
问题描述
小蓝对巧克力情有独钟,他每天都必须消费一块巧克力.某天小蓝前往超市打算购买若干块巧克力.货架上摆满了种类繁多的巧克力,每种规格都有其固定价格、库存数量以及剩余的有效期限.为了保证连续食用不出现中断的情况,请问购买满足 x 天需求所需的最低费用是多少?
输入格式
程序的第一行接收两个整数x, n作为输入参数。这两个参数分别代表吃巧克力所需的总天数以及不同种类巧克力的数量。接下来将详细列出货架上的各种巧克力信息。每个编号为i的条目都包含三个关键数据：该种巧克力的价格a_i、保质期剩余时间b_i(从当前时刻起还有b_i天可食用)以及库存数量c_i.
输出格式
请输出一个整数值表示小蓝所需的最小花费。如果不存在让小蓝吃 x 天的购买方案，请输出 −1
测试样例 1
Input：
10 3
1 6 5
2 7 3
3 10 10
Output：
18
Explanation：
一种最佳的方案是第 1 种买 5 块，第 2 种买 2 块，第 3 种买 3 块。前 5 天吃第 1 种，第 6、7 天吃第 2 种，第 8 至 10 天吃第 3 种。评测用例规模与约定
对于 30% 的评测用例，n, x \leq 1000。
对于所有评测用例，1 \leq n, x \leq 100000，1 \leq a_{i}, b_{i}, c_{i} \leq 10^{9}。
贪心算法
首先选择价格最低的巧克力，在吃完当前种类后才开始下一种。继续这个过程直到已经过去了 x 天或者没有可选的其他巧克力了。
为了简明扼要地证明这一点，请考虑以下情况：假设存在一块价格低于现有方案中每一块巧克力的巧克力。将该巧克力插入到任意可行位置时都会导致总花费减少。因此应当按照价格由低到高的顺序安排这些巧克力。
然后就是，在选定一个日期下的巧克力时要尽量不影响后面的选项选择，在这一时间段内最便宜的巧克力保质期区间内只会包含两种情况：当前可选项与后续选项都存在的情况；以及当前可选项存在而后续选项不存在的情况。显然，在前一种情况下选择当前选项更为优胜，在后一种情况下距离保质期结束时间越近则对后续选项的影响就越小。
狗屁不通真就那个论证失败但合理能让代码跑过样例。
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) { new Main().run(); }
void run() {
InputReader in = new InputReader(System.in);
int x = in.readInt(), n = in.readInt();
boolean[] calender = new boolean[x + 1];
int[][] chocos = new int[n][3];
long ans = 0, marked = 0;
for (int i = 0; i < n; i++) {
chocos[i][0] = in.readInt();
chocos[i][1] =
min(x, in.readInt());
chocos[i][2] = in.readInt();
}
Arrays.sort(chocos,
(a1, a2)->(a1[0] - a2[0]));
for (int[] choco : chocos)
while (choco[1] > 0 && choco[2] > 0) {
if (!calender[choco[1]]) {
calender[choco[1]] = true;
ans += choco[0];
choco[2]--;
marked++;
}
choco[1]--;
}
System.out.println(marked == x ? ans : -1);
}
int min(int a, int b) { return a < b ? a : b; }
class InputReader {
BufferedReader reader;
StringTokenizer token;
InputReader(InputStream in) {
this.reader = new BufferedReader(new InputStreamReader(in));
}
String read() {
while (token == null || !token.hasMoreTokens()) {
try {
token = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return token.nextToken();
}
int readInt() { return Integer.parseInt(read()); }
}
}但是基于贪心算法来解决这一类问题时，在这种情况下采用这样的方法可能会遇到效率上的限制。计算得到的时间复杂度为 O(n \log n + n \max(b_i, x)) ，其计算复杂度大致相当于 O(n^2) 在这种数据分布情况下 。因此，在这种数据规律下仍然存在明显的优化空间
不过这种动态更新标记，查找最小可用，这和一个常用数据结构很契合。
并查集优化
在确定好贪心策略之后，在程序运行过程中发现了一个显著的性能瓶颈。这个瓶颈主要体现在找出保质期内剩余未规划的巧克力数量上。
当我们将一个按照顺序排列的时间序列按照原顺序形成一个链表结构时，在链头超过1次的情况下，其左侧元素即为目标数值。
并且无需关注这种组织方式下的其余相关信息。仅凭上述信息即可实现对整个查找操作的优化，并查集即可完成这项任务。
并且在路径压缩的基础上，这个操作的时间复杂程度只有 O(1)。
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) { new Main().run(); }
int[] link;
void run() {
InputReader in = new InputReader(System.in);
int x = in.readInt(), n = in.readInt();
int[][] chocos = new int[n][3];
long ans = 0, marked = 0;
link = new int[x + 1];
for (int i = 0; i < n; i++) {
chocos[i][0] = in.readInt();
chocos[i][1] =
min(x, in.readInt());
chocos[i][2] = in.readInt();
}
Arrays.fill(link, -1);
Arrays.sort(chocos,
(a1, a2)->(a1[0] - a2[0]));
for (int[] choco : chocos)
while (choco[2]-- > 0) {
int d = find(choco[1]);
if (d > 0) {
link[d] = d - 1;
ans += choco[0];
marked++;
} else break;
}
System.out.println(marked == x ? ans : -1);
}
int find(int x) { return link[x] == -1 ? x : (link[x] = find(link[x])); }
int min(int a, int b) { return a < b ? a : b; }
class InputReader {
BufferedReader reader;
StringTokenizer token;
InputReader(InputStream in) {
this.reader = new BufferedReader(new InputStreamReader(in));
}
String read() {
while (token == null || !token.hasMoreTokens()) {
try {
token = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return token.nextToken();
}
int readInt() { return Integer.parseInt(read()); }
}
}时间复杂度为 O(n \log n + n + x)，即 O(n \log n)。
当然这里影响运行速度的参数不止 n 一个，
能力有限，这里不做过多的讨论。
贪心 + 大根堆
为了能够有效地限制除了变量 n 外的所有变量对程序整体运行时间的影响, 我们需要以种而非块的方式来安排巧克力的布局.
在该贪心策略实施的过程中，在实际操作中可能会遇到待安排的时间段存在间断性的问题。如果采用分段查找的方法来安排可用时间段，则可能导致的成本显著高于之前的方案。额外增加的代码量直接导致了调试难度和成本上升。
便捷地再次想到一种策略，在未选择变质巧克力的情况下，则应最大限度地选择价格最低的 d 个巧克力。
对此我们可以按保质期升序考虑每种巧克力，动态的维护选择方案。
更详细的说：
建立一个以价格为权值的大根堆，该堆代表已选中的巧克力，堆初始为空。
按保质期升序枚举巧克力的种类，枚举时会遇见两种情况：
1、当前巧克力数量 + 当前已选巧克力数量 \leq 当前巧克力保质期
这时我们视为选择当前巧克力，直接将其插入到堆里。
2、当前巧克力数量 + 当前已选巧克力数量 > 当前巧克力保质期
我们首先计算两个不等式两边绝对值之差；接着从堆中取出所有价格高于当前巧克力的价格，并满足数量不超过该差异；随后插入对应种类的数量（即与前一次选择相同的），使已选巧克力总数等于保质期天数。
可以看出，在假设没有将第d最便宜的巧克力加入到第d天方案中时，则意味着在该巧克力保质期内存在比它更便宜的选择使得其无法被选中。因此，在这种贪心策略下得出的结果是最佳选择。
最终，堆内的巧克力就是最优的选择方案。
当然，它可能排不满 x 天。
\ 不想写#I 翻转括号序列
时间限制: 10.0s 内存限制: 768.0MB 本题总分：25分
问题描述
设长度为n的括号序列为基准，并支持以下两种操作：
- 将区间[L_i, R_i]内的所有字符进行翻转（即将左括号变为右括号、右括号变为左括号）。
- 并确定起始点L_i时所能形成的最长合法子串对应的结束位置。
输入格式
程序的第一行读取两个整数n, m，其中n代表括号序列的总长度而m则表示后续的操作次数。在接下来的第二行中给出具体的括号序列内容，并根据不同的操作类型执行相应的处理：当行为类型为第一类时（记为1\ L_{i}\ R_{i}），系统将对该区间内的所有字符进行处理；而当行为类型为第二类时（记为2\ L_{i}），系统仅对该区间的起始位置进行处理以完成特定任务。
输出格式
对于每一个第二种操作，请生成一条输出记录对应于其相应的 R_i；若未找到对应的 R_i ，则记录为零。
测试样例 1
Input：
7 5
((())()
2 3
2 2
1 3 5
2 3
2 1
Output：
4
7
0
0评测用例规模与约定
在 2\,\% 的测试案例中，在变量 n,m\leq 5\times{1e}^{3} 范围内；
在 4\,\% 的测试案例中，在变量 n,m\leq 3\times{1e}^{4} 范围内；
在 6\,\% 的测试案例中，在变量 n,m\leq{1e}^{5} 范围内；
针对所有测试案例而言，则有约束条件：变量 n\in[1,{1e}^6] 和变量 m\in[1,{2\times{1e}^5}]
线段树
对于一个合法的括号序列，
该程序以'( ('开始，并利用栈结构来判断给定的序列是否构成有效的单调序列。其中栈仅存储'( ('中的字符，在遍历时遇到字符'( ('则将其推入栈中。当遇到字符') )('时若此时栈为空，则判定该序列为非法；否则弹出当前最顶端的字符（即'( ('），继续下一次匹配操作。如果遍历结束后栈已空，则该序列为有效；反之则无效。
通过分析可知，在括号匹配机制中，“(**”会对栈操作产生正向影响，在入栈操作时会增加栈深度（其对栈操作的影响是+1），而对应的“)”则会减少栈深度（其对栈操作的影响是-1）。任何合法有效的括号序列在执行至栈空时永远不会遇到无法匹配的情况。
我们可以用括号序列构建 \pm1 序列，并计算出它的前缀和数组 sum。
基于前面所述的性质，在一个括号序列中满足以下两个条件：一是区间端点处累积和相等（即sum[L - 1] = sum[R]），二是对于区间内的所有位置m来说有sum[m] \ge sum[L - 1]。同时也要证明其必要性。
若满足特定条件，则区间内的累加值 \sum_{L}^{R} 必然包含一个极大值 \sum_{k}；由此可知，在原始括号序列中第k位必定是左开括号 '(**' 。这是因为当k是一个极大值时，则有 \sum_{k+1} = \sum_{k} - 1 ，因此原始括号序列在第k+1位必然是右闭合括号 '*)' 。由此可知 \langle k, k+1 \rangle 形成了一个有效的匹配子串；将其从整体中删除后，则问题可简化为此子串之前的字符与之后的字符之间的匹配问题；如果存在多个极大值，则应同时删除所有对应的匹配子串；反复执行此操作直至整个字符串被完全消除
证毕。
现在的问题转化为寻找区间最小值的问题。当动态维护一个线段树时，在这种情况下，我们可以利用懒标记来优化区间反转操作。
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) { new Main().run(); }
void run() {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
int n = in.readInt(), m = in.readInt();
String str = in.read();
int[] sum = new int[n + 1];
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + (str.charAt(i - 1) == '(' ? 1 : -1);
Tree tree = new Tree(sum);
int c = 1;
while (m-- > 0) {
int q = in.readInt(), L, R, ans;
if (q == 1) {
L = in.readInt();
R = in.readInt();
tree.turn(L, R);
} else {
L = in.readInt();
int key = (L == 1 ? 0 : tree.query(L - 1));
ans = tree.firstLower(L, n, key);
ans = ans == 0 ? n : ans - 1;
ans = tree.lastLower(L, ans, key + 1);
out.println(ans == L ? 0 : ans);
}
}
out.flush();
}
class Tree {
int size;
Node root;
Tree(int[] values) { root = build(1, size = values.length - 1, values); }
void update(int L, int R, int[][] matrix, Node node) {
if (node.L >= L && node.R <= R) node.tag(matrix);
else {
pushDown(node);
if (node.left.R >= L) update(L, R, matrix, node.left);
if (node.right.L <= R) update(L, R, matrix, node.right);
pushUp(node);
}
}
int query(int index) { return query(index, root); }
int query(int index, Node node) {
if (node.L == node.R) return node.max;
else {
pushDown(node);
int res = query(index, node.left.R >= index ? node.left : node.right);
pushUp(node);
return res;
}
}
int[][] T = {{-1, 0}, {0, 1}};
void turn(int L, int R) {
if (L > 1) {
update(1, L - 1, T, root);
int k = query(L - 1);
update(L, size, new int[][]{{1, 0}, {2 * k, 1}}, root);
}
update(1, R, T, root);
if (R < size) {
int k = query(R);
update(R + 1, size, new int[][]{{1, 0}, {2 * k, 1}}, root);
}
}
int firstLower(int L, int R, int key) { return firstLower(L, R, key, root); }
int firstLower(int L, int R, int key, Node node) {
if (node.L == node.R) return node.L;
else {
int res = 0;
pushDown(node);
if (node.left.R >= L && node.left.min() < key)
res = firstLower(L, R, key, node.left);
if (res == 0 && node.right.L <= R && node.right.min() < key)
res = firstLower(L, R, key, node.right);
pushUp(node);
return res;
}
}
int lastLower(int L, int R, int key) { return lastLower(L, R, key, root); }
int lastLower(int L, int R, int key, Node node) {
if (node.L == node.R) return node.L;
else {
int res = 0;
pushDown(node);
if (node.right.L <= R && node.right.min() < key)
res = lastLower(L, R, key, node.right);
if (res == 0 && node.left.R >= L && node.left.min() < key)
res = lastLower(L, R, key, node.left);
pushUp(node);
return res;
}
}
void pushUp(Node node) {
node.max = max(node.left.max(), node.right.max());
node.min = min(node.left.min(), node.right.min());
}
void pushDown(Node node) {
if (node.lazy != null) {
node.left.tag(node.lazy);
node.right.tag(node.lazy);
node.lazy = null;
}
}
Node build(int L, int R, int[] values) {
if (L == R) return new Node(L, values[L]);
else {
Node node = new Node();
int mid = L + R >> 1;
node.left = build(L, mid, values);
node.right = build(mid + 1, R, values);
pushUp(node);
node.L = L;
node.R = R;
return node;
}
}
int max(int arg1, int arg2) { return arg1 > arg2 ? arg1 : arg2; }
int min(int arg1, int arg2) { return arg1 < arg2 ? arg1 : arg2; }
class Node {
Node left, right;
int max, min;
int[][] lazy;
int L, R;
Node() { super(); }
Node(int index, int value) {
max = min = value;
L = R = index;
}
int max() { return max > min ? max : min; }
int min() { return max < min ? max : min; }
void tag(int[][] matrix) {
if (lazy == null) lazy = matrix;
else {
int[][] A = new int[2][2];
A[0][0] = lazy[0][0] * matrix[0][0] + lazy[0][1] * matrix[1][0];
A[0][1] = lazy[0][0] * matrix[0][1] + lazy[0][1] * matrix[1][1];
A[1][0] = lazy[1][0] * matrix[0][0] + lazy[1][1] * matrix[1][0];
A[1][1] = lazy[1][0] * matrix[0][1] + lazy[1][1] * matrix[1][1];
lazy = A;
}
max = max * matrix[0][0] + matrix[1][0];
min = min * matrix[0][0] + matrix[1][0];
}
}
}
class InputReader {
BufferedReader reader;
StringTokenizer token;
InputReader(InputStream in) {
this.reader = new BufferedReader(new InputStreamReader(in));
}
String read() {
while (token == null || !token.hasMoreTokens()) {
try {
token = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return token.nextToken();
}
int readInt() { return Integer.parseInt(read()); }
long readLong() { return Long.parseLong(read()); }
}
}这题出的纯恶心选手。
#J 异或三角
时间限制: 5.0s 内存限制: 512.0MB 本题总分：25分
问题描述
设共有 T 个整数依次为 n_1, n_2, \dots, n_T. 对于每个整数n_i, 计算满足以下条件的数量:
- 对于所有整数a,b,c, 满足1 ≤ a,b,c ≤ ni;
- 整数a \bigoplus b \bigoplus c = 0, 其中\bigoplus表示二进制按位异或运算;
- 长度为a,b,c的三条边能够构成一个三角形.
输入格式
输入的第一行包含一个整数 T。
接下来 T 行每行一个整数，分别表示 n_{1}, n_{2}, · · · , n_{T}。
输出格式
输出 T 行，每行包含一个整数，表示对应的答案。
测试样例 1
Input：
2
6
114514
Output：
6
11223848130评测用例规模与约定
占总测试案例的十分之一中，
其中 T 等于 1, 并且每个测试案例中的变量满足条件：变量个数 ni 在区间 [L=4, R=8] 内。
占总测试案例的十分之一中，
其中 T 等于 3, 并且每个测试案例中的变量满足条件：变量个数 ni 在区间 [L=4, R=8] 内。
占总测试案例的五分之一中，
其中 T 等于 4, 并且每个测试案例中的变量满足条件：变量个数 ni 在区间 [L=4, R=8] 内。
占总测试案例的五分之三中，
其中 T 的取值范围是 [L=4, R=8], 而每个测试案例中的变量个数 ni 则满足条件：ni ∈ [4{},8{}]。
所有参与比较的测试案例中，
其中 T 的取值范围是 [L=4, R=8], 而每个测试案例中的变量个数 ni 则满足条件：ni ∈ [4{},8{}].
?这数据
线性递推
都线性了，那 40% 的 2^{30} 就不用想了。
先是要确定几个能帮助我们加快程序运行速度的性质。
该运算在对任意元素进行异或操作时满足自反性。
零元素在与自身进行异或操作时具有恒等性质。
由此可知，在本题中变量 a, b, c 必须互不相同。
对于最终计算出的方案数，
只需确保计算过程中满足变量 a, b, c
按降序排列，并将结果数量乘以阶乘三。
而 a < b + c 才能组成三角形，故需要满足 a = b \oplus c < b + c。
我们了解异或也叫作其别称，在基于模二运算的加法中使用；相当于在进行异或运算时，在二进制下执行加法操作而不考虑进位。
因此当 b 与 c 有任意一位同为 1 时，加法运算发生进位，不等式成立。
再考虑对任意 a 可能的方案数，
当a \geqslant 1\text{时}, 可知a\text{可表为}1x_{{\kern 0.5pt}1}x_{{\kern 0.5pt}2}\cdots x_{{\kern 0.5pt}m}\text{这类以}1\text{开头随后跟连续二进位串的形式}; 若要满足a > b > c, 则b\text{与}c\text{的二进位长度均不超过a\text{'s}}; 同理, 若a = b \oplus c, 则b\text{亦须具象化为上述形式之一};
因此 b 绝对大于 c，所以我们可以直接跳过对 c 的讨论。
基于以下条件限制，在分析c时发现其具有与b相同位1的充分必要条件是a在该位置为0。因此，在b < a的情况下，并且必须至少有一位二进制位与$a不同以确保这一特性得以保持。
依次筛选出所有满足条件 1y_{1}y_{2}\cdots y_{m} 的元素，并去除其中不符合特定性质的元素。
选择这个集合相当于增加一个去掉首位1后的二进制字符串，并从这个字符串中移除不符合特定性质的所有元素。这相当于从该字符串每一位所代表的2的幂次方中减去相应的值。
举个例子：
令 a = 67（因为二进制 1 为第一位） ，而整数 b > 64（二进制表示为 \texttt{1} 后面跟五位零） 。因此我们可以直接选择区间 [64,67)，即包含所有满足条件的元素。显然满足条件的集合大小为 2^{\texttt{countBit}(3)} ，其中 3 是二进制 3 中 '1' 的个数。
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) { new Main().run(); }
void run() {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
int T = in.readInt(), upper = 0;
int[] Q = new int[T];
for (int i = 0; i < T; i++)
upper = max(upper, Q[i] = in.readInt());
long[] A = new long[upper + 1];
for (int i = 1; i <= upper; i++) {
int b = i - highBit(i);
A[i] = A[i - 1] + b - (1 << countBit(b)) + 1;
}
for (int i = 0; i < T; i++)
out.println(6 * A[Q[i]]);
out.flush();
}
int highBit(int n) {
n |= (n >> 1);
n |= (n >> 2);
n |= (n >> 4);
n |= (n >> 8);
n |= (n >> 16);
return n - (n >>> 1);
}
int countBit(int n) {
n = n - ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
n = (n + (n >>> 4)) & 0x0f0f0f0f;
n += n >>> 8;
n += n >>> 16;
return n & 0x3f;
}
int max(int a, int b) { return a > b ? a : b; }
class InputReader {
BufferedReader reader;
StringTokenizer token;
InputReader(InputStream in) {
this.reader = new BufferedReader(new InputStreamReader(in));
}
String read() {
while (token == null || !token.hasMoreTokens()) {
try {
token = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return token.nextToken();
}
int readInt() { return Integer.parseInt(read()); }
}
}组合数学
根据上述递推，显然有对于每个询问 n_{i}，都有回答
\displaystyle\sum_{i = 1}^{n_{j}} (j + 1 - highBit(j) - 2^{countBit(j) - 1})，即
\cfrac{n_{i}(n_i + 3)}{2} - \displaystyle\sum_{j = 1}^{n_{i}} (highBit(j) + 2^{countBit(j) - 1})
对于每个 \displaystyle\sum_{j = 1}^{n_{i}} highBit(j)，都可以分解为
该表达式表示从k=1到\lfloor \log _{2} n_{i} \rfloor的累加求和，在每一个k范围内从j=2^{k-1}到2^{k}-1累加高比特(j)，然后再加上(n_{i}-n_{i}^{\lfloor \log _{2} n_{i}\rfloor }+1)乘以n_{i}取\lfloor \log _{2}\cdot\cdot\cdot\rfloor 后的高比特值
这个式子过于简单，这里便不再讨论，
为了更好地理解这一过程，在深入分析的基础上我们特别关注焦点在于以下关键公式：\displaystyle\sum_{j = 1}^{n_{i}} 2^{countBit(j) - 1} = \cfrac{\displaystyle\sum_{j = 1}^{n_{i}} 2^{countBit(j)}}{2} 。基于此基础，在后续的探讨中我们主要针对其分子部分展开分析，并相应地进行符号转换以简化运算过程
于是有公式 \displaystyle\sum_{i = 1}^{n} 2^{countBit(i)}
该表达式等于两个求和项之和：第一个求和项从i=1到i=2^k对每一项计算其二进制表示中'1'的数量取幂次方进行累加；第二个求和项从i=1到i=n-2^k对每一项计算其二进制表示中'1'的数量取幂次方并累加；其中k定义为n_i取以二为底的对数后再向下取整的结果
其中第二部分的所有i都满足i不超过2的k次方；从countBits函数的角度来看，在计算过程中有countBits(i + 2^k)等于号连接着countBits(i)加上1。
由此可见，在计算总和时可将其分解为两个部分：从i=1到i=2^k的部分与从i=1到n-2^k的部分乘以两倍。
而对于 n = 2^{k}，k \in N 的情况，我们可以对 [1,2^{k-1}] 做仿射变换到 [1,2^k]，同时映射出结果。
更详细的说，
定义正整数数集 N_{k} \in [1,2^{k}]，常量 A_{k} = \displaystyle\sum_{i = 1}^{N^{k}} 2^{countBit(i)}。
N_{0} = \{1\}，N_{k+1} 中的元素由 N_{k} 做 k = 2，b=\{0,1\} 的两次仿射变换而来，特殊的，2^k 映射为 1。
在集合N^{k}中不存在重复元素；同时，在仿射变换b=\{0,1\}下讨论两种情形时发现它们具有不同的奇偶性；这导致经过映射后得到的新集合N^{k+1}成为一个完美的集合。
显然地，在 2N^{k} + 0 的情况下（即当余数为零时），其结果与 A_{k} 完全一致）。而对于 2N^{k} + 1 的情形下（即当余数为一的时候），每一次执行特殊映射操作后产生的二进制数位长度为 2^k 位，并且每一位都为1。因此可得等式：2N^{k} + 1 = 2(A_{k} - 1) + 1
经过推导得出A_{k}满足以下关系式：A_{k}=3A_{k-1}-1=\sum\limits_{i=1}^{2^{k}}2^{\text{countBit}(i)}=\begin{cases} 1, & k=0 \\ 3\sum\limits_{i=1}^{2^{k-1}}2^{\text{countBit}(i)} -1, & k>0 \end{cases}
在此期间，我们归纳出一种能够在 O(\log n_{i}) 时间内完成计算该求和公式的算法框架，并进一步推导出一种能够在 O(\log n_{i}) 时间内完成计算的公式。
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) { new Main().run(); }
long[] highB = new long[0x20];
long[] countB = new long[0x20];
void run() {
InputReader in = new InputReader(System.in);
PrintWriter out = new PrintWriter(System.out);
int T = in.readInt(), n, m, k;
countB[0] = 1;
for (int i = 1; i < 0x20; i++) {
highB[i] = (highB[i - 1] << 2) | 1;
countB[i] = countB[i - 1] * 3 - 1;
}
while (T-- > 0) {
n = in.readInt();
k = floorLog2(n);
m = n - (1 << k);
out.println(6 * (
(n + 3L) * n / 2 -
(calcCountBit(n)) -
highB[k] - (m + 1L) * (1 << k)
));
}
out.flush();
}
long calcCountBit(int n) {
if (n == 0) return 0;
int m = highBit(n);
long ans = countB[floorLog2(m)];
if (n != m)
ans += calcCountBit(n - m) << 1;
return ans;
}
int[] FLOOR_LOG2_TABLE = { 0, 0, 1, 26, 2, 23, 27, 32, 3, 16, 24, 30, 28, 11, 33, 13, 4, 7, 17, 35, 25, 22, 31, 15, 29, 10, 12, 6, 34, 21, 14, 9, 5, 20, 8, 19, 18 };
int highBit(int n) {
n |= (n >> 1);
n |= (n >> 2);
n |= (n >> 4);
n |= (n >> 8);
n |= (n >> 16);
return n - (n >>> 1);
}
int floorLog2(int a) { return FLOOR_LOG2_TABLE[highBit(a) % 37]; }
class InputReader {
BufferedReader reader;
StringTokenizer token;
InputReader(InputStream in) {
this.reader = new BufferedReader(new InputStreamReader(in));
}
String read() {
while (token == null || !token.hasMoreTokens()) {
try {
token = new StringTokenizer(reader.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return token.nextToken();
}
int readInt() { return Integer.parseInt(read()); }
}
}