2021牛客暑期多校训练营1
A、Alice and Bob
题目大意
存在两堆石子,石子个数分别是和,数量级在,现在每个人轮流进行挑选,必须任选一堆拿走个石子,再从另外一堆拿走个石子,也就是第二次选的可以拿走个石子。先手,后手,第一个无法操作的人就输了,询问比赛谁胜利了。
Solution
考点:博弈
首先我们来考虑用代表第一堆有个石子,第二堆有个石子的先手必胜还是必败态。
初始化。
接下来暴力枚举第一堆石子,第二堆石子,如果某个点是现在必败态,说明把它加上若干个符合要求的左右石子数一定是必胜态。
但是这样一看复杂度有,我们再仔细观察,假设对于两个局面都是必败态,并且假设,那么我们就可以在局面的时候拿掉个石子,让局面变成这时候又是变成必胜态,前后矛盾,表明对于第一堆有个石子的时候,第二堆石子只有一种情况是必败态。这样我们复杂度就到了。
不过这个题还是很玄学,官方的题解说近似的复杂度是…用代替数组时间可以来到左右。
#include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<int, int> #define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__)) #define rep(i, sta, en) for(int i=sta; i<=en; ++i) #define repp(i, sta, en) for(int i=sta; i>=en; --i) #define debug(x) cout << #x << ":" << x << '\n' typedef tuple<int, int> tup; typedef long long ll; typedef unsigned long long ull; typedef long double ld; inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; } inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); } inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; } ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; } const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} }; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const ll INF64 = 0x3f3f3f3f3f3f3f3f; const int N = 5e3 + 1; struct Node { ll val; int id; bool operator < (const Node& opt) const { return val < opt.val; } }; ll n, m; bitset<N> f[N]; void init() { f[0][0] = 0; rep(i, 1, N - 1) f[i][0] = f[0][i] = 1; for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { if (!f[i][j]) { for (int a = 1; i + a < N; ++a) { for (int b = 0; b + j < N; b += a) { f[i + a][j + b] = 1; } } for (int a = 1; j + a < N; ++a) { for (int b = 0; b + i < N; b += a) { f[i + b][j + a] = 1; } } break; } } } } int solve() { n = read(), m = read(); return f[n][m]; } int main() { init(); int T = read(); rep(_, 1, T) { //solve(); cout << (solve() ? "Alice" : "Bob") << endl; } return 0; }
B、Ball Dropping
题目大意
下面的图像给出,要你判断这个小球是否会穿过漏斗,如果不穿过输出圆心距离漏洞底部的高度。
Solution
考点:计算几何
- 首先考虑何时会穿过漏斗,当且仅当的时候。
- 其他时候算出漏斗右上角角度,借用半径和就可以算到小三角形的底,接着就行了,借用一下官方题解的图片。
int solve() { double r, a, b, h; cin >> r >> a >> b >> h; if (r * 2 <= b) { cout << "Drop" << endl; } else { double sita = atan(h / ((a - b) / 2)); double L = r / sin(sita) - b / 2; double res = L * tan(sita); cout << "Stuck" << endl; printf("%.6f\n", res); } return 1; }
C、Determine the Photo Position
题目大意
给出一个的矩阵,你要用的矩阵填充的位置,询问你有多少种填充方案。
Solution
签到题,模拟连续的数量即可。
char s[N], t[N]; int solve() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> m; vector<string> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; string b; cin >> b; int res = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int cnt = 0; int k = j; while (k < n && a[i][k] == '0') ++k; res += max(0ll, k - j - m + 1); j = k; } } print(res); return 1; }
F、Find 3-friendly Integers
题目大意
定义一个数是,当且仅当这个数的某个子串。求中是的个数。
Solution
考点:数位dp思维题
首先我们知道某个数是的倍数,可以对他若干项累加求和,然后我们还知道。
那么我们思考大于等于的数,他们一定存在某位后不为。但是在发现这些一系列组合下来一定存在某个子串累加求和,那么我们就任意了,直接暴力处理前个数即可。
bool check(int x) { int p[3]; p[0] = x % 10; if (p[0] % 3 == 0) return 1; x /= 10; if (!x) return 0; p[1] = x % 10; if (p[1] % 3 == 0) return 1; if ((p[0] + p[1]) % 3 == 0) return 1; x /= 10; if (!x) return 0; p[2] = x; if (p[2] % 3 == 0) return 1; if ((p[0] + p[2]) % 3 == 0 || (p[1] + p[2]) % 3 == 0 || (p[0] + p[1] + p[2]) % 3 == 0) return 1; return 0; } int solve() { ll l = read(), r = read(); if (r <= 100) { int x = 0; for (int i = l; i <= r; ++i) { x += check(i); } print(x); } else { ll res = r - l + 1; for (ll i = l; i <= 100; ++i) { res -= !check(i); } print(res); } return 1; }
G、Game of Swapping Numbers
题目大意
给定等长度序列,你必须交换次序列中的两个不同的数,输出最终最大是多少。
Solution
考点:贪心
我们假设序列,那么我们在绝对值求和就代表着要向集合分配正负号,并且保证最终两个集合一起计算的时候正负号数量相等,单个集合内正负号数量可以不同。
那么对于上面我们的最优分配策略就是,可以看出最优解就是前大放正号,前小放负号。
我们还可以发现对于的时候来说,最优解的最少次数和最优解的最少次数是一致的,因为这时候中一定存在最少个相同的符号,我们只需要交换这两个相同的符号磨平次数即可,的时候判断的奇偶性即可。
接下来就要来看如何构建尽可能优的解,首先我们可以拿到初始的正号集合与负号集合,我们每次交换中两个数,就可以调整个数的符号把一个正号变成负号,把一个负号变成正号,那么很显然要让答案最优,一定是先把最大的负号和最小的正号做一次符号互换,知道处理完全部的数或者用尽。
int a[N], b[N]; int maxi[N], mini[N]; int solve() { n = read(), k = read(); rep(i, 1, n) a[i] = read(); rep(i, 1, n) b[i] = read(); if (n == 2) { if (k & 1) print(abs(a[1] - b[2]) + abs(a[2] - b[1])); else print(abs(a[1] - b[1]) + abs(a[2] - b[2])); } else { ll sum = 0; for (int i = 1; i <= n; ++i) { maxi[i] = max(a[i], b[i]); mini[i] = min(a[i], b[i]); sum += abs(a[i] - b[i]); } sort(maxi + 1, maxi + 1 + n); // 正号集合 小的开始挑 sort(mini + 1, mini + 1 + n, greater<int>()); // 负号集合 大的开始挑 for (int i = 1; i <= n && i <= k; ++i) { if (mini[i] > maxi[i]) { sum += 2 * (mini[i] - maxi[i]); } else break; } print(sum); } return 1; }
H、Hash Function
题目大意
给出一个长度为互不相同的序列,你要选择一个让个数在模的前提下互不相同,求最小的。
Solution
考点:多项式乘法,卷积
首先考虑一个简化问题,给出一个序列,一个序列如果你可以选择任意两个数我要你判断这个数是否存在,你能如何处理,首先不考虑开桶的做法,我们要求处理,很明显我们写出这个序列的生成函数。
很显然我们对着卷积之后就可以得到全部的前面的系数,也就可以判断出来这个数是否存在。
那么回到这个问题,我要选择一个让全部的数都不发生哈希冲突,也就是没有下面的几个式子。
那么问题就变成了我要找到一个让他不是任意一个的约数。
上面我们知道如何快速的求解的系数,这里做减法的话也是同理,用一个偏移量把负数转成正数即可。
接下来对着和做一次,然后再去枚举最小的因子即可。
#include <bits/stdc++.h> using namespace std; #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<int, int> #define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__)) #define debug(x) cout << #x << ":" << x << '\n' typedef tuple<int, int> tup; typedef long long ll; typedef unsigned long long ull; typedef long double ld; inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; } inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); } inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; } ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; } const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} }; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const ll INF64 = 0x3f3f3f3f3f3f3f3f; const int N = (2097152) + 7; // 2^21 ll n, m; const double PI = acos(-1); struct cp { double r, i; cp(double _r = 0, double _i = 0) { r = _r, i = _i; } cp operator+(const cp& x)const { return cp(r + x.r, i + x.i); } cp operator-(const cp& x)const { return cp(r - x.r, i - x.i); } cp operator*(const cp& x)const { return cp(r * x.r - i * x.i, r * x.i + i * x.r); } cp conj() { return cp(r, -i); } }a[N], b[N]; int c[N], rev[N], limit; double p1[N], p2[N]; const int P = 500001; void FFT(cp* a, int inv) { for (int i = 0; i < limit; ++i) { if (i < rev[i])swap(a[i], a[rev[i]]); } for (int mid = 1; mid < limit; mid <<= 1) { cp w1(cos(PI / mid), inv * sin(PI / mid)); for (int i = 0; i < limit; i += mid * 2) { cp wk(1, 0); for (int j = 0; j < mid; ++j, wk = wk * w1) { cp x = a[i + j], y = wk * a[i + j + mid]; a[i + j] = x + y, a[i + j + mid] = x - y; } } } if (inv == -1) { for (int i = 0; i < limit; ++i) c[i] = a[i].r / limit + 0.5; } } bool vis[N]; bool check(int x) { for (int i = x; i <= P; i += x) { if (vis[i]) return 0; } return 1; } int solve() { n = read(); for (int i = 1; i <= n; ++i) { int x = read(); a[x].r = 1; b[P - x].r = 1; } int bit = 0; while (1 << bit < P * 2) ++bit; limit = 1 << bit; for (int i = 0; i < limit; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1)); FFT(a, 1); FFT(b, 1); for (int i = 0; i < limit; ++i) a[i] = a[i] * b[i]; FFT(a, -1); for (int i = 0; i < limit; ++i) { if (c[i] > 0) vis[abs(i - P)] = 1; } for (int i = n; i < P + 1; ++i) { if (check(i)) return print(i), 1; } return 1; } int main() { //int T = read(); rep(_, 1, T) { solve(); //cout << (solve() ? "YES" : "NO") << endl; } return 0; }
I、Increasing Subsequence
题目大意
给出一个长度为的排列,两名玩家轮流选数,如果某名玩家选了这个数那么后手只能选择某个,并且满足。问这局游戏的期望局数。
Solution
考点:期望
我们定义是上一次选了这个数,下次选了这个数的期望。
那么状态转移方程就是:,其中合法的转移叠加,是合法的转移次数,代表着多执行的一步操作。
那么我们得到状态转移方程之后,倒序的枚举上一次选择的这个数,然后从后往前遍历。
如果说明是一个合理转移累计和;
如果说明应该被计算一次答案了。
最终我们的答案就是,涉及的除法就用逆元计算,可以用线性逆元预处理。
const int MOD = 998244353; const int N = 5e3 + 7; ll n, m; ll p[N], inv[N]; ll f[N][N]; // f[i][j] 上次选了i,下次选j的期望 int solve() { n = read(); inv[0] = inv[1] = 1; for (int i = 2; i <= n; ++i) inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD; for (int i = 1; i <= n; ++i) p[i] = read(); for (int i = n; i >= 1; --i) { // 上一次选的是i ll sum = 0, cnt = 0; // sum后面可选的全部期望之和,cnt后面可选的次数 for (int j = n; j >= 0; --j) { if (p[j] > i) { ++cnt; sum += f[i][p[j]]; sum %= MOD; } else if (p[j] < i) { f[p[j]][i] = 1; f[p[j]][i] += sum * inv[cnt] % MOD; f[p[j]][i] %= MOD; } } } ll res = 0; for (int i = 1; i <= n; ++i) res = (res + f[0][i]) % MOD; print(res * inv[n] % MOD); return 1; }
J、Journey among Railway Stations
题目大意
你有一个个点的火车路线,每个火车站开放的时间是,从第号火车站去往第号火车站时间是。
题目有种操作,可以修改某个点的,或者修改,第三种操作就是询问你从号点的时刻出发能否通过最后一个火车站。火车站通过的标准是你可以提前到来等待,但是不允许迟到。
Solution
考点:数据结构(线段树)
这题我觉得官方题解写的挺好的我就贴一下他们的题解,以及我自己的代码了,不过我至今不知道为什么我的代码用参数控制线段树编号,控制的左边界,控制的右边界,就永远只能过左右,把放进线段树的里面控制就可以可能是这题空间给的不够导致回溯的时候爆栈了?
#include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<ll, ll> #define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__)) #define rep(i, sta, en) for(int i=sta; i<=en; ++i) #define repp(i, sta, en) for(int i=sta; i>=en; --i) #define debug(x) cout << #x << ":" << x << '\n' typedef long long ll; typedef unsigned long long ull; typedef long double ld; inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; } inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); } inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; } ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; } const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} }; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; const ll INF64 = 0x3f3f3f3f3f3f3f3f; const int N = 1e6 + 7; ll u[N], v[N], d[N], suf[N]; struct node { int l, r, mid; ll uma, vmi, lazy; bool ok; }tree[N << 2]; #define ls x<<1 #define rs x<<1|1 #define MID (L+R>>1) void merge(node& x, node lson, node rson) { x.uma = max(lson.uma, rson.uma); x.vmi = min(lson.vmi, rson.vmi); x.ok = (lson.ok && rson.ok && lson.uma <= rson.vmi); } void build(int x, int l, int r, int L, int R) { tree[x] = { l,r,(l + r) >> 1,0,0,0,0 }; if (l == r) { tree[x].uma = u[l]; tree[x].vmi = v[l]; tree[x].ok = 1; tree[x].lazy = 0; return; } int mid = tree[x].mid; assert(l == L); assert(r == R); assert(MID == mid); build(ls, l, mid, L, MID); build(rs, mid + 1, r, MID + 1, R); merge(tree[x], tree[ls], tree[rs]); } void solve(int x, ll k) { tree[x].uma += k; tree[x].vmi += k; tree[x].lazy += k; } void pd(int x) { if (tree[x].lazy) { solve(ls, tree[x].lazy); solve(rs, tree[x].lazy); tree[x].lazy = 0; } } void modify(int x, int l, int r, ll k, int id) { if (l <= tree[x].l && tree[x].r <= r) { if (id == 1) solve(x, k); else if (id == 2) tree[x].uma += k; else if (id == 3) tree[x].vmi += k; return; } pd(x); int mid = tree[x].mid; if (l <= mid) modify(ls, l, r, k, id); if (r > mid) modify(rs, l, r, k, id); merge(tree[x], tree[ls], tree[rs]); } node query(int x, int l, int r) { if (l <= tree[x].l && tree[x].r <= r) { return tree[x]; } int mid = tree[x].mid; pd(x); node ans = { 0,0,0,0,0,0,0 }; if (r <= mid) ans = query(ls, l, r); else if (l > mid) ans = query(rs, l, r); else merge(ans, query(ls, l, mid), query(rs, mid + 1, r)); return ans; } void solve() { int n = read(); rep(i, 1, n) u[i] = read(); rep(i, 1, n) v[i] = read(); rep(i, 1, n - 1) d[i] = read(); suf[n] = 0; repp(i, n - 1, 1) suf[i] = suf[i + 1] + d[i]; rep(i, 1, n) u[i] += suf[i], v[i] += suf[i]; build(1, 1, n, 1, n); int Q = read(), op, l, r, pos, w; while (Q--) { op = read(); if (op == 0) { l = read(), r = read(); if (query(1, l, r).ok) { puts("Yes"); } else { puts("No"); } } else if (op == 1) { pos = read(), w = read(); modify(1, 1, pos, w - d[pos], 1); // 差分修改 d[pos] = w; } else if (op == 2) { pos = read(), l = read(), r = read(); modify(1, pos, pos, suf[pos] - u[pos] + l, 2); modify(1, pos, pos, suf[pos] - v[pos] + r, 3); u[pos] = suf[pos] + l; v[pos] = suf[pos] + r; } } } signed main() { int T = read(); rep(_, 1, T) { solve(); } return 0; }
K、Knowledge Test about Match
题目大意
随机生成一个权值范围为的序列,你要用去和它匹配,匹配函数是。要求平均情况下和标准值偏差不能超过。
Solution
这题没啥考点…看到随机生成几个字就可以赛后补题开始乱搞了。
所以这题题解是来水的的
const int N = 1e3 + 7; ll n, m; int p[N]; double sqr[N]; int solve() { n = read(); rep(i, 0, n - 1) p[i] = read(); sort(p, p + n); int t = 5; while (t--) { for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (sqr[abs(i - p[i])] + sqr[abs(j - p[j])] > sqr[abs(i - p[j])] + sqr[abs(j - p[i])]) { swap(p[i], p[j]); } } } } rep(i, 0, n - 1) print(p[i], " \n"[i + 1 == n]); return 1; } int main() { rep(i, 1, N - 1) sqr[i] = sqrt(i); int T = read(); rep(_, 1, T) { solve(); //cout << (solve() ? "YES" : "NO") << endl; } return 0; }
))补题-ing