这次头有点晕，A题2分钟秒了，B题想法对的，但是头晕一直没把式子写对，纯纯掉分了
A. Max Plus Size
暴力模拟
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<string.h>
#include<string>
#include<math.h>
#include<queue>
#include<bitset>
#include<stack>
#include<algorithm>
#include<deque>
#include<random>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
ll gcd(ll x, ll y)
{if (y == 0)return x;elsereturn gcd(y, x % y);
}
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1)ans *= x;x *= x;y >>= 1;}return ans;
}
void fio()
{ios::sync_with_stdio();cin.tie(0);cout.tie(0);
}
ll a[250000];
int main()
{fio();ll t;cin >> t;while (t--){ll n;cin >> n;for (ll i = 1; i <= n; i++)cin >> a[i];ll k1 = 0, k2 = 0;ll ans = 0, cnt = 0;for (ll i = 1; i <= n; i++){if (i % 2 == 0){ans++; k1 = max(k1, a[i]);}elsecnt++, k2 = max(k2, a[i]);}cout << max(ans + k1, cnt + k2) << endl;}}
B. All Pairs Segments
不难，看懂题意就会了，求正好被扫过某个次数的给定区间数字的个数
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<string.h>
#include<string>
#include<math.h>
#include<queue>
#include<bitset>
#include<stack>
#include<algorithm>
#include<deque>
#include<random>
using namespace std;
typedef long long ll;
mt19937 rnd(time(0));
ll gcd(ll x, ll y)
{if (y == 0)return x;elsereturn gcd(y, x % y);
}
ll ksm(ll x, ll y)
{ll ans = 1;while (y){if (y & 1)ans *= x;x *= x;y >>= 1;}return ans;
}
void fio()
{ios::sync_with_stdio();cin.tie(0);cout.tie(0);
}
ll a[250000];
ll b[250000];
int main()
{fio();ll t;cin >> t;while (t--){ll n, q;cin >> n >> q;for (ll i = 1; i <= n; i++)cin >> a[i];map <ll, ll>f;ll ans = 0;for (ll i = 1; i <= n ; i++){f[n - i + (i - 1) * (n - i + 1)]++;if (i != n){f[i * (n - i)] += a[i+1] - a[i]-1;}}for (ll i = 1; i <= q; i++){cin >> b[i];}for (ll i = 1; i <= q; i++){cout << f[b[i]] << " ";}cout << endl;}}
E. Tree Pruning
直接暴力把所有长度先记录下来，
暴力所有留下长度的可能性，用\(dfs\)往上爬，通过看儿子是否全被标记再考虑是否往上爬，这样子就可以把短的边去掉了
\(Onlog(n)\)
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<string.h>
#include<string>
#include<math.h>
#include<queue>
#include<bitset>
#include<stack>
#include<algorithm>
#include<deque>
#include<random>
using namespace std;
typedef long long ll;
ll ko = 0;
ll faa[500005];
void fio()
{ios::sync_with_stdio();cin.tie(0);cout.tie(0);
}
ll sz[500025];
vector<ll>g[500050];
set<ll>q[500050];
set <ll>f;
ll vis[550000];
ll dfs1(ll x)
{ll cnt = 0;if (x == 1)return 0;if (vis[x]==g[x].size()-1){vis[faa[x]]++;return dfs1(faa[x])+1;}elsereturn 0;
}
void dfs(ll x,ll fa,ll sd)
{sz[x] = 1;q[sd].insert(x);f.insert(sd);faa[x] = fa;for (auto j : g[x]){if (j == fa)continue;dfs(j, x,sd+1);sz[x] += sz[j];}return;
}
int main()
{fio();ll t;cin >> t;while (t--){ll n;cin >> n;f.clear();for (ll i = 1; i <= n; i++){faa[i] = 0;g[i].clear();sz[i] = 0;vis[i] = 0;q[i].clear();}for (ll i = 1; i <= n - 1; i++){ll l, r;cin >> l >> r;g[r].push_back(l);g[l].push_back(r);}dfs(1, 0, 0);for (ll i = 1; i <= n; i++)vis[i] = 0;ll ans = 0;ll u = 9999999999;ll ou = 0;ko = 0;for (auto j : f){ans = 0;if (j != 0){ou = ko;for (auto k : q[j]){ans += sz[k] - 1;if (sz[k] == 1){ko+=dfs1(k);}}u = min(u, ou + ans);}}cout << u << endl;}
}
