Codeforces Round #769 (Div. 2) A B C D
- 新年后的康复训练，把近几场vp了，题能补的补补掉。
A ABC(800)
思路： 明显$0$或$1$两者中其中一者出现次数大于等于$2$就一定无法重新排列成长度最大为$1$的回文。
- 参考代码：
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
string s;
cin>>s;
int sum1,sum2;
sum1=sum2=0;
for(int i=0;i<s.size();i++)if(s[i]=='0')sum1++;
else sum2++;
if(sum1>=2||sum2>=2)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
B Roof Construction(1000)
思路： 因为要求所以相邻数的$⊕$的最大值最小。那么在二进制形式下可以发现，最大的不超过$n$的$2^x$一定要和$0$相邻才能使得$⊕$最小，因为剩余的$2^x+1$~$n$之间的数可以通过相邻的放置使得$⊕$永远小于$2^x$和$0$的$⊕$值。
- 参考代码：
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int x=n-1;
int sum=1;
while(sum<x){
sum*=2;
}
if(sum>x)sum/=2;
for(int i=n-1;i>=sum;i--)cout<<i<<' ';
for(int i=0;i<=sum-1;i++)cout<<i<<' ';
cout<<endl;
}
return 0;
}
C Strange Test(1600)
- Tip:brute force、math
思路： 对于$methon3$有两种选择，一种是不使用$methon3$那么最少的操作次数显然是$b-a$，一种是使用$methon3$且最多只会使用一次，因为$a|b$$\ge$$b$，在操作一次$methon3$之后我们剩下的只需操作$methon2$即可。然后通过推公式可得：假设$c$$\ge$$a$，$d$$\ge$$b$，$c$和$d$是$a$和$b$通过操作$methon1$和$methon2$转变而来，那么我们可得公式：$sum=c-a+d-b+c|d-d+1=c+c|d+(1-a-b)$，由于$(1-a-b)$是$constant$所以我们最终的目标值是使$c+c|d$最小，$c$的迭代区间为$[a,b-1]$，因为$c$$\ge$$b$的话还不如$b-a$来的更优。由于$all$ $b$ $\le$ $1e6$所以跑暴力时间复杂度为$O(b)$可以接受。然后每次的$c$是确定的，为了$c|d$尽可能小，所以我们构造一个$d$即可($d$$\ge$$b$)。
$1:If$ $current$ $bit$ $of$ $c$ $is$ $0$ $and$ $b$ $is$ $1,$ $set$ $the$ $current$ $bit$ $of$ $d$ $to$ $1.$
$2:If$ $current$ $bit$ $of$ $c$ $is$ $0$ $and$ $b$ $is$ $0,$ $set$ $the$ $current$ $bit$ $of$ $d$ $to$ $0.$
$3:If$ $current$ $bit$ $of$ $c$ $is$ $1$ $and$ $b$ $is$ $1,$ $set$ $the$ $current$ $bit$ $of$ $d$ $to$ $1.$
$4:If$ $current$ $bit$ $of$ $c$ $is$ $1$ $and$ $b$ $is$ $0,$ $set$ $the$ $current$ $bit$ $of$ $d$ $to$ $1$ $and$ $stop.$
- 参考代码：
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
signed main(){
int t;
cin>>t;
while(t--){
int a,b;
cin>>a>>b;
int ans=b-a;
for(int c=a;c<b;c++){
int d=0;
for(int j=31;j>=0;j--){
if(b>>j&1){
d+=1<<j;
}
else{
if(c>>j&1){
d+=1<<j;
break;
}
}
}
ans=min(ans,c+(c|d)+1-a-b);
}
cout<<ans<<endl;
}
return 0;
}
D New Year Concert(2000)
- Tip: greedy、math、two pointers、sparse table
思路： 很不错的一道题，让我捡起了ST表，之前在$Acwing$学过倍增。但是对于ST表的建立和区间查询的板子还没有学习，这次给一起学了。感觉这道题综合了很多东西。首先如果一个区间内所有数的$gcd$等于该区间$r-l+1$那么这个区间是个$bad$的区间，我们的任务就是找到所有的$bad$区间，通过最小的更改使得所有的$bad$的区间消失。因为$a$的范围非常大，我们可以找一个很大的质数使得该原本$bad$的区间变成$good$的区间。然后我们需要在区间内选择一个数将其变成该很大的质数，显然区间的最后一个数是最优的(贪心)，因为可能后续有很多的$bad$区间的$l$会$\le$当前区间的$r$，那么更改最后一个，我们可以使得后续的那些$l$$\le$当前区间的$r$的区间全部变成$good$区间，这会使得我们最终的操作次数最少。然后区间查询$gcd$就套用$ST$表的板子。然后进行处理，有一个很强的性质，$gcd$会随着区间的变大越来越小，$r-l+1$会越来越大。而我们题目要求最终输出是随着$r$变大的在线区间内最小的更改次数。那么随着$r$变大如果$gcd($l$-$r$)$已经$<$$r-l+1$那么永远无法再找到$gcd($l$-$r$)$$==$$<$$r-l+1$因为前者会越来越小后者会越来越大。我们我们如果碰到$gcd($l$-$r$)$$<$$r-l+1$的情况我们需要将$l++$直到$gcd($l$-$r$)$$\ge$$r-l+1$。
- 参考代码：
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long
#define re register int
#define pb emplace_back
#define lowbit(x) (x&-x)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
int n;
const int N=2e5+10;
int a[N];
int st[N][20];
void make_st(){
int k=__lg(n);
for(int i=1;i<=n;i++)st[i][0]=a[i];
for(int i=1;i<=k;i++){
for(int j=1;j+(1<<i)-1<=n;j++){
st[j][i]=gcd(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
}
}
int query(int l,int r){
int k=__lg(r-l+1);
return gcd(st[l][k],st[r-(1<<k)+1][k]);
}
signed main(){
snow;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
make_st();
int ans=-1;
int res=0;
int l=1;
for(int r=1;r<=n;r++){
while(l<r&&query(l,r)<r-l+1)l++;
if(query(l,r)==r-l+1){
if(l>ans){
ans=r;
res++;
}
}
cout<<res<<' ';
}
cout<<endl;
return 0;
}
