嗯，总之，是我太傻了。
我真傻，真的，我单知道最小生成树，却不知道还有最大生成树
T1
最大生成树....
累加每一个环内，最大生成树的边权，（对环求最大生成树，则必然剩下一个边权最小的边（因为是求生成树，所以这个边肯定不会被算上））
然后因为对于不同联通块，跑最大生成树，彼此之间依旧无法有想连接的边，所以对于森林跑最大生成树是没有问题的
最后所有边的边权和 减去 所有联通块的最大生成树的边权和 即可得到答案
最小生成树性质之一：最大边权最小
最大生成树性质之一：最小边权最大
最后是吐槽：我写了4kb的dfs，疯狂地dfs,使用各种奇奇怪怪的操作，并且计算的复杂度是允许的！最后好不容易调过了样例
最后因为数组开的太大，直接MLE，连正确性都不知道....
AC代码如下：
#include<bits/stdc++.h>
#define uint unsigned int
using namespace std;
const int maxn = ;
const int maxm = ;
struct shiki {
int x, y;
double val;
}e[maxm << ];
struct enkidu {
int x, y;
}a[maxn];
int lin[maxn], len = ;
int fa[maxn];
double num, need;
int n, m; inline int read() {
int x = , y = ;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') y =-;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << ) + (x << ) + ch - '';
ch = getchar();
}
return x * y;
} inline bool cmp(shiki x, shiki y) {
return x.val > y.val;} inline double dis_val(int x, int y) {
int x1 = a[x].x, y1 = a[x].y, x2 = a[y].x, y2 = a[y].y;
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
} int getfather(int x) {
if(x == fa[x]) return x;
return fa[x] = getfather(fa[x]);
} int main() {
// freopen("plan.in", "r", stdin);
// freopen("plan.out", "w", stdout);
n = read(), m = read();
for(register uint i = ; i <= n; ++i)
a[i].x = read(), a[i].y = read();
for(register uint i = ; i <= m; ++i) {
e[i].x = read(), e[i].y = read();
e[i].val = dis_val(e[i].x, e[i].y);
}
for(register uint i = ; i <= n; ++i) fa[i] = i;
sort(e + , e + m + , cmp);
for(register uint i = ; i <= m; ++i) {
int u = getfather(e[i].x);
int v = getfather(e[i].y);
num += sqrt(e[i].val);
if(u == v) continue;
fa[u] = v;
need += sqrt(e[i].val);
}
printf("%0.9lf", num - need);
// fclose(stdin);
// fclose(stdout);
return ;
}
T2
我T1为了完成sb的4kb的超暴力搜索，花费了差不多2个小时的时间，然后看到这道题后，我一眼以为是一个博弈论...
然后我又想了想，觉得自己的题意好像出锅了....
然后就按照贪心思想完成了一个dfs，最后贪心顺利骗到10分...
Dp
题意：
最优策略指：差值最大
因为我们在某个位置选或是不选由[i+1, i+m]中的状态推导来的，也就是说，我们要保证下一个人取得是最优策略。
但是我们正序进行的话，我们无法保证当前状态是最优策略，所以我们倒序进行
划分阶段：
以进行每个点i为阶段
f[i]表示，在当前回合，选择数ai时，所能得到的最大得分
添加状态
正常操作：
f[i][0]表示到第i个数时，该棋子为大魔王选时，你的得分减去大魔王的得分
f[i][1]表示到第i个数时，该棋子为你选时，你的得分减去大魔王的得分
f[i][0] = max{f[k][1]} - a[i]
f[i][1] = min{f[k][0]} + a[i]
也就是说要维护f[k][1]和f[k][0]在[i-m, i-1]的单调性
倒序与第一题一样
优化1：空间优化
假定第ai个数必须取，f[i]表示若选择一定选择第ai个数，当前的人和对方的最大差值
因为每个人都取最优策略，所以选择第ai个数我们能够得到的分数是
f[i] = ai - max{f[j]}(j ∈ [i+1, i+m])
可得方程f[i] = ai - max{f[j]}(j ∈ [i+1, i+m])
因为f[j]是对方的最大差值，我们选择了a[i]，则我们要计算自己的得分，就要用a[i] - max{f[j]}
优化2：时间优化：
(1)单调队列维护单调性：好写，代码量小
(2)线段树取区间最大值，正常操作，显然
#include<bits/stdc++.h>
#define uint unsigned int
#define ll long long
using namespace std;
const int maxn = ;
int q[maxn];
int f[maxn];
int n, m;
int a[maxn];
int l = , r = ;
int ans = -; inline int read() {
int x = , y = ;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') y = -;
ch = getchar();
}
while(isdigit(ch)) {
x = (x << ) + (x << ) + ch - '';
ch = getchar();
}
return x * y;
} int main() {
// freopen("game.in", "r", stdin);
// freopen("game.out", "w", stdout);
n = read(), m = read();
for(register uint i = ; i <= n; ++i) a[i] = read();
f[n] = a[n];
q[++r] = n;
for(register uint i = n - ; i >= ; --i) {
while(l <= r && q[l] > i + m) l++;
f[i] = a[i] - f[q[l]];
while(l <= r && f[q[r]] < f[i]) r--;
q[++r] = i;
}
for(register uint i = ; i <= m; ++i)
ans = max(ans, f[i]);
cout << ans << '\n' << -ans << '\n';
// fclose(stdin);
// fclose(stdout);
return ;
}
T3
不得不说，样例就是sb，我最初以为是只能从根节点出发
然后我就写了个树Dp的暴力，然后就爆0了
后来才知道，是求的直径.....
暴力思路：
对于每一次询问，都手动封点，求树的直径
能拿50%的分
正解思路：不会，回来补吧....