2023南海区信息学区赛（初中组） T1二进制整除

第1题     二进制整除 查看测评数据信息

交换二进制数相邻两个位置的数字，需要花费1元的代价。

读入整数n以及n位二进制数(也许有前导0)，你需要依次回答n个独立的问题，第i个问题(1<=i<=n)是这样的：

假如要使得读入的二进制数是2^i的倍数，至少需要花费多少元的代价？如果不可能，则输出-1。

注意：每个问题都是独立的，不会相互影响，也就是说，每个问题只是假设，不会真的改变n位二进制数，纯粹是为了计算答案而已。

输入格式

第一行，一个整数n。1<=n<=100000。

第二行，n位二进制数，每位是0或1。

【提示】

60%的数据，n<=10。

输出格式

一行，共n个整数。

输入/输出例子1

输入：

5

10101

输出：

1 3 -1 -1 -1 

样例解释

无

分析：

注意这里，使二进制数是2^i的倍数，其实就可以转化为，能不能把二进制变成1后面全都是0

比如样例中

10101

i=1

想要为2^1的倍数，在i+1之前的位置都必须为0

原数2^0+2^2+2^4,=1+4+16=21

改变后2^1+2^2+2^4=2+4+16=22

22%2^1=22%2=0

为什么呢？因为至少满足i^2的倍数，那i+1这个位必须为1，然后他后面的数为1为0都行

2^1+2^2+2^4

看i=1后面的

拆解成

2+2*2+2*2*2*2

后面的数必然为i这个数的倍数，因为每个数都是i这个数乘了一定数量的2（都是在i这个数的基础上乘了很多个2），相加起来也就是很多个2相乘，加上i对应的数（这里是2*1），那么肯定为i这里的数的倍数

 但是前面的数不一定，因为并不是在i的基础上乘的

问题转化成了

i+1为1，包含i和i后面的数全为0最少交换几次

怎么找？有学长说并查集（没学不说。。）

我们模拟并查集（可能）

用双指针i，j定位0,1的位置

i是1，j是0，找到后交换

交换次数可以理解为

i-j，并不用真的一个一个统计，举例说明

#include <bits/stdc++.h>
using namespace std;

const int N=100005;
int n, i=0, j=0, ans=0, m=0, a[N], t=0;
char s[N];
int main()
{
	scanf("%d%s", &n, s+1);
	i=n, j=n;
    for (int k=1; k<=n; k++)
    	a[k]=-1;
	for (int k=n; k>=1; k--)
		if (s[k]=='0') a[n-k+1]=0; //1
		else break;
	for (int k=1; k<=n; k++)
	{
		ans+=i-j;
		a[n-i+1]=ans; //2
		
		while (s[i]!='1' && i>=1) i--; //3
		if (j>=i) j=i-1;//4
		while (s[j]!='0' && j>=1) j--;//5
		if (i<1 || j<1) break;	
		swap(s[i], s[j]);
	}
	
	for (int k=1; k<=n; k++)
		printf("%d ", a[k]);
	return 0;
}

1 注意这里，后面尾巴的零要特殊判断，这里卡了我好久  例如1010,0正常是无法处理的，会是-1次，但是实际上为0次
2 由于是从n往后，答案是倒着的，不好输出，统计起来答案
3 注意i>=1，否则可能越界
4 这里卡了1小时了快，只有j在i的后面才把j放i前面来，否则的话j按原位继续往下找，必须加if，不然时间超了，每次都重复回i来浪费了时间
5 同3