Code Jam 2017 Qualification Round Problem A. Oversized Pancake Flipper

短命女 2022-04-16 00:30 121阅读 0赞

# 题目 #

给定字符串 S 由`+`或`-`组成和 K ，现有一种操作：能将串 S 中连续 K 个字符进行反转（ `+` 变成`-`以及 `-`变成`+` ）。问最少进行多少次上述操作，可以把串 S 变成全由 + 组成。当然也可能无解，即不能将所有字符都变成`+`。  
[Oversized Pancake Flipper][]。  
输入：  
![在这里插入图片描述][20181114201531265.png]  
输出：  
Case \#1: 3  
Case \#2: 0  
Case \#3: IMPOSSIBLE

# 思路 #

在整个数组上有多个滑动区间`[i, i+K-1]`。操作就是会对区间内的符号进行翻转。

某个元素最终是加还是减，跟将它覆盖掉的区间数量的奇偶性有关，而与这些区间的执行顺序无关。

从左到右，能对0索引产生影响的只有区间`[0, 0+K-1]`，在将0索引处理后，0索引就应该保持现状，所以执行后面的区间；同理，1索引只被区间`[1, 1+K-1]`影响。

所以当到了最后一个区间`[n-K+1,n]`时，应判断是否区间内符号都为加（区间前面的符号都已经到达了正确状态），否则无解。

# 代码 #

f = open('A-large-practice.in',encoding='utf-8')
    num = eval(f.readline().strip())
    li = []
    Kli = []
    for line in f:
        temp = line.strip().split()
        li.append(temp[0])
        Kli.append(int(temp[1]))    
    
    def inverse(sLi,start,end):
        for i in range(start,end+1):
            if sLi[i] == '+':
                sLi[i] = '-'
            else:
                sLi[i] = '+'
    
    def solve(s,k):
        #s is str
        #k is int
        count = 0
        n = len(s)
        sLi = [i for i in s]
        for i in range(0,n-k+1):
            #from 0 to n-k,i present current section's start index
            if i != n-k:
                #只保证当前区间第一个元素为1
                if sLi[i] == '-':
                    inverse(sLi,i,i+k-1)
                    count += 1
            else:
                if sLi[i] == '-':
                    inverse(sLi,i,i+k-1)
                    count += 1
                flag = True
                for j in range(n-k,n):
                    if sLi[j] == '-':
                        return False
        return count
    
    out = open('result.out','w',encoding='utf-8')        
    for i in range(len(li)):
        resu = solve(li[i],Kli[i])
        if resu is False:
            out.write('Case #%d: IMPOSSIBLE\n'%(i+1))
        else:
            out.write('Case #%d: %d\n'%(i+1,resu))
        
    out.close()

[Oversized Pancake Flipper]: https://code.google.com/codejam/contest/3264486/dashboard
[20181114201531265.png]: /images/20220416/f4562afc93b74556afe410d7336f4c99.png