十场航电必须打满八场(lus说的),而且是线下!
去年的经验表明,HDU主要考验数据结构…
HDU2025-1
今年第一场的题乍一看全都不会,会的交几发全假了,人傻了.
1001
有n个房间,每个房间内是一个独立的nim游戏:该房间谁没石子能拿了才能去下一个房间先手拿石子(最后没房间能去就输了),现在给你n个房间的情况,计算出房间有多少种先后排列能让先手Alice赢?
喵喵结论题.
在做这题之前，我们需要知道 Anti_Nim：即在经典 Nim 游戏中，把获胜的条件改成最后一个将石子取完的人 失败 。我们有以下结论：
- 当每堆石子的数量都为1时，异或和为0时先手获胜；
- 当有至少一堆石子的个数大于1时，异或和不为0时先手获胜。
由于全1的情况比较特殊，我们先假设不存在有全1的堆。此时可以发现，当异或和不为0的时候，在Nim和Anti_Nim中都是必胜的。在本题中，当异或和不为0的时候，先手就可以决定下一个房间谁先手。因此，当第一个房间的异或和不为0的时候先手必胜，反之先手必败。
现在考虑加入全1的房间。我们发现如果是偶数个1，对本题没有任何影响；如果是奇数个1，如果不放在最开头的情况下也没有任何影响。而如果放在开头，也只是改变了 Alice 和 Bob 的先手顺序。
因此最后的结论为：
- 当开头有奇数个1时，第一个非全1的房间的异或和不为0时 Alice 必胜；
- 当开头有偶数个1时，第一个非全1的房间的异或和为0时 Alice 必胜；
计算方案数的时候，我们先不考虑偶数个全1的房间。然后我们枚举有多少个奇数个全1的房间放在最前面(以上题解原话)
具体地:首先判断全是1的时候Alice赢还是输.
然后枚举奇数个1在前面的时候的排列,假设为i,对于i是奇数有:
(意思是,先处理非全是1的排列:举1个在最前面,剩下的随意,后者的意思是,所有剩下的位置除了选定的i个全是1堆和1个非1堆,剩下的由1堆随意排列)
同理,对于i是偶数有:
最后res需要乘上res=res*fac[cnt0]%mod*fac[cnt1]%mod*fac[cnt2]%mod*fac[cnt3]%mod*C(n,cnt0)%mod;,因为上述房间性质一样就可以阶乘去判断,且最后偶数的房间可以任意从n中选位置.
1005
分层图,对每个协会都建一个图,最后设置一个源点一个汇点跑最短路.
1006
分析题干板子题……
这个题很无语的地方是,看起来数据是随便出的,然而不是…
首先 没有任意两片山区一个高度 意味着不用tarjan,直接判断是不是比周围几个都高就需要建传送门.
然后 传送门建造费用极高 ,告诉我们除了这些门,在联通时不会额外建立其他的传送门.
然后 114xx 5141xx 919810xx 这个公式看似随便出,结果因为高度对结果影响非常大,直接按照高度对点排序即可,事实上根本不需要用到最小生成树的算法.
1009
找到最长的子序列满足两端的元素大于中间的所有值.
不妨从高枚举,这样里面的数一定比这个值小.
然后往低枚举,假如在区间里,答案不会变化.
假如不在,这个时候某一个比这个数大的数字一定会加进区间内,答案就是 $(r-l+1)-(n-i-1)$ .
1010
求中位数目前发现的trick:
- 二分
- 枚举:中位数是某个特定的数的情况
- 推平:枚举某个特定的数字之后,数字之间的关系就剩下单纯的大或者小,所以用1代替所有比枚举的p大的数,-1代替小的数.
然后求前缀和.这个数组的意思是,假如存在 $sum[r]==sum[l-1]$ 那么这个子串满足中位数是p(p必须在区间内).
本题没想到3.
然而本题中要求区间长度必须为奇数,怎么保证?
1 0 -1 其实已经保证了.
假如换成”区间长度必须为偶数”呢?
把排列数字本身换成1或者-1即可.
HDU2025-2
1012
首先发现每次只会选间隔2个或者间隔3个的(因为更大的间距不如选中间元素不劣)
然后直接搜索,克隆线性基即可.
注意使用 new 开数组的线性基在克隆的时候要一并克隆原函数,不然会一直是一个数组,会WA.
HDU2025-3
1007 性质不同的数字
将每个线段编号，观察数轴上的位置pos，把位置上所有覆盖的线段所构成的集合记为其状态，比如在pos=3的位置上有编号为{1,3,4}的三条线段覆盖，pos=3的状态即为{1,3,4},题目所求即整个数轴上有多少种不同的状态。
所以我们需要对线段进行随机哈希,维护抑或和(因为抑或上区间两端等于没有抑或).
HDU2025-4
1008
赛时假了.
正确做法是生成一个单调序列,然后从里面抽数字出来形成新的序列,答案不变更优就跳出.
HDU2025-5
1002 避税
二分答案,对这个答案进行check:
如果全装满都不够m,直接return 0.
然后尽量装满,假设一个元素竖着全部能装满,要取min.
否则先装满,对剩下的元素排个序,贪心的取最后几个能装的元素.
最后查验是否大于等于m即可.
1004 跃迁
置换的性质:结合律,所以我们可以尝试先算后面次方.
对于后面的次方,对于一个特定的q,一定能找到一个p0.
所以答案是 $(n!)^m$ ,赛时Flu认为答案是 $m(n!)$ 交还WA了一发…
1005 四角洲行动
注意到一个 1x2 能拆成两个1x1,一个1x3能被拆成一个1x1和一个1x2,一个2x2能被拆成两个1x2,其中他们除了1x1都是可以接着参加后续分拆的.
看起来直接dp非常麻烦,所以我们尝试转化为检验性问题:我们枚举ijk表示强制i个2x2被拆成1x2,j个1x3被拆成1x1和1x2,k个1x2被拆成1x1,所以对物品排个序做前缀和就可以O(1)判定最大值,问题就解决了.