藍橋杯 2021年國賽真題（Java 大學 B 組）

#A 整數范圍
#B 純質數
- 預備知識
- 樸素解法
- 按位列舉
#C 完全日期
- Java黨的完全勝利
- 樸素解法
- 樸素改進
- 不依賴 API 的實作
#D 最小權值
- 記憶化搜索
- 動態規劃
#E 大寫
#F 123
- 前綴和
#G 和與乘積
- 優雅騙分
#H 巧克力
- 貪心演算法
- 并查集優化
- 貪心 + 大根堆
#I 翻轉括號序列
- 線段樹
#J 異或三角
- 線性遞推
- 數位DP

認真整下，不嘻嘻哈哈了，

#A 整數范圍

本題總分：5 分

問題描述

??用 8 8 8 位二進制（一個位元組）來表示一個非負整數，表示的最小值是 0 0 0，則一般能表示的最大值是多少？

答案提交

??這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

255

calcCode：

public class Test {

    public static void main(String[] args) {
        System.out.print(0xFF);
    }
}

#B 純質數

本題總分：5 分

問題描述

??如果一個正整數只有 1 1 1 和它本身兩個約數，則稱為一個質數（又稱素數），
??前幾個質數是： 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , ? ? ? 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, · · · 2,3,5,7,11,13,17,19,23,29,31,37,??? ，
??如果一個質數的所有十進制數位都是質數，我們稱它為純質數，例如： 2 , 3 , 5 , 7 , 23 , 37 2, 3, 5, 7, 23, 37 2,3,5,7,23,37 都是純質數，而 11 , 13 , 17 , 19 , 29 , 31 11, 13, 17, 19, 29, 31 11,13,17,19,29,31 不是純質數，當然 1 , 4 , 35 1, 4, 35 1,4,35 也不是純質數，
??請問，在 1 1 1 到 20210605 20210605 20210605 中，有多少個純質數？

答案提交

??這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

1903

預備知識

??如果不會一種合數篩法的，估計跑到比賽結束結果都出不來，

??質數打表，

??就是為了這點題解，

??我才寫的這篇博客，

??就是為了這篇博客，

??我才立的這個標題，

樸素解法

??一種樸素的想法，在打表 [ 1 , 20210605 ] [1,20210605] [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 ) [0,10) [0,10) 中，質數僅占 { 2 , 3 , 5 , 7 } \{2,3,5,7\} {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 ] (1,N] (1,N] 這個范圍中的質數大約有 N ln ? N \cfrac{N}{\ln N} lnNN? 個，而按位組成的可能是純質數的數大約有 4 ln ? N 4^{\ln N} 4lnN 個，這顯然不是一個增值量級的，

??但這里放這么一段代碼，是為了進一步擴展刷題較少的讀者的解題思路，能掌握一種方法來解決其他的問題，

#C 完全日期

本題總分：10 分

問題描述

??如果一個日期中年月日的各位數字之和是完全平方數，則稱為一個完全日期，
??例如： 2021 2021 2021 年 6 6 6 月 5 5 5 日的各位數字之和為 2 + 0 + 2 + 1 + 6 + 5 = 16 2 + 0 + 2 + 1 + 6 + 5 = 16 2+0+2+1+6+5=16，而 16 16 16 是一個完全平方數，它是 4 4 4 的平方，所以 2021 2021 2021 年 6 6 6 月 5 5 5 日是一個完全日期，
??例如： 2021 2021 2021 年 6 6 6 月 23 23 23 日的各位數字之和為 2 + 0 + 2 + 1 + 6 + 2 + 3 = 16 2 + 0 + 2 + 1 + 6 + 2 + 3 = 16 2+0+2+1+6+2+3=16，是一個完全平方數，所以 2021 2021 2021 年 6 6 6 月 23 23 23 日也是一個完全日期，
??請問，從 2001 2001 2001 年 1 1 1 月 1 1 1 日到 2021 2021 2021 年 12 12 12 月 31 31 31 日中，一共有多少個完全日期？

答案提交

??這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

977

Java黨的完全勝利

??LocalDate好用，

樸素解法

