首页 > 其他分享 >Codeforces Round 960 (Div.2) 补题

Codeforces Round 960 (Div.2) 补题

时间:2024-07-21 11:08:52浏览次数:9  
标签:右移 geq 960 max lt 补题 数组 Div.2 presum

A

非常容易观察到性质,注意 Alice 为先手,发现当 \(a_{\max}\) 的个数为奇数时显然能 win,但如果 \(a_{\max}\) 的个数为偶数且有一个数具有奇数个可以作为跳板,那么也能 win,否则就 lose。

B

结论:\(presum_x \geq 2 + presum_{y - 1} \geq 2 + \min{presum_i} \geq 1 + \max{presum_i}\),后缀和同理。

C

模拟一下容易发现每次操作后整个数组都会向后移动。

我们首先对数组进行一次操作模拟,发现整个数组就变成单调不降的了。

之后我们开始观察,对于一个连续的序列 \(a[l, r] = x (l \lt r, x \gt 0)\),在一次运算之后,得到一个新的限制 \(a[l + 1, \min{(r + 1, n)}] = x\) 成立,然后再给结论:如果数组中所有非零连续段(出去最后一段)的长度都大于 \(1\),那么数组就遵循一个 “右移” 定律。

对于 “右移” 数组,不难得到 \(b_i \lt b_{i + 1} \lt b_{i + 2}\),可以推断出 \(b_i = a_i, b_{i + 1} = a_{i + 1}\),并且至少有 \(a_j = a_{i + 1}(j \leq i)\) 成立,这也就说明 \(a\) 并不是非单调递减的,也就是说经过 \(2\) 次运算总能得到一个 “右移” 数组。

D

标签:右移,geq,960,max,lt,补题,数组,Div.2,presum
From: https://www.cnblogs.com/Yuics/p/18314257

相关文章

  • 题解:Codeforces Round 960 (Div. 2) A
    A.SubmissionBaittimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputAliceandBobareplayingagameinanarray\(a\)ofsize\(n\).Theytaketurnstodooperations,withAlicestarting......
  • Codeforces Round 960 (Div. 2) 补题记录(A~D)
    打的稀烂,但是还是上分了(A考虑对值域做一个后缀和。若某一个后缀和的值是奇数那么先手就可以获胜。否则就不可以获胜。(我才不会告诉你我这题吃了一次罚时的)#pragmaGCCoptimize(3)#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;intmysqrt(intx){......
  • 牛客小白月赛98补题
    D一道很典型的区间DP//区间DP典题#include<bits/stdc++.h>usingnamespacestd;#definelllonglongconstintN=520;lln,L,R;strings;llsum0[N],sum1[N];llf[N][N];voidsolve(){cin>>n>>L>>R>>s;s='......
  • CodeForces Round #959 sponsored by NEAR (Div. 1 + Div. 2) 补题记录(A~E)
    简单场.pngA若\(n\timesm=1\)则显然无解。否则因为\(a\)矩阵是一个\(n\timesm\)的排列,所以说只需要让其循环右移一位即可。时间复杂度\(O(nm)\)。#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=500100;inta[233][233];sign......
  • 杭电多校补题
    1001.循环位移#include<bits/stdc++.h>usingnamespacestd;typedefunsignedlonglongull;constintN=1048580*2;constintP=131;ullp[N],h1[N],h2[N];voidsolve(){stringa,b;cin>>a>>b;intn=a.size()......
  • 2024夏令营提高1模考0718模拟赛(提高1)补题报告
    2024夏令营提高1模考0718模拟赛(提高1)补题报告$$0718模拟赛(提高1)\\补题报告\2024年7月18日\by\\\唐一潇$$一、做题情况第一题比赛$100/100$,赛后通过第二题比赛$0/100$,赛后通过第三题比赛$0/100$,赛后通过第四题比赛$0/100$,赛后通过比......
  • 牛客day1的补题和总结
    C和I是签到题,没什么好说的。从A开始。A读题读了我20分钟,我才把样例弄懂。。这题目比cf阴间一佰倍,主要也是这类题的题面就是麻烦,有时候中文的题面的也能让我写一半回去再读几遍。这个主要就是写太慢了。完全可以更快的,而且这个思路我觉得大部分其实是lhgg帮我出的,我自己的思路......
  • 河南萌新联赛2024第(一)场 补题报告
    小蓝的二进制询问找规律,可以发现把从0开始的十进制数字转化为二进制。每一个二进制位有0或1两种状态。从低到高的第一位以2为周期,第二位以4为周期,第三位以8为周期……也就是说第n位以2^{n}为周期。每个周期都是前一半是0,后一半是1。举例:000001010011100……#inclu......
  • 码蹄杯国赛补题
    由于今天脑子没完全恢复,打算补一下题目清醒清醒加上寝室里无聊打算补补之前的题过过脑子提高一下A.MC0340矩阵虫题意:给你一个n构成n*n矩阵每一行数字依次为1,2,3,4...Code:#include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin......
  • Codeforces Round 958 (Div. 2)补题
    文章目录A题(拆分多集)B题(获得多数票)C题(固定OR的递增序列)A题(拆分多集) 本题在赛时卡的时间比较久,把这题想复杂了,导致WA了两次。后来看明白之后就是将n每次转换成k-1个1,到最后分不出来k-1个1直接一次就能分完,即结果加一;#include<bits/stdc++.h>#definein......