一、行李

• 思路1：直接用哈希表统计每个字母出现的次数，取行李出现的次数与限制次数的最小值。
• 思路2:涉及到字母的哈希操作可以采用一个整数数组（长度为26）。
• 代码：

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        // 输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        String s = in.next();
        
        // 定义字符出现次数的数组并计算字符串出现次数
        int[] cnt = new int[26];
        for (char c: s.toCharArray()) {
            cnt[c - 'a']++;
        }
        
        int ans = 0;
        for (int num: cnt) {
            ans += Math.min(num, k);
        }
        System.out.println(ans);
    }
}

二、退化

• 技巧：
• x & (-x) 实际上获取的是数字二进制中最右侧的1。
• 多写几个例子发现，Cost值等于该数字最高有效位对应的全1数（例如，数字5的二进制最高位是4，对应的全1数为7）
• 思路：区间划分（在区间内，Cost值相同为），贡献计算(区间长度*Cost值)、累计求和
• 代码：

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long t = in.nextInt();
        for (long i  = 0; i < t; i++) {
            long n = in.nextInt();
            long res = calSum(n);
            System.out.print(res + " ");
        }
    }
    
    private static long calSum(long n) {
        long total = 0;
        long k = 0;
        while ((1 << k) <= n) {
            long s = 1 << k;
            long e = Math.min((1 << (k + 1)) - 1, n);
            long cnt = e - s + 1;
            total += cnt * ((1 << (k + 1)) - 1);
            k++;
        }
        return total;
    }
}