首页 > 其他分享 >2024/8/21 模拟赛

2024/8/21 模拟赛

时间:2024-08-21 21:38:44浏览次数:8  
标签:21 mid 2024 异或 答案 ans oplus 模拟 字典

T1

试卷答案

试卷由若干道不定项选择题构成,只有 ABCD 四个选项。每道题的答案是一个按字典序排列的非空字符串。例如,A、CD 是合法的答案,而 BB、DC 不是合法的答案。
一张合法的试卷由k道题目组成。
给定一个长度为\(n\)的由ABCD组成的字符串,进行\(Q\)次操作。
支持区间加(将区间内所有选项后移一位,D移位后为A)
区间查询(查询区间内有多少种不同的恰好包含\(k\)道题的试卷。

很容易想到用线段树,但是赛时却想不到怎么区间查询。
正常建一个线段树,每个节点记录4个数组。分别是将区间的所有选项移位0,1,2,3位后的尽可能大的连续的字典序上升子段数,同时对于每个子段长度单独记录子段数,方便后面计算。
例如BACDA移位0位的值为3 三个尽可能大的子段分别为B,ACD,A

然后区间查询时见L到mid和mid+1到R的数值相加。
判断s[mid]和s[mid+1]是否按字典序上升,如果是,那么将结果减一,代表两个段中有一个合法题目的答案连起来了。否则就不动。

最后统计答案的时候组合一下算答案即可。


T2

A+B Problem(ez)

本题有 \(T\) 组数据。对于一组数据,有 \(q\) 组询问,每次询问给定两个非负整数 \(a,b\),输出 \((a+b)\bmod2^{32}\)。

你需要“离线”回答每组询问。具体地,记第 \(i\) 次回答的答案为 \(ans_i\),在第 \(i\) 组询问中你读入 \(a_i',b_i'\) 后,真正询问的值为 \(a_i=a_i' \oplus ans_{i−1},b_i=b_i' \oplus ans_{i−1}\)。特殊地,记 \(ans_0=ans_q\)。

请求出 \(ans_1,...,ans_q\) 并输出。如果存在多组解,请输出字典序最小的解。

先找一个规律。
就是形如$ a \oplus x + b \oplus y$这类式子异或对加法运算的影响,由于是按位异或,现在只关注0和1的情况。

以下都是二进制方面考虑的

由于1和0异或0都不变,所以0没有影响,再来看1:

$1 \oplus 1 + 1 \oplus 1 $的最低位 = \(1 + 1\)的最低位
$1 \oplus 1 + 0 \oplus 1 $的最低位 = \(1 + 0\)的最低位
$0 \oplus 1 + 0 \oplus 1 $的最低位 = \(0 + 0\)的最低位
我们发现了,这个无论加法之前每个元素是不是异或过,结果的最低位都不会变。
所以我们可以根据a,b把所有对应的ans的第一位算出来,如果有进位的话就进位。这么一进位,第二位就有了,把ans[n+1]同步到ans[0]再根据ans已知的位数和a的后面的位数逐位计算ans的每一位,最后的解肯定是正确的。
至于字典序最小,都这么算了,很显然就只有一个解,所以放心输出就可以了。

标签:21,mid,2024,异或,答案,ans,oplus,模拟,字典
From: https://www.cnblogs.com/Kang-shifu/p/18372607

相关文章

  • 模拟赛25
    模拟赛25最近怎么狂挂不止。博弈考虑策略,首先是优先最小的,但是由于有重复的,所以在最小个数为偶数时会败,以此类推,可以想到当有一个数出现次数时奇数先手必胜,否则必败。考虑将相同的两两相消,发现\(u\tov\)和\(u\to根\tov\)是等价的。于是每个点维护一下当前的数,问题变......
  • 『模拟赛』暑假集训CSP提高模拟26
    Rank打得一般,倒数第二场了。。A.博弈直接搬了牛客的一套题。一眼没思路,模了一会放弃直接去打T2了,后来把\(\mathcal{O(n^2)}\)暴力打了拿30pts。正解用到了异或哈希。首先确定合法的数量即为总对数\(\frac{n(n-1)}{2}\)减去不合法的数量,而比较显然的,不合法的判断......
  • 2024.8.21 鲜花
    NeverGonnaGiveYouUpWe'renostrangerstoloveYouknowtherulesandsodoIAfullcommitment'swhatI'mthinkingofYouwouldn'tgetthisfromanyotherguyIjustwannatellyouhowI'mfeelingGottamakeyouunderstandNe......
  • [赛记] 暑假集训CSP提高模拟24
    与和100pts签到题但还是做了很久。。。考虑与的条件,可以发现,如果将$a$转化成二进制,那么二进制上为$1$的位置$x$和$y$都必须是$1$,所以首先将$s$减去$2\timesa$,然后再判断一下$(s-2\timesa)\operatorname{and}a$是否为$0$即可;赛时用......
  • 国内外ChatGPT镜像网站集合【2024-08-21最新】~
     一、GPT4o& &4.0turbo&GPT4omini介绍总有人问我,GPT4o、GPT4.0和GPT3.5有什么区别?国内怎么才能用上,听说很复杂以一张表来表达他们的区别吧GPT3.5、GPT3.5Turbo、GPT4.0均已经被官方放弃维护,也就是说我们其实已经使用不到这几个模型了。目前官方主流开放的模型有GP......
  • 【题解】Solution Set - NOIP2024集训Day12 树上启发式合并
    【题解】SolutionSet-NOIP2024集训Day12树上启发式合并https://www.becoder.com.cn/contest/5472「CF600E」Lomsatgelral直接dsuontree。记录每一个颜色的出现次数。「IOI2011」Race之前是用点分治做的。考虑dsuontree。每个子树内维护到根节点的距离为\(x\)......
  • 2024暑假集训测试30
    前言比赛链接。T1普及了一下异或哈希,T2、T3赛时应该算乱搞题,还搞挂了,T4高级平衡树题,不太可做。原题全部出自:2022牛客OI赛前集训营-提高组(第四场)。T1博弈部分分\(30pts\):\(O(n^2)\)暴力。正解:不难推出必胜策略就是\((x,y)\)路径上每个边权出现的次数不全为......
  • 汇总国内外ChatGPT镜像网站集合【2024-08最新】可无限制使用~
     一、GPT4o& &4.0turbo&GPT4omini介绍总有人问我,GPT4o、GPT4.0和GPT3.5有什么区别?国内怎么才能用上,听说很复杂以一张表来表达他们的区别吧GPT3.5、GPT3.5Turbo、GPT4.0均已经被官方放弃维护,也就是说我们其实已经使用不到这几个模型了。目前官方主流开放的模型有GP......
  • 【教学类-72-02】20240819建筑对称图纸02(图案最大化)
    背景需求【教学类-72-01】20240803建筑对称图纸01-CSDN博客文章浏览阅读423次,点赞13次,收藏5次。【教学类-72-01】20240803建筑对称图纸01https://blog.csdn.net/reasonsummer/article/details/140893003我感觉房子有大有小,有大量空白,我想让建筑变得最大使用以下代码,把房子......
  • 【教学类-76-01】20240820书包01(图案最大化)
    背景需求通义万相生成图片,把图案最大化的方法(切掉白边)【教学类-75-01】20240817“通义万相图片最大化+透明png”的修图流程-CSDN博客文章浏览阅读1.6k次,点赞56次,收藏17次。【教学类-75-01】20240817“通义万相图片最大化+透明png”的修图流程https://blog.csdn.net/reasons......