??列舉 [ 2001 [2001 [2001- 01 01 01- 01 01 01， 2021 2021 2021- 12 12 12- 31 ] 31] 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 [2001 [2001- 01 01 01- 01 01 01， 2021 2021 2021- 12 12 12- 31 ] 31] 31] 中，各數位之和不僅存在最大值 2 + 0 + 1 + 9 + 0 + 9 + 2 + 9 = 32 2 + 0 + 1 + 9 + 0 + 9 + 2 + 9 = 32 2+0+1+9+0+9+2+9=32，還存在有最小值 2 + 0 + 0 + 1 + 0 + 1 + 0 + 1 2 + 0 + 0 + 1 + 0 + 1 + 0 + 1 2+0+0+1+0+1+0+1，也就是說，可能的完全平方數，不外乎 3 × 3 3 × 3 3×3、 4 × 4 4 × 4 4×4、 5 × 5 5 × 5 5×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 T T，小藍定義這棵樹中結點的權值 W ( T ) W(T) W(T) 如下：
??空子樹的權值為 0 0 0，
??如果一個結點 v v v 有左子樹 L L L, 右子樹 R R R，分別有 C ( L ) C(L) C(L) 和 C ( R ) C(R) C(R) 個結點，則 W ( v ) = 1 + 2 W ( L ) + 3 W ( R ) + ( C ( L ) ) 2 C ( R ) W(v) = 1 + 2W(L) + 3W(R) + (C(L))^{2} C(R) W(v)=1+2W(L)+3W(R)+(C(L))2C(R)，
??樹的權值定義為樹的根結點的權值，
??小藍想知道，對于一棵有 2021 2021 2021 個結點的二叉樹，樹的權值最小可能是多少？

答案提交

??這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，

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 N = 2021 N=2021， W ( 0 ) = 0 W(0) = 0 W(0)=0， W ( N ) = min ? { 1 + 2 W ( L ) + 3 W ( R ) + ( C ( L ) ) 2 C ( R ) } W(N) = \min \{1 + 2W(L) + 3W(R) + (C(L))^{2}C(R)\} W(N)=min{1+2W(L)+3W(R)+(C(L))2C(R)}，其中 L + R = N ? 1 L + R = N - 1 L+R=N?1， 0 ≤ L ≤ R ≤ N 0 \leq L \leq R \leq N 0≤L≤R≤N，

