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<bits/stdc++.h>
#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<bits/stdc++.h>
#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<bits/stdc++.h>
#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;
}
原文地址：https://blog.csdn.net/2302_80707071/article/details/140458073
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！