AtCoder Beginner Contest 416 - AtCoder题解 | 123hh2 = Keep moving forward

# AtCoder Beginner Contest 416

比赛链接

# A - Vacation Validation

模拟

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	signed main()
	{
	int n=read(),l=read(),r=read();
	string awa;cin>>awa;
	int f=0;
	for(int i=l-1;i<r;i++)
	{
	if(awa[i]=='x') {f=1;break;}
	}
	if(f) cout<<"No";
	else cout<<"Yes";
	return _123hh2;
	}

# B - 1D Akari

贪心，能变成 o 就变

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	signed main()
	{
	string awa;cin>>awa;
	int f=1;
	for(int i=0;i<awa.size();i++)
	{
	if(awa[i]=='#') {f=1;cout<<awa[i];}
	if(awa[i]=='.')
	{
	if(f) cout<<'o';
	else cout<<'.';
	f=0;
	}
	}
	return _123hh2;
	}

# C - Concat (X-th)

注意到数据范围很小，我们可以直接暴力枚举所有可能拼接的字符串，排序后选第 $X$ 小的字符串即可

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	string awa[11];
	vector<string> qwq;
	signed main()
	{
	int n=read(),m=read(),k=read();
	for(int i=1;i<=n;i++) cin>>awa[i];
	sort(awa+1,awa+1+n);
	int chose[6]={0,1,1,1,1,1};
	string now="";
	for(int i=1;i<=m;i++) now+=awa[chose[i]];
	qwq.push_back(now);
	for(int i=2;i<=pow(n,m);i++)
	{
	chose[m]++;
	for(int j=m;j>=1;j--)
	{
	if(chose[j]==n+1) chose[j]=1,chose[j-1]++;
	}
	now="";
	for(int j=1;j<=m;j++) now+=awa[chose[j]];
	qwq.push_back(now);
	}
	sort(qwq.begin(),qwq.end());
	cout<<qwq[k-1];
	return _123hh2;
	}

# D - Match, Mod, Minimize 2

我们先把两个序列的数对 $M$ 取模，这样我们只需要求出使原式取模次数最多的方案

对于一个数 $x$ ，至少需要一个大于等于 $M - x$ 的数才能使取模次数增加

不妨将任意一个序列排序并从大到小枚举这个序列的数 $x_i$ ，找在另一个序列的最小的大于等于 $M - x_i$ 的数

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=3e5+5;
	int awa[maxn];
	multiset<int> qwq;
	signed main()
	{
	int t=read();
	while(t-->0)
	{
	int n=read(),m=read(),ans=0;
	for(int i=1;i<=n;i++) awa[i]=(read()%m);
	for(int i=1;i<=n;i++) qwq.insert(read()%m);
	sort(awa+1,awa+1+n);
	for(int i=n;i>=1;i--)
	{
	int now=awa[i];
	int f=m-now;
	auto it=qwq.lower_bound(f);
	if(it==qwq.end()) it--;
	ans+=((*it+now)%m);
	qwq.erase(it);
	}
	cout<<ans<<endl;
	}
	return _123hh2;
	}

# E - Development

$1 \leq N \leq 500$

显然考虑 $Floyd$

先用 $Floyd$ 将两点间距离 $dp[u][v]$ 求出来

对于操作 1，直接改变 $dp[u][v]$ 和 $dp[v][u]$ 的值并跑一遍更新，这是经典做法

对于操作 2，如果单纯每次加点就对每个更新的边重新跑 $n^2$ 的更新，复杂度是不允许的，但是注意到机场间是互连的，我们可以用一个源点 $n+1$ 表示经过了机场，这样更新点 $u$ 的时候只用更新 $dp[u][n+1]$ 和 $dp[n+1][u]$ ，转换成了操作 1

注意这样做会导致坐飞机的时间加倍，因此我们可以把公路时间也加倍，最后统计答案的时候除以 2 就可以了

对于操作 3，直接输出即可

总复杂度 $O(QN^2+N^3)$

注意：输入中包含重边，记得取 min

	#include<bits/stdc++.h>
	#define int long long
	#define in inline
	#define ri register
	#define _123hh2 0
	using namespace std;
	in int read()
	{
	int x=0,f=1;char ch=getchar();while(ch>'9'\|\|ch<'0') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}return x*f;
	}
	in void write(int x) {if(x<0) {x=-x;putchar('-');}if(x>9) write(x/10);putchar(x%10+'0');}
	const int maxn=505;
	int awa[maxn][maxn],dp[maxn][maxn];
	vector<int> D;
	signed main()
	{
	memset(dp,0x3f,sizeof(dp));
	int n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
	int u=read(),v=read(),w=read();
	if(w*2>=dp[u][v]) continue;
	dp[u][v]=dp[v][u]=w*2;
	}
	int k=read(),t=read();
	for(int i=1;i<=k;i++)
	{
	int x=read();
	dp[x][n+1]=dp[n+1][x]=t;
	}
	for(int i=1;i<=n+1;i++) dp[i][i]=0;
	for(int i=1;i<=n+1;i++)
	{
	for(int j=1;j<=n+1;j++)
	{
	for(int k=1;k<=n+1;k++)
	{
	dp[j][k]=min(dp[j][k],dp[j][i]+dp[i][k]);
	}
	}
	}
	int q=read();
	while(q-->0)
	{
	int op=read();
	if(op==1)
	{
	int u=read(),v=read(),x=read();
	if(dp[u][v]<=x*2) continue;
	dp[u][v]=dp[v][u]=x*2;
	for(int i=1;i<=n+1;i++)
	{
	for(int j=1;j<=n+1;j++)
	{
	dp[i][j]=min(dp[i][j],dp[i][u]+dp[v][j]+dp[u][v]);
	dp[i][j]=min(dp[i][j],dp[i][v]+dp[u][j]+dp[v][u]);
	}
	}
	}
	else if(op==2)
	{
	int x=read();
	D.push_back(x);
	int u=x,v=n+1;
	if(dp[u][v]<=t) continue;
	dp[u][v]=dp[v][u]=t;
	for(int i=1;i<=n+1;i++)
	{
	for(int j=1;j<=n+1;j++)
	{
	dp[i][j]=min(dp[i][j],dp[i][u]+dp[v][j]+dp[u][v]);
	dp[i][j]=min(dp[i][j],dp[i][v]+dp[u][j]+dp[v][u]);
	}
	}
	}
	else
	{
	int ans=0;
	for(int i=1;i<=n;i++)
	{
	for(int j=1;j<=n;j++)
	{
	if(dp[i][j]==0x3f3f3f3f3f3f3f3f) continue;
	ans+=dp[i][j]/2;
	}
	}
	write(ans),puts("");
	}
	}
	return _123hh2;
	}