??狀態轉移方程就在臉上： d p ( y ) = { 0 i = 0 min ? { 1 + 2 d p ( l ) + 3 d p ( r ) + l 2 r } l + r = i ? 1 ， 0 ≤ l ≤ r ≤ i dp(y)=\left\{ \begin{array}{lr} 0&i = 0\\ \min \{1 + 2dp(l) + 3dp(r) + l^{2}r\}&l + r = i - 1，0 \leq l \leq r \leq i \end{array} \right. dp(y)={0min{1+2dp(l)+3dp(r)+l2r}?i=0l+r=i?1，0≤l≤r≤i???懂得都懂，

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.0 1.0 1.0s 記憶體限制: 512.0 512.0 512.0MB 本題總分： 15 15 15分

問題描述

??給定一個只包含大寫字母和小寫字母的字串，請將其中所有的小寫字母轉換成大寫字母后將字串輸出，

輸入格式

??輸入一行包含一個字串，

輸出格式

??輸出轉換成大寫后的字串，

測驗樣例₁

Input：
LanQiao

Output：
LANQIAO

評測用例規模與約定

??對于所有評測用例，字串的長度不超過 100 100 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.0 5.0 5.0s 記憶體限制: 512.0 512.0 512.0MB 本題總分： 15 15 15分

問題描述

??小藍發現了一個有趣的數列，這個數列的前幾項如下：
?? 1 , 1 , 2 , 1 , 2 , 3 , 1 , 2 , 3 , 4 , . . . 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, ... 1,1,2,1,2,3,1,2,3,4,...
??小藍發現，這個數列前 1 1 1 項是整數 1 1 1，接下來 2 2 2 項是整數 1 1 1 至 2 2 2，接下來 3 3 3 項是整數 1 1 1 至 3 3 3，接下來 4 4 4 項是整數 1 1 1 至 4 4 4，依次類推，
??小藍想知道，這個數列中，連續一段的和是多少，

輸入格式

??輸入的第一行包含一個整數 T T T，表示詢問的個數，
??接下來 T T T 行，每行包含一組詢問，其中第 i i i 行包含兩個整數 l i l_{i} li? 和 r i r_{i} ri?，表示詢問數列中第 l i l_{i} li? 個數到第 r i r_{i} ri? 個數的和，

輸出格式

??輸出 T T T 行，每行包含一個整數表示對應詢問的答案，

測驗樣例₁

Input：
3
1 1
1 3
5 8

Output：
1
4
8

評測用例規模與約定

??對于 10 10 10% 的評測用例， 1 ≤ T ≤ 30 , 1 ≤ l i ≤ r i ≤ 100 1 \leq T \leq 30, 1 \leq l_{i} \leq r_{i} ≤ 100 1≤T≤30,1≤li?≤ri?≤100，
??對于 20 20 20% 的評測用例， 1 ≤ T ≤ 100 , 1 ≤ l i ≤ r i ≤ 1000 1 \leq T \leq 100, 1 \leq l_{i} \leq r_{i} ≤ 1000 1≤T≤100,1≤li?≤ri?≤1000，
??對于 40 40 40% 的評測用例， 1 ≤ T ≤ 1000 , 1 ≤ l i ≤ r i ≤ 1 0 6 1 \leq T \leq 1000, 1 \leq l_{i} \leq r_{i} ≤ 10^{6} 1≤T≤1000,1≤li?≤ri?≤106，
??對于 70 70 70% 的評測用例， 1 ≤ T ≤ 10000 , 1 ≤ l i ≤ r i ≤ 1 0 9 1 \leq T \leq 10000, 1 \leq l_{i} \leq r_{i} ≤ 10^{9} 1≤T≤10000,1≤li?≤ri?≤109，
??對于 80 80 80% 的評測用例， 1 ≤ T ≤ 1000 , 1 ≤ l i ≤ r i ≤ 1 0 12 1 \leq T \leq 1000, 1 \leq l_{i} \leq r_{i} ≤ 10^{12} 1≤T≤1000,1≤li?≤ri?≤1012，
??對于 90 90 90% 的評測用例， 1 ≤ T ≤ 10000 , 1 ≤ l i ≤ r i ≤ 1 0 12 1 \leq T \leq 10000, 1 \leq l_{i} \leq r_{i} ≤ 10^{12} 1≤T≤10000,1≤li?≤ri?≤1012，
??對于所有評測用例， 1 ≤ T ≤ 100000 , 1 ≤ l i ≤ r i ≤ 1 0 12 1 \leq T \leq 100000, 1 \leq l_{i} \leq r_{i} ≤ 10^{12} 1≤T≤100000,1≤li?≤ri?≤1012，

前綴和

??區間和問題，一般先考慮的都是使用前綴和，但這里給出的區間范圍太大，以至于用全部的記憶體來存放前綴和，能通過的用例可能也只有半數，因此這里要將原序列 [ 1 , 1 , 2 , 1 , 2 , 3 , 1 , ? ? , n ? 1 , n ] \pmb[1,1,2,1,2,3,1,\ \cdots,n-1,n\pmb] [?[??[1,1,2,1,2,3,1, ?,n?1,n]?]??]變形為矩陣 [ 1 1 2 1 2 3 ? ? ? ? 1 2 3 ? n ] \begin{bmatrix}1\\1&2\\1&2&3\\\vdots&\vdots&\vdots&\ddots\\1&2&3&\cdots&n\end{bmatrix} ????????111?1?22?2?3?3????n?????????為了能涵蓋 [ 1 , 1 0 12 ] [1,10^{12}] [1,1012] 間的查詢，即矩陣包含 1 0 12 10^{12} 1012 個元素，這里 n n n 取 n = 2 E 12 n = \sqrt{2E12} n=2E12 ?，

??對于序列變形的矩陣，我們分別求出列與最后一行的前綴和后，組合起來就能在對數時間內 (需要二分查找給定 k 所在的行) 得到任意 [ 1 , k ] [1,k] [1,k]， k ∈ [ 1 ， 1 0 12 ] k \in [1，10^{12}] k∈[1，1012] 間內的元素和，對于任意 ∑ i = l r a i \sum_{i = l}^{r} a_{i} ∑i=lr?ai?，我們只需轉換為 ∑ i = 1 r a i ? ∑ i = 1 l ? 1 a i \sum_{i = 1}^{r} a_{i} - \sum_{i = 1}^{l - 1} a_{i} ∑i=1r?ai??∑i=1l?1?ai? 問題就被解決了，

??還有就是溢位問題，形如這種矩陣，在最大元素為 n n n 時，其矩陣元素和為 n + 2 ( n ? 1 ) + 3 ( n ? 2 ) + ? + n n + 2(n - 1) + 3(n - 2) + \cdots + n n+2(n?1)+3(n?2)+?+n ，
?? = n ( 1 + 2 + 3 + ? + n ) ? n ( 1 × 2 + 2 × 3 + 3 × 4 + ? + ( n ? 1 ) n ) =n(1 +2+3+\cdots+n)-n(1×2+2×3+3×4+\cdots+(n - 1)n) =n(1+2+3+?+n)?n(1×2+2×3+3×4+?+(n?1)n)
?? = n 2 ( n ? 1 ) 2 ? ( 1 2 + 1 + 2 2 + 2 + 3 2 + ? + ( n ? 1 ) 2 + n ? 1 ) =\cfrac{n^{2}(n-1)}{2} - (1^2+1 + 2^2 + 2 + 3^2 +\cdots +(n - 1)^2 + n - 1) =2n2(n?1)??(12+1+22+2+32+?+(n?1)2+n?1)
?? = n 2 ( n ? 1 ) 2 ? { ( 1 2 + 2 2 + 3 2 + ? + ( n ? 1 ) 2 ) + ( 1 + 2 + 3 + ? + n ? 1 ) } =\cfrac{n^{2}(n-1)}{2} - \{(1^2 + 2^2 + 3^2 +\cdots +(n - 1)^2) + (1 + 2 + 3 + \cdots + n - 1)\} =2n2(n?1)??{(12+22+32+?+(n?1)2)+(1+2+3+?+n?1)}
?? = n 2 ( n ? 1 ) 2 ? n ( n ? 1 ) ( 2 n ? 1 ) 6 ? n ( n ? 1 ) 2 =\cfrac{n^{2}(n-1)}{2} - \cfrac{n(n - 1)(2n - 1)}{6}-\cfrac{n(n-1)}{2} =2n2(n?1)??6n(n?1)(2n?1)??2n(n?1)?

??取 n n n 為 2 E 12 \sqrt{2E12} 2E12 ?，矩陣元素和約為 4.7 E 17 4.7E17 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.0 1.0 1.0s 記憶體限制: 512.0 512.0 512.0MB 本題總分： 20 20 20分

問題描述

??給定一個數列 A = ( a 1 , a 2 , ? ? , a n ) A = (a_{1}, a_{2}, \cdots, a_{n}) A=(a1?,a2?,?,an?)，問有多少個區間 [ L , R ] [L, R] [L,R] 滿足區間內元素的乘積等于他們的和，即 a L ? a L + 1 ? ? a R = a L + a L + 1 + ? + a R a_{L} · a_{L+1} \cdots · a_{R} = a_{L} + a_{L+1} + \cdots + a_{R} aL??aL+1???aR?=aL?+aL+1?+?+aR? ，

輸入格式

??輸入第一行包含一個整數 n n n，表示數列的長度，
??第二行包含 n n n 個整數，依次表示數列中的數 a 1 , a 2 , ? ? , a n a_{1}, a_{2}, \cdots, a_{n} a1?,a2?,?,an?，

輸出格式

??輸出僅一行，包含一個整數表示滿足如上條件的區間的個數，

測驗樣例₁

Input：
4
1 3 2 2

Output：
6

Explanation：
符合條件的區間為 [1, 1], [1, 3], [2, 2], [3, 3], [3, 4], [4, 4]，

評測用例規模與約定

??對于 20 20 20% 的評測用例， n ≤ 3000 n \leq 3000 n≤3000；
??對于 50 50 50% 的評測用例， n ≤ 20000 n \leq 20000 n≤20000；
??對于所有評測用例， 1 ≤ n ≤ 200000 , 1 ≤ a i ≤ 200000 1 \leq n \leq 200000, 1 \leq ai \leq 200000 1≤n≤200000,1≤ai≤200000，

優雅騙分

??推了一天，啥也沒推出來，放棄了，

??面對這種樸素思路復雜度在 O ( n 2 ) O(n^{2}) O(n2) 的問題，我們可以選擇一個不可能的元素將其折半，假設這個元素在序列的第 m m m 個，折半后的復雜度就在 O ( m 2 + ( n ? m ) 2 ) O(m^{2} + (n - m)^{2}) O(m2+(n?m)2)，

??理論上， m m m 越小且每個點分布的越均勻，那么安裝這種方法拆分，復雜度可以將至 O ( n log ? n ) O(n \log n) O(nlogn) 甚至 O ( n ) O(n) O(n)，

??在 a L ? a L + 1 ? ? a R = a L + a L + 1 + ? + a R a_{L} · a_{L+1} \cdots · a_{R} = a_{L} + a_{L+1} + \cdots + a_{R} aL??aL+1???aR?=aL?+aL+1?+?+aR? 這個運算式中，若 R ? L > 1 R - L >1 R?L>1 的情況，兩邊必為合數，

??如果任意 a L ? a L + 1 ? ? a R a_{L} · a_{L+1} \cdots · a_{R} aL??aL+1???aR? 中存在一個較大的質數 p p p，那么有極大的可能 a L + a L + 1 + ? + a R a_{L} + a_{L+1} + \cdots + a_{R} aL?+aL+1?+?+aR? 不能將其整除，也就是任給若干個 ( 0 , 2 × 1 0 5 ] (0,2×10^{5}] (0,2×105] 間的自然數，他們的和 p p p 的和是 p p 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()); }
    }
}

