上大大大大大分!!!
A
题意解析:自己翻译去。
没什么好说的,使用 string 数组,for 循环输入,判断用 ==。我这里使用了三目运算符,等价于 if else。
时间复杂度:O(n∣s∣)O(n|s|)O(n∣s∣)。
B
题意解析:
定义 f(x)f(x)f(x) 为 xxx 的十进制位反转后的结果。如 f(114514)=415411f(114514)=415411f(114514)=415411。
定义 “反转斐波那契数列”AnA_nAn 如下:
An={xn=1yn=2f(An−1+An−2)n≥3A_n= \begin{cases} x & n=1\\ y & n=2\\ f(A_{n-1}+A_{n-2}) & n\ge 3 \end{cases} An =⎩⎨⎧ xyf(An−1 +An−2 ) n=1n=2n≥3
现给定 x,yx,yx,y,求 A10A_{10}A10 的值。
我们可以用 to_string 和 stoi(stoll) 模拟反转过程,然后递推求就行了。注意开 long long。
时间复杂度:O(1)O(1)O(1)。
C
题意解析:
给定一个 AB 字符串,每次操作可以交换相邻两个元素,问最少操作多少次可以变成一个 ABABAB... 或 BABABA... 字符串。
懒得写了,反正就是不考虑 A 或 B 把交换当做移动就行。直接亮代码。
时间复杂度:O(n)O(n)O(n)。
F
题意解析:给定一个数组 AAA,AAA 最初只有一个元素,该元素为 000。
你需要进行 qqq 次操作,每次操作分为操作 111 和操作 222。
* 操作 111:给定一个正整数 xxx,在 AAA 数组元素为 xxx 的后一个位置添加一个元素 iii。
* 操作 222:给定两个正整数 x,yx,yx,y,令 x,yx,yx,y 在 AAA 数组的下标分别为 p,qp,qp,q,则请你输出 AAA 数组中区间 [min{p,q}+1,max{p,q}−1][\min\{p,q\}+1,\max\{p,q\}-1][min{p,q}+1,max{p,q}−1] 的所有元素和,并删除该区间。
显然,操作 222 影响不到操作 111,因为无论何时 AAA 中的元素都互不相同,如果某个数 kkk 被删除了,那么操作 111 就不能让 x=kx=kx=k 了。同理,操作 222 之间也互不影响。
所以我们可以离线所有的操作,预处理出如果没有操作 222,最终的 AAA 中每个位置的值和每个值对应的下标。显然可以使用链表求出。
然后按顺序执行每次操作,开一个线段树,操作 111 直接将 xxx 对应的下标改成 xxx,操作 222 用求出区间和,然后将区间的所有值都设为 000 即可。
时间复杂度:O(qlogq)O(q\log q)O(qlogq)。