JSOISC2022模拟1
update 2022-07-14
T1
不是很难，可以先算出编号有多少位，然后再从左边第一位开始计算每一位。但是考场上因为亿些细节问题调了很长时间（
T2
其实考场上想出了 \(60pts\) 的暴力，但是因为不会证明误以为是错的于是写了 \(20pts\) 的暴力。
\(60pts\) 的 \(n^{2}\) 暴力，就是枚举选择的门派数量 \(i\) ，再找到 \(i\) 个门派下的最大战斗力。具体可以选择前 \(i\) 个门派最强士卒，再从剩余的士卒中选择 \(w\) 前 \(k-i\) 大的。不用考虑这些士卒是否会增加门派数量，因为考虑一定比不考虑更优，会覆盖不考虑的最大值。（当时就没想到这些（wssb
我太蒻了
正解就是先把所有士卒按 \(w\) 从大到小排序，先选择前 \(k\) 大的士卒，再按 \(w\) 由大到小枚举剩余的士卒，如果枚举到的士卒的门派没出现过，就试着用他替换前面的战斗力最低的非门派最强士卒。如果替换过后的总战斗力大于当前的 \(ans\) ，就更新 \(ans\) 。具体实现可以用小根堆存前 \(k\) 个士卒中的非门派最强士卒，更新的士卒不需要加入堆，因为他一定是门派最强。
感觉这题主要难在贪心思路的证明。
T3
容斥原理
容斥原理
zzk布置的容斥原理补充题：
- \(n\) 个有标号小球，放入 \(m\) 个有标号盒子，盒子非空，求方案数
- \(n\) 个有标号小球，放入 \(m\) 个无标号盒子，盒子非空，求方案数
- bzoj 2839（现在 bzoj 炸了，可以用 darkbzoj）
- 求 \(n\) 个元素的排列恰好有 \(k\) 个位置错排的方案数
解题思路大概是仿照错位排列，可以钦定排列有 \(l\) 个位置恰好满足 \(|p_{i}-i| = k\) ，这样的排列数量记录为 \(f(n,l)\)。
对于 \(60pts\) 可以直接暴力求解 \(f(n,l)\)。
对于正解我先把前置知识学完再写（咕咕咕
T4
写不出来怎么办（wssb
（先学习前置知识吧（（（
虚树
P2495 题解
洛谷日报：浅谈虚树
线段树相关
线段树相关寄巧总结
线段树分治
线段树分治总结
P5787 题解
后寄
好多坑啊填不完了填不完了qwq