??給這題錘的神志不清了，有無大哥指點一下迷津，

#H 巧克力

時間限制: 1.0 1.0 1.0s 記憶體限制: 512.0 512.0 512.0MB 本題總分： 20 20 20分

問題描述

??小藍很喜歡吃巧克力，他每天都要吃一塊巧克力，
??一天小藍到超市想買一些巧克力，超市的貨架上有很多種巧克力，每種巧克力有自己的價格、數量和剩余的保質期天數，小藍只吃沒過保質期的巧克力，請問小藍最少花多少錢能買到讓自己吃 x x x 天的巧克力，

輸入格式

??輸入的第一行包含兩個整數 x , n x, n x,n，分別表示需要吃巧克力的天數和巧克力的種類數，
??接下來 n n n 行描述貨架上的巧克力，其中第 i i i 行包含三個整數 a i , b i , c i a_{i}, b_{i}, c_{i} ai?,bi?,ci?，表示第 i i i 種巧克力的單價為 a i a_{i} ai?，保質期還剩 b i b_{i} bi? 天（從現在開始的 b i b_{i} bi? 天可以吃），數量為 c i c_{i} ci?，

輸出格式

??輸出一個整數表示小藍的最小花費，如果不存在讓小藍吃 x x x 天的購買方案，輸出 ? 1 ?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 30 30% 的評測用例， n , x ≤ 1000 n, x \leq 1000 n,x≤1000，
??對于所有評測用例， 1 ≤ n , x ≤ 100000 1 \leq n, x \leq 100000 1≤n,x≤100000， 1 ≤ a i , b i , c i ≤ 1 0 9 1 \leq a_{i}, b_{i}, c_{i} \leq 10^{9} 1≤ai?,bi?,ci?≤109，

