526互联

AtCoder Beginner Contest 308 ABCDEF

发布时间 2023-07-04 00:34:45作者: nannan4128

[AtCoder Beginner Contest 308](AtCoder Beginner Contest 308 - AtCoder)

A - New Scheme

Problem Statement

题意：给你8个数，如果满足以下条件输出Yes，否则输出No

条件：

  1. 单调不减
  2. 大小在100到675之间
  3. 都是25的倍数

Solution

按照题意判断即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll last = 0;

int main()
{
	bool ok = true;
	for(int i = 1;i<=8;i++)
	{
		string s;
		cin>>s;
		if(s.size()>3)ok = false;
		ll x = stol(s);
		if(x>675||x<100)ok = false;
		if(x%25)ok = false;
		if(x<last)ok = false;
		last = x;
	}
	if(ok)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

B - Default Price

Problem Statement

题意：给你N个串，代表不同的颜色，再给你M个串，对于M个价格，如果上述N个串中有M个中没出现过的，那价值就是p0.问你价格是多少。

Solution

思路：模拟，用map映射一下就ok

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 110;
int n,m;
map<string,int>mp;
string s[N],t[N];
int price;
int main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
		cin>>s[i];
	for(int i = 1;i<=m;i++)
		cin>>t[i];
	int p0;
	cin>>p0;
	for(int i = 1;i<=m;i++)
	{
		int p;
		cin>>p;
		mp[t[i]] = p;
	}
	ll ans = 0;
	for(int i = 1;i<=n;i++)
	{
		if(mp[s[i]])ans+=mp[s[i]];
		else ans += p0;
	}
	cout<<ans<<endl;
	return 0;
}

C - Standings

Problem Statement

题意：给你N组\(A_i\)和\(B_i\),用\(\dfrac{Ai}{Ai+Bi}\)表示胜率。问胜率按从大到小排的结果。

Solution

思路：之间用小数算会有精度问题，我们对柿子变形一下。

\(\dfrac{A_i}{A_i+B_i}>\dfrac{A_j}{A_j+B_j}\)

\(A_i*(A_j+B_j)>A_j*(A_i+B_i)\)

用long long记录，判断即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
array<ll,3>v[N];
bool cmp(array<ll,3>a,array<ll,3>b)
{
	if(a[0]*(b[0]+b[1])!=b[0]*(a[0]+a[1]))return a[0]*(b[0]+b[1])>b[0]*(a[0]+a[1]);
	else return a[2]<b[2];
}
int main()
{
	int n;
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		ll a,b;
		cin>>a>>b;
		v[i] = {a,b,i};
	}	
	sort(v+1,v+1+n,cmp);
	for(int i = 1;i<=n;i++)
	{
		cout<<v[i][2]<<" ";
	}
	cout<<endl;
	return 0;
}

D - Snuke Maze

Problem Statement

题意：起点是(1,1)，终点是(n,m)，问你存不存在从(1,1)走到(n,m)都是"snuke"的循环的一条路径呢？

Solution

思路：\(dfs\)搜，注意\(vis\)数组不用回溯，因为这条路不能走，换个方向肯定也是不行的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N  = 510;
int n,m;
char a[N][N];
int dir[5][2]={{1,0},{0,1},{0,-1},{-1,0}};
string s = "snuke";
bool ok;
bool in(int x,int y)
{
	return x>=1&&x<=n&&y>=1&&y<=m;
}
bool vis[N][N];
void dfs(int x,int y,int cur)
{
	if(ok)return;
	if(x==n&&y==m)
	{
		ok = true;
		return;
	}
	for(int i = 0;i<4;i++)
	{
		int dx = x+dir[i][0],dy = y+dir[i][1];
		if(in(dx,dy)&&a[dx][dy] == s[(cur+1)%5]&&!vis[dx][dy])
		{
			vis[dx][dy] = true;
			dfs(dx,dy,(cur+1)%5);
		}
	}
}


