CSP-J 2019 笔试
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张花色一致