貪心演算法

??優先考慮最便宜的巧克力，每種巧克力盡可能晚的吃，直至已經吃了 x x 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 \log n + n \max (b_{i}, x)) O(nlogn+nmax(bi?,x))，接近 O ( n 2 ) O(n^2) O(n2) 顯然在這個資料規律下，還是相當不理想的，

??不過這種動態更新標記，查找最小可用，這和一個常用資料結構很契合，

并查集優化

??在確定完貪心策略后，程式中很大的一個性能瓶頸，出現在查找保質期內最大未規劃巧克力的時間，

??如果我們將一串規劃好的時間按原順序組成鏈表，那么在鏈頭大于一的情況下，鏈頭左邊的元素，就是我們要找的值，

??并且不需要關心這樣組織起的鏈表其他資訊，我們只需上述的資訊就能優化整個查找操作，并查集就能完成這項任務，

??并且在路徑壓縮的基礎上，這個操作的時間復雜程度只有 O ( 1 ) O(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 + x) O(nlogn+n+x)，即 O ( n log ? n ) O(n \log n) O(nlogn)，

??當然這里影響運行速度的引數不止 n n n 一個，

??能力有限，這里不做過多的討論，

貪心 + 大根堆

??為了能部分屏蔽除 n n n 以外的變數對程式整體運行時間的影響，我們需要按種而不是按塊來討論巧克力的規劃，

??但在上述貪心策略程序中，待規劃的日期是不連續的，如果將可安排日期按段查找，付出的代價可能遠比之前要大，額外增加的代碼量相應的也會增加除錯的風險與成本，

