2020/05/10 北方大学ACM多校训练赛 第五场

日期： 2020/05/10 (原日期: 2017/04/02)
链接： https://www.jisuanke.com/contest/704/challenges
做题统计：王瑞琦： 冯宇扬： 常程：
(BOMB)

（这场比赛和上一场一样，题解难找，一些题只能说一下我们的思路）

solved by, upsolved by .

题意：对于$N\times M(max(N,M)\ge2)$的网格，最少使用多少$K\times K$的覆盖，使该网格依然存在从左上角走到右下角的方案，且所有方案的步数都大于$N+M-2$？
题解：

solved by, upsolved by .

题意：
题解：没有找到题解，自己也不是很会_(:зゝ∠)_

solved by None, upsolved by 发源于.
题意：n个数，q次查询。定义一种操作是在n个数中选取3个数进行或。每次查询给出一个数，计算得到这个结果的不同操作数。
$n \le 3 \times 10^5$， $q \le 3 \times 10^5$
题解：容斥。
设n个数的数组为 a 、、 定义 $f[i]=size({j | \forall k (2^k \& j \to 2^k \& i) })$
或者说 f[i] 为所有i 第 k 位为0时 j 的对应位也为0的 j 的数量
所以，很显然就有转移式 $f[i] = f[i]+ f[i \oplus (2^k)]\times bool(i\&(2^k)) (0\le k \le \log_2 \max (a)$)
初始状态， $f[a[i]]=1 \; (1\le i \le n)$
然后 方案数 $tot[i]=f[i]^3$

最后，对tot[i]容斥
对于每位 k， 我们构造掩码 $mask[k]=2^{k+1}-1$
$ans[i]=tot[i]-tot[mask[k] \& i]\times bool(i \& 2^k) \; (1\le 2^k <n)$

solved by, upsolved by常程.
题意： n($n=2^t$)个人序号从1到n，每个人的节操是序号，同时有一个节操常数k:当两个硬度相差超过k的节操相撞时，硬度小的节操必碎；而当两个硬度相差不超过k的节操相撞时，不一定哪个碎（自行决定），不会两边都碎。进行淘汰赛，计算冠军的节操最小值。
题解： 二分答案，对于每一个值自上向下构造竞赛树，构造的时候贪心地对于每一个点的节操值选取其所能战胜的最大的仍存在的另一个节操值作为儿子之一（理由是越大越容易存活）。如果不能构建这样的树就说明无法达到这样的最小值。
code

solved by, upsolved by.
题意：有一位神奇的mo法师，他可以给若干人续命。续命方式很独特：将N个人排成一排，从左至右将这N个人编号为0,1,2…N-1。然后进行60次操作，第i次操作会将编号mod$2^i$大于等于$a_i$的人+1s（1≤i≤60）。现在给出N和$a_1$到$a_60$，问最终被续了0,1,2…60秒的人各多少个。
题解：

solved by,upsolved by.
题意：之后每行给出3个整数：A,B,M，A和B为奇数，M为2的幂，数据保证有解。A,B,M<$10^9$。计算x，使得在模M的意义下，x的A次方等于B。 题解：

只能说是我们太菜了……