这一场比较简单，与普转提的小朋友们一起打的。
签到题，字符串模拟即可。
一个一眼看上去非常贪心的题目，但贪心只能过样例 。本题贪心也可以做，但需要判断负数个数的奇偶性，还有一些细节，哪有直接 d p dp dp 来的快呢？
不难发现，将 a a a 从大到小排序后， A l i c e Alice Alice 选择的数显然是一段区间，所以相当于在一段区间中扣掉几个不连续的数求最大和。显然可以设 f [ i ] f[i] f[i] 为前 i i i 个数中最大和。
转移方程： f [ i ] = m a x ( f [ i − 1 ] , f [ i − 2 ] ) + a [ i ] f[i]=max(f[i-1],f[i-2])+a[i] f[i]=max(f[i−1],f[i−2])+a[i]
初始状态： f [ 1 ] = a [ 1 ] , f [ 2 ] = a [ 1 ] + a [ 2 ] f[1]=a[1],f[2]=a[1]+a[2] f[1]=a[1],f[2]=a[1]+a[2]
目标： f [ n ] f[n] f[n]
考场上没有做出来的一道题。
50 50 50 分：
显然直接枚举 l , r l,r l,r 暴力统计即可。
20 20 20 性质分：
不难观察到对于每一段需要使平均数为整数，每个数要么全是 1 1 1 ，要么全是 2 2 2 。直接找 1 , 2 1,2 1,2 的连续段然后统计即可。
满分：
观察到 a i a_i ai 的取值范围很小，进而想到平均数的范围也很小，所以以平均数 s c o sco sco 作为阶段，考虑平均数等于 s c o sco sco 的区间个数。
套路的，我们对每一个数减去 s c o sco sco 然后计算前缀和，一个区间 [ l , r ] [l,r] [l,r] 的平均数等于 s c o sco sco 当且仅当 s u m [ l − 1 ] = s u m [ r ] sum[l-1]=sum[r] sum[l−1]=sum[r] ，开个桶从头到尾扫一遍即可。
#include<bits/stdc++.h>
using namespace std;
const int INF=10000000;
int n,a[200000],b[200000],t[20000000];
long long ans;
int main()
{freopen("score.in","r",stdin);freopen("score.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=100;i++){for(int j=1;j<=n;j++)b[j]=a[j]-i;t[INF]=1;int sum=0;for(int j=1;j<=n;j++){sum+=b[j];ans+=t[INF+sum];t[INF+sum]++;}t[INF]=0;sum=0;for(int j=1;j<=n;j++){sum+=b[j];t[INF+sum]=0;}}printf("%lld",ans);return 0;
}反思：对于平均数的这个套路有些许生疏了。
性质题。
假设 b 1 b_1 b1 为前缀最大值，那么后面的 b i b_i bi 应为一个类单峰。先单调递减，后单调递增，否则不满足条件。为什么是类单峰？因为如果在后端上升的时候，如果有几个点不满足整体的上升趋势，但是他等于谷底的值，我们可以使他成为前缀最小值，然后给他附一个极大值，从而接受它的“不合群”。
因为我们钦定 b 1 b_1 b1 为前缀最小值，会缺少情况，所以我们再倒着做一遍即可。
一道码农题。
思路很简单，先并查集和必须城市群，然后从大到小慢慢合并，最后群内连边以及群外连边。
考场上 = = = 手误码成了 = = == ==， t o t tot tot 写成了 n n n ，从 100 p t s 100pts 100pts 秒变 35 p t s 35pts 35pts Q A Q quad QAQ QAQ 。
反思：对于码农题，码的时候还是要耐心加细心。
总结：没啥可总结的 ，套路还是得常记，码农最怕不仔细。
这一场难度有所上升，但是总体上还比较简单，同样是与普转提的小盆友们一起打的。
显然的将军饮马，但是考场上审题审错了，以为是 y = k x y=kx y=kx ,调了一个小时，最后才发现审错了。。。
反思：十年 OI 一场空，瞎审题目见祖宗。
题解是二分的做法，考场上我写的离线。
把靶子按左端点排序，之后把询问给离线下来，这道题看似有 A g a i n Again Again ,不能离线，但转念一想只需要记录下哪个靶子就行， A g a i n Again Again 在答案统计时自动就可以判出。
这是之前模拟赛考过的一道题，真的是一眼折半搜索加二分，但是考场上写挂了。。。
不过讲正解之前我想先写点小插曲，考试结束后，这道题我得了八十分，因为写挂了嘛。但是我看见有很多人得到了一百分，我觉得很不合理，因为这道题也不算是特别简单，我是因为做过所以才很快有了思路，当时做这题的时候可把我折磨坏了 ，所以我看了看他们的代码，看完后震惊住了，他们居然 d f s dfs dfs 爆搜过了。
这题 n n n 的范围直接指数级爆搜肯定是过不去的，不过他们都加了一个神奇剪枝：
if(sum+num2[n]-num2[x]<=ans) return ;//a^b>=a当前不符合则说明无论如何xor都不符合。
仔细思考一下，这个剪枝其实相当强大，异或的不确定性直接用加法的确定性排除，再加上排完序后感性理解一下，价值小的一般要选，所以 d f s dfs dfs 的深度优先搜索的优势就被发挥出来了。我们用拍拿正解和这种做法拍了好长时间一直拍不出来 T T T 的数据。
但错解终究是错解，我们决定手动造一组数据来卡掉他。
h a c k hack hack 数据：
36 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 114514 1919810 54188 12345678 10086 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 1000000000 36,1\ 2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536\131072,262144,524288,1048576 ,2097152,4194304,8388608,16777216\33554432,67108864,134217728,268435456,536870912,114514,1919810 ,54188\12345678,10086,1\ 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35, 1000000000 361248163264128256512102420484096819216384327686553613107226214452428810485762097152419430483886081677721633554432671088641342177282684354565368709121145141919810541881234567810086112345678910111213141516171819202122232425262728293031323334351000000000
构造思路:
考虑到深度优先搜索的优先性，我们把可行的答案放在最后，使其难以搜到。为了前面不被最优化剪枝减掉，我们把大小设为 2 2 2 的整次幂，这样保证了选取的全面性，这样就卡掉了 d f s dfs dfs 。
顺便一提，这题本来有一个随机化的做法，每次随机整个排列，直接选取前几个来更新答案，感性理解一下因为 n n n 很小，所以概率非常大。但是这组数据顺便也把随机化给卡掉了，可能是因为满足这个答案的情况比较少吧。
好了终于到正解了：
观察数据范围 n ≤ 36 nle36 n≤36,这个数据范围很小，但偏偏要比一般搜索大，那么考虑折半搜索。思考如何把中间的答案合并，因为是异或，自然而然的想到 01 t r i e 01trie 01trie 树，考虑把一半答案插入 t r i e trie trie 树中，并递归求解 m a x max max 数组。对于另一半答案，按位枚举，如果 m m m 当前位为 0 0 0 ，那么 t r i e trie trie 树上只能跳转与 a n s ans ans 当前位相同的 t r i e trie trie 树节点；如果 m m m 当前位为 1 1 1 ，那么 t r i e trie trie 树上跳与 a n s ans ans 相同的节点一定合法，直接用 m a x max max 数组更新。然后考虑跳与 a n s ans ans 当前位相反的 t r i e trie trie 树节点。如果跳的过程中该节点不存在，则直接返回。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[50],b[50],trie[6000000][2],tot;
long long maxx[6000000],ans,en[6000000];
void insert(int x,long long y)
{int p=0;for(int i=31;~i;i--){int now=(x>>i)&1;if(!trie[p][now])trie[p][now]=++tot;p=trie[p][now];maxx[p]=max(maxx[p],y);}en[p]=max(en[p],y);
}
long long ask(int x)
{int p=0;long long las=-1e18;for(int i=31;~i;i--){int p1=(x>>i)&1,p2=(m>>i)&1;if(!p1){if(!p2){if(!trie[p][0])return las;p=trie[p][0];}else{if(trie[p][0])las=max(las,maxx[trie[p][0]]);if(!trie[p][1])return las;p=trie[p][1];}}else{if(!p2){if(!trie[p][1])return las;p=trie[p][1];}else{if(trie[p][1])las=max(las,maxx[trie[p][1]]);if(!trie[p][0])return las;p=trie[p][0];}}}return max(las,en[p]);
}
void dfs1(int x,int y,long long z)
{if(x==n/2){insert(y,z);return;}dfs1(x+1,y^a[x+1],z+b[x+1]);dfs1(x+1,y,z);
}
void dfs2(int x,int y,long long z)
{if(x==n){ans=max(ans,ask(y)+z);return;}dfs2(x+1,y^a[x+1],z+b[x+1]);dfs2(x+1,y,z);
}
void solve()
{dfs1(0,0,0);dfs2(n/2,0,0);
}
int main()
{freopen("shop.in","r",stdin);freopen("shop.out","w",stdout);scanf("%d%d",&n,&m);memset(maxx,0xcf,sizeof maxx);memset(en,0xcf,sizeof en);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++)scanf("%d",&b[i]);solve();printf("%lld",ans);return 0;
}这是一道博弈论，因为没学过所以做起来很恶心，不过也不是完全不可做。
观察到状态只与层数有关，也就是说可能的状态只有 3 n 3^n 3n 种，可以直接 d f s dfs dfs 枚举。对于博弈论的部分，思考如果是叶子结点，那么判断是谁以及当前状态的奇偶性从而判断胜负，对于非叶子结点，如果存在状态后手必败，那么显然可以先手必胜，否则先手必败。
算一下时间复杂度，对于第i层的点，会dp n-i次，这一层有2^i个点
复杂度 O ( ∑ i = 1 n 2 i ∗ 3 n − i ) O(sumlimits _{i=1}^n 2^i*3^{n-i}) O(i=1∑n2i∗3n−i)。
#include<bits/stdc++.h>
using namespace std;
int n,l[33000],r[33000],c[33000];
vector<int> q;
bool dfs(vector<int> x,bool dep,bool num)
{bool flag=num;for(int i=0;i<x.size();i++)flag^=c[x[i]];vector<int> cc;cc.clear();if(l[x[0]]){for(int i=0;i<x.size();i++)cc.push_back(l[x[i]]);if(!dfs(cc,dep^1,flag))return 1;cc.clear();for(int i=0;i<x.size();i++)cc.push_back(r[x[i]]);if(!dfs(cc,dep^1,flag))return 1;for(int i=0;i<x.size();i++)cc.push_back(l[x[i]]);if(!dfs(cc,dep^1,flag))return 1;return 0;}else{if(!flag&&!dep||flag&&dep)return 0;return 1;}
}
int main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d%d%d",&l[i],&r[i],&c[i]);for(int i=1;i<=n;i++){q.clear();q.push_back(i);if(dfs(q,1,0))puts("Alice");elseputs("Bob");}return 0;
}暴力很好写，直接模拟即可。暴力之后打表可以发现这个排列的变化是有循环元的，所以考虑对于每一个位置，把他的变化建环，先算出循环元 s s s ，然后每一个位置考虑 m m o d s m,mod,s mmods，直接计算位置即可。
正解：
上面的做法时间复杂度是 O ( n l g m ) O(nlgm) O(nlgm)，不足以通过此题，但是对于大小相同的环，走几步最后的落脚点是一样的，所有环的大小之和为 n n n ，所以环的种类只有 n sqrt n n 种 这样时间复杂度就被优化到了 O ( n l g m ) O(sqrt nlgm) O(n lgm) 但仍不足以通过本题，不过我们对于高精数 m m m 的存储没有必要按位存储，直接每 17 17 17 位用一个 l o n g l o n g long,long longlong 存储，这样复杂度就变为了 O ( n ⋅ l g m 17 ) O(sqrt n cdotfrac{lgm}{17}) O(n ⋅17lgm) 足以通过本题。
#include<bits/stdc++.h>
using namespace std;
int n,a[1000100],c[1000100],tot,nn,f[1000100],now,id[1000100],bignum;
char s[1000100];
vector<int> q[1000100];
__int128 num[1000100];
int ksm(int x,int y,int z)
{int ans=1;while(y){if(y&1)ans=((long long)ans*x)%z;x=(long long)x*x%z;y>>=1;}return ans%z;
}
int Mod(int x)
{int ff=0,lx=1;bignum=ksm(10,36,x);for(int i=1;i<=now;i++){ff=(ff+num[i]%x*lx%x)%x;lx=(long long)lx*bignum%x;}return ff;
}
int main()
{freopen("pow.in","r",stdin);freopen("pow.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=1;i<=n;i++){if(c[a[i]])continue;int jl=a[a[i]],js=0;c[a[i]]=++tot;id[a[i]]=0;q[tot].push_back(a[i]);while(jl!=a[i]){c[jl]=tot;id[jl]=++js;q[tot].push_back(jl);jl=a[jl];}}scanf("%s",s+1);nn=strlen(s+1);for(int i=nn;i>0;i-=36){__int128 jl=0;for(int j=max(i-35,1);j<=i;j++)jl=jl*10+s[j]-'0';num[++now]=jl;}for(int i=1;i<=n;i++){if(f[q[c[a[i]]].size()]){if(id[a[i]]+f[q[c[a[i]]].size()]>q[c[a[i]]].size())printf("%d ",q[c[a[i]]][id[a[i]]+f[q[c[a[i]]].size()]-q[c[a[i]]].size()-1]);elseprintf("%d ",q[c[a[i]]][id[a[i]]+f[q[c[a[i]]].size()]-1]);}else{int ys=Mod(q[c[a[i]]].size());if(!ys)ys=q[c[a[i]]].size();f[q[c[a[i]]].size()]=ys;if(id[a[i]]+f[q[c[a[i]]].size()]>q[c[a[i]]].size())printf("%d ",q[c[a[i]]][id[a[i]]+f[q[c[a[i]]].size()]-q[c[a[i]]].size()-1]);elseprintf("%d ",q[c[a[i]]][id[a[i]]+f[q[c[a[i]]].size()]-1]);}}return 0;
}
总结：
这场考试时间分配严重失衡，大部分时间都放在了前三题，第三题还写挂了，还是得多注意时间。博弈论也要涉足一些了，高精不太熟练了，导致考场上都不太敢码。
这一场是多校联考，难度明显上升。
签到题，倒序模拟即可。
首先这题不管怎么样都得先做一遍最大点独立集。考试的时候没有往正解方向去想，光想着怎么当暴力哥了。最后码了个 32 p t s 32pts 32pts 的基环树（我真的很喜欢在考场上码一些我没写过的算法，嗯）。搞笑的是最后因为码的太丑，常数太大，只拿了 8 p t s 8pts 8pts。。。
正解：
思考到当且仅当两个必选点连边是不合法的，考虑如何算出必选点的点集。我们再来看一下最大点独立集的转移方程，其实救赎之道就在其中
f [ i ] [ 0 ] = ∑ j ∈ s o n [ i ] m a x ( f [ j ] [ 0 ] , f [ j ] [ 1 ] ) f[i][0]=sumlimits_{jin son[i]}max(f[j][0],f[j][1]) f[i][0]=j∈son[i]∑max(f[j][0],f[j][1])
f [ i ] [ 1 ] = ∑ j ∈ s o n [ i ] f [ j ] [ 0 ] f[i][1]=sumlimits_{jin son[i]}f[j][0] f[i][1]=j∈son[i]∑f[j][0]
如果 i i i 为必选点，那么 j j j 根据方程为必不选点。
如果 i i i 为必不选点，因为要保证最优性，那么 j j j 为 { 必选点 i f f [ j ] [ 0 ] < f [ j ] [ 1 ] 必不选点 i f f [ j ] [ 0 ] > f [ j ] [ 1 ] 无所谓点 i f f [ j ] [ 0 ] = f [ j ] [ 1 ] begin{cases}必选点&if,f[j][0]<f[j][1]\必不选点&if,f[j][0]>f[j][1]\无所谓点&if,f[j][0]=f[j][1]end{cases} ⎩ ⎨ ⎧必选点必不选点无所谓点iff[j][0]<f[j][1]iff[j][0]>f[j][1]iff[j][0]=f[j][1]
如果 i i i 为无所谓点，那么 j j j 为 { 必不选点 i f f [ j ] [ 0 ] > f [ j ] [ 1 ] 无所谓点 i f f [ j ] [ 0 ] ≤ f [ j ] [ 1 ] begin{cases}必不选点&if,f[j][0]>f[j][1]\无所谓点&if,f[j][0]le f[j][1]end{cases} {必不选点无所谓点iff[j][0]>f[j][1]iff[j][0]≤f[j][1]
初始状态 1 1 1 想像其虚拟父亲为必不选点来做即可。
#include<bits/stdc++.h>
using namespace std;
int n,head[300000],tot,f[300000][2],flag[300000],sum;
struct node
{int to,nex;
} edge[600000];
void add(int x,int y)
{edge[++tot].nex=head[x];edge[tot].to=y;head[x]=tot;
}
void dfs1(int x,int fa)
{f[x][1]=1;for(int i=head[x];i;i=edge[i].nex){if(edge[i].to==fa)continue;dfs1(edge[i].to,x);f[x][0]+=max(f[edge[i].to][0],f[edge[i].to][1]);f[x][1]+=f[edge[i].to][0];}
}
void dfs2(int x,int fa)
{for(int i=head[x];i;i=edge[i].nex){if(edge[i].to==fa)continue;if(flag[x]==1){if(f[edge[i].to][0]>f[edge[i].to][1])flag[edge[i].to]=1;else if(f[edge[i].to][0]<f[edge[i].to][1]){flag[edge[i].to]=2;sum++;}elseflag[edge[i].to]=3;}else if(flag[x]==2)flag[edge[i].to]=1;else{if(f[edge[i].to][0]>f[edge[i].to][1])flag[edge[i].to]=1;elseflag[edge[i].to]=3;}dfs2(edge[i].to,x);}
}
int main()
{freopen("road.in","r",stdin);freopen("road.out","w",stdout);scanf("%d",&n);for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);add(u,v);add(v,u);}dfs1(1,0);if(f[1][0]>f[1][1])flag[1]=1;else if(f[1][0]<f[1][1]){flag[1]=2;sum++;}elseflag[1]=3;dfs2(1,0);printf("%lld",(long long)n*(n-1)/2-(long long)sum*(sum-1)/2);return 0;
}反思：考试的时候没有注意到这题的可做性，直接莽没有写过的算法，很不正确。对于把点分状态没有想到无所谓点如何处理，还得多加思考。
这题暴力是直接 d p dp dp，设 f [ i ] [ j ] f[i][j] f[i][j] 表示对于前 i i i 个字符，把第 i i i 个字符改成 j j j 所需的最小代价。
显然有 f [ i ] [ j ] = min k = ∣ a ∣ j f [ i − 1 ] [ k ] + ∣ j − k ∣ f[i][j]=minlimits_{k=left|aright|}^{j}f[i-1][k]+left|j-kright| f[i][j]=k=∣a∣minjf[i−1][k]+∣j−k∣
对于 52 p t s 52pts 52pts 其实我们可以换一种思路，因为他具有修改与查询操作，考虑线段树。但是我们现在设的状态并不适合线段树这种维护区间的数据结构，改一下，设 n u m [ i ] [ j ] num[i][j] num[i][j] 表示左端点为 i i i ，右端点为 j j j 的最小花费，这样子线段树直接暴力维护即可。
复杂度 O ( q l o g n ⋅ 5 4 ) O(q,log,ncdot 5^4) O(qlogn⋅54)
55 p t s 55pts 55pts 直接把暴力和线段树一分段即可。
#include<bits/stdc++.h>
using namespace std;
int q,id,f[100010][30],ans=0x3f3f3f3f,n;
char s[200000],c;
struct node
{int l,r,num[5][5];
} tree[400000];
void build(int p,int l,int r)
{tree[p].l=l;tree[p].r=r;if(l==r){for(int i=0;i<5;i++)for(int j=i;j<5;j++)tree[p].num[i][j]=0x3f3f3f3f;for(int i=0;i<5;i++)tree[p].num[i][i]=abs(s[l]-'a'-i);return;}int mid=(l+r)/2;build(2*p,l,mid);build(2*p+1,mid+1,r);for(int i=0;i<5;i++)for(int j=i;j<5;j++)tree[p].num[i][j]=0x3f3f3f3f;for(int i=0;i<5;i++){for(int j=i;j<5;j++){for(int k=j;k<5;k++){for(int a=k;a<5;a++)tree[p].num[i][a]=min(tree[p].num[i][a],tree[2*p].num[i][j]+tree[2*p+1].num[k][a]);}}}
}
void change(int p,int x,char y)
{if(tree[p].l==tree[p].r){for(int i=0;i<5;i++)for(int j=i;j<5;j++)tree[p].num[i][j]=0x3f3f3f3f;for(int i=0;i<5;i++)tree[p].num[i][i]=abs(y-'a'-i);return;}int mid=(tree[p].l+tree[p].r)/2;if(x<=mid)change(2*p,x,y);elsechange(2*p+1,x,y);for(int i=0;i<5;i++)for(int j=i;j<5;j++)tree[p].num[i][j]=0x3f3f3f3f;for(int i=0;i<5;i++){for(int j=i;j<5;j++){for(int k=j;k<5;k++){for(int a=k;a<5;a++)tree[p].num[i][a]=min(tree[p].num[i][a],tree[2*p].num[i][j]+tree[2*p+1].num[k][a]);}}}
}
int ask()
{int jl=0x3f3f3f3f;for(int i=0;i<5;i++)for(int j=i;j<5;j++)jl=min(jl,tree[1].num[i][j]);return jl;
}
int main()
{freopen("lock.in","r",stdin);freopen("lock.out","w",stdout);scanf("%s%d",s+1,&q);n=strlen(s+1);if(q<=10){memset(f,0x3f,sizeof f);f[0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<26;j++){for(int k=0;k<=j;k++)f[i][j]=min(f[i][j],f[i-1][k]+abs(s[i]-'a'-j));if(i==n)ans=min(ans,f[i][j]);}}printf("%dn",ans);while(q--){scanf("%d %c",&id,&c);// cout<<id<<' '<<c<<endl;s[id]=c;memset(f,0x3f,sizeof f);f[0][0]=0;ans=0x3f3f3f3f;for(int i=1;i<=n;i++){for(int j=0;j<26;j++){for(int k=0;k<=j;k++)f[i][j]=min(f[i][j],f[i-1][k]+abs(s[i]-'a'-j));if(i==n)ans=min(ans,f[i][j]);}}printf("%dn",ans);}}else{build(1,1,n);printf("%dn",ask());while(q--){scanf("%d %c",&id,&c);change(1,id,c);printf("%dn",ask());}}return 0;
}对于正解，是把字符串拆成 26 26 26 个 01 01 01 串进行求解，但是证明过程没有怎么看懂，感觉思路也不咋常用，先当一个坑吧。
考试时连暴力都没有写，现在重新看来随便瞎搞搞应该就能拿暴力分了。
正解是双指针加启发式合并，目前没啥订的欲望，先当做一个坑吧。
总结：这场比赛总体打的比较自闭，没有做出来 T 2 T2 T2 体验感非常差。调了大半小时的基环树还因为常数寄掉了。
这是目前的最后一场比赛了，好像是最难的，也是最自闭的。
二分加优先队列。
这题本质上不算是啥大难题，但是相比于其他的 T 1 T1 T1 也算是比较难了，考场上完全没有往二分上想是不应该的。想着直接 n 2 n^2 n2 贪心瞎搞搞还是寄掉了。
具体做法上没啥可总结的，思路上。。谨防贪心陷阱。
这题没有写出来暴力是本场最大的失误。开始觉得题面很复杂，直接写了指数级的暴力，然后把时间直接全部砸在了其他题上，最后一分没有。
这题的暴力其实在我想出指数级暴力的时候就应该想到了。对于每一条边的删除实际上是相互独立的。那么我们完全可以把 m m m 当成容量， s i z e u size_u sizeu 当成体积， s i z e u × ( n − s i z e u ) × l e n [ u ] [ f a u ] size_utimes(n-size_u)times len[u][fa_u] sizeu×(n−sizeu)×len[u][fau] 当成价值，跑一遍 01 01 01 背包即可。
对于正解，考虑到树是随机的 ∑ s i z e [ x ] = O ( n l o g n ) sum size[x]=O(n,log,n) ∑size[x]=O(nlogn)，故只有最多 n l o g n sqrt {nlogn} nlogn 种不同的 s i z e x size_x sizex 所以跑二进制优化或者单调队列优化的多重背包即可。
#include<bits/stdc++.h>
using namespace std;
int n,m,head[200000],tot,now;
long long size[200000],V[200000],a[200000],f[600000],sum,maxx,cv[200000],ca[200000],c[200000];
map<pair<long long,long long>,int> q;
struct node
{int to,nex,v;
} edge[500000];
void add(int x,int y,int z)
{edge[++tot].nex=head[x];edge[tot].to=y;edge[tot].v=z;head[x]=tot;
}
void dfs(int x,int fa)
{size[x]=1;for(int i=head[x];i;i=edge[i].nex){if(edge[i].to==fa)continue;dfs(edge[i].to,x);if(q.find(make_pair(size[edge[i].to],size[edge[i].to]*(n-size[edge[i].to])*edge[i].v))=&#d()){V[++tot]=size[edge[i].to];a[tot]=size[edge[i].to]*(n-size[edge[i].to])*edge[i].v;c[tot]=1;q[make_pair(size[edge[i].to],size[edge[i].to]*(n-size[edge[i].to])*edge[i].v)]=tot;}elsec[q[make_pair(size[edge[i].to],size[edge[i].to]*(n-size[edge[i].to])*edge[i].v)]]++;sum+=size[edge[i].to]*(n-size[edge[i].to])*edge[i].v;size[x]+=size[edge[i].to];}
}
int main()
{freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);}tot=0;dfs(1,0);for(int i=1;i<=tot;i++){long long lx=1;while(c[i]>lx){c[i]-=lx;cv[++now]=lx*V[i];ca[now]=lx*a[i];lx*=2;}cv[++now]=c[i]*V[i];ca[now]=c[i]*a[i];}for(int i=1;i<=now;i++){for(int j=m;j>=cv[i];j--)f[j]=max(f[j],f[j-cv[i]]+ca[i]);}for(int i=0;i<=m;i++)maxx=max(maxx,f[i]);printf("%lld",sum-maxx);return 0;
}反思：对于背包的敏感度一直比较低，还是得多加练习。
暴力是一个简单的区间 d p dp dp 。
对于正解是对这个区间 d p dp dp 找性质进行疯狂的优化，差不多听懂讲解了，但暂时还不太想订。
正解是线段树分治加可持久化并查集。emm 都是我不太熟练的算法，还是先放放吧。
总结：要有一颗能发现突破点的双眼，不能因为哪个题面简单就单纯的把他当成突破口，说不定哪天考场上就又被坑了。
本文发布于:2024-03-08 22:29:37，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/1710122394133373.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
