删除树节点
#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 w[110000], fa[110000], n, k; VI G[110000]; void dfs(int x, int f) { fa[x] = f; if(w[x] < k) { fa[x] = -1; for(int i = 0; i < G[x].size(); i++) { int y = G[x][i]; dfs(y, f); } } else { for(int i = 0; i < G[x].size(); i++) { int y = G[x][i]; dfs(y, x); } } } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif //makedata(); std::ios::sync_with_stdio(0), cin.tie(0); int root; cin >> n >> k; for(int i = 1; i <= n; i++) cin >> w[i]; for(int i = 1; i <= n; i++) { cin >> fa[i]; G[fa[i]].push_back(i); if(fa[i] == 0) root = i; } dfs(root, 0); for(int i = 1; i <= n; i++) cout << fa[i] << ' '; return 0; }
鱼雷射击
mei yi si lan de xie le
公平分队II
一个人拿到最大的两个，另一个拿到最小的两个，剩下的平均分配。
#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); int n; cin >> n; lint ans = 0; for (int i = 3; i < 2 * n - 1; i++) ans += i; ans /= 2; ans += 4 * n - 1; if (n == 1) ans = 2; cout << ans << endl; return 0; }
数组区间
依次计算每个数字在多少个区间中出现，乘起来求和。
p[i][j]表示第i个数字左边第j个比它大的数字的位置，q[i][j]表示第i个数字右边第j个比它大的数字的位置。因为数据中每个数字都不相同，所以按从小到大的顺序计算每个数字的p和q，只需直接取其左右的连续数字即可，计算完成后将该数字删除。
对于第i个数字出现区间数的计算，枚举其左边比它大的数字j，左边界的可能种类数为p[i][j] - p[i][j + 1]，右边界的可能种类数为q[i][k - j] - q[i][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); } lint a[110000], pre[110000], nex[110000]; lint p[110000][60], q[110000][60]; vector<PII> v; int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); #endif //makedata(); std::ios::sync_with_stdio(0), cin.tie(0); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; v.clear(); for (int i = 1; i <= n; i++) v.push_back(make_pair(a[i], i)); sort(v.begin(), v.end()); for (int i = 1; i <= n; i++) pre[i] = i - 1, nex[i] = i + 1; for (int i = 0; i < v.size(); i++) { int id = v[i].second, ptr; p[id][0] = q[id][0] = id; ptr = id; for (int i = 1; i <= k; i++) { if (pre[ptr] > 0) { p[id][i] = pre[ptr]; ptr = pre[ptr]; } else break; } ptr = id; for (int i = 1; i <= k; i++) { if (nex[ptr] <= n) { q[id][i] = nex[ptr]; ptr = nex[ptr]; } else break; } nex[pre[id]] = nex[id]; pre[nex[id]] = pre[id]; } lint ans = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= k; j++) { if (q[i][j] == 0) q[i][j] = n + 1; } } for (int i = 1; i <= n; i++) { for (int j = 0; j < k; j++) { if (p[i][j] == 0) break; ans += (p[i][j] - p[i][j + 1]) * (q[i][k - j] - q[i][0]) * a[i]; } } cout << ans << endl; return 0; }