Caddi Programming Contest 2021(AtCoder Beginner Contest 193) 题解（A-D）

Caddi Programming Contest 2021(AtCoder Beginner Contest 193) 题解（A-D）

A-Discount

题目大意：

给出一个商品的现价和原价，求在原价在基础上打几折，误差不超过\(10^{-2}\)。

解题思路：

直接计算即可

代码如下：

#include<iostream>
using namespace std;
double a,b;
int main()
{
	cin>>a>>b;
	cout<<100*(1-b/a)<<endl;
	return 0;
}

?

B-Play Snuke

题目大意：

有\(n\)个商店，\(a_i\)表示到达第\(i\)个商店要花的时间，\(p_i\)表示第i个商店的售价，\(x_i\)表示第i个商店的库存，因为商品畅销，每个商店在每个单位时间内都会出售一个商品，问能否买到一个商品，能买到的话输出要支付的最低价钱，否则输出-1.

解题思路：

很明显，对于每个商品而言，只有\(a_i<p_i\)的情况下才有可能买到，所以答案就是所有能买到的店铺中售价的最小值。

代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm> 
using namespace std;
const int inf=0x3f3f3f3f;
int n,a,p,x;
int main()
{
	scanf("%d",&n);
	int res=inf;
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&a,&p,&x);
		if(a<x) res=min(res,p);
	}
	if(res==inf) puts("-1");
	else printf("%d\n",res);
	return 0;
}

C-Unexpressed

题目大意：

给出一个整数\(N\)(\(1<=N<=10^{10}\))，问有多少在\([1,N]\)之间的整数不能表示成\(a^b\)的形式，其中\(a>=2,b>=2\)。

解题思路:

因为\(N\)的最大值是\(10^{10}\)，不能从1枚举到\(N\)。所以我们可以考虑用\([1,\sqrt{N}]\)内的整数筛去能被表示成\(a^b\)的整数。因为存在一个数可以表示成多种形式的\(a^b\)（例如16可以表示成\(2^4\)和\(4^2\)两种形式），可能会被计算多次，可以考虑用set去重或者用数组记录一下保证不会用已经被筛去的数去筛更大的数。展示的代码是第二种做法。时间复杂度\(O(\sqrt{N}\log_2\sqrt{N})\)。

代码如下：

#include<iostream>
using namespace std;
typedef long long LL;
const int maxn=1e5+10;
LL n;
bool vis[maxn];
int main()
{
	cin>>n;
	LL res=0;
	for(LL i=2;i<=n/i;i++){
		if(vis[i]) continue;
		LL t=i*i; 
		while(t<=n){
			if(t<=100000) vis[t]=1;
			res++;
			t*=i;
		}
	}
	cout<<n-res<<endl;
	return 0;
}

D-Poker

题目大意：

有\(9K\)张牌，其中\(1,2,\cdots,9\)各有k张。洗牌之后发五张牌给两个玩家，其中四张牌是朝上可见的，有一张牌朝下看不见的。五张牌的得分规则定义如下\(\sum\limits_{i=1}^9{i\times10^{c_i}}\)，其中\(c_i\)表示卡牌数字等于\(i\)的数量(例如\(11449\)的分数100+2+3+400+5+6+7+8+90=621 )。现在分贝给出两个玩家的两副牌（只有四张可见），问第一个玩家获胜的概率是多少，误差不大于\(10^{-5}\)。

解题思路:

枚举最后一张牌的出现情况，最多也就是81种情况。将每种情况下获胜的情况累加起来可以得到能够获胜总方案数，一共\(9K\)张牌，每个人一共用去八张牌，剩下的全部情况就是\((9\times K-8) \times(9\times K -9)\)种，将前面算到总和除以\((9\times K-8) \times(9\times K -9)\)就是答案。

代码如下：

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long LL;
int k,num[10],cnt[10];
string s,t;
int score(string s){
	int res=0;
	for(int i=1;i<=9;i++) cnt[i]=i;
	for(auto c : s) cnt[c-‘0‘]*=10;
	for(int i=1;i<=9;i++) res+=cnt[i];
	return res;
}
int main()
{
	cin>>k>>s>>t;
	for(int i=1;i<=9;i++) num[i]=k;
	for(int i=0;i<4;i++){
		num[s[i]-‘0‘]--;
		num[t[i]-‘0‘]--;
	}
	LL sum=0;
	for(int i=1;i<=9;i++){
		for(int j=1;j<=9;j++){
			s.back()=i+‘0‘;
			t.back()=j+‘0‘;
			int s1=score(s),s2=score(t);
			if(s1>s2)	sum+=(LL)num[i]*(num[j]-(i==j)); 
		}
	}
	LL t=(LL)(9*k-8)*(9*k-9);
	cout<<(double)sum/t<<endl;
	return 0;
}

Caddi Programming Contest 2021(AtCoder Beginner Contest 193) 题解（A-D）

原文：https://www.cnblogs.com/Momo-zzz/p/14458059.html