首页 > 其他分享 >AT_agc011_d [AGC011D] Half Reflector 题解

AT_agc011_d [AGC011D] Half Reflector 题解

时间:2024-11-13 15:31:28浏览次数:1  
标签:Reflector int 题解 AGC011D rept 异或 Half

用 \(1\) 表示 A,\(0\) 表示 B,观察进行一次操作后字符串会发生什么变化。首先当第一个数为 \(1\) 时,只会将第一个数变为 \(0\)。对于剩下的情况,手玩一下可以发现会将第一个数移到末尾,然后将所有数异或 \(1\)。

先考虑暴力怎么做,可以记一个指针 \(i\) 和当前应该给全体数异或的值 \(c\)。如果 \(a_i\neq c\),则将 \(a_i\) 改为 \(1\),否则将 \(i\) 往后移一位,\(c\) 取反。发现操作等价从左到右将每个数依次跟 \(i\bmod 2\) 比较,如果不同就改正,最多进行 \(2n\) 次操作后就会进入循环。当 \(n\) 为偶数时循环节长度为 \(1\),奇数长度为 \(2\),将 \(k\) 缩小后暴力操作即可,时间复杂度 \(\mathcal O(n)\)。

参考代码:

#include<bits/stdc++.h>
#define mxn 200003
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
using namespace std;
int n,k,c,a[mxn];
char s[mxn];
signed main(){
	scanf("%d%d%s",&n,&k,s+1);
	rep(i,1,n)a[i]=s[i]=='A'?0:1;
	if(!(n&1))k=min(k,n*2);
	else if(k>=n*4)k=(k-n*2)%(n*2)+n*2;
	int r=1;
	rept(i,0,k){
		if(a[r]==c)a[r]^=1;
		else c^=1,r=r%n+1;
	}
	rept(i,0,n)putchar((a[r]^c)?'B':'A'),r=r%n+1;
	return 0;
}

标签:Reflector,int,题解,AGC011D,rept,异或,Half
From: https://www.cnblogs.com/zifanoi/p/18544061

相关文章

  • P10856 【MX-X2-T5】「Cfz Round 4」Xor-Forces题解
    题意:给定一个长度为\(n=2^k\)的数组\(a\),下标从\(0\)开始,维护\(m\)次操作:给定\(x\),设数列\(a'\)满足\(a'_i=a_{i\oplusx}\),将\(a\)修改为\(a'\)。其中\(\oplus\)表示按位异或运算。给定\(l,r\),查询\(a\)的下标在\(l,r\)之间的子数组有多少颜色段。不保......
  • [题解]P3225 [HNOI2012] 矿场搭建
    P3225[HNOI2012]矿场搭建挖煤点坍塌相当于把该点和与其相连的边在图上删掉。借用wjyyy的题解,我们定义“叶子连通块”为“只包含\(1\)个割点的点双连通分量”,“非叶子连通块”为“包含\(\ge2\)个割点的点双连通分量”。如下图,橙色点是割点,红色框圈出的是点双,加粗的是叶子连通......
  • P2612 [ZJOI2012] 波浪 题解
    前置知识:连续段dp题目链接:P2612[ZJOI2012]波浪随机一个\(1\)到\(n\)的排列\(P_{1...n}\),问以下式子的值\(\lem\)的概率是多少?\[|P_1-P_2|+|P_2-P_3|+|P_3-P_4|+...+|P_{n-1}+P_n|\]输出一个答案表示概率。保留\(k\)位小数。对于\(40%\)......
  • P11071 「QMSOI R1」 Distorted Fate题解
    题意:给定一个序列,给定两种操作:将一个区间异或上一个给定的值。给定\(l,r\)求\[{\large(\sum_{i=l}^r\bigcup_{j=l}^iA_j)\bmod2^{30}}\]\(0\lea_i,x<2^{30}\),\(1\lel\ler\len\)思路由于操作数以及区间过大,一位一位地去模拟肯定是不行的。因此考虑去离线......
  • [题解]CF1407D Discrete Centrifugal Jumps
    思路注意到第二个条件和第三个条件本质相似,可以用相同的维护方式处理,因此这个只讨论第二个条件的维护方式。定义\(dp_i\)表示走到\(i\)的最少步数。第一个条件的转移显然为\(dp_i\leftarrowdp_{i-1}\)。对于第二个条件,\(i\)能向\(j\)转移,当且仅当\(h_{i+1\sim......
  • Codeforces Round 985 div1+2 个人题解(A~E)
    CodeforcesRound985div1+2个人题解(A~E)Dashboard-Refact.aiMatch1(CodeforcesRound985)-Codeforces火车头#include<bits/stdc++.h>usingnamespacestd;#defineftfirst#definesdsecond#defineyescout<<"yes\n"#definenoc......
  • [CF1935E] Distance Learning Courses in MAC 题解
    [CF1935E]DistanceLearningCoursesinMAC难度正常的一道题。首先我们发现“挑选若干个区间”就是一句废话,因为按位或只会贡献答案而不会减小答案。所以我们需要在\([L,R]\)的每个区间都挑一个数,使得最终的按位或最大。想办法让尽可能多的二进制位都变成\(1\),且越是高......
  • [USACO06NOV] Corn Fields G 题解
    题目链接[USACO06NOV]CornFieldsG题解这是一道典型的状压dp,对于\(M\)行\(N\)列的图,由于每个点只有\(1\)和\(0\)两种状态,我们将其压缩为一个长度为\(M\)的数组,数组(\(g\))的每一项\(g_{i}\)表示状态的二进制表示法表示的数(如\(101\)表示为\(5\)),我们预先处......
  • [CEOI2023] A Light Inconvenience 题解
    Description今年CEOI的开幕式上有一场精彩的火炬表演。表演者们站成一排,从\(1\)开始从左往右编号。每个表演者举着一根火炬,初始只有一个举着点燃的火炬的表演者。表演分为\(Q\)幕。在第\(a\)幕开始之前,要么\(p_a>0\)个表演者从右侧加入表演,他们的火炬是熄灭的;要么最......
  • gym103102H AND = OR 题解
    非常巧妙的一个题。我们首先考虑单组询问该怎么做。首先需要注意到一个结论,即设答案为\(x\),那么对于\(\forally<x\),\(y\)都应该放在与组;同样的,对于\(\forally>x\),\(y\)都应该放在与组。进一步的,我们观察在\(\text{popcount}\)上也有同样的性质,即对于\(\forally,......