AtCoder Beginner Contest 193 题解报告（先写 A ~ E，后面再写）

AtCoder Beginner Contest 193

https://atcoder.jp/contests/abc193/tasks。

A - Discount

https://atcoder.jp/contests/abc193/tasks/abc193_a。

老样子，A题还是签到题。题目要求计算折扣，要求答案的精度在 $10^{-2}$ 以上。因此我们只需要输出的时候保留的小数点位数足够多就可以达到要求，比如保留 18 位。

#include <iostream>
#include <iomanip>
using namespace std;
int main() {
	int a,b;
	cin>>a>>b;
	double ans=100.0*(a-b)/a;
	cout<<fixed<<setprecision(18)<<ans<<"\n";
	return 0;
}

B - Play Snuke

https://atcoder.jp/contests/abc193/tasks/abc193_b。

买东西，到第 i 个商店需要 a[i] 时间，价格为 p[i]，每分钟库存减少一个。求最小价格。

一个简单的模拟题。难度还是在英文的理解上。

#include <iostream>
#include <iomanip>
using namespace std;
typedef long long ll;
const int MAXN=1e5+4;
ll a[MAXN];//分钟
ll p[MAXN];//价格
ll x[MAXN];//库存
int main() {
	int n;
	cin>>n;
	for (int i=1; i<=n; i++) {
		cin>>a[i]>>p[i]>>x[i];
	}
 
	ll ans=1e9+4;
	bool flag=false;
	for (int i=1; i<=n; i++) {
		if (x[i]>a[i]) {
			ans=min(ans, p[i]);
			flag=true;
		}
	}
 
	if (true==flag) {
		cout<<ans<<"\n";
	} else {
		cout<<"-1\n";
	}
 
	return 0;
}

C - Unexpressed

https://atcoder.jp/contests/abc193/tasks/abc193_c。

给一个 N，求区间 [1, N] 中不能表示为 $a^b$ 数的个数。a 和 b 不小于数字 2。

如果本题不看 N 的范围，那么我们可以直接穷举每个数据 i，测试 i 能否表示为 $a^b$。框架代码如下：

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

这样代码的时间复杂度为 $O(N*logN*logN)$。但是考虑本题 N 为 $10^{10}$，因此这样肯定是 TLE。

我们可以借鉴筛法来解决这个问题。

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
 
int main() {
	ll n;
	cin>>n;
 
	vector<bool> flag(1e5+4, false);
	ll ans=n;
	for (ll i=2; i*i<=n; i++) {
		if (flag[i]) {
			//已经标志过
			continue;
		}
 
		ll t=i*i;
		while (t<=n) {
			ans--;
			if (t<flag.size()) {
				flag[t]=true;
			}
			t*=i;
		}
	}
 
	cout<<ans<<"\n";
 
	return 0;
}

D - Poker

https://atcoder.jp/contests/abc193/tasks/abc193_d。

看了一下题目，好像是组合数学问题，苍天啊。题目好长，英文看得脑壳疼。

根据题目的描述，我们可以推导出如下公式：

$\left\{\begin{matrix} C_x*C_y & x \neq y\\ C_x*(C_x-1) & x = y \end{matrix}\right.$，其中 $C_i$ 表示的是没有翻开的牌 i。

#include <iostream>
#include <vector>
#include <numeric>
#include <iomanip>
 
using namespace std;
typedef long long ll;
 
ll check(string s) {
	vector<ll> cnt(10);
	ll res=0;
	for (int i=0; i<5; i++) {
		cnt[s[i]-'0']++;
	}
	for (int i=1; i<=9; i++) {
		ll t=i;
		while (cnt[i]--) {
			t*=10;
		}
		res+=t;
	}
	return res;
}
 
int main() {
	int k;
	string s, t;
	cin>>k>>s>>t;
 
	vector<ll> card(10, k);
	for (int i=0; i<4; i++) {
		card[s[i]-'0']--;
		card[t[i]-'0']--;
	}
 
	ll res = 9*k-8;
	ll tot = res*(res-1);
	ll ans=0;
	for (int i=1; i<=9; i++) {
		for (int j=1; j<=9; j++) {
			s[4] = '0'+i;
			t[4] = '0'+j;
			if (check(s)<=check(t)) {
				continue;
			}
			if (i==j) {
				ans += card[i]*(card[i]-1);
			} else {
				ans += card[i]*card[j];
			}
		}
	}
 
	cout<<fixed<<setprecision(18)<<1.0*ans/tot<<"\n";
 
	return 0;
}

E - Oversleeping

https://atcoder.jp/contests/abc193/tasks/abc193_e。

题目推敲了半天，尼玛，就是中国剩余定理（Chinese Remainder Theorem, CRT）啊。直接利用 AtCoder 提供的 Math 包里的 crt 算法就可以了。

#include <bits/stdc++.h> 
#include <atcoder/math>
 
using namespace std;
typedef long long ll;
 
int main() {
	int t;
	cin>>t;
	while (t--) {
		ll x,y, p, q;
		cin>>x>>y>>p>>q;
		
		ll ans=LLONG_MAX;
		for (ll i=x; i<x+y; i++) {
			for (ll j=p; j<p+q; j++) {
				auto [t, lcm] = atcoder::crt({i, j}, {(x+y)*2, p+q});
				if (0==lcm) {
					continue;
				}
				ans = min(ans, t);
			}
		}
		
		if (ans==LLONG_MAX) {
			cout<<"infinity\n";
		} else {
			cout<<ans<<"\n";
		}
	}
	
	return 0;
}