CF1779A Hall of Fame 题解

· · 个人记录

可能更好的阅读体验

题目传送门

题目翻译

有 n 个纪念碑以及对应的 n 个台灯。
给定一个由 L 和 R 组成的序列 a，代表台灯的朝向。
如果第 i 个台灯为 L，代表着朝左，也就是 1,2,\dots,i-1 这些纪念碑都被照亮。
如果第 i 个台灯为 R，代表着朝右，也就是 i+1,i+2,\dots,n 这些纪念碑都被照亮。
现在你需要让所以的纪念碑被照亮。
你最多可以交换一次台灯，输出交换的位置。或者输出 0 代表不用交换，或者输出 -1 代表无解。

n,\sum n\le 10^5

题目解析

卡20minD2A，大耻辱
显然可以想到所以纪念碑都被照到的一个条件是存在 i<j 并且 a_i=R,a_j=L。
我们发现再加一个条件 i=j-1 依然成立。

所以只要存在 RL 就是不用交换。
存在 LR 翻转这两位即可。 全是 L 或 R 无解。

int n; char s[maxn];
void work(){
    n=read(); scanf("%s",s+1); int i;
    for(i=1;i<n;i++)
        if(s[i]=='L'&&s[i+1]=='R'){ print(i),pc('\n'); return; }
        else if(s[i]=='R'&&s[i+1]=='L'){ pc('0'),pc('\n'); return; }
    puts("-1"); return;
}

鞭尸：
赛时提交记录：
00:05:01 A Wrong answer on pretest 1 [pretests] → 187729108 （死因：题目看错）
（鬼知道我中间想了多久）
00:21:07 A Runtime error on pretest 2 [pretests] → 187749611 （死因：数组开小）
00:21:52 A Happy New Year! [main tests] → 187750590