Codeforces Round #852 (Div. 2) A.Serval and Mocha's Array算法本质思维题目大意对于一个长度>=2的数组，有好、美丽两种属性。好：数组内元素gcd之和 <= 其长度美丽：数组的所有（长度>=2的）前缀数组都是好的给定一个数组，现在可以重新排序其元素，能否使得其美丽。思路推演美丽是好的延申属性。先看好，gcd所有元素和长度比较，这具有单调性。所以可知，如果数组的前2个元素满足好，则当前数组美丽。即找到2个元素gcd <= 2即可。B.Serval and Inversion Magic算法本质思维题目大意给出一个01字符串，选择某个区间内字符反转（0变1、1变0），是否能构成回文。思路推演回文的特定就是左右相等。当一个字符串出现了需要操作才能变为回文，就是左右出现了不相等情况。通常的想法是，改变一边，另外一边不动。手动模拟找特征得知：l r不需要跨过中间原字符串就是回文是可行的对称性很强。原字符串找其中左右两边对比，如果出现不一样的地方连续为一整块，即可构成回文，否则不可。C.Serval and Toxel's Arrays算法本质思维、结构题目大意有一个长度为n的数组，接下来进行m次操作，每次操作改变其中一个元素的值，随后保存新生成的数组，保证每个数组不会有重合的元素。这样就会有m+1个数组（包含最初的），让数组两两相互组合一次，组合时去重剩下的元素个数加入到ans，最后求ansm、n <= 2e5 1 <= 元素值 <= m+n思路推演 - 1首先，这种题一眼可知，是找到某种看题的视角（做题的数据结构），才能完成复杂度下的任务。如果我们暴力做，就会有$O(m^2n)$的复杂度。通常这种题的优化有2个方向：常见数据结构考察如st表、线段树、树状数组等，特点是区间运算映射合并特征比如在暴力做法下，我们是将所有数组一一对比实现的，因为每个数组其实是独特的。但是可以找到某个共通点，将其合并在一起运算。当然，还是可以从不同寻常的地方找到一些线索：元素值<=4e5每个数组的元素不会重复从这2个条件几乎可以看出，优化做法的方向是映射合并特征，而且其单位很有可能是元素值。思路推演 - 2所以，元素值在所有数组中出现的次数，可能作为特征。如果a在数组中只出现了1次，那其贡献就是m。如果出现了2次，则可以发现其贡献本应该是2*m，但是因为这2个元素之间相互会有重复，所以是2*m-2*1/2如果出现x次，贡献是x*m - (x-1)*x/2ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>n>>m; rep(i,1,n) cin>>ar[i]; rep(i,1,n+m) last[i]=-1, hui[i]=0; rep(i,1,n) last[ar[i]]=0; //cal for (int ci=1; ci<=m; ci++) { int pos, val; cin>>pos>>val; int a=ar[pos], b=val; ar[pos] = val; hui[a] += ci-last[a]; last[a] = -1; last[b] = ci; } for (int i=1; i<=n; i++) hui[ar[i]] += m+1-last[ar[i]]; //cal 2 int ans = 0; for (int val=1; val<=n+m; val++) //这里hui[val]相当于x ans += hui[val]*m - hui[val]*(hui[val]-1)/2; cout<<ans<<endl; return; }

