526互联

CSP-J 2019 笔试

发布时间 2023-08-24 08:25:10作者: 月光幻影

CSP-J 2019 笔试

二分最大次数

  • 二分最大次数 = floor(__lg(n)) + 1

球相同，盒子相同

//n * 球，m * 盒子

for(int i = 0; i <= n; i++){
    for(int j = 1; j <= m; j++){
        if(i == 0 || j == 1){
            f[i][j] = 1;
        }else if(i < j){
            f[i][j] = f[i][i];
        }else{
            f[i][j] = f[i - j][j] + f[i][j - 1];
            //f[i - j][i]：盒子都放满了（每个盒子至少一个球，由每个盒子都少一个球转移过来）
            //f[i][j - 1]：最后一个盒子空着
        }
    }
}

正解（暴力枚举放满了几个盒子）

  • 放满5个盒子
    1 + 1 + 1 + 1 + 4
    1 + 1 + 1 + 2 + 3
    1 + 1 + 2 + 2 + 2
  • 放满4个
    1 + 1 + 1 + 5
    1 + 1 + 2 + 4
    1 + 1 + 3 + 3
    1 + 2 + 2 + 3
    2 + 2 + 2 + 2
  • 放满3个
    1 + 1 + 6
    1 + 2 + 5
    1 + 3 + 4
    2 + 2 + 4
    2 + 3 + 3
  • 放满2个
    1 + 7
    2 + 6
    3 + 5
    4 + 4
  • 放满1个
    8

乘法原理

—些数字可以颠倒过来看，例如0,1,8颠倒过来还是本身，6颠倒过来是9，9颠倒过来看还是6，其他数字颠倒过来都不构成数字。类似的，一些多位数也可以颠倒过来看，比如106颠倒过来是901。假设某个城市的车牌只由5位数字组成，每一位都可以取0到9。请问这个城市最多有多少个车牌倒过来恰好还是原来的车牌？（）

  • 0，1，8的对侧也必须放0,1,8

  • 6，9的对侧是9，6

  • 中间位置只能是0，1，8

  • 前两位有 $ 5 \times 5$ 种，第三位 \(3\) 种，后两位 \(1\) 种，由前两位决定

  • 一共 $ 5 \times 5 \times 3 \times 1\times 1 = 75$种

鸽巢原理

—副纸牌除掉大小王有52张牌，四种花色，每种花色13张。假设从这52张牌中随机抽取13张纸牌，则至少（）张牌的花色一致

  • 四种花色分布最均匀的情况是 $ 3 + 3 + 3 + 4$ 其余情况必然有一种花色 \(\ge 4\)，所以至少4张花色一致