??容易地再想到一個策略，對于每個日期 d d d，在不選擇變質巧克力的前提下，盡可能的選擇最便宜的 d d d 個巧克力，

??對此我們可以按保質期升序考慮每種巧克力，動態的維護選擇方案，

?更詳細的說：

??建立一個以價格為權值的大根堆，該堆代表已選中的巧克力，堆初始為空，

?按保質期升序列舉巧克力的種類，列舉時會遇見兩種情況：

?1、當前巧克力數量 + 當前已選巧克力數量 ≤ \leq ≤ 當前巧克力保質期

??這時我們視為選擇當前巧克力，直接將其插入到堆里，

?2、當前巧克力數量 + 當前已選巧克力數量 > > > 當前巧克力保質期

??我們先計算出兩項的不等式兩邊的絕對差，然后從堆中彈出價格大于當前巧克力的巧克力，并且數量不能大于這個差值，然后插入若干當前種類的巧克力，使得當前已選巧克力數量等于當前巧克力保質期，

??可以預見的是，最終如果第 d d d 便宜的巧克力沒有加入第 d d d 天的方案，這就意味著在第 d d d 便宜的巧克力保質期內，有更便宜的巧克力使得第 d d d 便宜的巧克力無法加入，所以這個貪心策略下的結果是最優的，

??最終，堆內的巧克力就是最優的選擇方案，

??當然，它可能排不滿 x x x 天，

\\ 不想寫

#I 翻轉括號序列

時間限制: 10.0 10.0 10.0s 記憶體限制: 768.0 768.0 768.0MB 本題總分： 25 25 25分

問題描述

??給定一個長度為 n n n 的括號序列，要求支持兩種操作：
?? 1 1 1. 將 [ L i , R i ] [L_{i}, R_{i}] [Li?,Ri?] 區間內（序列中的第 L i L_{i} Li? 個字符到第 R i R_{i} Ri? 個字符）的括號全部翻轉（左括號變成右括號，右括號變成左括號），
?? 2 2 2. 求出以 Li 為左端點時，最長的合法括號序列對應的 R i R_{i} Ri? （即找出最大的 R i R_{i} Ri? 使 [ L i , R i ] [L_{i}, R_{i}] [Li?,Ri?] 是一個合法括號序列），

輸入格式

??輸入的第一行包含兩個整數 n , m n, m n,m，分別表示括號序列長度和操作次數，
??第二行包含給定的括號序列，括號序列中只包含左括號和右括號，
??接下來 m m m 行，每行描述一個操作，如果該行為 “ 1 L i R i ” “1 L_{i} R_{i}” “1Li?Ri?”，表示第一種操作，區間為 [ L i , R i ] [L_{i}, R_{i}] [Li?,Ri?]；如果該行為 “ 2 L i ” “2 L_{i}” “2Li?” 表示第二種操作，左端點為 L i L_{i} Li?，

輸出格式

??對于每個第二種操作，輸出一行，表示對應的 R i R_{i} Ri?，如果不存在這樣的 R i R_{i} Ri?，請輸出 0 0 0，

測驗樣例₁