Codeforces Round #852 (Div. 2) A.Yet Another Promotion算法本质模拟、思维题目大意食物商店只卖2次土豆：第一次A元/斤，每买m斤送1斤第二次B元/斤求2次合计购买n斤土豆的最低花费。思路推演这类题目，分类讨论模拟，最好的方法之一就是：将可能是最便宜的方法列出，然后都求出，取min值。可以简单分为三类：仅买第一次仅买第二次混合买B.Fedya and Array算法本质思维题目大意给定你a b两个数，需要你给定一个环形数组，要求：极大值（局部最大值）之和为a极小值之和为b相邻元素之差<=1尽可能短思路推演先手动玩一下数组。随机创造一个数组，比如最基础的波浪形，然后改变一下其形状。发现在差值固定为1时，改变形状只是会引起极大值、极小值之和此消彼长。于是尝试直接做到极端——保留一个为a的极大值、一个为b的极小值。发现可行，而且是最好实现的。C.Dora and Search算法本质思维题目大意给定一个排列，找到一个区间l r，使得这个区间中的最大、小值都不在l r下标上。可能有多解，找到其一即可（不可返回-1）。思路推演首先肯定想，要是1 n都不在边缘，那岂不是直接找到了。考虑1 n在边缘的情况：如果1在边缘，则直接不管这个点，然后看2 n如果n在边缘，则丢这个点，看1 n-1哦，递推呀。写成双指针即可。D.Moscow Gorillas算法本质思维题目大意给出2个排列：p q计算满足条件的l r数目：MEX(p[l~r]) == MEX(q[l~r])思路推演一看题还是不知所措，那就上手玩一下把。看能不能找一些东西，合并简算。MEX，那岂不是没有1就全部为1，那先算l r都取不了p q的1值的情况。那剩下的情况全是需要取1的，欸，这个时候考虑一下不取2的情况……递推思考，同C题一样的，只是其中情况稍微复杂度一点。最后实际表现出来的就是，分别计算MEX值为1、2、……、n+1的情况即可。E.Velepin and Marketing算法本质思维题目大意（改）将n个人分配到若干房间，保证每个房间至少一人。对于第i人，当其所在房间人数>=ai时，他会感到安全。下面给出m次询问，每次询问会给出具体的房间数，请问最多可以使得多少人感到安全。n、ai、m、房间数<=3e5思路推演通过查看题目的范围，可以很明确的发现，这种题最经典的流程是：预处理a[]数据，使得之后每次查询可以log级别得到结果。但同时请注意房间数<=3e5这个条件，这说明是有可能求出全部情况然后打表输出的——通常是房间数x的答案可以借助小于x的答案。随后找到两个限制条件：房间至少一人使得感到安全的人尽量多通过手动模拟了一会，可以发现，我们优先满足房间至少一人这个条件，思考会方便很多。继续模拟思考找规律，发现目前的条件不足以让我们直接得到答案，所以想到了二分——二分可以先假设一个信息，使得手中信息+1。于是开始尝试思考：现在目标是判断，在当前情况下能否满足x个人可以获得安全感。注意，这里并没有确认用二分做，只是有可能。 同时这里有漏掉正解的可能，从二分的角度去思考也可以帮助我们理解。思考单调性——满足。再转过头回顾大局，解题的方向就只有2个了，一是二分，二是找到不同房间数答案之间的关联打表做。做题要注意大局观思路推演 - 二分要求人数最多思路推演即人的收益都一样，但是成本ai不同，所以先按照成本排序，优先处理ai小的。已经要满足前x人的需求，则后面n-x人可以视作永远无法满足的人，结合优先铺满房间的思路，把这些人先都拿来铺房间。如果房间能够铺满，那就很简单了，把房间铺满后，剩下的人（包括前x个人）都放在一个房间，看房间人数是否可以超过a[x]即可。重点在于无法铺满的情况，首先能铺多少是多少，然后回过头来看，前x个人能否在剩下的y个房间中满足。我们都知道，想要用少的人办多的事，先用成本较低的人，于是有了下面的思考：对于排序后的a[]，形成一个组的概念。 将ai加入组中，当组的元素个数==ai时，增加一个新组。 比如[1,2,3,3,4,5,7]就可以分为3个组：[1] [2,3,3] [4,5,7] （其中最后一个组不完备）前x个人形成的完备组数<y时则肯定是无法完成的。前x个人形成的完备组数>=y时将靠后多出的组全部加入第y组，查看第y是否能满足所有人（第x个人）。（贪心思维）至此二分的做法已完成。思路推演 - 打表这里的打表并非利用上面的关系来做，而是更加广义一点。我们可以逐个探讨，当我们想要强制保证前x个人可以被满足的时候，最多可以有多少个房间。于是先设：f[x]：在仅有前x个人且满足他们的前提下，最多放置房间数 （注意f[]可能存在无解情况） g[x]：在仅有前x个人 的前提下，最多放置房间数当ar[x] <= x则有解（全部放一起就是其中一个解）其转移公式f[x] = g[x-ar[x]] + 1，理解为g[x-ar[x]]的房间数 + 后面ar[x]个人一起组成的一个房间，其中g[x-ar[x]]部分人没有被满足的可以放在后面那个房间。此时前面有f[x]个房间，还可以找来n-x个人一人一间，所以可以占f[x]+n-x个房间。当ar[x] > x则无解但是又要强制保证前x人可以被满足，于是我们凑前ar[x]到第一房间，剩下的人一人一间，可以占n-ar[x]+1个房间。同时记得维护g[x] = max(f[x], g[x-1])。ac核心代码 - 二分头文件、宏定义、快读模板、常见变量、常见变量等略。 struct Person { int id, rank; //小组下标、组内排名 }; Person per[maxn]; //pos为主键 int group[maxn], pre[maxn]; //小组下标(0开始)-->小组大小 bool judge(int x, int room) { int y=n-x; //有y个人去铺房间 if (y>=room) //能铺满 return y-room+1+x >= ar[x]; //剩下的人挤一起就好 int zu=per[x].id; //zu表示可以生产的完备组 if (zu-(per[x].rank != group[per[x].id]) < room-y) //完备组数<剩下的房间，直接完蛋 return 0; else return x - pre[room-y] + group[room-y] >= ar[x]; } inline void solve() { //init cin>>n; rep(i,1,n) cin>>ar[i]; sort(ar+1, ar+1+n); //cal 预处理 int cnt=1; for (int i=1; i<=n; i++) { group[cnt]++; per[i].id = cnt; per[i].rank = group[cnt]; if (group[cnt] == ar[i]) cnt++; } for (int i=1; i<=cnt; i++) pre[i] = pre[i-1] + group[i]; //cal int q; cin>>q; while (q--) { int x; cin>>x; int l=0, r=n; int res=l; while (l<=r) { int mid=(l+r)/2; if (judge(mid, x)) { res = mid; l = mid+1; } else r = mid-1; } cout<<res<<endl; } return; }ac核心代码 - 打表头文件、宏定义、快读模板、常见变量、常见变量等略。 int f[maxn], g[maxn], ans[maxn]; inline void solve() { //init cin>>n; rep(i,1,n) cin>>ar[i]; sort(ar+1, ar+1+n); //cal f[0] = 0; for (int i=1; i<=n; i++) { if (ar[i] <= i) //说明有解 { f[i] = g[i-ar[i]] + 1; ans[ f[i]+n-i ] = max(ans[ f[i]+n-i ], i); } else ans[ n-ar[i]+1 ] = max(ans[ n-ar[i]+1 ], i); g[i] = max(f[i], g[i-1]); } for (int i=n-1; i>=1; i--) //补全空解 ans[i] = max(ans[i], ans[i+1]); //out int q, x; cin>>q; while (q--) { cin>>x; cout<<ans[x]<<endl; } return; }

