A 割韭菜
B 抓球
题意：n白m黑，取k个黑，问q次全黑的“概率”
思路： 1. 如下公式，可知我们需要预处理阶乘，不然会TLE 2. 对除法转换成 逆元 3. 这题就愉快的结束了
int inf[N]; void init() { inf[0] = 1; for (int i = 1; i < N; i++) { inf[i] = inf[i - 1] * i % mod; } } void solve() { int k, p; int n, m; cin >> n >> m >> k >> p; int x = 1, y = 1; if(n >= k) { y = inf[n] * qmi(inf[n - k], mod - 2) % mod; y = qmi(y, p) % mod; } else { cout << 0 << endl; return ; } x = inf[n + m] * qmi(inf[n + m - k], mod - 2) % mod; x = qmi(x, p) % mod; cout << y * qmi(x, mod - 2) % mod << endl; } signed main() { IOS int _ = 1; init(); cin >> _; while(_--) { solve(); } return 0; }
C 迷宫
原来C是个暴力，赛时不敢开题， 溜了溜了~~
（不取消同步会T
#include <bits/stdc++.h> using namespace std; const int N = 100010, INF = 1e9; int a[3][N]; int main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t; cin >> t; while(t--) { int n, m, h, q; cin >> n >> m >> h >> q; int s = 0; memset(a, 0, sizeof a); while(q--) { int op, x, y, z; cin >> op >> x >> y >> z; if(op == 1) { a[0][s] = x, a[1][s] = y, a[2][s] = z; s++; } else { int res = INF, tmp; for (int i = 0; i < s; i++) { tmp = abs(x - a[0][i]) + abs(y - a[1][i]) + abs(z - a[2][i]); if(res > tmp) res = tmp; } cout << res << endl; } } } return 0; }
D gk的爬山之旅
E gk的字符串
题意：？换成（a-z），且满足相邻字符不同。求最小字典序。
思路：又是一眼贪心题。O(26*n)，贪心的去从小到大放字符
void solve() { string s; cin >> s; int n = s.sz; s = '#' + s; s += '#'; for (int i = 1; i <= n; i++) { if(s[i] == '?') { for (int j = 0; j < 26; j++) { if(s[i - 1] != j + 'a' && s[i + 1] != j + 'a') { s[i] = j + 'a'; break; } } } } string t = ""; for (int i = 1; i <= n; i++) t += s[i]; cout << t << endl; }
F gk的树
题意：删边使得每一个点度<=k
思路： 跑dfs，含义是以u为根删除与f的边 （当作为子节点删边：若要删掉与父节点的公共边，那么父节点需要删边时就能节省需要删的边；所以子节点删边要尽可能删自己与父节点的公共边） （当作为父节点删边：就必须删掉其子节点们要求删掉的公共边） （回溯到父节点就能节省了）
int n, k; int res; int dfs(vii &v, int u, int f) { int len = v[u].sz; for (auto x: v[u]) { if(x == f) continue; len -= dfs(v, x, u); // 减掉子节点删掉的公共边 } if(len > k) {res += len - k; return 1; } // 需要删，返回1 return 0; } void solve() { cin >> n >> k; res = 0; vector<vector<int>> v(n + 1, vector<int>()); vector<int> d(n + 1, 0); for (int i = 1; i <= n - 1; i++) { int a, b; cin >> a >> b; v[a].pb(b); v[b].pb(a); } dfs(v, 1, 0); cout << res << endl; }
G gk的数字游戏
（真TLE，一眼模拟hhh）
思路：
- 发现当a > 2 * b, a会减2次，才会轮到b去减。那么n次的话，模拟自然超时。（a=1,b=1e9），TIME++++
- 可以看出a > n * b， a可以直接减n个b，即a/b。
void solve() { int n, m; cin >> n >> m; int res = 0; while(n && m) { if(n >= m) { res += n / m; n -= (n / m) * m; } else { res += m / n; m -= (m / n) * n; } } cout << res << endl; }
H 进来DP
I 又AK了
题意：给定n个题的AC时刻，问其它A题顺序下，罚时最少是多少？
思路：算出每个题目的花费时间，贪心的从小到大排序，然后累加算出现每个题的AC时刻。 答案：最终求一遍和
void solve() { int n = 1; cin >> n; vi a(n); for (int &v: a) cin >> v; vi b; sort(all(a)); b.pb(a[0]); for (int i = 1; i < a.sz; i++) b.pb(a[i] - a[i - 1]); sort(all(b)); int res = 0; for (int i = 1; i < b.sz; i++) b[i] += b[i - 1]; for (int i = 0; i < b.sz; i++) res += b[i]; cout << res << endl; }
J 大数乘法
这里给出欧拉降幂公式：
由于y的数据范围太大，所以输入考虑用string类型。
这里又涉及一个知识点：
求一个大数对p的模，等价于遍历该数位，每次升权对p取模，最终结果等于直接取模。（证明略~~~）
直观代码如下：
string num = "12356"; int mod = 7; int tmp = 0; for (int i = 0; i < num.size(); i++) { tmp = tmp * 10 + num[i] - '0'; tmp %= mod; }
本题又会用到欧拉函数
模板如下：
int phi(int x) // 欧拉函数 { int res = x; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { res = res / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) res = res / x * (x - 1); return res; }
现在就能愉快的AC了，hhh
const int N = 250010; int mod = 1000000007; using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; /*---------------------------------------------------------------------------------------------------------------------------*/ ll gcd(ll a, ll b){ if(b == 0){return a;} return gcd(b, a%b);} ll lcm(ll a, ll b){ return (a * (b / gcd(a, b)));} ll qmi(ll a, ll b){ if(!b) return 1ll; if(b&1) return a*qmi(a*a%mod, b>>1)%mod; return qmi(a*a%mod, b>>1)%mod;} /*---------------------------------------------------------------------------------------------------------------------------*/ int phi(int x) { int res = x; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { res = res / i * (i - 1); while (x % i == 0) x /= i; } if (x > 1) res = res / x * (x - 1); return res; } void solve() { int x, p; string yy; cin >> x >> yy >> p; mod = p; int y = 0, now = 0; int pp = phi(p); for (int i = 0; i < yy.sz; i++) { now = now * 10 + yy[i] - '0'; now %= pp; } y = now; cout << qmi(x, y) << endl; }
K 蹦蹦炸弹
L NP-hard
题意：进制转换
int sum(int x, int b) { int res = 0; int now = x; while(now) { if(now % b == 1) res++; now /= b; } return res; } void solve() { int n, x, y; cin >> n >> x >> y; if(sum(n, x) > sum(n, y)) cout << ">" << endl; else if(sum(n, x) == sum(n, y)) cout << "=" << endl; else cout << "<" << endl; }
