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;

}

巴特西

Codeforces 1272 A-E

Codeforces 1272 A-E

A Three Friends

code

B Snow Walking Robot

code

C Yet Another Broken Keyboard

code

D Remove One Element

code

E Nearest Opposite Parity

code

最新文章

热门文章