Codeforces Round #852 (Div. 2) One and Two算法本质模拟题目大意给一个有1 2组成的数组a[]，是否存在一个k，使得前k个元素的连乘等于后n-k个数的连乘。思路推演略。B.Sum of Two Numbers算法本质模拟题目大意给定数字n，找出一对数字a b满足：a+b == na所有位数字和 与 b所有位数字和 差值<=1思路推演按位平分。C.Matching Numbers算法本质思维题目大意给定数字n，构造一个2n的排列，要求满足：每2个相邻元素组成一对（a[2k]和a[2k+1]），a[2k]+a[2k+1] + 1 == a[2k+2]+a[2k+3]（靠左对+1 == 靠右对）无法完成输出No。思路推演很容易可以求到元素总和：(1+2n)*2n/2然后要化成n个自然数相加：(3n+3)/2 ~ (5n+1)/2当n为奇数的时候当然不可行。此时就要找方法看怎么填了，手动模拟一下即可得到。D.Moving Dots算法本质思维题目大意在一条线上，有n个给定的点（不相重），任选>=2个点，玩游戏将得分加入ans，输出所有情况都玩过后的ans%mod值。游戏内容如下：游戏开始后，点会找最近的点（优先左边）以固定相等的速度移动，当点第一次发生碰撞后就会停下（但是任然算作点，可以被其他移动的点碰撞）。当所有的点停下后，所有点所处不同位置数目就是分数。n <= 3e3 点坐标：[1, 1e9]思路推演所有情况一共n**2种，显然，此题是需要合并某个特征值，化简为n^2的复杂度。当然，也可以考虑dp。这其中，最合适的就是找到点 --> 贡献值。即找到某点在不同情况下对ans的贡献值。以单点来看，点会因为所选点的不同而左右移动，无法判断。以dp来看，相邻的点集没有可以简算的递推公式。以二分来看，并无单调性。这其中的奥秘出在复杂度上，3e3的数据范围是支持n^2的，当然正面思考到任然有一些难度，从ans入手。思考ans的来源，其实游戏结束后聚集在一起，可以看作最开始2个点干的，其他只是趋势。结合3e3的数据，能不能以2个点为单位，思考其对ans的贡献。如果2点为单位，驱赶附近点，任选远处点，这2点会始终对ans有贡献。并且其他点被吸引或是自己组合与2点无关。存在附近点的情况，可以转化为另外2点单位的情况。复杂度允许，开整。ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 int x[maxn]; inline void solve() { //init cin>>n; rep(i,1,n) cin>>x[i]; //cal int ans=0; for (int i=1; i<=n; i++) { for (int j=i+1; j<=n; j++) { // debug2(i,j) int dis=x[j]-x[i]; int l = lower_bound(x+1, x+1+n, x[i]-dis) - x; //找到第一个>=左边界的 l--; //<左边界的个数 int r = lower_bound(x+1, x+1+n, x[j]+dis) - x; //找到第一个>=右边界的 r = n - r + 1; //>=右边界的个数 ans += qpow(2, l+r, mod); ans %= mod; } } //output cout<<ans<<endl; return; }

