文章目录
A题 (拆分多集)
本题在赛时卡的时间比较久，把这题想复杂了，导致WA了两次。后来看明白之后就是将n每次转换成k-1个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)
#define fi first
#define se second
#define PII pair <int,int>
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
int a[N],b[N];
void solve () {
int n,k;
cin>>n>>k;
if(n==1) {
cout<<0<<'\n';return;
}
int pos=0;
while (n>k) {
n-=k-1;
pos++;
}
cout<<pos+1<<'\n';
}
signed main () {
IOS;
int T =1;
cin>>T;
while(T--) solve ();
return 0;
}
B题(获得多数票)
题意就是给出一段字符串，字符串里面只包含0,1。然后可以找到
[
l
,
r
]
[l,r]
[l,r]区间里面，将区间里面的字符串变成一个字符，这个字符是0或1，到底是哪个，图片中有详细描述。
思路：将字符串里面连续的0全部转化成一个0，再比较0,1个数
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair <int,int>
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
int a[N],b[N];
void solve () {
int n;cin>>n;
string s;cin>>s;
int cnt=0,ans=0;int j;
for (int i=0;s[i]!='\0';) {
if (s[i]=='0') {
cnt++;
j=i;
while (s[j]=='0')j++;
i=j;
}
else {
i++;ans++;
}
}
if (cnt>=ans)cout<<"NO"<<'\n';
else cout<<"YES"<<'\n';
}
signed main () {
IOS;
int T =1;
cin>>T;
while(T--) solve ();
return 0;
}
C题（固定 OR 的递增序列）
题意：给一个数字n，写出一个序列，要求递增，并且两项之间或运算为n
思路：根据我的理解，就是要把原数字的二进制上的数字1换成零，例如23的二进制10111。后续的数字如果要符合条件就要在10111有1的地方换成0.例如10110,10101之类的。这时就要考虑如何将1换掉了。利用二进制的特点，用23不断除以二，判断是否是奇数（因为只有除以2为奇数，二进制上才为1），是奇数的话，就可以减去
2
n
2^n
2n(这样可以直接将二进制上的1变成0)。最后逆序输出
#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define fi first
#define se second
#define PII pair <int,int>
#define ALL(x) x.begin(),x.end()
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
int a[N],b[N];
void solve () {
int n;cin>>n;
if (n==1||n==2) {
cout<<1<<'\n'<<1<<'\n';return ;
}a[0]=n;
int k=0;
int t=n,pos=1;
while (t) {
if (t&1) {
a[++k]=n-pos;
}
pos*=2;t/=2;
}
if (a[k]==0) {
cout<<1<<'\n'<<n<<'\n';return;
}
cout<<k+1<<'\n';
for (int i=k;i>=0;i--) {
cout<<a[i]<<' ';
}
cout<<'\n';
}
signed main () {
IOS;
int T =1;
cin>>T;
while(T--) solve ();
return 0;
}