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的每一位,最后的解肯定是正确的。
至于字典序最小,都这么算了,很显然就只有一个解,所以放心输出就可以了。