20zr联赛集训day15
A打表可以发现 $k>1$ 先手必胜，$k=1$ 取决于 $n$ 的奇偶性。具体证明：考虑如果 $n$ 是奇数的话，先手第一步取中间的那一块，序列变成了互相独立的两部分，之后先手只需要在没有被后手操作的块里模拟后手动作即可。如果 $n$ 是偶数的话，$k>1$ 也可以类似的划分成两段长度相等的段。$k=1$ 等价于每次只能取一个，所以 $n$ 是偶数的话后手能赢。#include...
A打表可以发现 $k>1$ 先手必胜，$k=1$ 取决于 $n$ 的奇偶性。具体证明：考虑如果 $n$ 是奇数的话，先手第一步取中间的那一块，序列变成了互相独立的两部分，之后先手只需要在没有被后手操作的块里模拟后手动作即可。如果 $n$ 是偶数的话，$k>1$ 也可以类似的划分成两段长度相等的段。$k=1$ 等价于每次只能取一个，所以 $n$ 是偶数的话后手能赢。#include...
A判断一下前面能否空出来就就行，也就是 $l \geq r-l+1$。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #d...
A. 跳石头首先我们观察一下青蛙是怎么跳的：对于一个断点 $(i,i+1)$，如果有 $x$ 只青蛙往左跳，那么一定有 $x$ 只青蛙往右跳，所以 $a_i$ 一定是偶数。并且我们发现从 $a_i$ 到 $a_{i+1}$，变化的只可能是 $i+1$ 这一个青蛙，也就是有 $|a_i-a_{i+1}| \in \{0,2,-2\}$。我们考虑 $a_i$ 到 $a_{i+1}$ 的变化：如果...
A. 异或考虑第 $i$ 位的贡献，发现每 $2^i$ 个数才会变化一次，所以答案是 $\sum_{i \geq 0} \lfloor\frac{n}{2^i}\rfloor $。考场上降智了，写了个枚举前缀卡到哪里算剩余贡献的垃圾做法。。#include <bits/stdc++.h> #define fi first #define se second #define db...
A一个暴力的想法是找出这条链，暴力跳。跳的定义是走到第一个满足和 $\geq k$ 的位置。于是可以想到用倍增。设 $f_{x,i}$ 表示 $x$ 点跳 $2^i$ 步在哪个点，首先跳 $2^0$ 步可以二分预处理，然后直接转移就好了。但是这只能处理往上的，往下怎么做呢？一种方法是直接树链剖分，就变成了若干个链的问题，但是这是 $O(\log^2n)$ 的，又难写又难调。我们可以观察到对于...