CodeChef FEB16月赛
CHEFDETE Chef-Detective
输出所有的叶子结点,傻题是也。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <bits/stdc++.h> using namespace std; int n, cnt[100005]; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int main() { cin >> n; for (int i = 1; i <= n; ++i) ++cnt[read()]; for (int i = 1; i <= n; ++i) if (!cnt[i]) printf("%d ", i); return 0; } |
STROPR Chef and Strange Operations
单独计算序列中的每一个数对于答案的贡献,傻不拉叽的组合数各种推。讲道理还不是那么好推吧。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include <bits/stdc++.h> using namespace std; #define P 1000000007 int test, n, x; long long m, inv[100005], a[100005], c[100005]; inline long long read() { long long x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int main() { inv[1] = 1; for (int i = 2; i <= 100000; ++i) inv[i] = inv[P % i] * (P - P / i) % P; cin >> test; while (test--) { cin >> n >> x >> m; for (int i = 1; i <= n; ++i) a[i] = read() % P; c[0] = 1; for (int i = 1; i < x; ++i) c[i] = ((m - 1) % P * inv[i] % P + 1) * c[i - 1] % P; long long ans = 0; for (int i = 1; i <= x; ++i) ans = (ans + a[i] * c[x - i]) % P; cout << ans << endl; } return 0; } |
DEVLDISC Devu and a light discussion
构造题。先构造出来一个四元环,在上面挑一个点作为起点。之后在另外三个点上各连出来一个爪,一共消耗结点数为7。当节点数变多的时候,再继续往出连爪就好了。当节点数小于7的时候,手画半天发现无解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | #include <bits/stdc++.h> using namespace std; int test, n; int main() { cin >> test; while (test--) { cin >> n; if (n <= 6) { puts("-1"); } else { printf("%d\n", n); puts("1 2\n1 3\n2 4\n3 4\n2 5\n3 6"); for (int i = 7; i <= n; ++i) printf("4 %d\n", i); puts("1"); } } return 0; } |
RECTLOVE Rectangles of Love
纯粹傻题一道。开始的时候读错题以为选出的矩形必须在整个矩形的边缘,后来调试了好久发现我就是一只勤劳的逗逼。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | #include <bits/stdc++.h> using namespace std; int test, n, m, k; long long pos; int main() { ios::sync_with_stdio(false); cin >> test; while (test--) { cin >> n >> m >> k; long double ans = 0, x, y; for (int i = 1; i <= k; ++i) cin >> pos, x = (pos - 1) / m + 1, y = (pos - 1) % m + 1, ans += x*(n-x+1)/n/(n+1)*y*(m-y+1)/m/(m+1)*4; cout << fixed << setprecision(10) << ans << endl; } return 0; } |
SEATL Sereja and Two Lines
谜之时间复杂度。分别考虑每一种颜色,求出它所有出现次数最多的行和列,然后枚举行和列的组合方式,判断它是否同时出现在交点处。
算时间复杂度吧!首先我们用O(NM)的时间遍历了好几遍矩阵。之后枚举每一种颜色出现次数最多的行和列。由于当找到一个异色交叉点就会退出循环,而我们枚举的交叉点两两不同,所以最坏情况下也只会将所有点遍历一遍,时间复杂度O(NM)。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | #include <bits/stdc++.h> using namespace std; #define N 1000005 int test, n, m, cnt[N], mc1[N], mc2[N]; vector<int> a[N], v1[N], v2[N]; inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int main() { cin >> test; while (test--) { cin >> n >> m; for (int i = 1; i <= n; ++i) a[i].resize(m + 1); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) a[i][j] = read(); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) ++cnt[a[i][j]]; for (int j = 1; j <= m; ++j) { int t = a[i][j]; if (cnt[t] > mc1[t]) mc1[t] = cnt[t], v1[t].clear(); if (cnt[t] == mc1[t]) v1[t].push_back(i); cnt[t] = 0; } } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) ++cnt[a[j][i]]; for (int j = 1; j <= n; ++j) { int t = a[j][i]; if (cnt[t] > mc2[t]) mc2[t] = cnt[t], v2[t].clear(); if (cnt[t] == mc2[t]) v2[t].push_back(i); cnt[t] = 0; } } int ans = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { int t = a[i][j], flag = 1; for (int k = 0; k < (int)v1[t].size(); ++k) for (int l = 0; l < (int)v2[t].size(); ++l) if (a[v1[t][k]][v2[t][l]] != t) { flag = 0; break; } ans = max(ans, mc1[t] + mc2[t] - flag); v1[t].clear(), v2[t].clear(), mc1[t] = mc2[t] = 0; } } cout << ans << endl; } return 0; } |
MTMXSUM Matrix Maximum Sum
发现生成矩阵的公式里面含有 i 和 j,我们不妨将式子做一下变形,发现 i 和 j 只需要在读入的时候顺便加进 Ai 和 Bj 里面就可以了。
于是现在我们需要求出对于每一个 K,所有 K*K 矩阵内的最大值之和。发现 A 和 B 两个序列可以分开计算最大值,最后直接相乘即可。
单独考虑一个序列,它在 K 递增的时候,依次变成下面的样子:
5 8 6 9
8 8 9
8 9
9
好像一个三角形的样子。考虑某一个 Ai 的出现次数,在最下层一定为一次,之后依次增大为两次、三次……直到旁边更大的元素(或边界)来将其覆盖,之后维持出现次数不变。当它遇到另一边的更大元素时,次数又会开始减小直到 0。
用单调栈扫一下,预处理出每一个元素两边更大的元素位置,之后递推一下就可以了。最终当两个序列的答案合并时直接相乘即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | #include <bits/stdc++.h> using namespace std; #define mod 1000000007 #define N 100005 int n, a[N], b[N], ans1[N], ans2[N]; inline void solve(int re[], int a[]) { stack<int> s; int l[N] = {0}, r[N] = {0}; for (int i = 1; i <= n; ++i) { while (!s.empty() && a[i] > a[s.top()]) s.pop(); l[i] = s.empty() ? i - 1 : i - s.top() - 1, s.push(i); } while (!s.empty()) s.pop(); for (int i = n; i >= 1; --i) { while (!s.empty() && a[i] >= a[s.top()]) s.pop(); r[i] = s.empty() ? n - i : s.top() - i - 1, s.push(i); } while (!s.empty()) s.pop(); for (int i = 1; i <= n; ++i) { re[1] = (re[1] + a[i]) % mod; re[l[i] + 2] = (re[l[i] + 2] - a[i] + mod) % mod; re[r[i] + 2] = (re[r[i] + 2] - a[i] + mod) % mod; re[l[i] + r[i] + 3] = (re[l[i] + r[i] + 3] + a[i]) % mod; } for (int upd = 0, i = 1; i <= n; ++i) { upd = (upd + re[i]) % mod; re[i] = (re[i - 1] + upd) % mod; } } inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int main() { cin >> n; for (int i = 1; i <= n; ++i) a[i] = read() + i; solve(ans1, a); for (int i = 1; i <= n; ++i) b[i] = read() + i; solve(ans2, b); for (int i = 1; i <= n; ++i) printf("%lld ", 1ll * ans1[i] * ans2[i] % mod); return 0; } |
CALLSCHE Call Center Schedule
网络流傻题,建图有点麻烦?题解忘记了考虑 N 的情况?还需要特判开会太多使得有人吃不上饭或者工作超时的情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 | #include <bits/stdc++.h> using namespace std; #define N 20000 #define M 1000000 #define inf 0x3f3f3f3f int test, p, ds, h, n, lt, rt; int f[75][75][75], mee1[75][75], mee2[75][75]; int s, t, head[N], cnt, d[N]; struct graph { int next, to, val; graph() {} graph(int _next, int _to, int _val) : next(_next), to(_to), val(_val) {} } edge[M]; inline void add(int x, int y, int z) { edge[++cnt] = graph(head[x], y, z); head[x] = cnt; edge[++cnt] = graph(head[y], x, 0); head[y] = cnt; } queue<int> q; bool bfs() { memset(d, 0, sizeof d); while (!q.empty()) q.pop(); d[s] = 1; q.push(s); while (!q.empty()) { int x = q.front(); q.pop(); for (int i = head[x]; i; i = edge[i].next) if (edge[i].val && !d[edge[i].to]) { d[edge[i].to] = d[x] + 1; if (edge[i].to == t) return true; q.push(edge[i].to); } } return false; } int dfs(int x, int f) { if (x == t) return f; int temp = f; for (int i = head[x]; i; i = edge[i].next) if (edge[i].val && d[edge[i].to] == d[x] + 1) { int k = dfs(edge[i].to, min(temp, edge[i].val)); if (!k) d[edge[i].to] = 0; edge[i].val -= k; edge[i ^ 1].val += k; if (!(temp -= k)) break; } return f - temp; } int dinic() { int re = 0; while (bfs()) re += dfs(s, inf); return re; } inline int daypos(int x, int y) { return p + (x - 1) * ds + y; } inline int lunpos(int x, int y) { return p + p * ds + (x - 1) * ds + y; } inline int clipos(int x, int y) { return p + 2 * p * ds + (x - 1) * h + y; } inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int main() { cin >> test; while (test--) { memset(head, 0, sizeof head), cnt = 1; memset(mee1, 0, sizeof mee1); memset(mee2, 0, sizeof mee2); cin >> p >> ds >> h >> n; s = 0, t = p + 2 * p * ds + ds * h + 1; for (int i = 1; i <= p; ++i) add(s, i, read()); cin >> lt >> rt; int sum = 0; for (int x, i = 1; i <= ds; ++i) for (int j = 1; j <= h; ++j) x = read(), sum += x, add(clipos(i, j), t, x); for (int i = 1; i <= p; ++i) for (int j = 1; j <= ds; ++j) for (int k = 1; k <= h; ++k) { f[i][j][k] = read(); if (k >= lt && k <= rt) mee2[i][j] += f[i][j][k] ^ 1; mee1[i][j] += f[i][j][k] ^ 1; } for (int i = 1; i <= p; ++i) for (int j = 1; j <= ds; ++j) { if (mee1[i][j] > n || mee2[i][j] > rt - lt) { puts("No"); goto end; } add(i, daypos(i, j), n - mee1[i][j]), add(daypos(i, j), lunpos(i, j), rt - lt - mee2[i][j]); for (int k = 1; k <= h; ++k) if (f[i][j][k] && k >= lt && k <= rt) add(lunpos(i, j), clipos(j, k), 1); else if (f[i][j][k]) add(daypos(i, j), clipos(j, k), 1); } puts(dinic() == sum ? "Yes" : "No"); end:; } return 0; } |
SEAPERMS Sereja and Permutations
先不考虑修改,我们可以在 O(N^2) 的时间内求出这道题的答案。
将所有元素排一个序,从小到大依次把元素们往排列里面插。预处理出对于每一个元素,它能够被插在多少个小元素的后面,加上它还可以被插在最前面,很容易就可以算出来方案数。
之后对于一个修改,同样可以在 O(N) 之内处理。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | #include <bits/stdc++.h> using namespace std; #define N 200005 #define mod 1000000007 int n, d, m, a[N], p[N], v[N], inv[N], sum[N], cnt[N]; long long ans = 1ll; vector<int> b; void del(int x) { ans = ans * inv[sum[x] + cnt[x]] % mod, --cnt[x]; for (int j = x + 1; j < (int)b.size() && b[j] - b[x] < d; ++j) ans = ans * inv[sum[j] + cnt[j]] % mod * sum[j] % mod, --sum[j]; } void ins(int x) { ++cnt[x], ans = ans * (sum[x] + cnt[x]) % mod; for (int j = x + 1; j < (int)b.size() && b[j] - b[x] < d; ++j) ++sum[j], ans = ans * inv[sum[j]] % mod * (sum[j] + cnt[j]) % mod; } inline int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return x * f; } int main() { cin >> n >> d; inv[1] = 1; for (int i = 2; i <= n; ++i) inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod; for (int i = 1; i <= n; ++i) b.push_back(a[i] = read()); cin >> m; for (int i = 1; i <= m; ++i) p[i] = read(), b.push_back(v[i] = read()); sort(b.begin(), b.end()); b.erase(unique(b.begin(), b.end()), b.end()); for (int x, i = 1; i <= n; ++i) { ++cnt[x = lower_bound(b.begin(), b.end(), a[i]) - b.begin()]; for (int j = x + 1; j < (int)b.size() && b[j] - b[x] < d; ++j) ++sum[j]; } for (int i = 0; i < (int)b.size(); ++i) for (int j = 1; j <= cnt[i]; ++j) ans = ans * (sum[i] + j) % mod; for (int i = 1; i <= m; ++i) { del(lower_bound(b.begin(), b.end(), a[p[i]]) - b.begin()); ins(lower_bound(b.begin(), b.end(), a[p[i]] = v[i]) - b.begin()); printf("%lld\n", ans); } return 0; } |
WRDSUM Weird Sum
神题,高精度取模,吓得我都写 Python 了。
首先考虑如何计算 $\sum_{i=1}^n i^k \mod P(n\le \sqrt[k]{10^{2016})}$。首先,P 是一个大质数,观察 k 次方和公式,分子的地方有一个 n,分母的地方不含 P,所以可以猜想 $\sum_{i=1}^P i^k \mod P=0$。于是我们直接将 n 对 P 取模不会有任何问题。
之后,我们用类似于组合数的东西预处理一个系数矩阵 coe,有公式 $\sum_{i=1}^n i^k = \sum_{i=1}^k coe[k][i]*{n+1\choose i+1}\mod P$。这样可以用 O(k^2) 的时间预处理,用 O(k) 的时间回答询问。
回到原题,我们可以发现,所有的无次方因子数的 F 值都是本身,而其他的数的 F 值等于其开方后的 F 值。我们不妨枚举 k,计算所有含有 k 次方因子且不含更高次方因子的数对答案的贡献。首先,k 不会大于 7000。我们可以预处理出 8000 项以内的莫比乌斯函数,之后进行容斥。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | mod = 998244353 coe = [[0], [0, 1]] for i in range(2, 500): p = [0] for j in range(1, i): p.append((coe[-1][j - 1] + coe[-1][j]) * j % mod) p.append(coe[-1][-1] * i % mod) coe.append(p) inv = [0, 1] for i in range(2, 8000): inv.append(inv[mod % i] * (mod - mod / i) % mod) def power_sum(n, k): if (k >= 500): re = 0 for i in range(2, n + 1): re = (re + pow(i, k, mod)) % mod return re re = 0 n = n % mod pa = (n + 1) % mod for i in range(1, k + 1): pa = pa * (n + 1 - i + mod) * inv[i + 1] % mod re = (re + coe[k][i] * pa) % mod return (re - 1 + mod) % mod p = [] mu = [0 for i in range(8000)] vis = [0 for i in range(8000)] mu[1] = 1; for i in range(2, 8000): if (vis[i] == 0): p.append(i); mu[i] = -1 for j in p: if (i * j >= 8000): break vis[i * j] = 1 if (i % j): mu[i * j] = -mu[i] else: mu[i * j] = 0; break for test in range(int(raw_input())): n = int(raw_input()) arr = [0, n] p = 0 base = 1 while (base < n): base *= 2; p += 1 for i in range(2, p): l = 2 r = arr[-1] ans = 0 while (l <= r): mid = (l + r) / 2 if (mid ** i <= n): l = mid + 1; ans = mid else: r = mid - 1 arr.append(ans) ans = 0 for i in range(1, len(arr)): cadd = power_sum(arr[i], 1) for j in range(2, 8000): aidx = i * j if (aidx >= len(arr)): break cadd += mu[j] * power_sum(arr[aidx], j) ans = (ans + cadd) % mod print ans |