Codeforces Round #848 (Div. 2) A.Flip Flop Sum算法本质模拟题目大意给定一个由1 -1组成的数组a[]，现在必须选择相邻的两个元素取反。求操作后a[]元素和的最大值。思路推演模拟B.The Forbidden Permutation算法本质模拟题目大意给定长度为n的排列p[]，长度为m的数组a[]，整数d。设pos[]，p[i]=val --> pos[val]=i。a[]称作不好满足以下条件：对于任意i：pos[ai] < pos[a(i+1)] <= pos[ai]+d现在可以对p[]进行操作：交换2个相邻元素位置求最少需要多少次操作使得a[]变好。思路推演分析题面，不好的条件很苛刻，只需要找到其中一组i i+1，破坏左边或者右边一个条件即可。两种情况都可以O(1)计算，然后整体O(n)。C.Flexible String算法本质模拟题目大意长度为n的a b字符串，a由至多有10个字符组成，现在可以至多对a选择k个字符，对这些字符可以任意改变为另一字符。操作后，a b的[l r]区间一致，最大化r-l+1，输出最大值。思路推演暴力模拟即可。D.Flexible String Revisit算法本质概率dp、数学思路推演概率dp，两种设计方式：f[x]表示当前还有x个字符未对齐，达到还有0个字符没有对齐的期望次数。 dp[x]表示当前还有x个字符未对齐，达到还有x-1个字符没有对齐的期望次数。 f[x] = 1 + (x/n)*f[x+1] + (1-x/n)*f[x-1] //当前成本 + 成功概率*成功后的期望 + 失败概率*失败后的期望 dp[x] = 1 + (dp[x+1]+dp[x])*(1-x/n) //当前成本 + 失败概率*失败后的期望动脑一想，我们选择dp[]来做，然后就很轻易的做出来了——ac核心代码-1。当然如果是用f[]来做也不要紧，因为已经f[0]=0，所以我们对公式进行改动：f[i] = n/(n-i+1) * (f[i-1] - 1 - (i-1)/n*f[i-2])。这说明所有f[i]都可以用f[0] f[1]来表示，其中f[0]=0已知，设f[1]=x，因为公式都是线性的，所以所有的f[i]都可以用ax+b表示。在边缘n可以得到一个式子：f[n] = 1+f[n-1]，用将表示出来的f[n] f[n-1]带入上式，可以解出f[1]的值————ac核心代码-2。ac核心代码-1头文件、宏定义、快读模板、常见变量、常见变量等略。 int dp[maxn]; string a, b; inline void solve() { //init cin>>n; cin>>a>>b; a=" "+a; b=" "+b; int cnt=0; for (int i=1; i<=n; i++) cnt += a[i]!=b[i]; //cal dp[x]表示当前有x个不同的，如果要提升到有x-1个不同所期望的次数 dp[n] = 1; ans=0; for (int i=n-1; i>0; i--) { dp[i] = n*qpow(i,mod-2,mod)%mod + (n-i)*qpow(i,mod-2,mod)%mod*dp[i+1]%mod; dp[i] %= mod; } for (int i=1; i<=cnt; i++) ans += dp[i]; ans %= mod; cout<<ans<<endl; return; }ac核心代码-2头文件、宏定义、快读模板、常见变量、常见变量等略。 string a, b; int x[maxn], val[maxn], inv[maxn]; inline void solve() { //init cin>>n; cin>>a>>b; a=" "+a; b=" "+b; //cal int cnt=0; for (int i=1; i<=n; i++) cnt += a[i]!=b[i]; //f(x)表示当前还有x个不同位置，达到完全相同的位置的期望数 x[0]=val[0]=val[1]=0; x[1]=1; for (int i=2; i<=n; i++) { inv[n] = qpow(n, mod-2, mod); inv[n-i+1] = qpow(n-i+1, mod-2, mod); x[i] = n*inv[n-i+1]%mod * (x[i-1] - (i-1)*inv[n]%mod*x[i-2]%mod)%mod; x[i] = (x[i]%mod+mod)%mod; val[i] = n*inv[n-i+1]%mod * (val[i-1] - 1 - (i-1)*inv[n]%mod*val[i-2]%mod)%mod; val[i] = (val[i]%mod+mod)%mod; } int num_x = (x[n]-x[n-1]+mod)%mod; int num_val = (1+val[n-1]-val[n]+mod)%mod; int val_x = num_val/num_x; ans = x[cnt]*val_x + val[cnt]; ans %= mod; cout<<ans<<endl; return; }

