【题解】Educational Codeforces Round 187 (Rated for Div. 2)

【题解】Educational Codeforces Round 187 (Rated for Div. 2)

Problem A. Towers of Boxes

• 一个箱子里可以装入 $d/m$ 个箱子，加上自己共 $d/m+1$ 个

#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
int n,m,d;
cin >> n >> m >> d;
int k = d/m;$
cout << (n+k)/(k+1) << '\\n';
}

signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while(t —){
solve();
}
}

Problem B. Beautiful Numbers

• 如果 $x<10^{18}$，那么 $f(x)<180$。
• 在 $0$ ~ $180$ 的数中，满足 $F(x)=x$ 的数只有 0,1,2,3,4,5,6,7,8,9。
• 判断该数的数字和是否能减小到 $9$ 以下即可。
• 注意特判最高位，最高位只能减小到 $1$，其他位可以减小到 $0$。

#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
int x;
cin >> x;
vector<int> v;
while(x){
v.push_back(x % 10);
x /= 10;
}
int sum = 0,ans1 = 0,ans2 = 0;
vector<int> v2 = v;
sum += v.back();
v.pop_back();
sort(v.begin(),v.end());
if(sum + accumulate(v.begin(),v.end(),0ll) <= 9){
ans1 = 0;
}else{
for(int i = 0; i < (int)v.size(); i ++){
if(sum + v[i] > 9){
ans1 = (int)v.size() – i;
break;
}else{
sum += v[i];
}
}
}
//cout << ans1 << endl;
v = v2;
sum = 0;
sum += 1;
v.pop_back();
ans2 ++;
sort(v.begin(),v.end());
if(sum + accumulate(v.begin(),v.end(),0ll) <= 9){
ans2 = 1;
}else{
for(int i = 0; i < (int)v.size(); i ++){
if(sum + v[i] > 9){
ans2 += (int)v.size() – i;
break;
}else{
sum += v[i];
}
}
}
cout << min(ans1,ans2) << '\\n';
}

signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while(t —){
solve();
}
}

Problem C. Test Generator

• 二分答案，设当前二分到的答案为 $n$。
• $m$ 为 $1$ 的每一个二进制位,a中的数都可以设为 1 以求消耗 $s$，当 $s$ 被消耗干净，则有解，若枚举完所有位置都没有解，则无解。
• 从贪心的角度考虑，较高的二进制没有较低的二进制位“精细”, 要优先使用不够“精细”的位置消耗 $s$。
• “精细”的说明：当 $s=20$，$n=3$，$m=7$ 时，正确的方法是依次用三个 “4”，三个“2”，两个“1”消耗 $s$。如果一开始就用三个“1”去消耗，$s$ 就消耗不干净了。

#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
int s,m;
cin >> s >> m;

auto check = [&](int mid) -> bool{
int sum = s;
for(int i = 63; i >= 0; i —){
if((m >> i) & 1){
int val = 1ll << i;
int t = sum/val;
if(t <= mid){
sum = sum % val;
}else{
sum -= mid * val;
}
if(sum == 0) return true;
}
}
if(sum == 0) return true;
else return false;
};
if(!check(1e18 + 10)){
cout << –1 << '\\n';
return;
}
int l = 1,r = 1e18 + 10;
while(l != r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l << '\\n';
}

signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while(t —){
solve();
}
}

Problem D. The Greatest Common Divisor

• 所有数可以分为三类，只有 Alice 能选的，两人都可以选的，只有 Bob 能选的，依次设为$cnta,cntl,cntb$。
• 博弈策略是先选两人都能选的，然后再选只有自己可以选的

if(cntl % 2 + cnta > cntb){
cout << "Alice\\n";
}else{
cout << "Bob\\n";
}
}

• 用调和级数的复杂度求解 $cnta,cntb,cntl$ 即可。
• 不建议直接预处理 $1$ ~ $2e6$ 中每个数的因数，频繁使用容量小的变长 $vector$ 可能会超时

#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
int n,m;
cin >> n >> m;
vector<int> a(n+1),b(m+1);
vector<int> cnt(n+m+1),fact(n+m+1);
for(int i = 1; i <= n; i ++) {
cin >> a[i];
cnt[a[i]] ++;
}

for(int j = 1; j <= m; j ++) {
cin >> b[j];
}
for(int i = 1; i <= n + m + 1; i ++){
if(cnt[i]){
for(int j = 1; j * i <= n + m; j ++){
fact[i*j] += cnt[i];
}
}
}
int cnta = 0,cntb = 0,cntl = 0;
for(int i = 1; i <= m; i ++){
if(fact[b[i]] == 0){
cntb ++;
}else if(fact[b[i]] == n){
cnta ++;
}else cntl ++;
}
if(cntl % 2 + cnta > cntb){
cout << "Alice\\n";
}else{
cout << "Bob\\n";
}

}

signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = 1;
cin >> t;
while(t —){
solve();
}
}

Problem E. The Greatest Common Divisor

• Bob 一定选择恰好比 Alice 大的牌或者恰好比 Alice 小的牌。
• 设 Alice 选择的牌是第 $idx$ 大，Bob 选择 $idx+1$ 大的牌的得分是 $cos{t}_r$,选择 $idx-1$ 小的牌的得分是 $cos{t}_l$。
• Alice 的目标是最小化 $max(cos{t}_r,cos{t}_l)$。
• $cos{t}_r$ 是随 $idx$ 增大而减小的, $cos{t}_l$ 是随 $idx$ 增大而增大的，二者相等的位置附近就是 $max(cos{t}_r,cos{t}_l)$ 的最小值。
• 计算距离和需要树状数组+离散化，维护数量树状数组($tr1$)以及总和的树状数组($tr2$)即可。

//维护方式分别为+1和+a[i]
tr1.add(idx,1);
tr2.add(idx,a[i]);

• 枚举相等位附近的几个位置即可。找到下一个位置需要维护第 $k$ 大，使用树状数组二分维护 $maxright$。

int maxright = tr1.select(k);
int select(int k){
int x = 0,cur = 0;
for(int i = 1 << __lg(len); i ; i /= 2){
if(x + i <= len && cur + a[x+i] <= k){
cur += a[x + i];
x += i;
}
}
return x;
}

完整代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;

struct Fenwick{
const int len;
vector<int> a;
Fenwick(int n1) : len(n1),a(len + 3){}
#define lowbit(x) ((x) & (–x))
void init(vector<int> &b)
{
for(int i = 1; i <= len; i ++)
{
a[i] += b[i];
int j = i + lowbit(i);
if(j <= len) a[j] += a[i];
}
}
void add(int x,int c)
{
for(int i = x; i <= len; i += lowbit(i))
a[i] += c;
}
int sum(int x)
{
int ret = 0;
for(int i = x; i; i -= lowbit(i)) ret += a[i];
return ret;
}
int sum(int l,int r)
{
return sum(r) – sum(l – 1);
}
int select(int k){
int x = 0,cur = 0;
for(int i = 1 << __lg(len); i ; i /= 2){
if(x + i <= len && cur + a[x+i] <= k){
cur += a[x + i];
x += i;
}
}
return x;
}
};

int qmi(int a,int b){
int ret = 1;
while(b){
if(b & 1) ret = 1ll * ret * a % mod;
a = 1ll * a * a % mod;
b >>= 1;
}
return ret;
}

void solve(){
int m;
cin >> m;
vector<int> a(m+1);
for(int i = 1; i <= m; i ++){
cin >> a[i];
}
vector<int> val = a;
val.push_back(0);
val.push_back(1e12 + 1);

sort(val.begin()+1,val.end());

Fenwick tr1(m+5),tr2(m+5);
for(int i = 1; i <= m; i ++){
int idx = lower_bound(val.begin()+1,val.end(),a[i]) – val.begin();
tr1.add(idx,1);
tr2.add(idx,a[i]);
if(i <= 2) continue;
int l = 1,r = m;

auto check = [&](int x){
int suml = val[x] * tr1.sum(x) – tr2.sum(x);
int sumr = tr2.sum(x,m+3) – tr1.sum(x,m+3) * val[x];
return suml <= sumr;
};

while(l != r){
int mid = l + r + 1 >> 1;
if(check(mid)) l = mid;
else r = mid – 1;
}

int c = tr1.sum(l);
int ans = 1e18;
for(int j = max(1ll,c–4); j <= min(i,c+4); j ++){
int res = 0;
if(j > 1){
int y = tr1.select(j–2) + 1;
res = max(res,tr1.sum(y) * val[y] – tr2.sum(y));
}
if(j < i){
int y = tr1.select(j) + 1;
res = max(res,tr2.sum(y,m+3) – tr1.sum(y,m+3) * val[y]);
}
ans = min(ans,res);
}
cout << (ans % mod) * qmi(i–2,mod–2) % mod << '\\n';
}
}

signed main(){
ios::sync_with_stdio(false);
cin.tie(0);

int t = 1;
//cin >> t;
while(t —){
solve();
}
}