这里写目录标题
A思维题【AC】
思路：每次分成k-1个1，1个其他
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
//const int N = 2e5+10;
void solve()
{
int n,k;cin>>n>>k;
int cnt=0;
if(k>=n)
{
if(n==1)cout<<0<<endl;
else cout<<1<<endl;
return ;
}
while(n>k)
{
n=n-(k-1);
cnt++;
}
if(n!=0)cnt++;
cout<<cnt<<endl;
return ;
}
int main()
{
int t;cin>>t;
while(t--)
{
solve();
}
return 0;
}
B贪心（+双指针）【补题】
思路：多个连续的0当作一个0，一个1还是一个1。
egg:
100111001
cnt0=2,cnt1=5
冗余代码（我的）：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5+10;
int a[N];
void solve()
{
int n;cin>>n;
int cnt1=0,cnt0=0;
string s;cin>>s;
for(int i=0;i<n;i++)a[i]=s[i]-'0';
int f0=0;
for(int i=0;i<n;i++)
{
if(a[i]==1)
{
if(f0==1)cnt0++;
cnt1++;
f0=0;
}
else
{
f0=1;
}
}
if(a[n-1]==0)cnt0++;
if(cnt1>cnt0)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
// cout<<"num0:"<<cnt0<<","<<"num1:"<<cnt1<<endl;
}
int main()
{
int t;cin>>t;
while(t--)
{
solve();
}
return 0;
}
大佬：双指针代码
指针i慢指针，指针j快指针
#include<bits/stdc++.h>
using namespace std;
char s[200005];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
scanf("%s",s+1);
int c0=0,c1=0;
for(int i=1;i<=n;){
int j=i;
while(j<=n&&s[j]==s[i])++j;
if(s[i]=='0')++c0;
else c1+=j-i;
i=j;
}
puts(c1>c0?"Yes":"No");
}
return 0;
}
借鉴后代码
#include<bits/stdc++.h>
using namespace std;
char s[200005];
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
scanf("%s",s+1);
if(s[n]=='0')s[n+1]='1';
else s[n+1]='0';
int c0=0,c1=0;
for(int i=1,j=1;i<=n+1;)
{
if(s[i]==s[j])i++;
else
{
if(s[j]=='1')c1+=i-j;
else c0++;
j=i;
}
}
// cout<<"num0:"<<c0<<","<<"num1:"<<c1<<endl;
puts(c1>c0?"Yes":"No");
}
return 0;
}
C异或问题【补题】
存在n,输出最长数组a,使得 a[i] | a[i+1]=n
a,b,c,d,e
a|b=b|c=c|d=d|e=n
思路：将n变成二进制数，例如:n=23=16+4+2+1=10111
答案：23,23-1,23-2,23-4,23-16【23,22,21,19,6】
若n=1,2,4,8,16,32,64等，答案：n
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
long long a[N];
long long lowbit(long long n)
{
return -n&n;
}
void slove()
{
long long n;cin>>n;
long long k=0,t=n;
if(lowbit(t)==n)
{
cout<<1<<endl;
cout<<n<<endl;
return;
}
a[k++]=n;
while(t!=0)
{
a[k++]=n-lowbit(t);
t=t-lowbit(t);
}
cout<<k<<endl;
for (int i = k-1; i >=0; i -- )cout<<a[i]<<" ";
cout<<endl;
}
int main()
{
int t;cin>>t;
while(t--)
{
slove();
}
return 0;
}