题解归档 - cf343B

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf343B
• 本地来源：problems/cf343B/idea.md
• 题目链接：https://codeforces.com/contest/343/problem/B
• 原始标题：cf343B — Alternating Current

思路

cf343B — Alternating Current

题意

两根电线从墙（左）连到设备（右）。左侧 plus 固定在上、minus 在下。给定从左到右每个交叉点的相对顺序：+ 表示 plus 在上，- 表示 minus 在上。问能否在不拔线、不移动设备的前提下，通过拉伸/移动电线消除所有交叉。

做法

相邻两个相同的交叉可以一并「抬走」消除（题面样例 ++、-++- 均如此）。因此问题等价于：能否把字符串完全消空。

用栈贪心：扫一遍，若当前字符与栈顶相同则弹栈，否则压栈。最终栈空则 Yes，否则 No。

• -++-：- → + → ++ 抵消 → - 抵消 → 空 → Yes
• +-：无法消尽 → No
• ++：抵消 → Yes
• -：单独一个 → No

复杂度 O(n)，n ≤ 10^5。

验证

• 四组官方样例通过
• 与暴力「反复删相邻相同字符对」对拍 50 组（Kali/WSL 不可用时本地验证）

代码

来源：problems/cf343B/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:52:35
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s;
char st[100005];
char zc(char c,ll i){
    if(i%2==0){
        if(c=='+') return 'A';
        return 'B';
    }
    if(c=='+') return 'B';
    return 'A';
}
int main(){
    cin>>s;
    ll top=0,i,n=s.size();
    for(i=0;i<n;i++){
        char c=zc(s[i],i);
        if(top and st[top-1]!=c) top--;
        else st[top++]=c;
    }
    if(top==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}