int main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	if(a[1][1]!='s')
	{
		cout<<"No\n";
		return 0;
	}
	vis[1][1] = true;
	dfs(1,1,0);
	if(ok)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

E - MEX

Problem Statement

题意：给你一个长度为N的串S，由MEX三种字母组成

找到所有的\((i,j,k)\)满足\((A_i,A_j,A_k)\)是MEX的，求他们的\(mex\)的和。

\(mex\)表示没出现过的最小非负整数。

Solution

思路：前缀和思想。

直接枚举肯定是不行的，复杂度太高了。

我们可以对M进行分类,按类别计数。

\(cntl[i][0\)~\(2]\)表示前缀的前\(i\)个有多少个M = 0，M = 1，M = 2的

同理对X统计后缀:

\(cntr[i][0\)~\(2]\)表示后缀的后\(i\)个有多少个X = 0，X = 1，X = 2的

按照上述操作，接下来我们只需要考虑E。

我们枚举E，用\(mex\)函数算值，设E的位置是\(pos\)，那么我们用\(cntl[pos-1][0\)~ \(2]*cntr[pos+1][0\)~\(2]*1*mex\)

注意不要爆int，开long long。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int a[N];
string s;
int cntl[N][3],cntr[N][3];
ll res;
int mex(int i,int j,int k)
{
	int ans = 0;
	if(i==0||j==0||k==0)
	{
		ans++;
		if(i == 1||j==1||k==1)
		{
			ans++;
			if(i == 2||j==2||k==2)
			{
				ans++;
			}
		}
	}
	return ans;
}
int main()
{
	int n;
	cin>>n;
	for(int i = 1;i<=n;i++)
		cin>>a[i];
	cin>>s;
	s ="?"+s;
	for(int i = 1;i<=n;i++)
	{
		if(s[i]=='M')
			cntl[i][a[i]]++;
		for(int j = 0;j<3;j++)
			cntl[i][j] += cntl[i-1][j];
	}
	if(s[n]=='X')cntr[n][a[n]]++;
	for(int i = n-1;i>1;i--)
	{
		if(s[i]=='X')
			cntr[i][a[i]]++;
		for(int j = 0;j<3;j++)
			cntr[i][j] += cntr[i+1][j];
	}

	for(int i = 2;i<n;i++)
	{
		if(s[i]!='E')continue;
		for(int j = 0;j<3;j++)
		{
			for(int k = 0;k<3;k++)
			{
				res += 1ll*cntl[i-1][j]*cntr[i+1][k]*mex(j,a[i],k);
			}
		}
	}
	cout<<res<<endl;
	return 0;
}

F - Vouchers

Problem Statement

思路：\(N\)种商品，对应价格是\(P。有M个优惠券，满\)\(L_i\)减\(D_i\)

问你怎么买最便宜？

Solution

思路：贪心。能优惠就优惠。用set 的 lower_bound二分，找到第一个大于等于限制\(L_i\)的\(P_i\),当然优惠券要按优惠力度排序先。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
ll p[N],sum;
bool vis[N];
map<ll,int>cnt;
set<ll>s;
struct ty
{
	ll l,d;
}a[N];
bool cmp(ty a,ty b)
{
	return a.d>b.d;
}
main()
{
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		int x;
		cin>>x;
		cnt[x]++;
		s.insert(x);
		sum += x;
	}
	for(int i = 1;i<=m;i++)
		cin>>a[i].l;
	for(int i = 1;i<=m;i++)
		cin>>a[i].d;
	sort(a+1,a+1+m,cmp);

	for(int i = 1;i<=m;i++)
	{
		int L = a[i].l,D = a[i].d;
		int val = *s.lower_bound(L);
		if(cnt[val])
		{
			sum-=D,cnt[val]--;
			if(!cnt[val])s.erase(val);
		}
	}
	cout<<sum<<endl;
	return 0;
}