2020.7.12 牛客多校第一场 pro: 4/4/10 rk: 45

2020.7.13 牛客多校第二场 pro: 4/4/11 rk: 168

CR655C

链接

题意：

一个排列，每次可以任选一个子序列重新排，只需满足每个数都不在原来的位置；

做法：

可以观察到最多只需两次，一次让所有的数都不在正确位置。于是分别验证0次和1次可不可即可

CR655D

链接

题意：2n+1个数排成一圈，每次选三个连续的数消去，并把两侧的两个数之和放在原位，问还剩一个数时最大值。

做法：观察，如果是一条链，最后的和最大值一定是所有奇数位置之和（因为奇偶不同位置永远不能求和）。成环以后一个数可以从两个分别加和，于是可以取一次连续两个位置，然后其他位置隔一选一。证明很显然，显然不能存在连续三个都选，如果存在两个连续两个选的位置，则这两个对中相近的侧的两个数一定先合并，此时剩余三个数一定无法加和。

没有专题

没有比赛

没有专题

没有比赛

上周atc的F链接
题意：给$N\leq 10^9$，要求找5对数$a_i,b_i$满足$0\leq a_i<b_i,\sum_i(a_i+b_i)\leq N$，求所有方案的$\prod_i(b_i-a_i)$
做法：拉格朗日拟合，由题意，答案应该是一个十几次的多项式，暴力算几个点拟合一下。由于下面的说明，奇偶是两个不同的多项式，要分开来做。
或者排列组合，将$a_i,b_i$转为$\Delta=b_i-a_i，2a_i$，则问题转化为在数量为N的球中插板，并且板之间球的个数有一定要求（偶数）。

这周做题比较少，就推荐一下CR655D

CR655D

链接

题意：2n+1个数排成一圈，每次选三个连续的数消去，并把两侧的两个数之和放在原位，问还剩一个数时最大值。
tag:找规律
做法：观察，如果是一条链，最后的和最大值一定是所有奇数位置之和（因为奇偶不同位置永远不能求和）。成环以后一个数可以从两个分别加和，于是可以取一次连续两个位置，然后其他位置隔一选一。
证明:显然不能存在连续三个都选，如果存在两个连续两个选的位置，则这两个对中相近的侧的两个数一定先合并，此时剩余三个数一定无法加和。
comment：一道结论一般显然的结论题

推荐这周div2的F题链接
题意：给$N\leq 10^9$，要求找5对数$a_i,b_i$满足$0\leq a_i<b_i,\sum_i(a_i+b_i)\leq N$，求所有方案的$\prod_i(b_i-a_i)$
tag:拉格朗日拟合，排列组合
做法：拉格朗日拟合，由题意，答案应该是一个十几次的多项式，暴力算几个点拟合一下。由于下面的说明，奇偶是两个不同的多项式，要分开来做。
或者排列组合，将$a_i,b_i$转为$\Delta=b_i-a_i，2a_i$，则问题转化为在数量为N的球中插板，并且板之间球的个数有一定要求（偶数）。
comment:大概是常规的思维题？

推荐这周牛客第二场的E链接
tag：FWT，位运算
题意：从给定集合里选n个数，使得它们的异或值最大，数小于2^18
题解：n大于19时可以通过异或的开关性化成小于等于19的情况，小于等于19时用异或卷积(FWT)算答案
comment：头一次见到FFT还能这么玩，计划下周详细介绍快速沃尔变换FWT