省赛组队赛暨省赛积分赛2
https://vjudge.net/contest/553926#overview
依旧是寄了，菜死的一天。
先放补了的。
G. Path Queries
并查集维护size
反思：赛时看到不大于k就想到点分治然后就误入歧途。中途也有想过离线处理询问，反正最后就是因为签到提耽误了太久，就想快快把这题解决，并没有认真算复杂度，也没有往别的方向考虑。但，他真的就是非常非常简单的数据结构，并查集维护一下就好了，特别特别经典。如果不是在限定环境下感觉还有做出来的可能，但就是心态特别差！反思！
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int n, m, fa[N], sz[N];
pii p[N];
ll ans[N];
struct Node {
int a, b, c;
bool operator<(const Node &t) const {
return c < t.c;
}
}e[N];
int find (int x) {
if (x != fa[x]) fa[x] = find (fa[x]);
return fa[x];
}
ll count (int x) { //size为x的组合中选出多少对点对
return 1ll * x * (x - 1) / 2;
}
int main () {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;
for (int i = 1; i < n; i++) {
int a, b, c;
scanf ("%d%d%d", &a, &b, &c);
e[i] = {a, b, c};
}
sort (e + 1, e + n);
//离线加边
for (int i = 1; i <= m; i++) {
int t;
scanf ("%d", &t);
p[i] = {t, i};
}
sort (p + 1, p + m + 1);
int pos = 1;
ll sum = 0;
for (int i = 1; i <= m; i++) {
int maxn = p[i].first, id = p[i].second;
while (pos < n && e[pos].c <= maxn) {
int a = e[pos].a, b = e[pos].b;
a = find (a), b = find (b);
if (a != b) {
sum += count (sz[a] + sz[b]) - count (sz[a]) - count (sz[b]);
fa[a] = b, sz[b] += sz[a];
}
pos ++;
}
ans[id] = sum;
}
for (int i = 1; i <= m; i++) printf ("%lld ", ans[i]);
}
//离线处理 + 并查集维护size
//从小到大加边
B. Mike and Children
唯一写出的，贪心。但是想了好久。
先两两任意组合然后记录出现次数最大的那个值，直接找有无即可
（其实我不是很确定这么作为什么是对的，就不会严谨的证明，所以绕来绕去想好久）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1005;
int a[N], n, ans;
int main () {
cin >> n;
map<int, int> mp, mp2;
for (int i = 1; i <= n; i++) {
cin >> a[i];
mp2[a[i]] ++;
}
sort (a + 1, a + n + 1);
int cnt = 0, maxn = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int sum = a[i] + a[j];
mp[sum] ++;
if (mp[sum] > cnt) {
cnt = mp[sum], maxn = sum;
}
}
}
//cout << maxn << ' ';
//count maxn
for (int i = 1; i <= n; i++) {
if (mp2[maxn - a[i]]) ans ++;
}
cout << ans / 2;
}
D. Array Splitting
好题，非常妙的贪心。
每次一断就相当于该点后面全累加一边
因为这个累加具有叠加性质,所以只需贪心选最大的k个后缀和即可
注意第一个是一定要选的!!!!(即全局和不要算进去，单独累加)
反思：最初想法————dp!但是数据范围不允许，然后又想着贪心，其实写写画画的时候发现了应该是要考虑区间和之类的，还想着要双指针枚举断点之类的，但是总感觉怪怪的，不太行，因为断点不只有一个。反正也没往前缀和这方面想
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 5;
int n, k, a[N];
ll sum;
int main () {
scanf ("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
vector<ll> v;
for (int i = n; i > 1; i--) sum += a[i], v.push_back (sum);
sort (v.begin (), v.end (), greater<ll>());
sum += a[1];
for (int i = 0; i < k - 1; i++) sum += v[i];
cout << sum;
}
//非常妙的贪心
//每次一断就相当于该点后面全累加一边
//因为这个累加具有叠加性质,所以只需贪心选最大的k个后缀和即可
//注意第一个是一定要选的!!!!(即全局和不要算进去，单独累加)
其它题还有上一场的别的明天再看。
总结
训练少了，做题懈怠了，是大大大大问问题，要反思。这周其实搞大大小小的实验报告啥的很烦，占据太多时间，既然选择了打就好好打，不要每次打不好了才来哭，我个人认为这是很不好的行为（进行一番严厉的自我批判)。一定要从每次的失败中总结教训。还有就是心态问题，两场都出现了我觉得在正常状况下能想出来的，但是赛时思维僵化，扭不过来，这个也是问题。我觉的主要原因就是平常做题太松散，没有限时，营造一个紧张的氛围，拖拖拉拉的做就很不好！
继续加油吧，你还有很多很多东西要学。