A.permutation
|
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; typedef long long LL; const int N = 1e5 + 10, mod = 1e9 + 7; int n; int main() { freopen("permutation.in", "r", stdin); freopen("permutation.out", "w", stdout); cin >> n; int res = 1; for (int i = 3; i <= n * 2; ++ i) res = (LL)res * i % mod; cout << res << endl; fclose(stdin); fclose(stdout); return 0; } |
B.Deque
|
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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; int c[N], n; int a[N], b[N]; int lowbit(int x) { return x & -x; } void add(int x, int v) { for (int i = x; i < N; i += lowbit(i)) c[i] += v; } int query(int x) { int res = 0; for (int i = x; i; i -= lowbit(i)) res += c[i]; return res; } int main() { freopen("Deque.in", "r", stdin); freopen("Deque.out", "w", stdout); scanf("%d", &n); for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]), b[i] = a[i]; sort(b + 1, b + 1 + n); int k = unique(b + 1, b + 1 + n) - b - 1; for (int i = 1; i <= n; ++ i) a[i] = lower_bound(b + 1, b + 1 + k, a[i]) - b; LL ans = 0; add(a[1], 1); for (int i = 2; i <= n; ++ i) { int x = query(a[i] - 1); ans += min(x, query(n) - query(a[i])); add(a[i], 1); } cout << ans << endl; fclose(stdin); fclose(stdout); } |
C.Book
|
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 |
#include <bits/stdc++.h> using namespace std; const int N = 200005, M = N; int h[N], e[M], ne[M], idx; int n, q[N], d[N], dp[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++; } bool topsort() { int tt = -1, hh = 0; for (int i = 1; i <= n; ++ i) if (!d[i]) q[++ tt] = i; while (hh <= tt) { int t = q[hh ++]; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; -- d[j]; if (j > t) dp[j] = max(dp[j], dp[t]); else dp[j] = max(dp[j], dp[t] + 1); if (!d[j]) q[++ tt] = j; } } return tt == n - 1; } int main() { freopen("Book.in", "r", stdin); freopen("Book.out", "w", stdout); memset(h, -1, sizeof h); scanf("%d", &n); for (int i = 1; i <= n; ++ i) { int k, b; scanf("%d", &k); if (!k) dp[i] = 1; while (k --) { scanf("%d", &b); add(b, i); d[i] ++; } } if (topsort()) { int res = 0; for (int i = 1; i <= n; ++ i) res = max(res, dp[i]); cout << res << endl; } else cout << -1 << endl; fclose(stdin); fclose(stdout); } |
D.lines
|
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 |
#include <bits/stdc++.h> using namespace std; const int N = 10000 + 10, M = 2e3 + 10; int n, a[N], m; bool f[2][M]; bool check(int x) { for (int i = 0; i <= x; ++ i) f[0][i] = 1; for (int i = 0; i < n; ++ i) { int id = i & 1; for (int j = 0; j <= x; ++ j) f[id ^ 1][j] = 0; for (int j = 0; j <= x; ++ j) { if (!f[id][j]) continue; if (j - a[i] >= 0) f[id ^ 1][j - a[i]] = 1; if (j + a[i] <= x) f[id ^ 1][j + a[i]] = 1; } } for (int i = 0; i <= x; ++ i) if (f[n & 1][i]) return true; return false; } int main() { freopen("lines.in", "r", stdin); freopen("lines.out", "w", stdout); scanf("%d", &n); for (int i = 0; i < n; ++ i) scanf("%d", &a[i]); int l = 0, r = M; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } cout << l << endl; fclose(stdin); fclose(stdout); } |
发表回复