题目分析

题意简述

本题接受多组测试数据，每组数据包含三个整数$n$、$m$、$k$以及两个分隔字符。当输入的整数$n$为$-1$时，程序结束。对于每组有效输入，通过对两个**位集合（bitset）**进行一系列的位操作，最终输出$n$、$m$、$k$以及经过操作后位集合中被设置为$1$的位的数量。

输入

• 多组测试用例，每组首先输入一个整数$n$，若$n = -1$，则程序结束。
• 若$n$不为$-1$，继续输入一个字符、整数$m$、字符、整数$k$，其中字符用于分隔数据。

输出

对于每组有效输入，按照格式“$n$,$m$,$k$: $count$”输出，其中$n$、$m$、$k$为输入的整数，$count$是经过一系列位操作后得到的位集合中值为$1$的位的数量。

解题思路

位集合初始化

1. 定义两个bitset<130>类型的变量$c$和$a$，其中bitset是一种用于处理位集合的数据结构。
2. 使用a.set(i)将位集合$a$的前$n$位设置为$1$，表示初始的一种状态。
3. 使用c.set(i)将位集合$c$的前$m$位设置为$1$ ，表示另一种初始状态。

位操作与状态更新

通过循环for(int i = 0; i < k; i++)，对$c$进行$k$次操作：

1. 首先检查$c$的第$n - 1$位是否为$1$，即bool l = c.test(n - 1);。
2. 将$c$左移一位得到新的位集合$t$，即bitset<130> t = c<<1;。
3. 如果$c$的第$n - 1$位为$1$，则将$t$的第$0$位设置为$1$，即if(l) t.set(0);。
4. 通过异或操作c = c ^ t;更新$c$的状态。

结果计算与输出

1. 使用按位与操作c = c & a;，将$c$与$a$进行按位与，得到最终的位集合状态。
2. 通过c.count()获取最终位集合$c$中值为$1$的位的数量，并按照格式“$n$,$m$,$k$: $count$”输出结果。

代码实现

#include <stdio.h>
#include <bitset>
using namespace std;
int n, m, k;
char f;
int main() {
    while(1){
        scanf("%d", &n);
        if(!(~n)) return 0;
        bitset<130> c;
        bitset<130> a;
        for(int i = 0; i < n; i++) a.set(i);
        scanf("%c%d%c%d", &f, &m, &f, &k);
        for(int i = 0; i < m; i++) c.set(i);
        for(int i = 0; i < k; i++){
            bool l = c.test(n - 1);
            bitset<130> t = c<<1;
            if(l) t.set(0);
            c = c ^ t;
        }
        c = c & a;
        printf("%d,%d,%d: %d\n", n,m,k,c.count());
    }
    return 0;
}

代码说明

1. 变量定义：定义全局变量$n$、$m$、$k$用于存储输入的整数，$f$用于存储分隔字符。
2. 输入处理：通过while(1)循环持续读取输入，使用scanf("%d", &n);读取整数$n$，当$n = -1$时，通过if(!(~n)) return 0;结束程序。继续使用scanf("%c%d%c%d", &f, &m, &f, &k);读取分隔字符和整数$m$、$k$。
3. 位集合初始化：创建位集合$c$和$a$，并分别通过循环将$a$的前$n$位、$c$的前$m$位设置为$1$。
4. 位操作循环：通过循环对$c$进行$k$次操作，包括检查特定位、左移、条件设置位以及异或操作，更新$c$的状态。
5. 结果计算与输出：对$c$和$a$进行按位与操作，然后通过c.count()获取$c$中值为$1$的位的数量，并按照指定格式输出结果。