Codeforces Round 838 (Div. 2) A.Divide and Conquer算法本质思维题目大意给n个元素，可以进行以下操作：选则元素值x，使得x /= 2（向下取整）最小化操作使得元素和为偶数。思路推演如果开始元素和为偶数则ans = 0否则暴力每个元素改变奇偶性所需的操作数，找出最小值。B.Make Array Good算法本质思维题目大意给长度为n的数组a[]，对于a[]定义美丽：任意两个元素中的大值 % 小值 == 0允许最多进行n次以下操作：选择i，使a[i]加上一个[0, a[i]]的值输出操作情况。思路推演首先排序a[]方便观察。（升序）随后手动模拟发现，a[i]对于a[i-1]总是可以轻易地增加到其倍数。于是发现贪心即可。C.Binary Strings are Fun算法本质思维题目大意对于总长为奇数的01字符串s，定义美丽：对于奇数下标i，s[1~i]中s[i]的字符占比超过一半对于长度为n的01字符串s1，若长度为2*n-1的01字符串s2满足以下条件，则称s2是s1的扩展字符串：对于任意i：s2[2*i-1] = s1[i]现给定长度为n的01字符串a，求其n个 前缀字符串 的 美丽 扩展字符串数目。（%mod）思路推演题目看起来定义繁琐、复杂，先手动模拟一下。当s的末尾为01或者10时，其美丽扩展字符串的情况只有一种。（这个结论不详述）进一步思考随后s考虑结尾是多个相同字符情况，发现s对ans的贡献为2^(结尾连续相同字符数-1)。于是预处理a每个下标的结尾连续相同字符数即可。D.GCD Queries算法本质思维题目大意给定0~n-1n个元素，将其顺序打乱放入p[]中。通过至多2n次以下询问来猜测0值元素的位置：输出? x y，会返回gcd(p[x], p[y])（gcd(0, x) == x）猜测：输出! x y，若p[x]==0 || p[y]==0即算作猜测正确思路推演-1 试错这类题，最需要考虑就是每个数字本身的特性。显然的一个做法是：根据数字的特性，将某个数字x，对其他数字都询问一遍，获得信息，然后进一步缩小范围。若x为0，其得到结果唯一，好判断。若x不为0，则会得到一部分1、一部分大于1的值，而0就藏在那部分大于1的值中。重复过程、便可一直缩小0的范围。但是这个做法，当第一次取x取到1时，所需要的最多操作数为3n。（希望找到某个方法优化，但是找不到）思路推演-2 正解正解这个思路相当……让人有：这tm也可以？平均一下哎，每2次查询都需要去掉一个非0位置。选择3个值a b c：查询gcd(a,b)和gcd(a,c)前值==后值：则a一定不是0值，丢掉前置!=后值：假设gcd(a,b) < gcd(a,c)则b一定不是0值，丢掉ac核心代码头文件、宏定义、快读模板、常见变量、常见变量等略。 inline void solve() { //init cin>>n; deque<int> dq; rep(i,1,n) dq.push_back(i); //cal while (dq.size() > 2) { int a=dq.front(); dq.pop_front(); int b=dq.front(); dq.pop_front(); int c=dq.front(); dq.pop_front(); int gcd_ab, gcd_ac; cout<<"? "<<a<<" "<<b<<endl; cout<<"? "<<a<<" "<<c<<endl; cin>>gcd_ab>>gcd_ac; if (gcd_ab == gcd_ac) { dq.push_back(b); dq.push_back(c); } else if (gcd_ab < gcd_ac) { dq.push_back(a); dq.push_back(c); } else { dq.push_back(a); dq.push_back(b); } } cout<<"! "<<dq.front()<<" "<<dq.back()<<endl; cin>>m; return; }