思路:
在每一个$0$,的左侧和右侧.都要插入两个0.
特判下边界,没有左侧和右侧的情况.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
int ans=0;
string s;cin>>s;
for(int i=0;i<s.size()-1;i++)
{
if(s[i]=='0')
{
if(s[i+1]=='0')ans+=2;
else
{
if(s[i+2]=='0'&&i+2<s.size())ans++;
}
}
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
B. Marin and Anti-coprime Permutation
结论题
思路：
当$n$,为奇数的时候,由于相邻的数一定是互质的,且一定是一奇数,一偶数的.
因此要想使得,$ gcd(1 * p_1 , 2 * p_2 , ...... , n * p_n) >1 $.就必须给每一个奇数$*2$
那么当$n$为奇数时,奇数数量严格比偶数多.就有一个奇数没有办法乘上偶数.
当$n$为偶数时,所有的奇数都可以乘上一个偶数,全部的数就都变成偶数了.$gcd\geq 2$
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=998244353;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
ll fac[1010];
void init()
{
fac[0]=1;
for(int i=1;i<=1001;i++)fac[i]=(fac[i-1]*i)%mod;
}
void solve()
{
ll ans=0;
ll n;cin>>n;
if(n%2==0)cout<<fac[n/2]*fac[n/2]%mod<<endl;
else cout<<"0"<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
init();
int t;cin>>t;
while(t--)solve();
return 0;
}
C. Shinju and the Lost Permutation
思路:
由于最大的数在第一位时 答案一定是$1$,而且操作是周期性的.以$n$为周期.
因此每次锁定$1$,所在位置.
每次向右移动的过程.答案至多$+1$或者不加.减小至多减小到$2$.
Proof
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n;cin>>n;
vector<int>a(2*n+1);
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=n+1;i<=2*n;i++)a[i]=a[i-n];
int pos=find(a.begin()+1,a.begin()+1+n,1)-a.begin();
if(pos==n+1)
{
cout<<"NO"<<endl;
return ;
}
if(n==1&&a[1]==1)
{
cout<<"YES"<<endl;
return ;
}else if(n>=2&&a[pos+1]!=2)
{
cout<<"NO"<<endl;
return ;
}
for(int i=pos+1;i<=pos+n-1;i++)
if(a[i]-a[i-1]==0||a[i]-a[i-1]==1)continue;
else
{
if(a[i]<a[i-1]&&a[i]>=2)continue;
else
{
cout<<"NO"<<endl;
return ;
}
}
cout<<"YES"<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
思路:
按位来构造$x$,每次统计原始排列$0,1,2,3,…r$.每一位上$0 1$的数量.
检查下 $array a$每一位上$0 1$的数量是否发生变化了.
如果发生变化了,则说明$x$在该位上必定是$1$.
如果没有发生变化,则说明$x$在该位上可能发生变化,也可能没有发生变化.这两种情况均可.
观察一下 $n=7$时,
000
001
010
011
100
101
110
首先,如果出现$0 1$数量相等,排列元素的个数必定是偶数.
那么,我们就发现,由于$l=0$,因此从$0$开始,每两个二进制数除去某一位不同以外,其余位完全相同.
那么当 排列的所有元素,在某一位上的$0 1$个数相等时,无论$x$在该位取$1$或者$0$.仅仅只是改变相邻的两个数的位置
因此并不会影响排列本身.
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define s() to_string()
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int cnt[18];
int cur[18];
void solve()
{
int l,r;
cin>>l>>r;
memset(cnt,0,sizeof cnt);
memset(cur,0,sizeof cur);
int n=r-l+1;
for(int i=0;i<=r;i++)
{
bitset<18>bit(i);
for(int k=0;k<18;k++)
if(bit[k]==1)cnt[k]++;
}
for(int i=1;i<=n;i++)
{
int x;cin>>x;
bitset<18>bit(x);
for(int k=0;k<18;k++)
if(bit[k]==1)cur[k]++;
}
bitset<18>bit;
for(int k=0;k<18;k++)
{
if(cur[k]!=cnt[k])bit[k]=1;
else bit[k]=0;
}
cout<<bit.ll()<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
字典树/位运算
思路:
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define s() to_string()
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int tr[N][2],idx;
void insert(string s)
{
int p=0;
for(auto c:s)
{
int u=c-'0';
if(!tr[p][u])tr[p][u]=++idx;
p=tr[p][u];
}
}
void init()
{
for(int i=0;i<=idx;i++)tr[i][0]=tr[i][1]=0;//把前一段用过的节点删除
idx=0;
}
PII query(int x)
{
PII ans;
int p=0;
bitset<18>bit(x);
string s=bit.s();
int pos=17;
bit.reset();
for(auto c:s)
{
int u=c-'0';
if(tr[p][u^1])
{
p=tr[p][u^1],bit[pos]=u^1;
}
else bit[pos]=u,p=tr[p][u];
pos--;
}
ans.first=(bit.ll()^x);
p=0,bit.reset(),pos=17;
for(auto c:s)
{
int u=c-'0';
if(tr[p][u])p=tr[p][u],bit[pos]=u;
else p=tr[p][u^1],bit[pos]=u^1;
pos--;
}
ans.second=(bit.ll()^x);
return ans;
}
void solve()
{
init();//清空字典树
int l,r;
cin>>l>>r;
set<int>st;
vector<int>a;
for(int i=l;i<=r;i++)
{
int x;cin>>x;
a.push_back(x);
bitset<18>bit(x);
string s=bit.s();
st.insert(x^l);
insert(s);
}
for(set<int>::iterator it=st.begin();it!=st.end();++it)
{
int x=*it;
PII ans=query(x);
int Max=ans.first,Min=ans.second;
if(Max==r&&Min==l)
{
cout<<x<<endl;
return ;
}
}
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