Input：
7 5
((())()
2 3
2 2
1 3 5
2 3
2 1

Output：
4
7
0
0

評測用例規模與約定

??對于 20 20 20% 的評測用例， n , m ≤ 5000 n, m \leq 5000 n,m≤5000；
??對于 40 40 40% 的評測用例， n , m ≤ 30000 n, m \leq 30000 n,m≤30000；
??對于 60 60 60% 的評測用例， n , m ≤ 100000 n, m \leq 100000 n,m≤100000；
??對于所有評測用例， 1 ≤ n ≤ 1 0 6 , 1 ≤ m ≤ 2 × 1 0 5 1 \leq n \leq 10^{6}, 1 \leq m \leq 2 × 10^{5} 1≤n≤106,1≤m≤2×105，

線段樹

??對于一個合法的括號序列，

??它總是以 ‘(’ 開始，使用堆疊來判斷一個序列是否為合法的單調序列，即堆疊內只存放 ‘(’ ，遍歷序列時遇到 ‘(’ 壓入堆疊里，遇到 ‘)’ 若堆疊為空則序列非法，否則彈出堆疊頂 ‘(’，若遍歷完成堆疊為空，則序列合法，否則序列非法，

??很容易發現 ‘(’ 對堆疊大小的貢獻為 ‘ 1 1 1’，而 ‘)’ 對堆疊大小的貢獻為 ‘ ? 1 -1 ?1’，一個合法的括號序列始終不會為堆疊空時遇到 ‘)’ ，

??我們可以用括號序列構建 ± 1 \pm1 ±1 序列，并計算出它的前綴和陣列 s u m sum sum，

??按照上述性質，一個括號序列合法的充分條件是 s u m [ L ? 1 ] = s u m [ R ] 且 ? m ∈ [ L , R ] 都有 s u m [ m ] ≥ s u m [ L ? 1 ] sum[L - 1] = sum[R]\ 且\ \forall m \in[L,R]都有sum[m] \ge sum[L - 1] sum[L?1]=sum[R] 且 ?m∈[L,R]都有sum[m]≥sum[L?1]??再證其必要性，

??若有上述條件，則區間 s u m [ L , R ] sum[L,R] sum[L,R] 存在峰值 s u m [ k ] sum[k] sum[k]，而原括號序列 k k k 位必然為 ‘(’ ，因為 k k k 為峰值，所以 s u m [ k + 1 ] = s u m [ k ] ? 1 sum[k + 1] = sum[k] - 1 sum[k+1]=sum[k]?1，即原括號序列 k + 1 k + 1 k+1 位必然為 ‘)’ ， [ k , k + 1 ] [k,k+1] [k,k+1] 為一個合法的括號序列，將其從序列中剔除，如存在多個峰值則同時剔除多個，重復此程序直至序列為空，

??證畢，

??現在將問題轉變為查找區間最小值，如果我們動態維護一個線段樹的話，同時我們也能使用懶節點優化區間的翻轉，

\\節點懶，我也懶

#J 異或三角

時間限制: 5.0 5.0 5.0s 記憶體限制: 512.0 512.0 512.0MB 本題總分： 25 25 25分

問題描述

??給定 T T T 個數 n 1 , n 2 , ? ? ? , n T n_{1}, n_{2}, · · · , n_{T} n1?,n2?,???,nT?，對每個 n i n_{i} ni? 請求出有多少組 a , b , c a, b, c a,b,c 滿足：
?? 1 1 1. 1 ≤ a , b , c ≤ n i 1 \leq a, b, c \leq n_{i} 1≤a,b,c≤ni?；
?? 2 2 2. a ⊕ b ⊕ c = 0 a \oplus b \oplus c = 0 a⊕b⊕c=0，其中 ⊕ \oplus ⊕ 表示二進制按位異或；
?? 3 3 3. 長度為 a , b , c a, b, c a,b,c 的三條邊能組成一個三角形，

輸入格式

??輸入的第一行包含一個整數 T T T，
??接下來 T T T 行每行一個整數，分別表示 n 1 , n 2 , ? ? ? , n T n_{1}, n_{2}, · · · , n_{T} n1?,n2?,???,nT?，

輸出格式

??輸出 T T T 行，每行包含一個整數，表示對應的答案，

測驗樣例₁

Input：
2
6
114514

Output：
6
11223848130

評測用例規模與約定

??對于 10 10 10% 的評測用例， T = 1 , 1 ≤ n i ≤ 200 T = 1, 1 \leq n_{i} \leq 200 T=1,1≤ni?≤200；
??對于 20 20 20% 的評測用例， T = 1 , 1 ≤ n i ≤ 2000 T = 1, 1 \leq n_{i} \leq 2000 T=1,1≤ni?≤2000；
??對于 50 50 50% 的評測用例， T = 1 , 1 ≤ n i ≤ 2 20 T = 1, 1 \leq n_{i} \leq 2^{20} T=1,1≤ni?≤220；
??對于 60 60 60% 的評測用例， 1 ≤ T ≤ 100000 , 1 ≤ n i ≤ 2 20 1 \leq T \leq 100000, 1 \leq n_{i} \leq 2^{20} 1≤T≤100000,1≤ni?≤220；
??對于所有評測用例， 1 ≤ T ≤ 100000 , 1 ≤ n i ≤ 2 30 1 \leq T ≤ 100000, 1 \leq n_{i} \leq 2^{30} 1≤T≤100000,1≤ni?≤230，

???這資料

線性遞推

??都線性了，那 40 40 40% 的 2 30 2^{30} 230 就不用想了，

??先是要確定幾個能幫助我們加快程式運行速度的性質，

?? a ⊕ a = 0 a \oplus a = 0 a⊕a=0， 0 ⊕ 0 = 0 0 \oplus 0 = 0 0⊕0=0，因此 a , b , c a,b,c a,b,c 互不相等，對于最終計算出的方案數，我們只需在計算時滿足 a > b > c a > b > c a>b>c，然后對結果乘以 3 ! 3! 3!，

??而 a < b + c a < b + c a<b+c 才能組成三角形，故需要滿足 a = b ⊕ c < b + c a = b \oplus c < b + c a=b⊕c<b+c，

??我們都知道異或還有個別名，模二意義下的加法，也就是兩個數做異或運算相當在二進制下做加法并舍棄進位，

??因此當 b b b 與 c c c 有任意一位同為 1 1 1 時，加法運算發生進位，不等式成立，

??再考慮對任意 a a a 可能的方案數，

?? a ≥ 1 a \ge 1 a≥1，因此 a a a 能被表示為 1 x 1 x 2 ? x m 1x_{1}x_{2}\cdots x_{m} 1x1?x2??xm? 這種 1 1 1 接后繼二進制串的形式；為了使 a > b > c a > b > c a>b>c， b b b、 c c c 的二進制表示長度不會大于 a a a；為了使 a = b ⊕ c a = b \oplus c a=b⊕c， b b b 也必須被表現為 1 y 1 y 2 ? y m 1y_{1}y_{2}\cdots y_{m} 1y1?y2??ym? 這種形式；

??因此 b b b 絕對大于 c c c，所以我們可以直接跳過對 c c c 的討論，

??受上述條件限制， c c c 有和 b b b 相同位 1 1 1 的充分條件是 a a a 在此位為 0 0 0，所以 b b b 在小于 a a a 的同時，必須還有一位二進制數與 a a a 相反，為了滿足這個性質，這里換一種思路，

??直接選擇所有 1 y 1 y 2 ? y m 1y_{1}y_{2}\cdots y_{m} 1y1?y2??ym?， y 1 y 2 ? y m < x 1 x 2 ? x m y_{1}y_{2}\cdots y_{m} < x_{1}x_{2}\cdots x_{m} y1?y2??ym?<x1?x2??xm?，然后從中剔除不滿足性質的元素，

??選擇這個集合等價于增加 a a a 去掉前導 1 1 1 的一串二進制數，而去掉不滿足性質的元素，等價于減去 2 2 2 的這串二進制數中 1 1 1 的個數次冪，

??舉個例子：

??設 a a a 為 0 b 101011 0\mathrm{b}101011 0b101011， b b b 必大于 0 b 100000 0\mathrm{b}100000 0b100000，因此我們直接選中 [ 0 b 100000 , 0 b 101011 ) [0\mathrm{b}100000,0\mathrm{b}101011) [0b100000,0b101011) 即 0 b 101011 ? 0 b 100000 = 0 b 1011 0\mathrm{b}101011 - 0\mathrm{b}100000 = 0\mathrm{b}1011 0b101011?0b100000=0b1011 個元素，而不存在 a a a 該位為 0 0 0 而 b b b 不為 1 1 1 這種情況的集合為 { 0 b x 1 0 x 2 x 3 } \{0\mathrm{b}x_{1}0x_{2}x_{3}\} {0bx1?0x2?x3?}， x i ∈ 0 o r 1 x_{i} \in 0\ or\ 1 xi?∈0 or 1，顯然集合元素數量為 2 c o u n t B i t ( 0 b 1011 ) 2^{\mathrm{countBit}(0\mathrm{b}1011)} 2countBit(0b1011)，相減后即為我們想要的結果，

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

數位DP

// 不會，在學

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/327983.html

標籤：java

上一篇：我是如何用單例模式征服面試官的？

下一篇：Java基礎總結

第十二屆藍橋杯 2021年國賽真題 (Java 大學B組)

藍橋杯 2021年國賽真題（Java 大學 B 組 ）

#A 整數范圍

#B 純質數

預備知識

樸素解法

按位列舉

#C 完全日期

Java黨的完全勝利

樸素解法

樸素改進

不依賴 API 的實作

#D 最小權值

記憶化搜索

動態規劃

#E 大寫

#F 123

前綴和

#G 和與乘積

優雅騙分

#H 巧克力

貪心演算法

并查集優化

貪心 + 大根堆

#I 翻轉括號序列

線段樹

#J 異或三角

線性遞推

數位DP

藍橋杯 2021年國賽真題（Java 大學 B 組）