hohahola
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<stack> #include<string> #include<functional> #include<math.h> //#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef vector<int> VI; typedef pair<int, int> PII; typedef queue<int> QI; void makedata() { freopen("input.txt", "w", stdout); fclose(stdout); } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif //makedata(); std::ios::sync_with_stdio(0), cin.tie(0); lint n, x, y, z; cin >> n >> x >> y >> z; if (z >= y) cout << (n * z / x) << endl; else { lint l = 0, r = n, mid; lint ans = 0; while (l + 1 < r) { mid = (l + r) / 2; if ((n - mid) * z >= (x - y) * mid) { l = mid; ans = max(ans, mid); } else r = mid; } cout << ans << endl; } return 0; }
最大顺子
要使顺子的值最大，m张任意牌肯定全用完了，因为任意牌可以放在有数字的牌的右边
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<stack> #include<string> #include<functional> #include<math.h> //#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef vector<int> VI; typedef pair<int, int> PII; typedef queue<int> QI; void makedata() { freopen("input.txt", "w", stdout); fclose(stdout); } lint a[110000], f[110000], s[110000]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif //makedata(); std::ios::sync_with_stdio(0), cin.tie(0); int n, m, k; cin >> n >> m >> k; for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); lint ans = 0; int p = k - m; for (int i = 0; i + p - 1 < n; i++) { int j = i + p - 1; if (a[j] - a[i] + 1 - p <= m) ans = max(ans, a[i] + k - 1); } cout << ans << endl; return 0; }
路径包含问题
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<stack> #include<string> #include<functional> #include<math.h> //#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef vector<int> VI; typedef pair<int, int> PII; typedef queue<int> QI; void makedata() { freopen("input.txt", "w", stdout); fclose(stdout); } class LCA { public: int n; int ancient[110000][20], depth[110000], father[110000], sz[110000]; vector<vector<int>> * T; void init(vector<vector<int>> *, int, int); void dfs(int, int, int); int query(int, int); }; void LCA::dfs(int root, int fa, int dep) { ancient[root][0] = fa; depth[root] = dep; sz[root] = 1; for (int i = 0; i < (*T)[root].size(); i++) { int u = (*T)[root][i]; if (u == fa) continue; dfs(u, root, dep + 1); sz[root] += sz[u]; } } void LCA::init(vector<vector<int>> * G, int root, int nn) { T = G, n = nn; dfs(root, -1, 0); for (int i = 0; i < 20; i++) ancient[root][i] = -1; for (int i = 1; i < 20; i++) { for (int j = 1; j <= n; j++) { if (ancient[j][i - 1] == -1) ancient[j][i] = -1; else ancient[j][i] = ancient[ancient[j][i - 1]][i - 1]; } } } int LCA::query(int u, int v) { if (depth[u] > depth[v]) swap(u, v); int d = 0; while (depth[u] != depth[v]) { if ((depth[v] - depth[u]) & (1 << d)) v = ancient[v][d]; d++; } if (u == v) return u; for (int i = 19; i >= 0; i--) { if (ancient[u][i] != ancient[v][i]) u = ancient[u][i], v = ancient[v][i]; } return ancient[u][0]; } LCA lca; vector<vector<int>> G(110000, vector<int>());; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif //makedata(); std::ios::sync_with_stdio(0), cin.tie(0); int n, m, u, v; cin >> n >> m; for (int i = 1; i < n; i++) { cin >> u >> v; G[u].push_back(v); } lca.init(&G, 1, n); for (int i = 0; i < m; i++) { cin >> u >> v; if (lca.depth[u] > lca.depth[v]) swap(u, v); int w = lca.query(u, v), vv = v; if (w == u) { int d = 0; while (lca.depth[u] != lca.depth[vv] - 1) { if ((lca.depth[vv] - 1 - lca.depth[u]) & (1 << d)) vv = lca.ancient[vv][d]; d++; } cout << (1LL * (n - lca.sz[vv])*lca.sz[v]) << endl; } else cout << (1LL * lca.sz[u] * lca.sz[v]) << endl; } return 0; }
树上的节点cd之间有两种关系，其中一个是另一个的祖先，或两者都不是对方的祖先，判断两者的关系，把路径两端的点的数量相乘
随机排列
枚举左边界
#pragma comment(linker, "/STACK:102400000,102400000") #include<stdio.h> #include<string.h> #include<stdlib.h> #include<vector> #include<algorithm> #include<iostream> #include<map> #include<queue> #include<stack> #include<string> #include<functional> #include<math.h> //#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef vector<int> VI; typedef pair<int, int> PII; typedef queue<int> QI; void makedata() { freopen("input.txt", "w", stdout); fclose(stdout); } lint ans[110000]; int a[110000], m[110000][20], M[110000][20], LOG2[110000]; void init(int n) { for (int i = 2; i <= n; i++) LOG2[i] = LOG2[i >> 1] + 1; for (int i = 1; i <= n; i++) m[i][0] = M[i][0] = a[i]; for (int j = 1; (1 << j) <= n; j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) { m[i][j] = min(m[i][j - 1], m[i + (1 << (j - 1))][j - 1]); M[i][j] = max(M[i][j - 1], M[i + (1 << (j - 1))][j - 1]); } } } int query(int l, int r) { int k = LOG2[r - l + 1]; return max(M[l][k], M[r - (1 << k) + 1][k]) - min(m[l][k], m[r - (1 << k) + 1][k]); } VI R, C; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif //makedata(); std::ios::sync_with_stdio(0), cin.tie(0); int n, t; cin >> t; while (t--) { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; memset(ans, 0, sizeof(ans)); init(n); R.clear(); for (int i = n; i >= 1; i--) { C = R; R.clear(); R.push_back(i); for (int j = 0; j < C.size(); j++) { if (query(i, R[R.size() - 1]) != query(i, C[j])) R.push_back(C[j]); } for (int j = 0; j < R.size() - 1; j++) ans[query(i, R[j])] += R[j + 1] - R[j]; ans[query(i, R[R.size() - 1])] += n - R[R.size() - 1] + 1; } for (int i = 0; i < n; i++) { cout << ans[i] << endl; ans[i + 1] += ans[i]; } } return 0; }