Codeforces Round 958 (Div. 2)[部分题解ABC]

A. Split the Multiset

题意：

给一个包含一个整数n的集合和一个正整数k，在操作中，你可以任意选择集合中的数u，将其删除，并插入不超过k个整数，且·k个整数的和等于u，找到使集合中所有的数都变为1的最小操作数。

解题思路：

每次可任意选取转换为不超过k个整数，例如
6,3->1,1,4->1,1,1,1,2->1,1,1,1,1,1
最少操作3次，我们可以发现每次拆分出来（k-1）个1，在最后一次则可以拆分为k个1，因此我们可以将n中其中一个1，留到最后一次拆分，那么问题则转换为了（n-1）中含有多少个（k-1),如果不为整数个，则需加1。

解题思路：

#include
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int a[1010];
signed main()
{
	IOS
	int n;
	cin>>n;
	while(n--)
	{
			int a,b;
	cin>>a>>b;
	if(a==1)
	cout<<"0"<<endl;
	else if(a<=b)
	cout<<"1"<<endl;
	else
	{
		double x;
		int y;
		x=1.0*(a-1)/(b-1);
		y=(a-1)/(b-1);
		if(x!=y)
		y++;
		cout<<y<<endl;
	}
	}
	return 0;
}

B. Make Majority

题意：

给出一个由0，1组成的序列，我们可以任意选择范围，将其中的元素进行替换，替换规则为：在此范围中如果0的个数大于等于1的个数，则该范围替换为单个元素0，否则替换为单个元素1.根据输入的序列，判断是否可以用有限数量的操作使得a=[1].

解题思路：

最后的结果是让序列变为a=[1],我们应该尽量让1的数量大于0，因此我们可以将连续的多个0进行替换，变为一个0，然后将整个序列进行替换后，判断0，1的个数，如果0的个数大于等于1，则不能达到a=[1]的结果，输出“NO”，否则输出“YES”。

解题代码：

#include
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
signed main()
{
	IOS
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		string s;
		cin>>s;
		int x=0,y=0; 
		int p=0;
		for(int i=0;i<n;i++)
		{
			if(s[i]=='0'&&p==0)
			{
				x++;
				p=1;
			}
			if(s[i]=='1')
			{
				y++;
				p=0;
			}
		}
		if(x>=y)
		cout<<"NO"<<endl;
		else
		cout<<"YES"<<endl;
	}
	return 0;
}

C. Increasing Sequence with Fixed OR

题意：

给出一个正整数n，找到一个最长正整数的递增序列a=[a1,a2,…ak]，该数列满足a[i]|a[i-1]=n,其中表示按位or运算。
输入一个整数n,输出两行，第一行为最长子序列的长度，第二行为该序列，如果有多个满足条件的最长序列，输出其中一个即可。

解题思路:

这是一个多实例问题。
将n转换为2进制的数，二进制下其中含有ans个1，依次将不同位置的的1转换为0，可以得到ans个数，再加上n本身，共有ans+1个数，但由于题上要求为正整数序列，因此如果含有0，应该减去。

解题代码

#include
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=1e5;
int a[N],c[N];
int p;
void zh2(int x);
int zh10(int b[],int p);
signed main()
{
	IOS
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		if(n==1)
		cout<<"1"<<endl<<"1"<<endl;
		else
		{
			zh2(n);
			int ans=0;
			for(int i=0;i<=p;i++)
			{
				
				if(a[i]==1)
				ans++;
			}
			for(int i=1;i<=ans;i++)
			{
				int r=0;
				int b[N];
				for(int j=0;j<=p;j++)
				{
					b[j]=a[j];
					if(a[j]==1)
					{
						r++;
						if(r==i)
						b[j]=0;
					}
				}
				c[i]=zh10(b,p);
			}
			int o;
			if(c[ans]==0)
			{
				cout<<ans<<endl;
				o=ans-1;
			}
			
			else
			{
				cout<<ans+1<<endl;
				o=ans;
			}
			
			for(int i=o;i>=1;i--)
			{
				cout<<c[i]<<" "; 
			}
			cout<<n<<endl;
		}
	}
	return 0;
}
void zh2(int x)
{
	p=0;
	while(x/2!=0)
	{
		a[p++]=x%2;
		x=x/2;
	}
	a[p]=x%2;
}
int zh10(int b[],int p)
{
	int z=0;
	for(int i=p;i>=0;i--)
	{
		z=z*2+b[i];
	}
	return z;
 }