题解：P14258 好感（favor）

Giorno_ · 2025-10-19 16:10:28 · 题解

提供一种非常规做法。

问题：

题目大意：给定一个 01 串 a，每次可以选择一个 a_i 进行取反操作且 a_{1 \sim i} 中的元素下标减一，即 a_{k-1} \gets a_k。并将 a_0 的值赋到 a_i，代价为 i。求将 01 串 a 中元素全部转化为 0 或 1 的最小代价。

思路：

Step1：

对于一个 a_x，假设对 a_{x+1 \sim n} 内的元素进行了 k 次操作，那么位置会变为 a_{x-k}，对其代价相应的会减少 k。因为每次操作只会影响到 i 及其以前的下标，所以考虑倒序遍历，可以做到每次操作后使下次操作的代价也减少。

Step2:

对于每个 a_i，若其不是我们想要的值才会进行操作。因此为了避免对一个 a_i 重复操作，应保证操作前 a_1 为我们想要将 a_i 转化为的值，因为每次操作后实际上是将 a_1 的值赋到 a_i 上。

Step3：

对于每个 a_i 我们有两种选择：

1. 保持不变。
2. 将其进行取反操作并把 1 \sim i 的元素向前移动。

因为我们是倒序遍历，那么每个不需要修改的元素或是已经修改的元素都不会影响到我们后续到操作，所以可以直接删去，因此可以保证每次遍历的 a_i 都为 01 串 a 的最后一个元素，那么其对应的代价也变成了 01 串 a 的长度或者是元素个数。

Step4：

我们可以总结每次操作的总体流程为:

1. 将 a_i 进行取反操作。
2. 将 1 \sim i 内所有下标减一。
3. 将 a_0 移动到 a_i 位置。
4. 统计代价 i。

观察每个流程，可以发现：
第一步可以看成将 a_i 删除后在原位置加入 a_i 取反后的值。
第二步可以看作将 1 \sim i 所有元素向前移动。
第三步可以看作将第一个元素移动到末尾（因为我们保证了当前遍历的 a_i 为 01 串的最后一个元素）。
第四步可以看作获取 01 串的长度（因为我们保证了当前遍历的 a_i 为 01 串的最后一个元素）。

综合起来发现，每一个操作都符合队列的基本操作！！！那么现在就要请出我们的 deque 双端队列了！！！

实现方式：

定义一个双端队列 q，将字符串转化为数字后存入队列。以队列不为空为条件循环，每次判断队列首元素是否为想要转化的值。

• 若不是，花费 1 的代价（队首元素下标为 1）将队首元素改变。
• 否则，判断队尾元素是否需要操作：
  1. 若需要操作：将队尾弹出，重新插入想要的值（对应取反操作）；将队首元素弹出（此时队内其他元素自动向前移动一格），插入到队尾。将答案加上代价即队列长度。
  2. 若不需要：直接弹出即可，因为我们后续不可能再遍历到它了。 若所有元素均已修改完成，队列中所有值均会弹出，停止循环，此时统计的代价即最小代价。

特别的，因为我们不知道究竟要把所有的 1 改为 0 还是要把所有的 0 改为 1，所以两种方案同时进行取最小值作为最终答案。

代码实现:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int N = 1e6 + 10;
ll t,a[N],n,b[N];
deque<ll>q;
inline ll c1(){//将所有1转换为0的最小化费
    q.clear();
    ll ans = 0;
    for(int i = 1;i <= n;i ++)q.push_back(a[i]); 
    while(!q.empty()){
        if(q.front() == 1)q.pop_front(),q.push_front(0),ans ++;//若队首元素不是我们想要的 修改 
        if(q.back() == 0)q.pop_back();//若不用修改 从队尾弹出即可 
        else {ans += q.size();q.pop_front();q.pop_back();}//等价于 ans += q.size();int x = q.front();q.pop_front();q.pop_back();q.push_back(0);q.push_back(x);
    }
    return ans;
}
inline ll c0(){//将所有0转换为1的最小化费
    q.clear();//多测不清空，爆零两行泪 
    ll ans = 0;
    for(int i = 1;i <= n;i ++)q.push_back(a[i]);
    while(!q.empty()){
        if(q.front() == 0)q.pop_front(),q.push_front(1),ans ++; 
        if(q.back() == 1)q.pop_back();
        else {ans += q.size();q.pop_front();q.pop_back();}
    }
    return ans;
}
inline void solve(){
    cin >> n;
    string s;
    cin >> s; 
    int pos = 0;
    for(auto x : s){pos ++,a[pos] = x - '0';} 
    cout << (ll)min(c1(),c0()) << endl; 
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> t;
    while(t --)solve();
    return 0;
}