Codeforces 343B Alternating Current 题解
题意
有两根长度为$n (1\le n\le 10^5)$个单位,两头固定的电线,它们缠绕在一起,给定一个长为$n$,由+
和-
组成的字符串$s$,其中
若$s_i$为
+
,则在第$i$个单位长度时,第一根电线在第二根电线上。若$s_i$为
-
,则在第$i$个单位长度时,第二根电线在第一根电线上。
求不拔出电线且不移动装置时,是否能解开它们。若可以,输出Yes
;否则输出No
。
题解
根据题意知道:若两个+
或两个-
连在一起时,则那两个单位长度可以解开。
那么如果删去了所有的++
和--
后,字符串为空,则可以解开;否则不可以。
因为$1\le n\le 10^5$,所以程序的时间复杂度不能是$O(n^2)$,在字符串中暴力删除肯定不行。
考虑$O(n)$的做法。若当前长度为$i$,字符$s_i (0<i\le n)$等于$s_{i-1}$,则使$i=i-2$。这样删去后 后面的字符也可以和前面的字符配成++
或--
,符合题目要求。判断有没有删完即可。
使用stack
可以使程序更简洁。
程序
1 | // #pragma GCC optimize(2) |