AtCoder Beginner Contest 277 题解

掉大分力（悲

A - ^{-1}

直接模拟。

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

#define TIE cin.tie(0),cout.tie(0)

#define int long long

using namespace std;

int n,a[200005],x,ans;

signed main(){

	IOS;TIE;

	cin>>n>>x;

	for(int i=1;i<=n;i++){

		cin>>a[i];

		if(a[i]==x) ans=i;

	}

	cout<<ans<<endl;

	return 0;

}

B - Playing Cards Validation

直接判断即可。判重的话搞个 \(\text{map}\) 就好。

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

#define TIE cin.tie(0),cout.tie(0)

#define int long long

using namespace std;

int n,fl;

map<string,bool> mp;

string s;

signed main(){

	IOS;TIE;

	cin>>n;

	while(n--){

		cin>>s;

		if(mp[s]) fl=1;

		mp[s]=1;

		if(s[0]!='H'&&s[0]!='D'&&s[0]!='C'&&s[0]!='S'){

			fl=1;

		}

		if(s[1]!='A'&&s[1]!='J'&&s[1]!='Q'&&s[1]!='K'&&s[1]!='T'&&!(s[1]>='2'&&s[1]<='9')){

			fl=1;

		}

	}

	cout<<(fl?"No":"Yes")<<endl;

	return 0;

}

C - Ladder Takahashi

考虑用 \(\text{map}\) 进行离散化，同时记下每个楼层离散化之前的值，然后就可以建图跑 \(\text{DFS}\) 了。

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

#define TIE cin.tie(0),cout.tie(0)

#define int long long

using namespace std;

int n,u,v,ans=1,tot=1,val[200005];

map<int,int> mp;

vector<int> a[200005];

bool vis[200005];

void dfs(int x){

	for(int i=0;i<a[x].size();i++){

		int tmp=a[x][i];

		if(!vis[tmp]){

			ans=max(ans,val[tmp]);

			vis[tmp]=1;

			dfs(tmp);

		}

	}

}

signed main(){

	IOS;TIE;

	cin>>n;

	mp[1]=1;

	for(int i=1;i<=n;i++){

		cin>>u>>v;

		if(!mp[u]) mp[u]=++tot,val[tot]=u;

		if(!mp[v]) mp[v]=++tot,val[tot]=v;

		a[mp[u]].push_back(mp[v]);

		a[mp[v]].push_back(mp[u]);

	}

	vis[1]=1;

	dfs(1);

	cout<<ans<<endl;

	return 0;

}

实际上就是求排序后最大连续整数段和。但是有一个取模的条件，也就是说可以是 \(m-2,m-1,0,1,2,\dots\) 这样的一段，所以考虑复制一遍排序后的数组。同时末尾放一个未出现数，防止最后一段取不到。设这样求出的最大连续整数段和为 \(mx\)，原先所有数之和为 \(sum\)，则最后答案为 \(\max(0,sum-mx)\)。和 \(0\) 取 \(\max\) 是为了防止整段形成一个环，使得有些数取了两次。

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

#define TIE cin.tie(0),cout.tie(0)

#define int long long

using namespace std;

int n,a[400005],m,sum;

signed main(){

	IOS;TIE;

	cin>>n>>m;

	for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];

	sort(a+1,a+n+1);

	int tmp=0,mx=0;

	a[0]=a[1];

	for(int i=n+1;i<=n*2;i++) a[i]=a[i-n];

	a[n*2+1]=-1;

	for(int i=1;i<=n*2+1;i++){

		if(a[i]==a[i-1]||a[i]==(a[i-1]+1)%m) tmp+=a[i];

		else{

			mx=max(mx,tmp);

			tmp=a[i];

		}

	}

	cout<<max(sum-mx,0ll)<<endl;

	return 0;

}

E - Crystal Switches

考虑当成普通的 \(\text{BFS}\) 求最短路来做。不同之处在于，边是否可走与当前开关状态有关。想到，每个点在一种状态下应当只被访问一次，因为相同状态多次访问情况会变得相同。所以只需要把原先的 \(vis\) 数组改成二维，记 \(vis_{0/1,i}\) 表示边为 \(0/1\) 状态时是否更新过 \(i\)。所以在 \(\text{BFS}\) 的队列中也要再加入一个参数 \(now\) 表示当前状态。

设初始状态为 \(0\)，\(k.to\) 为当前队首，\(k.now\) 为当前队首状态，\(tmp.fl\) 为走向某一条边的初始状态，\(mark_i\) 为点 \(i\) 是否有开关，则有：

若 \(k.now\oplus tmp.fl=1\)，可以不更改状态更新
否则，若 \(mark_{k.to}=1\)，可以更改状态更新

#include<bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

#define TIE cin.tie(0),cout.tie(0)

#define int long long

using namespace std;

int n,m,k,s,u,v,t,ans=1e18;

bool mark[200005],vis[2][200005];

struct node{

	int to,fl;

};

vector<node> a[200005];

struct Node{

	int to,ans,now;

};

queue<Node> q;

signed main(){

	IOS;TIE;

	cin>>n>>m>>k;

	for(int i=1;i<=m;i++){

		cin>>u>>v>>t;

		a[u].push_back({v,t});

		a[v].push_back({u,t});

	}

	for(int i=1;i<=k;i++) cin>>s,mark[s]=1;

	vis[0][1]=1;

	q.push({1,0,0});

	while(q.size()){

		Node k=q.front();q.pop();

		if(k.to==n){

			cout<<k.ans<<endl;

			return 0;

		}

		for(int i=0;i<a[k.to].size();i++){

			node tmp=a[k.to][i];

			if(k.now^tmp.fl){

				if(!vis[k.now][tmp.to]){

					vis[k.now][tmp.to]=1;

					q.push({tmp.to,k.ans+1,k.now});

				}

			}

			else if(mark[k.to]){

				if(!vis[k.now^1][tmp.to]){

					vis[k.now^1][tmp.to]=1;

					q.push({tmp.to,k.ans+1,k.now^1});

				}

			}

		}

	}

	cout<<-1<<endl;

	return 0;

}

咕咕咕

巴特西

AtCoder Beginner Contest 277 题解

A - ^{-1}

B - Playing Cards Validation

C - Ladder Takahashi

D - Takahashi's Solitaire

E - Crystal Switches

最新文章

热门文章