第 18 场 小白入门赛

6 武功秘籍

考察进制理解。

对于第 $i$ 位，设 $bi{t}_i=x$ ，每一位的最大值是 $b_j$ ，也就是说每一位是 $b_j+1$ 进制 ，那么第 $i$ 位的大小就是 $x\times {\sum }_{j=i+1}^{las}(b_j+1)$ 。

据此推导。

#include<bits/stdc++.h>
using namespace std;
#define int long longvoid solve(){int n, k;cin >> n >> k;if(k == 1){cout << "0\n";return ;}-- k;vector<int> bit;while(n){bit.push_back(n % 10);n /= 10;}vector<int> t(bit.size() + 1);// for(auto &x : bit) cout << x << ' '; cout << '\n';int l, r = 0, lasBit = 0;t[0] = 1;for(int i = 0; i < bit.size(); i ++){l = r + 1;r += t[i] * bit[i];if(r >= k){lasBit = i;break;}// cout << i << ' ' << l << ' ' << r << '\n';t[i + 1] = t[i] * (bit[i] + 1);}// cout << lasBit << '\n';for(int i = lasBit; i >= 0; i --){cout << (k / t[i]);k %= t[i];}
}signed main(){// ios::sync_with_stdio(false);// cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while (T --){solve();}return 0;
}

2 + 4 情报传递

思维题，技巧在于具有大量相同的区间，实际上只有左右两个特殊区间，以及中间大量相同的区间。

首先，如果不存在点不能走，那么从 $x$ 走到 $y$ ，贪心走 $\lceil \frac{y-x}{2}\rceil$ 即可。

假设在 $a\to b$ 区间内，存在 $x$ 个 $c$ 的倍数，设 $d$ 是这些点的最小值，$e$ 是最大值。

那么从 $a\to d-1$ 和 $e+1\to b$ 贪心走即可。

剩下的全是相同的走法。

$O(1)$ 。

dp 思路很简答，爬楼梯问题，$O(n)$ 。

Trick :

第一个 $\ge x$ 的 $c$ 的倍数 : $\lceil \frac{x}{c}\rceil \times c$

第一个 $\le x$ 的 $c$ 的倍数 : $\lfloor \frac{x}{c}\rfloor \times c$

#include<bits/stdc++.h>
using namespace std;
#define int long longint dis(int a, int b){return (b - a) / 2 + (b - a) % 2;
}void solve(){int a, b, c, x = 0;cin >> a >> b >> c;int d = (a + c - 1) / c * c; // 第一个 >= a 的 c 的倍数int e = b / c * c; // 第一个 <= b 的 c 的倍数if(d > b){ cout << dis(a, b) << '\n';}else{cout << dis(a, d - 1) + dis(e + 1, b) + 1 + dis(1, c + 1) * ((e - d) / c) << '\n';} 
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}

3 村长分钱

已知 $a,b$ , 求满足 $a\mathrm{mod}y=b$ ，多少 $y$ 满足要求

即 $a=b+xy$ 。

即 $xy=b-a$ ，计算一下 $b-a$ 有多少因子即可。

注意只统计 $>b$ 的因子。

#include <iostream>
#include <cmath>
using namespace std;int count_solutions(int a, int b) {if (a < b) return 0; // 无解的情况int d = a - b;int count = 0;// 枚举 d 的因数for (int x = 1; x * x <= d; ++x) {if (d % x == 0) {if (x > b) count++;         // x 是 d 的因数，且 x > bif (d / x != x && d / x > b) count++; // d/x 也是因数，且 d/x > b}}return count;
}int main() {int a, b;cin >> a >> b;cout << count_solutions(a, b) << endl;return 0;
}

5 好汉身份

假设先手的回合，发现选择 $a+b$ 小的更优。

发现后手同样如此。

#include<bits/stdc++.h>
using namespace std;
#define int long longstruct node{int a, b;bool operator < (const node & T) const {return a + b < T.a + T.b;}
}v[2100];int n;void solve(){cin >> n;n <<= 1;for(int i = 1; i <= n; i ++){cin >> v[i].a;}for(int i = 1; i <= n; i ++){cin >> v[i].b;}sort(v + 1, v + n + 1);int res = 0; for(int i = 1; i <= n; i ++){if(i & 1) res += v[i].a;else res -= v[i].b;}cout << res;
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;// cin >> T;while (T --){solve();}return 0;
}