Codeforces 1272 A-E

A Three Friends

直接枚举所有情况，共\(3\times 3\times 3=27\)种。

code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
int q;
int main(){
	//ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>q;
	while(q--){
		int a,b,c;
		cin>>a>>b>>c;
		int ans=abs(a-b)+abs(b-c)+abs(a-c);
		for(int i=-1;i<=1;i++){
			for(int j=-1;j<=1;j++){
				for(int k=-1;k<=1;k++){
					int x=a+i,y=b+j,z=c+k;
					ans=min(ans,abs(x-y)+abs(y-z)+abs(x-z));
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

B Snow Walking Robot

因为是无限大的网格，所以最简单的构造方法是走一个矩形框

注意要特判向任意方向走一步再走回起点的情况，样例中有。

code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=1e5+10;
int q;
char s[maxn];
int main(){
	ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>q;
	while(q--){
		cin>>s+1;
		int n=strlen(s+1);
		int L=0,R=0,U=0,D=0;
		for(int i=1;i<=n;i++){
			if(s[i]=='L') ++L;
			else if(s[i]=='R') ++R;
			else if(s[i]=='U') ++U;
			else ++D;
		}
		L=R=min(L,R);
		U=D=min(U,D);
		if(L&&U==0){
			cout<<2<<endl;
			cout<<"RL"<<endl;
		}else if(U&&L==0){
			cout<<2<<endl;
			cout<<"DU"<<endl;			
		}else if(U==0||L==0){
			cout<<0<<endl;
		}else{
			cout<<L*2+U*2<<endl;
			for(int i=1;i<=L;i++){
				cout<<'R';
			}
			for(int i=1;i<=D;i++){
				cout<<'D';
			}
			for(int i=1;i<=L;i++){
				cout<<'L';
			}
			for(int i=1;i<=D;i++){
				cout<<'U';
			}
			cout<<endl;
		}
	}
	return 0;
}

C Yet Another Broken Keyboard

在字符串s中所有不能打出的字母的位置作为隔板，隔出来的每个子串(设\(len\)为子串的长度)对答案的贡献即为\(len \times (len+1) /2\)。

code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=2e5+10;
int n,k;
char s[maxn],t[30];
int main(){
	ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>n>>k;
	cin>>s+1;
	for(int i=1;i<=k;i++){
		char c;
		cin>>c;
		t[c-'a']=1;
	}
	ll ans=0,cnt=0;
	for(int i=1;i<=n;i++){
		if(!t[s[i]-'a']){
			ans+=cnt*(cnt+1)/2;
			cnt=0;
		}else ++cnt;
	}
	ans+=cnt*(cnt+1)/2;
	cout<<ans<<endl;
	return 0;
}

D Remove One Element

\(O(n)\)预处理出\(l[i]\)为\(i\)作为终点的最长严格递增子段，\(r[i]\)为\(i\)作为起始点的最长严格递增子段。

不删除一个元素，\(ans=max\{l[i]\},(1<=i<=n)\)。
删除一个元素，\(ans=max\{l[i-1]+r[i+1]\},(1<i<n\&\&a[i-1]<a[i+1])\)

code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=2e5+10;
int n;
int a[maxn];
int l[maxn],r[maxn];
int main(){
	ios::sync_with_stdio(false);
	//freopen("in","r",stdin);
	cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>a[i-1]) l[i]=l[i-1]+1;
		else l[i]=1;
		ans=max(ans,l[i]);
	}
	r[n]=1;
	for(int i=n-1;i>=1;i--){
		if(a[i]<a[i+1]) r[i]=r[i+1]+1;
		else r[i]=1;
	}
	for(int i=2;i<n;i++){
		if(a[i+1]>a[i-1]) ans=max(ans,l[i-1]+r[i+1]);
	}
	cout<<ans<<endl;
	return 0;
}

E Nearest Opposite Parity

能发现若\(d[i+-a[i]]\)的值已确定，那么\(d[i]=min(d[i],d[i+-a[i]]+1)\)。

跟据这个性质我们以反边建图，所有边的边权都为1，以所有能一步到达奇偶性不同的点的点作为源点来跑最短路就行了(因为所有边权都为1，所以直接bfs也行)。

code

#include<bits/stdc++.h>
#define fi first
#define se second
#define lson l,mid,p<<1
#define rson mid+1,r,p<<1|1
#define pb push_back
#define ll long long
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
const int maxn=2e5+10;
int n;
int a[maxn];
vector<int>g[maxn];
int dis[maxn];
struct ppo{
    int v,c;
    bool operator <(const ppo &r) const{
        return c>r.c;
    }
};
int main(){
    ios::sync_with_stdio(false);
    //freopen("in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        dis[i]=inf;
        if(i-a[i]>=1){
            if(a[i-a[i]]%2!=a[i]%2) dis[i]=1;
            g[i-a[i]].pb(i);
        }
        if(i+a[i]<=n){
            if(a[i+a[i]]%2!=a[i]%2) dis[i]=1;
            g[i+a[i]].pb(i);
        }
    }
    priority_queue<ppo>q;
    for(int i=1;i<=n;i++){
        if(dis[i]==1) q.push(ppo{i,dis[i]});
    }
    while(!q.empty()){
        int u=q.top().v;q.pop();
        for(int x:g[u]){
            if(dis[u]+1<dis[x]){
                dis[x]=dis[u]+1;
                q.push(ppo{x,dis[x]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(dis[i]==inf) cout<<-1<<" ";
        else cout<<dis[i]<<" ";
    }
    return 0;
}