CodeForces904(Div2)B

N_Position · 2023-10-22 17:58:28 · 题解

CF1884B 题解

题目翻译

共 t 数据，对于每一组数据，有一个正整数 n 和一个仅由数字 0 和 1 组成的长度为 n 的字符串。

每一次操作，你可以交换相邻的两个字符。

对于每一个 i\in\left[1,n\right] 输出最小的操作次数使得原字符串对应的二进制数是 2^{i} 的倍数。

题目分析

当 i=1 时，显然只要字符串的最后一位为 0 即可。 设倒数第 i 个 0 位于整个字符串的倒数第 k_i 位，操作所需的次数 ans_1 为 k_1-1。

同理当 i\ne1 时，操作次数为 ans_i=ans_{i-1}+k_i-k 次。

对于无解情况：当需要 0 的个数大于所有的 0 的个数时，显然无解。

代码实现

实现复杂度为 O(tn)，其中 j 表示最后一个未使用过的 0 的位置，注意 ans 可能会爆 long long。

for(ll i=1;i<=n;i++){
    while(s[j] != '0' && j>=0){
        j--;
    }
    if(j < 0){
        printf("-1 ");
    }
    else{
        ans += (n-i-j);
        printf("%lld ",ans);
    }
    j--;
}

完整代码