Codeforces Round #731 (Div. 3)

A. Shortest Path with Obstacle
题意
给你三个点，$a_x,a_y,b_x,b_y,f_x,f_y$从a点到b点，f点是障碍物，问最少需要多少步。
思路
直接模拟就可以了。
代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int main()
{int t;cin>>t;while(t--){int xa,ya,xb,yb,xf,yf;cin>>xa>>ya>>xb>>yb>>xf>>yf;int ans=abs(xa-xb)+abs(ya-yb);//cout<<xa<<" "<<xb<<" "<<xf<<endl;if(xa==xb&&xb==xf){int maxx=max(ya,yb);int minn=min(ya,yb);if(minn<=yf&&yf<=maxx) ans+=2;}if(ya==yb&&yb==yf){int maxx=max(xa,xb);int minn=min(xa,xb);if(minn<=xf&&xf<=maxx) ans+=2;}cout<<ans<<endl;}return 0;
}

B - Alphabetical Strings
题意
给你一个字符串，让你判断是不是由题目中的条件拼接出来的。
条件：
思路
找到字母a，然后从这个点用两个指针向两边看是否有满足条件的字母。
代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int main()
{int t;cin>>t;while(t--){string s;cin>>s;bool flag=true;int id=-1;int len=s.length();for(int i=0 ; i<len ; i++)if(s[i]=='a'){id=i;break;}if(id==-1) flag=false;if(!flag){cout<<"NO"<<endl;continue;}int l=id-1,r=id+1;char c='b';int cnt=1;while(cnt<len){//cout<<l<<" "<<r<<" "<<c<<endl;bool flag1=false;if(l>=0&&l<len){if(s[l]==c){l--,cnt++,c++;flag1=true;continue;}}if(r<len&&r>=0){if(s[r]==c){r++,cnt++,c++;flag1=true;continue;}}if(!flag1){flag=false;break;}}if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;
}

C - Pair Programming
题意
给你两个数组a和b，如果$a_i=0||b_i=0$是相当于加一行代码，如果$a_i>0或者b_i>0$就表明修改$a_i或b_i$行的代码，但是要确定这一行有代码。
把两个数组拼接在一起，尽量使$a_i>0||b_i>0$的时候有代码。
思路
让两个数组中为0的排在前面，如果没有0就把两个较小的放在前面。
代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int a[110],b[110],ans[110];
int main()
{int t;cin>>t;while(t--){memset(ans,0,sizeof ans);int k,n,m;cin>>k>>n>>m;for(int i=1 ; i<=n ; i++) cin>>a[i];for(int i=1 ; i<=m ; i++) cin>>b[i];int i=1,j=1;bool flag=true;for(int z=1 ; z<=n+m ; z++){if(a[i]==0&&i<=n){ans[z]=a[i],i++,k++;continue;}if(b[j]==0&&j<=m){ans[z]=b[j],j++,k++;continue;}if(k>=a[i]&&i<=n){ans[z]=a[i],i++;continue;}else if(k>=b[j]&&j<=m){ans[z]=b[j],j++;continue;}else flag=false;}if(flag){for(int z=1 ; z<=n+m ; z++) cout<<ans[z]<<" ";cout<<endl;}else cout<<"-1"<<endl;}return 0;
}

D. Co-growing Sequence
题意
定义一种递增序列，如果$a_i$&$a_{i+1}=a_i$那就说明这个序列是递增的。
现在给你一个序列x，让你对x进行构造，使成为递增序列，构造的方式是
$x_i$=$x_i$^$y_i$，让你找出最小的y的序列。
思路
直接模拟就可以了。
代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 1e6+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int a[N],ans[N];
int qmi(int n,int k)
{int res=1;while(k){if(k&1) res*=n;n*=n;k>>=1;}return res;
}
int f(int x,int y) {int x_b[35];int y_b[35];int x_b1[35];int y_b1[35];memset(x_b,0,sizeof x_b);memset(y_b,0,sizeof y_b);int cnt_x=0,cnt_y=0;while(x){x_b[++cnt_x]=x%2;x/=2;}while(y){y_b[++cnt_y]=y%2;//cout<<y_b[cnt_y]<<endl;y/=2;}for(int i=1 ; i<=cnt_x ; i++){x_b1[i]=x_b[cnt_x-i+1];}for(int i=1 ; i<=cnt_y ; i++){y_b1[i]=y_b[cnt_y-i+1];}int ans=0;/*for(int i=1 ; i<=30 ; i++) cout<<x_b[i]<<" ";cout<<endl;for(int i=1 ; i<=30 ; i++) cout<<y_b[i]<<" ";cout<<endl;*/for(int i=1 ; i<=30 ; i++){if(x_b[i]==1&&y_b[i]==0) ans+=qmi(2,i-1);}return ans;
}
int main()
{int t;cin>>t;while(t--){int n,cnt=1;ans[1]=0;cin>>n;for(int i=1 ; i<=n ; i++) cin>>a[i];for(int i=2 ; i<=n ; i++){ans[++cnt]=f(a[i-1],a[i]);a[i]^=ans[cnt];//cout<<a[i-1]<<" "<<a[i]<<endl;}for(int i=1 ; i<=n ; i++) cout<<ans[i]<<" ";cout<<endl;}return 0;
}

我写的有些复杂了，当时被reverse这个函数搞了，不知道为啥一直错。
E - Air Conditioners
题意
给你n个点，有k个点上是有空调的，每个空调有一个温度，最后求出每个点上的温度。
计算每个点的温度的公式是：

也就是k个空调的距离加上他们的温度的最小值。
题意
昨天晚上的时候没有思路。
昨天晚上能想到的性质就是每个空调只能影响一部分点。
看来题解以后发现，我们可以把每个点收到的影响分为左和右，分开来看，然后再取最小值，在一个方向上，我们可以用o(n)的时间来维护出左边温度和右边点的温度，所以是可以解决的。
其实仔细思考的时候确实，因为每个点左边的空调和右边的空调都会对这个点有影响，如果我们分开来考虑，这个题就简单了很多了。
代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 3e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int a[N],t[N],c[N],ans[N],l[N],r[N];
int main()
{int T;cin>>T;while(T--){int n,k;cin>>n>>k;for(int i=1 ; i<=k ; i++) cin>>a[i];for(int i=1 ; i<=k ; i++) cin>>t[i];for(int i=1 ; i<=n ; i++) c[i]=INF;for(int i=1 ; i<=k ; i++) c[a[i]]=t[i];int p=INF;for(int i=1 ; i<=n ; i++){p=min(p+1,c[i]);l[i]=p;}p=INF;for(int i=n ; i>=1 ; i--){p=min(p+1,c[i]);r[i]=p;}for(int i=1 ; i<=n ; i++) cout<<min(l[i],r[i])<<" ";cout<<endl;}return 0;
}

F - Array Stabilization (GCD version)
题意
给你一个序列a，定义一种操作
$b_i$=$gcd(a_i,a_{i+1})$，$b_n=gcd(a_n,a_1)$，这样可以得到序列b，
a的序列和b的序列是相等的。
问你经过多少次这种操作可以使a中的所有元素都相等。
思路
我们很容易想到，最后相等元素就是所有的元素的最大公约数。
我们经过转换会发现：
第一次的$b_1=gcd(a_1,a_2)$。
第二次的$b_1=gcd(a_1,a_2,a_3)$.
第三次的$b_1=gcd(a_1,a_2,a_3,a_4)$.
第一次的$b_2=gcd(a_2,a_3)$。
第一次的$b_3=gcd(a_2,a_3,a_4)$。
我们从这里知道，经过n-1以后肯定可以使序列相等，但是可能并不需要n-1次，我们可以二分这个次数，然后用st表来查询区间最大公约数可以解决问题。
代码

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
const int N = 4e5+10;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
int a[N],Log[N],f[N][30];
int n,gc;
void Getlog()//log预处理
{Log[0]=-1;for(int i=1;i<=2*n;i++)Log[i]=Log[i>>1]+1;
}
void RMQ()//st表预处理
{for(int j=1;j<=Log[2*n];j++)for(int i=1;i+(1<<j)-1<=2*n;i++)f[i][j]=__gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int lr_gcd(int l,int r)
{int k=Log[r-l+1];return __gcd(f[l][k],f[r-(1<<k)+1][k]);
}
bool check(int x)
{for(int i=1 ; i<=n ; i++){//cout<<i<<" "<<lr_gcd(i,i+x)<<" "<<gc<<endl;if(lr_gcd(i,i+x)!=gc) return false;}return true;
}
int main()
{int t;cin>>t;while(t--){gc=0;cin>>n;for(int i=1 ; i<=n ; i++) cin>>a[i],a[i+n]=a[i];for(int i=1 ; i<=n ; i++) gc=__gcd(gc,a[i]);for(int i=1 ; i<=n*2 ; i++) f[i][0]=a[i];Getlog();RMQ();int l=0,r=n;while(l<r){int mid=l+r>>1;//cout<<l<<" "<<r<<endl;if(check(mid)) r=mid;else l=mid+1;}cout<<l<<endl;}return 0;
}