删除树节点
#pragma comment(linker, "/STACK:102400000,102400000")#include#include<string.h>#include#include#include#include#include#include#include#include<string>#include#include//#includeusing 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 ) { int y = G[x][i]; dfs(y, f); } } else { for(int i = 0; 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 <' '; return 0;}
鱼雷射击
mei yi si lan de xie le
公平分队II
一个人拿到最大的两个，另一个拿到最小的两个，剩下的平均分配。
#pragma comment(linker, "/STACK:102400000,102400000")#include#include<string.h>#include#include#include#include#include#include#include#include<string>#include#include//#includeusing 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 < 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#include<string.h>#include#include#include#include#include#include#include#include<string>#include#include//#includeusing 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 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 ) { 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 ) { if (p[i][j] == 0) break; ans += (p[i][j] - p[i][j + 1]) * (q[i][k - j] - q[i][0]) * a[i]; } } cout < endl; return 0;}
京公网安备 11010802041100号