题目链接 gym101778
Problem A
转化成绝对值之后算一下概率。这个题有点像 2018 ZOJ Monthly March Problem D ？ 不过那个题要难一些~
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const LL mod = 1e9 + 7; const int N = 2e5 + 10; int T; int n, m; LL fac[N]; inline LL Pow(LL a, LL b, LL mod){ LL ret(1); for (; b; b >>= 1, (a *= a) %= mod) if (b & 1) (ret *= a) %= mod; return ret; } inline LL C(LL n, LL m){ return m > n ? 0 : fac[n] * Pow(fac[m] * fac[n - m] % mod, mod - 2, mod) % mod; } int main(){ fac[0] = 1; rep(i, 1, 2e5 + 1) fac[i] = fac[i - 1] * 1ll * i % mod; scanf("%d", &T); while (T--){ scanf("%d%d", &n, &m); n = abs(n); if (n == 0 && m == 0){ puts("1"); continue; } if (m < n){ puts("0"); continue; } if ((m + n) % 2 == 1){ puts("0"); continue; } int x = (m + n) / 2; printf("%lld\n", C(m, x) * Pow(Pow(2, m, mod), mod - 2, mod) % mod); } return 0; }Problem B
把首项定成$1$然后二分答案就可以了
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; int T; LL n, a, l, r, t; int main(){ scanf("%d", &T); while (T--){ scanf("%lld%lld", &n, &a); l = 0, r = n; while (l + 1 < r){ LL mid = (l + r) >> 1; if (mid * (mid + 1) / 2ll <= n * a - n + mid) l = mid; else r = mid - 1; } if (r * (r + 1) / 2ll <= n * a - n + r) t = r; else t = l; printf("%lld\n", t); } return 0; }Problem C
找规律。$ans = (n - 1) * phi(n)$
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const int N = 1e6 + 10; int T; int phi[N]; int n; int main(){ rep(i, 2, 1e6 + 1){ if (!phi[i]){ for (int j = i; j <= 1e6; j += i){ if (!phi[j]) phi[j] = j; phi[j] -= phi[j] / i; } } } scanf("%d", &T); while (T--){ scanf("%d", &n); printf("%lld\n", 1ll * (n - 1) * phi[n]); } return 0; }Problem D
状态压缩，对于每一个集合求MST
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) const int N = 16; int T; int n, m, k; int a[N][N], c[1 << N]; int all; int ans; int main(){ scanf("%d", &T); while (T--){ scanf("%d%d%d", &n, &m, &k); memset(c, 0, sizeof c); memset(a, -1, sizeof a); ans = 2e9; rep(i, 1, m){ int x, y, z; scanf("%d%d%d", &x, &y, &z); --x; --y; a[x][y] = a[y][x] = z; } all = 0; rep(i, 1, k){ int x; scanf("%d", &x); --x; all |= (1 << x); } int mx = (1 << n) - 1; rep(i, 1, mx){ c[i] = 2e9; int p = 0; dec(j, n - 1, 0) if ((i >> j) & 1){ p = j; break; } if ((i ^ (1 << p)) == 0){ c[i] = 0; continue; } dec(j, n - 1, 0){ if ((i >> j) & 1){ rep(k, 0, n - 1){ if (((i >> k) & 1) && (j != k) && (~a[j][k])) c[i] = min(c[i], c[i ^ (1 << j)] + a[j][k]); } } } } rep(i, 1, mx) if ((i & all) == all) ans = min(ans, c[i]); printf("%d\n", ans); } return 0; }Problem E
直接模拟
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define fi first #define se second #define MP make_pair typedef long long LL; int T; int n, x, y; int id, d, m; int mxd, mxm; int main(){ scanf("%d", &T); while (T--){ scanf("%d%d%d", &n, &x, &y); mxd = 1e9, mxm = 0; id = -1; rep(i, 1, n){ scanf("%d%d", &d, &m); if (d <= x && m >= y){ if (mxd > d || (mxd == d && mxm < m)){ mxd = d; mxm = m; id = i; } } } printf("%d\n", id); } return 0; }Problem F
这个题略卡常数。
对每个权值求二维前缀和，二分答案就好了。
#include <bits/stdc++.h> namespace IO{ const int MT = 20 * 1024 * 1024; char IO_BUF[MT]; int IO_PTR, IO_SZ; void begin(){ IO_PTR = 0; IO_SZ = fread (IO_BUF, 1, MT, stdin); } template<typename T> inline bool scan_d (T & t){ while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != '-' && (IO_BUF[IO_PTR] < '0' || IO_BUF[IO_PTR] > '9'))IO_PTR ++; if (IO_PTR >= IO_SZ) return false; bool sgn = false; if (IO_BUF[IO_PTR] == '-') sgn = true, IO_PTR ++; for (t = 0; IO_PTR < IO_SZ && '0' <= IO_BUF[IO_PTR] && IO_BUF[IO_PTR] <= '9'; IO_PTR ++) t = t * 10 + IO_BUF[IO_PTR] - '0'; if (sgn) t = -t; return true; } }; using namespace IO; using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int M = 503; const int N = 1e2 + 2; int c[M][N][N]; int a[N][N]; int n, m, q; int mx; int T; int calc(int x1, int y1, int x2, int y2, int val){ return c[val][x2][y2] - c[val][x2][y1 - 1] - c[val][x1 - 1][y2] + c[val][x1 - 1][y1 - 1]; } void print(int x){ if (x > 9) print(x / 10); putchar(x % 10 + '0'); } int main(){ begin(); scan_d(T);; while (T--){ scan_d(n); scan_d(m); scan_d(q); mx = 0; rep(i, 1, n){ rep(j, 1, m) scan_d(a[i][j]), mx = max(mx, a[i][j]); } rep(k, 0, mx){ rep(i, 0, n + 1){ rep(j, 0, m + 1) c[k][i][j] = 0; } } rep(k, 1, mx){ rep(i, 1, n){ rep(j, 1, m){ c[k][i][j] = c[k][i - 1][j] + c[k][i][j - 1] - c[k][i - 1][j - 1] + (a[i][j] <= k); } } } while (q--){ int x1, y1, x2, y2; scan_d(x1); scan_d(y1); scan_d(x2); scan_d(y2); int all = (x2 - x1 + 1) * (y2 - y1 + 1); all = (all + 1) / 2; int l = 1, r = mx; while (l + 1 < r){ int mid = (l + r) >> 1; if (calc(x1, y1, x2, y2, mid) >= all) r = mid; else l = mid + 1; } int t; if (calc(x1, y1, x2, y2, l) >= all) t = l; else t = r; print(t); putchar(10); } } return 0; }Problem G
根据割线定理来做。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define fi first #define se second #define MP make_pair typedef long long LL; int T; int n, x, y; int id, d, m; int mxd, mxm; int main(){ scanf("%d", &T); while (T--){ scanf("%d%d%d", &n, &x, &y); mxd = 1e9, mxm = 0; id = -1; rep(i, 1, n){ scanf("%d%d", &d, &m); if (d <= x && m >= y){ if (mxd > d || (mxd == d && mxm < m)){ mxd = d; mxm = m; id = i; } } } printf("%d\n", id); } return 0; }Problem H
假的数据结构……其实还是模拟
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; const int N = 1e5 + 10; int T; int n, m; char s[N], ch[2]; int main(){ scanf("%d", &T); while (T--){ scanf("%d%d", &n, &m); scanf("%s", s + 1); int c = 0; rep(i, 1, (n + 1) >> 1) if (s[i] == s[n - i + 1]) ++c; int all = (n + 1) >> 1; int ans = 0; while (m--){ int x; scanf("%d%s", &x, ch); if (s[x] == s[n - x + 1]){ s[x] = ch[0]; if (s[x] != s[n - x + 1]) --c; } else{ s[x] = ch[0]; if (s[x] == s[n - x + 1]) ++c; } if (c == all) ++ans; } printf("%d\n", ans); } return 0; }Problem I
签到
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; int T; int main(){ scanf("%d", &T); while (T--){ int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); if (a == d && b == c){ puts("-1"); continue; } if (a + c == b + d){ if (c > a) puts("1"); else puts("2"); } else if (a + c > b + d) puts("1"); else puts("2"); } return 0; }Problem J
挺有意思的一个题。
其实暴力做就可以了。因为在1e9的范围内质数间隔最大大概只有$320$。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; int T; int fg; LL l, r; bool check(LL x){ if (x <= 10) return false; string s1 = ""; for (; x; x /= 10) s1 += x % 10 + '0'; reverse(s1.begin(), s1.end()); int n = s1.length(); string s2 = s1.substr(0, (n + 1) / 2); string s3 = s1.substr((n + 1) / 2); LL a = 0, b = 0; for (auto u : s2) a = a * 10 + u - '0'; for (auto u : s3) b = b * 10 + u - '0'; return __gcd(a, b) == 1; } int main(){ scanf("%d", &T); while (T--){ scanf("%lld%lld", &l, &r); fg = 0; for (LL i = r; i >= l; --i){ if (check(i)){ fg = 1; printf("%lld\n", i); break; } } if (!fg) puts("-1"); } return 0; }Problem K
模拟……
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) #define MP make_pair #define fi first #define se second typedef long long LL; struct state{ int x, y, z, t; state(){ x = y = z = t = -1; } state(int x, int y, int z, int t) : x(x), y(y), z(z), t(t){ } bool operator < (const state &e) const{ return t < e.t; } }; const int N = 1e2 + 2; int T; int n, m, k; int fb[N]; int WA[N][N], FAC[N]; vector <state> sub; int main(){ scanf("%d", &T); while (T--){ scanf("%d%d%d", &n, &m, &k); int x, y, z, tm, ts; sub.clear(); rep(i, 0, k - 1){ scanf("%d%d%d%d:%d", &x, &y, &z, &tm, &ts); sub.push_back(state(x - 1, y - 1, z, tm * 60 + ts)); } sort(sub.begin(), sub.end()); memset(fb, -1, sizeof fb); memset(WA, 0, sizeof WA); memset(FAC, 0, sizeof FAC); int ep = -1, sg = -1; pair<int, int> sp(-1, 0), rp(-1, 0); rep(i, 0, k - 1){ if (sub[i].z == 0) ++WA[sub[i].x][sub[i].y]; else{ if (fb[sub[i].x] == -1) fb[sub[i].x] = sub[i].y + 1; if (ep == -1) ep = sub[i].y + 1; sg = sub[i].y + 1; if (WA[sub[i].x][sub[i].y] == 0) ++FAC[sub[i].y]; if (FAC[sub[i].y] > sp.first || (FAC[sub[i].y] == sp.first && sub[i].y + 1 < sp.second)) sp = make_pair(FAC[sub[i].y], sub[i].y + 1); if (WA[sub[i].x][sub[i].y] > rp.first || (WA[sub[i].x][sub[i].y] == rp.first && sub[i].y + 1 < rp.second)) rp = make_pair(WA[sub[i].x][sub[i].y], sub[i].y + 1); } } rep(i, 0, n - 1) printf("%s%d", i ? " " : "", fb[i]); putchar(10); printf("%d %d %d %d\n", ep, sg, sp.se, rp.se); } return 0; }
转载于:https://www.cnblogs.com/cxhscst2/p/9017368.html
相关资源：各显卡算力对照表！