寻找证明我的算法在 codeforces 中有效的原因

Question

我正在尝试证明我的算法的正确性。
这是 codeforces 中的问题：https://codeforces.com/contest/1428/problem/C

这是我的 C++ 代码，已被接受：

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
 
using namespace std;
 
int main()
{
    int num, ans, top;
    string s;
 
    cin >> num;
 
    for (int i = 0; i < num; i++)
    {
        cin >> s;
 
        ans = s.size();
 
        top = 0; // meaning no characters behind
 
        for (int j = 0; j < s.size(); j++)
        {
            if (top == 0) top++;
            else if (s[j] == 'A') top++;
            else { ans -= 2; top--; }
        }
 
        cout << ans << endl;
    }
    return 0;
}

很容易看出，如果字符串中仍然包含B作为“中间字符”，我们总是可以进行更多的删除。而且为了让这个字符串尽可能短，我们总是会尝试用一个A删除B（所以，我们还有更多的B（s）继续删除过程）。

所以，解决这个问题的想法很简单：在跟踪字符串时，我们有一个名为 top 的变量，它“收集”所有的 A(s) 和字符串的第一个字符（原始字符或当 top = 0 时删除后的字符串）。每当我们遇到 B 时，如果我们收集了至少一个 A(top >= 2) 总是好的，或者我们不得不不情愿地用字符串的第一个字符擦除这个 B 而不知道它是 A 还是 B。

算法正确解决这个问题当且仅当：

删除所有中间B
它使字符串尽可能短

但是我们如何证明这个算法的正确性呢？显然，当 top >= 2 时，我的算法做了“正确的事情”。但是当 top = 1 时，我如何证明在不知道它是否是 A 的情况下用字符串的第一个字符擦除 B 的行为或者 B 是正确的？

我的进一步推理是这样的：
换句话说，有没有其他算法可以擦除相同数量的 AB 而不会遇到这种不情愿？

26/12/2021:

我们只考虑“真正不情愿”发生的情况。我的意思是当字符串的第一个字符是 B.

这么说吧，有这样“更好”和正确的算法（称之为 X）。也就是说：

X 擦除我们旧算法擦除的所有 AB。
有些时候我们的旧算法遇到“真正的不情愿”，但 X 找到了一个 AB 来擦除。

问题：问题是所有这些 AB 都在哪里？

(First character A)A...A B A...A B ... B*(characters of the original string)
-------------------^----------------^
-------------------|----bound Y----|

B* 是不情愿发生的地方。

首先要指出的是，根据条件1，X不允许用Y内部的A擦除Y外部的B。因为否则，Y内部存在一些B可以' t 被擦除，这证明 X 是一个错误的算法。 (*)

回到我们的问题，如果对于每一个这样的时刻，AB 都完全位于边界 Y 内，那么我们的旧算法会删除 X 所做的所有 AB。所以，X再好不过了。

所以，存在AB在Y之外的时刻，满足(*)。但是这个AB肯定很快就会被我们的算法抹掉（这个很容易想象和证明）。

B*...A...B...（这个A会被top收集，会和后面的B匹配）。
所以，X再好不过了。

因此，我们的算法是正确的。没有其他算法可以使字符串更短。

Answer 1

写的很棒。

这可能比您可能正在寻找的“正式证据”更具评论性。

这里有一些事情需要考虑：你根本不需要 ans 变量。 你只需在内部 for 循环完成时打印 top .当内部 for 循环完成时，我会断言 ans==top 无论如何。

因此，这种简化：

    cin >> s;
    top = 0; // meaning no characters behind

    for (char c : s)
    {
        if ((top == 0) || (c == 'A'))
        {
            top++;
        }
        else
        {
            top--;
        }
    }
    cout << top << endl;
}

您的算法有效地模拟了解析器堆栈的计数。每次从输入字符串中读取一个 char 时，它都会被压入堆栈。如果字符是 B（并且堆栈之前不是空的），则 B 和堆栈中的字符都会弹出。编写与堆栈相同的算法：

stack stk;
for (char c : s)
{
    if ((stk.size() == 0) || (c == 'A'))
    {
       stk.push(c);
    }
    else
    {
       stk.pop();  // 'B' was read => pop the previous element off the stack
    }
}

cout << stk.size() << endl;

以上是与您自己的代码相同的算法，但我们只是用实际堆栈替换了 top。因此，循环完成时仍保留在堆栈中的字符是原始字符串中无法折叠的字符。这就是我们在您的原始代码块中知道 top==ans 的方式。

如果您想打印实际折叠的字符串而不只是它的长度，只需反转堆栈即可

string temp;
while (stk.size() > 0)
{
   temp = string(s.front()) + temp;
   s.pop();
}
cout << temp << endl;

寻找证明我的算法在 codeforces 中有效的原因

Looking for a proof on why my algorithm in codeforces works

c++

proof-of-correctness