A. Alice and Bob题意：给出两堆石子a、b，两名玩家轮流取石子，取法是在一堆石子里取k个，并在另一堆石子里取$s\times k$个$(s\ge 0)$，给定a、b，问先后手谁必胜
观察得到，对于一堆石子为i个，那么只有最多一个对应的j，使得两堆石子为i、j时为必败态，于是必败态总数不超过n。对于每一个必败态，先枚举k，再枚举s，得到所有能一步达到该状态的必胜态，复杂度为调和级数$O(n\log n)$
阅读全文
MorphLing
7月 18, 2021
F. Nice Positions观察：对于一个序列，任意相邻两个数至少有一个是好的，即不存在两个连续的坏点
简单套个容斥就是
好点>=k的方案 <==> 坏点<=n-k的方案
然后从小到大把每个数插入排列，发现如果插入的数在一个坏点两侧，那么坏点数量不变，否则坏点数量+1
主要是一直在考虑，确定前i个点后再确定第i+1个点，从左往右依次确定的线性推法
但是如果从把最后一个数插入排列的任意位置的角度考虑就会简单很多
阅读全文
MorphLing
6月 10, 2021
E. Drinking观察一下不难发现，任意一端区间$g(l,r)=\sum\limits_{i=1}^nx_{(i)}\frac{1}{2^i},x(i)$表示区间内第$i$大的值，由于误差要求$<10^{-6}$，所以估一下只要取区间最大的T=50个数
自然想到单独计算每个数对答案的贡献。设第$i$个数左边比它大的数从右到左为$l_1,l_2,\cdots,l_T$，右边比它大的数从左往右为$r_1,r_2,\cdots,r_T$，那么每个数的贡献为
val_i=w_i\sum\limits_{u=1}^T\sum\limits_{v=1}^T(l_{u-1}-l_u)(r_v-r_{v-1})\frac{1}{2^{u+v-1}}
阅读全文
MorphLing
6月 03, 2021
A签到
C简单题
D最短路、树相关 待补
F数学、思维
首先由于$n’$最终取值范围为$[1,n]$，所以枚举$n’$可以得到一个$O(n)$的做法
然后把$[1,n]$分块为$[1,\sqrt m],[\sqrt{m}+1,\min\{n,m\}]$两部分，枚举第一部分n’取值，复杂度$O(\sqrt n)$，对于第二部分，可以把式子写成$m’=n’k$，此时$k$的取值范围为$[1,\sqrt m]$，枚举k，对于每个固定的k，可以找到一个贪心方案使代价最小，所以第二部分的代价也是$O(\sqrt m)$.
阅读全文
MorphLing
4月 29, 2021