Rank 192/4984. AC 9/13.被B题搞了，于是开摆
A. DFS搜索
题意
判断给定字符串是否包含子序列 \(\mathtt{DFS}\)，以及是否包含子序列 \(\mathtt{dfs}\)。用二进制给出两个判断结果。
思路
以第一个 \(\mathtt{D}\) 为起点往后找，然后将第一个 \(\mathtt{F}\) 作为起点继续找，如果能找到 \(\mathtt{S}\) 则包含子序列 \(\mathtt{DFS}\)。
小写同理。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
string s;
cin >> s;
s = " " + s;
char now = -1;
for(int i=1;i<=n;i++) {
if(now == -1 && s[i] == 'D') {
now = 'D';
}else if(now == 'D' && s[i] == 'F') {
now = 'F';
}else if(now == 'F' && s[i] == 'S') {
now = 'S';
}
}
if(now == 'S') cout << 1 << ' ';
else cout << 0 << ' ';
now = -1;
for(int i=1;i<=n;i++) {
if(now == -1 && s[i] == 'd') {
now = 'd';
}else if(now == 'd' && s[i] == 'f') {
now = 'f';
}else if(now == 'f' && s[i] == 's') {
now = 's';
}
}
if(now == 's') cout << 1 << '\n';
else cout << 0 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}搜索DFS
B. 关鸡
题意
对于一个宽为 \(2\)，长为 \(2 \times 10 ^ 9 + 1\) 的管道：
给定若干着火点，输出至少还要添加多少着火点，使位于 \((1, 0)\) 鸡无法到达左右边界。鸡可以上下左右移动一格、不能出管道上下边界、不能进入着火点。
思路
枚举每个点，如果这个点在第一行，那么判断第二行中该点下方、左下方、右下方是否有着火点，有则这一边无需添加着火点，否则需要添加一个；第二行同理。
最后，还需要特判 \((1, -1), (2, 0), (1, 1)\)。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
map<int, vector<bool>> mp;
int ans = 3;
for(int i=1;i<=n;i++) {
int r, c;
cin >> r >> c;
if(!mp.count(c)) mp[c] = vector<bool>(3);
mp[c][r] = true;
if(r == 2 && c == 0) ans --;
if(r == 1 && c == 1) ans --;
if(r == 1 && c == -1) ans --;
}
int mx1 = 0, mx2 = 0;
for(auto &[x, y] : mp) {
if(x > 0) {
int cnt = 0;
if(y[1]) cnt ++;
if(y[2]) cnt ++;
if(cnt == 2) mx1 = 2;
else {
mx1 = max(mx1, 1ll);
if(y[1]) {
if(mp.count(x + 1)) {
if(mp[x + 1][2]) mx1 = 2;
else mx1 = max(mx1, 1ll);
}
if(mp.count(x - 1)) {
if(mp[x - 1][2]) mx1 = 2;
else mx1 = max(mx1, 1ll);
}
}
if(y[2]) {
if(mp.count(x + 1)) {
if(mp[x + 1][1]) mx1 = 2;
else mx1 = max(mx1, 1ll);
}
if(mp.count(x - 1)) {
if(mp[x - 1][1]) mx1 = 2;
else mx1 = max(mx1, 1ll);
}
}
}
}
if(x < 0) {
int cnt = 0;
if(y[1]) cnt ++;
if(y[2]) cnt ++;
if(cnt == 2) mx2 = 2;
else {
mx2 = max(mx2, 1ll);
if(y[1]) {
if(mp.count(x + 1)) {
if(mp[x + 1][2]) mx2 = 2;
else mx2 = max(mx2, 1ll);
}
if(mp.count(x - 1)) {
if(mp[x - 1][2]) mx2 = 2;
else mx2 = max(mx2, 1ll);
}
}
if(y[2]) {
if(mp.count(x + 1)) {
if(mp[x + 1][1]) mx2 = 2;
else mx2 = max(mx2, 1ll);
}
if(mp.count(x - 1)) {
if(mp[x - 1][1]) mx2 = 2;
else mx2 = max(mx2, 1ll);
}
}
}
}
}
if(mp.count(0) && mp[0][2]) {
mx1 = max(mx1, 1ll);
mx2 = max(mx2, 1ll);
if(mp.count(1) && mp[1][1]) mx1 = 2;
if(mp.count(-1) && mp[-1][1]) mx2 = 2;
}
if(mp.count(1) && mp[1][1]) mx1 = max(mx1, 1ll);
if(mp.count(-1) && mp[-1][1]) mx2 = max(mx2, 1ll);
cout << min(ans, 4 - (mx1 + mx2)) << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}写的有点史，调也是调了半天
C. 按闹分配
题意
\(n\) 个人在同一个窗口办事，每个人办事需要 \(t_i\) 时间。
定义不满意度 \(S = \sum^n_{i=1}D_i\)，其中 \(D_i\) 为第 \(i\) 个人办完事的时刻。
由上，可得出最小不满意度 \(S_{\min}\)。
现在，\(A\) 可在任意位置插队，并需要 \(t_c\) 时间完成办事。插队后，这 \(n\) 个人的最小不满意度变为 \(S_c\)。若 \(S_c - S_{\min} \leq M\)，那么这个插队合法。
回答 \(Q\) 个询问，每个询问给出整数 \(M\)，输出插队合法的情况下，\(A\) 最早办完事的时刻。
思路
首先，当我们按 \(t_i\) 升序排序后，得到的顺序就可让 \(S\) 最小，因为前面的办事时间会累积到后面。
可以发现，如果我们插在 \(k\) 个人后面，那么 \(S\) 会变大 \(k \cdot t_c\)。
从而，我们可以将式子化为 \(kt_c \leq M\)，从而有 \(k_{\max} = \lfloor \frac{M}{t_c} \rfloor\)。
至于前面要等待的时间，预处理前缀和即可。
时间复杂度：\(O(n + q)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, q, tc;
cin >> n >> q >> tc;
vector<int> t(n + 1);
for(int i=1;i<=n;i++) cin >> t[i];
sort(all(t));
vector<int> pre(n + 1);
for(int i=1;i<=n;i++) {
pre[i] = pre[i - 1] + t[i];
}
while(q --) {
int m;
cin >> m;
int ind = max(0ll, n - m / tc);
cout << pre[ind] + tc << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}思维题
D. 数组成鸡
题意
给定一个长为 \(n\) 的数组 \(a\)，定义一次操作为将所有元素都 \(+1\) 或都 \(-1\)。
对于 \(q\) 次询问，每次询问给定一个整数 \(M\)，判断是否可以使 经过若干次操作 后的新数组的 所有元素乘积 等于 \(M\)。
思路
首先，因为 \(M\) 只有 \(10^9\)，约等于 \(2 ^ {30}\)，从而我们可以发现，构成 \(M\) 的元素中，最多只有不到 \(30\) 个非 \(1\) 数字。
那么，我们只需暴力枚举每个不同的元素 \(a_i\)，并在 \(-a_i\) 的值附近暴力枚举合法答案即可。
时间复杂度：\(O(n \cdot 能过)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
set<int> st;
auto prod = [&](int x) -> bool {
int ans = 1;
for(int i=1;i<=n;i++) {
ans *= a[i] - x;
if(abs(ans) > 1e9) return false;
}
st.ep(ans);
return true;
};
a[0] = -inf;
sort(a.rbegin(), a.rend() - 1);
for(int i=1;i<=n;i++) {
if(a[i] == a[i - 1]) continue;
int x = a[i];
while(prod(x)) x ++;
x = a[i];
while(prod(x)) x --;
}
while(q --) {
int x;
cin >> x;
cout << (st.count(x) ? "Yes\n" : "No\n");
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}类似的题 \(\mathtt{Codeforces}\) 上有一道，都是根据值域优化时间复杂度（但是我找不到了
E. 本题又主要考察了贪心
题意
给定 \(n\) 个选手，第 \(i\) 个选手具有初始积分 \(a_i\)。
对于 \(m\) 场比赛，每场比赛在 \(u_i, v_i\) 两个选手之间进行，胜者加 \(3\) 分，败者不加分，平局则双方各得 \(1\) 分。
输出第 \(1\) 位选手的最好排名，出现并列则输出并列最好的排名。
思路
观察数据范围，显然这题不是贪心，而是很无脑的爆搜。
如上，我们直接回溯搜索即可。
至于如何求排名，只需找出有多少个人的积分严格大于第一位选手即可。
时间复杂度：\(O(3 ^ m n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
for(int i=1;i<=n;i++) cin >> a[i];
vector<pii> e(m + 1);
for(int i=1;i<=m;i++) {
int u, v;
cin >> u >> v;
e[i] = {u, v};
}
int ans = inf;
auto dfs = [&](auto &&dfs, int ind) -> void {
if(ind == m + 1) {
int now = 1;
for(int i=2;i<=n;i++) {
if(a[1] < a[i]) now ++;
}
ans = min(ans, now);
return;
}
auto [u, v] = e[ind];
a[u] += 3;
dfs(dfs, ind + 1);
a[u] -= 3;
a[v] += 3;
dfs(dfs, ind + 1);
a[v] -= 3;
a[u] ++, a[v] ++;
dfs(dfs, ind + 1);
a[u] --, a[v] --;
};
dfs(dfs, 1);
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}又主要考察了诈骗
F. 鸡数题！
题意
构造长为 \(m\) 的数组 \(a\)，满足：
均为正数，且严格递增；
\(a_1 | a_2 | \ldots |a_m = 2^n - 1\)；
\(\forall i \neq j,\ s.t.\ a_i \& a_j = 0\)
输出方案数，并对 \(10^9+7\) 取模。
思路
最后两个条件等价于：在 \(m\) 个均为 \(0\) 的二进制数中，从左到右填入 \(1\)，且每一列只能有一个。
也就是说，我们需要把 \(n\) 个不同的数划分为 \(m\) 个集合，且方案数不考虑顺序。
而这就是第二类斯特林 (\(\mathtt{Stirling}\)) 数。
上述通项公式如下：
\(\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^m\dfrac{(-1)^{m-i}i^n}{i!(m-i)!}\)
代入即可。
至于阶乘以及逆元，既可以线性求阶乘逆元，也可以预处理阶乘，然后求逆元。
时间复杂度：\(O(m \log n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
int fac[N], inv_[N], fac_inv[N];
static __int128 qp(__int128 x, __int128 y, __int128 m = mod) {
static __int128 ans;
ans = 1, x %= m;
for (; y; y >>= 1, x = x * x % m) if (y & 1) ans = ans * x % m;
return ans;
}
int inv(int n, int m = mod) { return qp(n, m - 2, m); }
//线性求阶乘，逆元，阶乘逆元
void get_fact_inv(int n, int fac[], int inv[], int fac_inv[], int p = mod) {
fac[0] = fac_inv[0] = inv[0] = fac[1] = fac_inv[1] = inv[1] = 1;
for (int i = 2; i <= n; i++) {
fac[i] = fac[i - 1] * i % p;
inv[i] = (p - p / i * inv[p % i] % p) % p; //线性求逆元
fac_inv[i] = fac_inv[i - 1] * inv[i] % p;
}
}
void init() {
get_fact_inv(2e5, fac, inv_, fac_inv);
}
void solve() {
int n, m;
cin >> n >> m;
int ans = 0;
for(int i=0;i<=m;i++) {
int now = qp(i, n);
now = now * fac_inv[i] % mod;
now = now * fac_inv[m - i] % mod;
if((m - i) % 2 == 1) now = mod - now;
ans = (ans + now) % mod;
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
init();
int t = 1;
// cin >> t;
while (t--) solve();
}不知道这个的话貌似得用神奇的做法
G. why买外卖
题意
给定 \(n\) 个优惠，每个优惠为满 \(a_i\) 减 \(b_i\)，且可以叠加。
对于一个原价为 \(x\) 的商品，最后的价格为使用所有满足 \(x \geq a_i\) 的优惠后的价格。
现在，给出最后的价格，输出原价的最大值。
思路
显然，如果我们用了一个满 \(a_i\) 的优惠，那么小于等于 \(a_i\) 的所有优惠会被使用。
那么，我们贪心地从小到大使用满减，只要满足 最后的价格 加上 优惠掉的金额 大于等于 当前满减需要的金额下限，这个原价就是可行的。
从而我们从小到大枚举即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
vector<pii> p(n + 1);
for(int i=1;i<=n;i++) {
auto &[a, b] = p[i];
cin >> a >> b;
}
sort(all(p));
int now = m, ans = m;
for(int i=1;i<=n;i++) {
auto [a, b] = p[i];
now += b;
if(now >= a) ans = now;
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}乱写
H. 01背包，但是bit
题意
给定一个承重为 \(m\) 的背包，对于 \(n\) 个物品，每个物品具有价值 \(v_i\) 和重量 \(w_i\)。定义总重量为所选物品的重量进行 按位或运算 后的结果。
输出总重量不超过 \(m\) 的条件下，价值和的最大值。
思路
首先，二进制具有贪心的性质，只要我们将一位由 \(1\) 改为 \(0\)，那么无论低位有多高，都比原来的数低。
举个例子，\(101000 > 100111\)。
因为我们考虑的是二进制下按位或后和上界的大小关系，所以我们只需考虑上述构造的上界即可。
也就是说，我们枚举每个 \(1\)，将其改为 \(0\)，并将后面的低位全都改成 \(1\)，将其作为一个上界，枚举有多少个物品符合条件即可。
当然，修改前的 \(m\) 也是一个上界。
时间复杂度：\(O(n \log m)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, m;
cin >> n >> m;
vector<pii> p(n + 1);
for(int i=1;i<=n;i++) {
auto &[v, w] = p[i];
cin >> v >> w;
}
int ans = 0;
for(int i=1;i<=n;i++) {
auto [v, w] = p[i];
if((w | m) > m) continue;
ans += v;
}
for(int i=32;i>=0;i--) {
if(((m >> i) & 1ll) == 0) continue;
int lim = ((m >> i) << i) - (1ll << i);
if(i > 0) lim += (1ll << i) - 1;
int now = 0;
for(int j=1;j<=n;j++) {
auto [v, w] = p[j];
if((w | lim) > lim) continue;
now += v;
}
ans = max(ans, now);
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}别想着去写 \(dp\) 应该就能写出来（
I. It's bertrand paradox. Again!
题意
给定 \(10^5\) 个随机生成的圆，要求如下：
圆心坐标为整点、圆半径为整数。所有圆上的每一个点都在 \(−100 \leq x \leq 100\) 和 \(−100 \leq y \leq 100\) 所确定的平面区域内（可以在边界上），允许有重复的圆，但要求生成的圆是随机的。
判断这些圆是由下面哪个方案随机产生的：
bit-noob：
随机等概率地从开区间 \((−100,100)\) 生成两个整数 \(x\), \(y\)，随机等概率地从闭区间 \([1,100]\) 中生成一个 \(r\)；
判断 \((x,y)\) 为圆心、\(r\) 为半径的圆是否满足要求，若不满足，重新生成 \(r\)，若满足，则将该圆加入到结果中。
buaa-noob：
随机等概率地从开区间 \((−100,100)\) 生成两个整数 \(x\), \(y\)，随机等概率地从闭区间 \([1,100]\) 中生成一个 \(r\)。
判断 \((x,y)\) 为圆心、\(r\) 为半径的圆是否满足要求，若不满足，重新生成 \(x\), \(y\), \(r\)，若满足，则将该圆加入到结果中。
思路
不妨打个表，可以发现前者更靠近两侧，而后者更靠近中间，选择合适的阈值即可。
时间复杂度：\(O(n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 1e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
int ans = 0;
for(int i=1;i<=n;i++) {
int x, y, r;
cin >> x >> y >> r;
if(abs(x) >= 95 || abs(y) >= 95) ans ++;
}
if(ans >= 1000) cout << "bit-noob" << '\n';
else cout << "buaa-noob" << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}你怎么知道我概率论学的不咋样
J. 又鸟之亦心
题意
对于在数轴上的两个人 \(A, B\)，\(A\) 位于坐标 \(x\)，\(B\) 位于坐标 \(y\)。
给定一个长为 \(n\) 的数组 \(a\)，代表接下来的位置变化：对于每个 \(a_i\)，选择一个人，并将其移到该坐标。
输出最优选择下，两人距离的最大值的最小值。
思路
题面很直接，最后一句话一眼二分。
可以发现，如果答案越大，也就是说距离最大值的最小值越大，那么越可能存在方案，否则不存在方案。也就是说，单调性是存在的，我们可以使用二分答案。
至于如何 \(\mathtt{check}\)，可以发现每次移动后，一定有一个人位于 \(a_i\)，而既然我们指定了距离最大值的最小值，那么另一个人的可选位置也就被框定好了。
我们只需维护一个合法位置的集合，并用 \(a_i\) 将其约束到 与 \(a_i\) 的差的绝对值 小于等于 指定的最小值即可。
最后，我们只需判断中途或者结束的时候，集合是否为空，若为空，则该方案不存在。
时间复杂度：\(O(n \log n \cdot \log(1e9))\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n, x, y;
cin >> n >> x >> y;
vector<int> a(n + 2, inf);
for(int i=1;i<=n;i++) cin >> a[i];
auto check = [&](int d) -> bool {
set<int> st;
if(abs(x - y) <= d) st.ep(x), st.ep(y);
for(int i=1;i<=n;i++) {
while(!st.empty() && *st.begin() < a[i] - d) st.extract(*st.begin());
while(!st.empty() && *st.rbegin() > a[i] + d) st.extract(*st.rbegin());
if(!st.empty() && abs(a[i + 1] - a[i]) <= d) st.ep(a[i]);
}
return !st.empty();
};
int l = 0, r = 1e9, mid;
while(l < r) {
mid = (l + r) >> 1ll;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}好像也没有特别难（
K. 牛镇公务员考试
题意
给定一张包含 \(n\) 道单选题的试卷，其中第 \(i\) 道题的题面如下：
第 \(a_i\) 题的答案是（）。
A. \(s_{i,1}\)
B. \(s_{i,2}\)
C. \(s_{i,3}\)
D. \(s_{i,4}\)
E. \(s_{i,5}\)
输出全部答对所有题的答案序列的数量。
思路
我们不妨按照 \(i \to a_i\) 的方式建边，很容易发现，我们会得到由 点，环，环+链 (长得像 "6") 构成的非连通有向图。
我们可以把点视为环，从而只剩下两种情况。
显然，如果关系成了环，我们就需要保证每个选择都是合法的，因为最后这个选择要让前一个的选择恰好对应。
而恰恰相反，如果关系为一条链，那么我们就无所谓合法性了，因为我们无论对链头如何选择，都能对应到链尾的 \(5\) 个选择。
那么，我们现在要做的就是去掉链，留下环。而上述操作只需跑一遍拓扑排序。
排序结束后，我们对每个环，以任意一个元素为开头，遍历其 \(5\) 个选择，然后绕一圈，看最后一个选择是否和我们开始的选择一致即可。
最后，我们对每个环统计数量，乘起来即可。
时间复杂度：\(O(5n)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
using pis = pair<int, string>;
vector<pis> e(n + 1);
vector<int> in(n + 1);
for(int i=1;i<=n;i++) {
auto &[a, s] = e[i];
cin >> a >> s;
in[a] ++;
}
queue<int> q;
for(int i=1;i<=n;i++) {
if(in[i] == 0) q.ep(i);
}
vector<bool> vis(n + 1);
while(!q.empty()) {
int x = q.front();
q.pop();
vis[x] = true;
if(--in[e[x].fs] == 0) q.ep(e[x].fs);
}
int ans = 1;
auto dfs = [&](auto &&dfs, pii now, pii start) -> bool {
vis[now.fs] = true;
if(now.fs == start.fs) {
return now.sc == start.sc;
}
auto &[x, c] = now;
return dfs(dfs, {e[x].fs, e[x].sc[c] - 'A'}, start);
};
for(int i=1;i<=n;i++) {
if(vis[i]) continue;
int cnt = 0;
for(int j=0;j<5;j++) {
pii start = {i, j}, now = {e[i].fs, e[i].sc[j] - 'A'};
if(dfs(dfs, now, start)) cnt ++;
}
ans = ans * cnt % mod;
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
// cin >> t;
while (t--) solve();
}早知道多开点题了（
L. 要有光
题意
在 \(xyz\) 空间直角坐标系中，有一堵墙 \(S\)，在 \(xoy\) 平面上，\(S\) 前面的区域为地面。在 \(yoz\) 平面上有一个宽 \(2w\) 高 \(h\) 的不透光薄片 \(W\)。现在，在高为 \(d\) 的黑色线段 \(L\) 上，有一个可以上下移动的点光源。合理选择点光源的位置，使未被照亮的地面的面积尽可能大，并输出面积。
\(S:\left \{ \begin{array}{l} x = -c \\ z \leq 0 \end{array} \right.\)
\(W:\left \{ \begin{array}{l} x = 0 \\ -w \leq y \leq w \\ 0 \leq z \leq h \end{array} \right.\)
\(L:\left \{ \begin{array}{l} x = c \\ y = 0 \\ 0 \leq z \leq d \end{array} \right.\)
思路
显然，由光学知识，无论多高，投影到地面的面积都是一致的，从而我们无需在意高度，只需在地面上做，我们延长点光源到墙两边的直线，得到的梯形即为所求。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int c, d, h, w;
cin >> c >> d >> h >> w;
cout << 6 * w * c / 2 << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}简单到不敢交
M. 牛客老粉才知道的秘密
题意
对于一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(6\) 的滑动窗口，初始状态下窗口的左端点位于最左侧。
每次操作，窗口可以以 \(6\) 个单位向左和向右移动，如果遇到了右边界，那么窗口的右端点需要对齐右边界，左边界同理。
输出窗口的左端点可以位于多少个不同的点。
思路
我们根据 \(n\) 能否被 \(6\) 整除进行分讨：
如果 \(n\) 能被 \(6\) 整除，那么不会出现超出边界的情况，左端点只有 \(\frac{n}{6}\) 个取值；
否则，就存在超出边界的情况，此时对齐后，向左移动时一定不会和原来的一样，从而会多出 \(\frac{n}{6}\)。
时间复杂度：\(O(1)\)
对应AC代码
#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"
#include chatgpt3_5
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
constexpr int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);
void solve() {
int n;
cin >> n;
if(n % 6 == 0) {
cout << n / 6 << '\n';
}else {
int ans = n / 6 * 2;
cout << ans << '\n';
}
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
// init();
int t = 1;
cin >> t;
while (t--) solve();
}经典滑窗（