爆0的一场，寄寄寄。
A
\(n\)一开始肯定分成\(k\)份，每一份最多增加\(k-1\)。模拟计算即可。
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
int n,k; cin>>n>>k;
if(n==1)
{
cout<<0<<"\n";
return;
}
int ans=1;
int sum=k;
while(sum<n)
{
sum+=(k-1);
ans++;
}
cout<<ans<<"\n";
}
|
B
考虑少了一种情况：11在串中出现两次也是合法。
方法一：分类讨论直接写。
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
int n; cin>>n;
string s; cin>>s;
if(n==1)
{
if(s=="1") cout<<"YES\n";
else cout<<"NO\n";
return;
}
if(s[0]=='0' && s[n-1]=='0')
{
int cnt=0;
int cnt_1=1;
int maxn=0;
for(int i=0;i<n-1;i++)
{
if(s[i]==s[i+1] && s[i]=='1')
{
cnt_1++;
}
else
{
if(cnt_1>1)
{
cnt++;
}
maxn=max(cnt_1,maxn);
cnt_1=1;
}
}
if(maxn>2 || cnt>1) cout<<"YES\n";
else cout<<"NO\n";
}
else if(s[0]=='1' && s[n-1]=='1')
{
cout<<"YES\n";
}
else if(s[0]=='0' && s[n-1]=='1')
{
for(int i=0;i<n-1;i++)
{
if(s[i+1]==s[i] && s[i]=='1')
{
cout<<"YES\n";
return;
}
}
cout<<"NO\n";
}
else if(s[0]=='1' && s[n-1]=='0')
{
reverse(s.begin(),s.end());
for(int i=0;i<n-1;i++)
{
if(s[i+1]==s[i] && s[i]=='1')
{
cout<<"YES\n";
return;
}
}
cout<<"NO\n";
}
}
|
方法二：可以想到应该尽可能地少让1和0进行操作，应该尽量让全0串化为一个0。那么最终结果就会使一个由孤立0和1（连续或者不连续）组成的串。如果0的个数小于1则有解，否则无解。
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
int n; cin>>n;
string s; cin>>s;
int one=count(s.begin(),s.end(),'1');
int zero=0;
for(int i=0;i<s.size();i++)
{
if(s[i]=='0' && (i==0 || s[i-1]=='1'))
{
zero++;
}
}
if(zero<one)
{
cout<<"YES\n";
}
else
{
cout<<"NO\n";
}
}
|
C
观察样例发现都是以\(n\)结尾的，我们以样例四进行研究。
要使得单增，并且最长，且\(a_{i}|a_{i-1}=n
(2\leq i \leq
k)\)，我们进行倒推，那么第二大应该越大越好，同理推导下去。
14: 1 1 1 0
1 1 0 0
1 0 1 0
0 1 1 0
|
可以发现推导的结果如上。可以发现：从小到大，0一直在右移。我们可以统计\(n\)的组成，并且模拟这个过程，逐个进行计算输出。不过需要注意一些情况需要特判。
如果原来的数只有一个1（二进制），那么直接输出即可。
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
ll n; cin>>n;
vector<ll> a;
int k=0;
ll m=n;
int cnt=0;
while(n)
{
if(n&1)
{
a.push_back(k);
}
n>>=1;
k++;
}
if(a.size()==1)
{
cout<<1<<"\n";
cout<<m<<"\n";
return;
}
cout<<a.size()+1<<"\n";
cnt=a.size()-1;
for(int i=0;i<a.size();i++)
{
ll ans=0;
for(int j=0;j<a.size();j++)
{
if(j!=cnt)
{
ans+=(1ll<<a[j]);
}
}
cout<<ans<<" ";
cnt--;
}
cout<<m<<"\n";
}
|
另外一种写法：
可以发现我们可以使用位运算进行操作，只需要获取是哪个位置的1，并且进行异或运算即可。
#include <bits/stdc++.h>
#define lowbit(x) x&(-x)
const int MAXN=2e5+10;
const int mod=998244353;
using namespace std;
using ll=long long;
void solve();
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t=1;
cin>>t;
while(t--)
{
solve();
}
}
void solve()
{
ll n; cin>>n;
int one=__builtin_popcountll(n);
if(one==1)
{
cout<<1<<"\n"<<n<<"\n";
return;
}
cout<<one+1<<"\n";
for(int i=63;i>=0;i--)
{
if((n>>i) & 1)
{
cout<<(n^(1ll<<i))<<" ";
}
}
cout<<n<<"\n";
}
|
