#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
int sum[1<<16];
void solve()
{
cin>>n;
string s;cin>>s;
if(s=="1"||s=="0"||s=="01"||s=="10"){
cout<<"YES\n";
}
else cout<<"NO\n";
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
首先最大值肯定存在n里面最大的二进制的1的最高位
然后还有个结论是相邻的异或和最小,尽量是连续的数
所以直接在二进制的1的最高位的左边接个0断开就行了
其他连续就行
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
void solve()
{
cin>>n;
int mx=0;
for(int i=0;i<n;i++){
if((1<<i)<n){
mx=1<<i;
}
else break;
}
for(int i=1;i<mx;i++){
cout<<i<<" ";
}
cout<<"0 ";
for(int i=mx;i<n;i++) cout<<i<<" ";
cout<<"\n";
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
操作题先想操作性质
第三个操作使得 (a|b)>=max(a,b)
这个时候操作a已经没用了,只能让b增加到(a|b)
所以分类讨论
1先加a 然后或运算 然后让b增加
2.b增加 然后或运算 然后让b增加
因为b总和<=1e6 所以直接枚举操作增加多少次即可
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
void solve()
{
int a,b;
cin>>a>>b;
int res=b-a;
for(int i=a;i<=a+b-a;i++)
{
if(i==b)
{
res=min(res,i-a);
}
else
{
res=min(res,1+i-a+(i|b)-b);
}
}
for(int i=b;i<=b+b-a;i++)
{
res=min(res,i-b+1+(i|a)-i);
}
cout<<res<<"\n";
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
cin>>t;
while(t--) solve();
}
D:
gcd没思路就从因子身上出发
首先有个共同的点是,如果当前端点存在和前面点构成不合法区间
怎么办
修改当前端点为一个很大质数这样前面gcd都是1
又因为区间长度大于1所以前面的区间都不用管
维护一个pre 表示1到pre的区间都不用管了
先讲因子思路
每个数最多有logn个因子
所以直接枚举每个因子的开始区间和结束区间,
然后暴力枚举每个因子是否存在不合法的情况即可
假设因子开始区间是 l 结束区间是r
当前点是 i,因子是x
不合法就是 i-y+1=x
y=i-x+1
如果y在l到r则不合法
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
int f[N][22];
int gcd(int a, int b) // 欧几里得算法
{
return b ? gcd(b, a % b) : a;
}
void init(){
for (int j = 0; j < 20; j ++ )
for (int i = 1; i + (1 << j)-1<=n; i ++ )
if (!j) f[i][j] = a[i];
else f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int query(int l,int r){
int len=r-l+1;
int k=log(len)/log(2);
return gcd(f[l][k],f[r-(1<<k)+1][k]);
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int res=0;
int pre=0;
vector<array<int,3>> st;
for(int i=1;i<=n;i++){
for(auto&t:st){
t[2]=gcd(t[2],a[i]);
}
st.push_back({i,i,a[i]});
vector<array<int,3>> f;
for(int j=0;j<st.size();j++){
if(f.empty()){
f.push_back(st[j]);
}
else if(f.back()[2]==st[j][2]){
f.back()[1]=st[j][1];
}else f.push_back(st[j]);
}
swap(f,st);
for(auto&t:st){
int at=i-t[2]+1;
if(t[0]<=at&&at<=t[1]){
if(at>pre){
res++;
pre=i;
}
}
}
cout<<res<<" ";
}
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
// cin>>t;
while(t--) solve();
}
第二思路:
因为gcd是单调递减
上面的式子
i-y+1=x
i+1=x+y
因为y和x都是递减的
所以越靠左x+y越小,但是i+1是定值
满足二分
所以用个二分+st表查询区间gcd即可
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,mod=998244353;
#define int long long
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const long long inf=1e17;
using node=tuple<int,int,int,int>;
int n,m,k;
int a[N];
int f[N][22];
int gcd(int a, int b) // 欧几里得算法
{
return b ? gcd(b, a % b) : a;
}
void init(){
for (int j = 0; j < 20; j ++ )
for (int i = 1; i + (1 << j)-1<=n; i ++ )
if (!j) f[i][j] = a[i];
else f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int query(int l,int r){
int len=r-l+1;
int k=log(len)/log(2);
return gcd(f[l][k],f[r-(1<<k)+1][k]);
}
void solve()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
init();
int pre=1;
int res=0;
for(int i=1;i<=n;i++){
if(a[i]==1) res++,pre=i+1;
else{
int l=pre,r=i;
while(l<r){
int mid=l+r>>1;
if(query(mid,i)>=i-mid+1) r=mid;
else l=mid+1;
}
if(query(l,i)==i-l+1){
res++;
pre=i+1;
}
}
cout<<res<<" ";
}
}
signed main()
{
cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=1;
// cin>>t;
while(t--) solve();
}