Day1
T1
其实就是要问最多可以用银币买多少，那么把所有的按银币价格排序，买最小的那些，想都没想就冲了个树上莫队+分块，但是可以直接树上主席树做到一个log。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll in(){
ll x;
scanf("%lld",&x);
return x;
}
const int N=2e5+5;
int n,m,q;
int lst[N],to[N],nxt[N],pos[N],ec=1;
inline void ae(int x,int y){
to[++ec]=y,nxt[ec]=lst[x],lst[x]=ec;
}
int dfn1[N],dfn2[N],dfp[N],tot;
void dfs(int x,int fa){
dfn1[x]=++tot,dfp[tot]=x;
for(int i=lst[x];i;i=nxt[i]){
int y=to[i];
if(y==fa)continue;
pos[i>>1]=y;
dfs(y,x);
}
dfn2[x]=++tot,dfp[tot]=x;
}
int px[N],pc[N],num[N];
vector<int> v[N];
int sz[N],bl[N];
const int B=511;
struct qes{
int l,r,id;
}qe[N];
int qx[N];
ll qy[N];
inline bool cmp(const qes &a,const qes &b){
if(bl[a.l]==bl[b.l])return bl[a.l]&1?a.r<b.r:a.r>b.r;
return bl[a.l]<bl[b.l];
}
int all;
ll v0[N],v1[N],v2[N],v3[N];
void add(int p,int v){
int bl=p/B;all+=v;
v0[p]+=v,v1[bl]+=v;
v2[p]+=num[p]*v,v3[bl]+=num[p]*v;
}
int query(ll v){
if(!v)return 0;
int lim=m/B,res=0,p=lim+1;
for(int i=0;i<=lim;i++){
if(v3[i]>=v){p=i;break;}
v-=v3[i],res+=v1[i];
}
if(p>lim)return res;
for(int i=B*p;i<=m;i++){
if(v2[i]>=v)return res+(v/num[i]);
v-=v2[i],res+=v0[i];
}
assert(0);
return 0;
}
bool mark[N];
void upd(int x){
x=dfp[x];
for(int i:v[x]){
add(i,mark[x]?-1:1);
}
mark[x]^=1;
}
int ans[N];
int main(){
n=in(),m=in(),q=in();
for(int i=1;i<n;i++){
int x=in(),y=in();
ae(x,y),ae(y,x);
}
dfs(1,0);
for(int i=1;i<=m;i++){
px[i]=in(),pc[i]=num[i]=in();
}
sort(num+1,num+m+1);
for(int i=1;i<=m;i++){
pc[i]=lower_bound(num+1,num+m+1,pc[i])-num;
v[pos[px[i]]].push_back(pc[i]);
}
for(int i=1,now=0,tot=1;i<=n<<1;i++){
if(now+v[dfp[i]].size()<=B)now+=v[dfp[i]].size();
else now=v[dfp[i]].size(),tot++;
bl[i]=tot;
}
for(int i=1;i<=q;i++){
int x=in(),y=in();
if(dfn1[x]>dfn1[y])swap(x,y);
if(dfn2[x]>dfn2[y])x=dfn1[x]+1,y=dfn1[y];
else x=dfn2[x],y=dfn1[y];
qe[i]=(qes){x,y,i};
qx[i]=in(),qy[i]=in();
}
sort(qe+1,qe+q+1,cmp);
int L=1,R=0;
for(int i=1;i<=q;i++){
int l=qe[i].l,r=qe[i].r,id=qe[i].id;
while(R<r)upd(++R);
while(L>l)upd(--L);
while(R>r)upd(R--);
while(L<l)upd(L++);
ans[id]=all-query(qy[id]);
}
for(int i=1;i<=q;i++){
printf("%d\n",max(-1,qx[i]-ans[i]));
}
return 0;
}
T2
不会满分做法，场上花了 2 个小时搞了个三方的dp。
考虑从左往右一个一个填，每个位置有填l和填r两种选择，而且填r时要考虑和它配对的是前面的哪个l。 然后现在又有两种取法：一种是每次取能取的最小 l，一种是取能取的最小 r。在从左往右填的时候，如果我们填了一个r，考虑它配对的l，如果这个 l 恰好是当前最小的l，那么第一种取法的段数加一，如果这个 l 在上一次的 r 之后，第二种取法的段数加一。并且可以发现，如果某一时刻取法二的段数大于取法一的段数加一，那么最后它们的段数肯定不相等。于是我们可以设出状态：
\(f_{i,j,k,0/1/2,0/1}\) 前 \(i\) 个位置，填了 \(j\) 个 r，能与取法二匹配的 l 有 \(k\) 个，与取法一匹配的 l 没有/有一个且不能匹配取法二/有一个且能匹配取法二，取法二的段数比取法一多 0/1。然后转移是 O(1) 的，就获得了一个三方 dp。
#include<bits/stdc++.h>
using namespace std;
const int N=2e4+5;
int n,mod;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline void Add(int &a,int b){a+=b;if(a>=mod)a-=mod;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
namespace solve1{
int l[10],r[10],ans,cnt;
int calc1(){
int now=0,res=0;
for(int i=1;i<=n;i++){
if(l[i]>now)now=r[i],res++;
}
return res;
}
int calc2(){
int now=0,res=0;
for(int i=1;i<=n;i++){
int mn=n<<1|1;
for(int j=1;j<=n;j++){
if(l[j]>now)mn=min(mn,r[j]);
}
if(mn>n<<1)break;
now=mn,res++;
}
return res;
}
void dfs(int x,int y){
if(x-1==n<<1){
if(y!=n)return;
cnt++;
if(calc1()<calc2())ans++;
return;
}
if(y<n){
l[y+1]=x;
dfs(x+1,y+1);
l[y+1]=0;
}
for(int i=1;i<=y;i++){
if(!r[i]){
r[i]=x;
dfs(x+1,y);
r[i]=0;
}
}
}
void main(){
if(n>8)return;
dfs(1,0);
cout<<cnt<<endl;
cout<<ans%mod<<endl;
exit(0);
}
}
namespace solve2{
const int N=305;
int f[2][N][N][3][2],c;
void dp(int i){
int d=c^1;
for(int j=0;j<<1<=i;j++){
for(int k=0;k<=i-j;k++){
for(int x=0;x<3;x++){
for(int y=0;y<2;y++){
if(!f[c][j][k][x][y])continue;
int val=f[c][j][k][x][y];
f[c][j][k][x][y]=0;
Add(f[d][j][k+1][x==0?2:x][y],val);//填l
Add(f[d][j+1][k+1][x][y],mul(val,i-j-k-(x==1)));//填无用r
if(x==1)Add(f[d][j+1][k][0][y-1],val);//填一类r(ans1++)
if(y==0)Add(f[d][j+1][0][x==2?1:x][y+1],mul(val,k-(x==2)));//填二类r(ans2++)
if(x==2)Add(f[d][j+1][0][0][y],val);//填三类r(ans1++,ans2++)
}
}
}
}
}
void main(){
if(n>300)return;
int all=1;
for(int i=1;i<=n<<1;i+=2)all=mul(all,i);
f[0][0][0][0][0]=1;c=0;
for(int i=0;i<n<<1;i++)dp(i),c^=1;
int ans=0;
for(int k=0;k<=n;k++)
for(int x=0;x<3;x++){
Add(ans,f[c][n][k][x][0]);
}
cout<<add(all,mod-ans)<<endl;
exit(0);
}
}
int main(){
cin>>n>>mod;
solve1::main();
solve2::main();
return 0;
}
T3
先考虑一个简单的情况：如果所有区间都互不包含。在这个情况下，向左和向右的是各自独立的，所以我们只需要分别计算向左走到1和向右走到n各需要多少步。以向左为例，我们把区间按照左端点递增排序，记 \(f_i\) 为区间 i 走到 1 所需步数，那么我们转移就是 \(f_i=\min_{j=l_i}^{r_i} f_j+1\)。然后可以用个线段树维护dp。
再来考虑区间包含的情况，在这个情况下，我们可以从一个区间向左/向右走到一个包含它的区间然后再走到1和n。然后这个东西我们可以建图：区间 i 向所有包含 i 的去加连边，然后跑最短路更新。这一步要用到线段树优化建图。
仔细想想，这道题其实本质就是我们建图，从区间 i 可以走到所有区间内的点，然后我们要求 区间 i 走到 1和n 的最小路径并。然后我们就先求出每个点直接走到 1,n 的步数，然后再来更新其他点。
实现上我们需要一个线段树 dp，线段树优化建图然后跑 bfs，总复杂度 O(n)。
#include<bits/stdc++.h>
using namespace std;
inline int in(){
int x;
scanf("%d",&x);
return x;
}
const int N=2e5+5,inf=1e9;
int n,q;
struct node{
int l,r,id;
}a[N];
int fl[N],fr[N];
namespace seg1{
int val[N<<2];
void build(int p,int l,int r){
val[p]=inf;
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void modify(int p,int l,int r,int d,int v){
val[p]=min(val[p],v);
if(l==r)return;
int mid=l+r>>1;
if(d<=mid)modify(p<<1,l,mid,d,v);
else modify(p<<1|1,mid+1,r,d,v);
}
int query(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return val[p];
int mid=l+r>>1,res=inf;
if(ql<=mid)res=query(p<<1,l,mid,ql,qr);
if(mid<qr)res=min(res,query(p<<1|1,mid+1,r,ql,qr));
return res;
}
}
int lst[N<<2],to[N*50],nxt[N*50],ec;
inline void ae(int x,int y){
to[++ec]=y,nxt[ec]=lst[x],lst[x]=ec;
}
int dis[N*20];
namespace seg2{
void build(int p,int l,int r){
if(l==r){
ae(l,p+n);
return;
}
int mid=l+r>>1;
build(p<<1,l,mid),build(p<<1|1,mid+1,r);
ae((p<<1)+n,p+n),ae((p<<1|1)+n,p+n);
}
void update(int p,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr){
ae(p+n,x);
return;
}
int mid=l+r>>1;
if(ql<=mid)update(p<<1,l,mid,ql,qr,x);
if(mid<qr)update(p<<1|1,mid+1,r,ql,qr,x);
}
}
vector<int> v[N];
void bfs(){
deque<int> q;
for(int i=1;i<=n;i++)if(dis[i]<=n)v[dis[i]].push_back(i);
for(int d=0;d<=n;d++){
for(int x:v[d])if(dis[x]==d)q.push_front(x);
while(q.size()){
int x=q.front();if(dis[x]!=d)break;
q.pop_front();
for(int i=lst[x];i;i=nxt[i]){
int y=to[i],len=y<=n;
if(dis[y]>dis[x]+len){
dis[y]=dis[x]+len;
if(len)q.push_back(y);
else q.push_front(y);
}
}
}
}
}
int main(){
n=in();
for(int i=1;i<=n;i++)a[i].l=in(),a[i].r=in(),a[i].id=i;
sort(a+1,a+n+1,[](node a,node b){return a.l<b.l;});
seg1::build(1,1,n);
for(int i=1;i<=n;i++){
if(a[i].l==1)fl[a[i].id]=0;
else fl[a[i].id]=seg1::query(1,1,n,a[i].l,a[i].r)+1;
seg1::modify(1,1,n,a[i].id,fl[a[i].id]);
}
seg1::build(1,1,n);
sort(a+1,a+n+1,[](node a,node b){return a.r>b.r;});
for(int i=1;i<=n;i++){
if(a[i].r==n)fr[a[i].id]=0;
else fr[a[i].id]=seg1::query(1,1,n,a[i].l,a[i].r)+1;
seg1::modify(1,1,n,a[i].id,fr[a[i].id]);
}
seg2::build(1,1,n);
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++){
dis[a[i].id]=fl[a[i].id]+fr[a[i].id];
seg2::update(1,1,n,a[i].l,a[i].r,a[i].id);
}
bfs();
q=in();
while(q--){
int x=in();
if(dis[x]>n)puts("-1");
else printf("%d\n",dis[x]+1);
}
return 0;
}
Day2
T1
这个题是三分……随便爆切二分交互题的buff没有生效……
如果我们每次询问只在一个点上放产品，考虑它连出去的边，如果有一些边我们已知方向，就将那条边改为指向这个点，这个时候我们询问一次，如果结果的产品不在这个点，那么我们就新确定了一条出边，如果产品在这个点，那么所有剩下的边都是指向这个点的入边。所以我们对于一个还有边没确定方向的点询问一次，至少能新确定一条边。
然后我们考虑一次询问的时候对多个点并行地进行操作，为了这些点不相互影响，一种想法是选出的任意两个点的距离都要大于2，结果发现好像不好在树上直接选出这样的点集。但是我们从链的情况得到启发，我们把所有深度模三同余的点拿出，这样选出的点集，每个点的所有儿子都一定不会被其他点影响，虽然父亲可能被影响，但是我们已知所有儿子和自己的状态，用排除法来判断是否是去父亲。于是这样我们一下可以对所有深度模三同余的还有边没确定的点问出一条边。假设当前还剩 m 条边没有确定，那么深度模三的三种选择中我们选未确定点数最多的那种，那么至少可以问出 m/3 条边。所以最后询问的次数其实是 \(\log _{\frac 3 2} m\)，好像是29次，恰好足够。
#include "conveyor.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,dep[N];
int lst[N],to[N<<1],nxt[N<<1],ec=1;
inline void ae(int x,int y){
to[++ec]=y,nxt[ec]=lst[x],lst[x]=ec;
}
int fa[N],id[N],d[N];
vector<int> v[3];
void dfs(int x){
v[dep[x]%3].push_back(x);
for(int i=lst[x];i;i=nxt[i]){
int y=to[i];
if(y==fa[x])continue;
fa[y]=x,dep[y]=dep[x]+1;
id[y]=i^1;
dfs(y);
}
}
void Solve(int N,vector<int> A,vector<int> B) {
n=N;
for(int i=0;i<n-1;i++){
ae(A[i],B[i]),ae(B[i],A[i]);
}
fa[0]=-1;
dfs(0);
int m=n-1;
vector<int> ans(n-1,-1);
while(1){
for(int x=0;x<n;x++){
d[x]=0;
for(int i=lst[x];i;i=nxt[i]){
if(ans[(i>>1)-1]==-1)d[x]++;
}
}
int mx=0,p=0;
for(int i=0;i<3;i++){
int sum=0;
for(int j:v[i])sum+=d[j]>0;
if(sum>mx)mx=sum,p=i;
}
if(!mx)break;
vector<int> q1(n-1,0),q2(n,0),res;
for(int x:v[p]){
q2[x]=1;
for(int i=lst[x];i;i=nxt[i]){
if(ans[(i>>1)-1]==-1)continue;
if((ans[(i>>1)-1]==0)^(i&1))q1[(i>>1)-1]=1;
}
}
res=Query(q1,q2);
for(int x:v[p]){
if(res[x]){
for(int i=lst[x];i;i=nxt[i]){
ans[(i>>1)-1]=(i&1)^q1[(i>>1)-1]^1;
}
continue;
}
bool flag=0;
for(int i=lst[x];i;i=nxt[i]){
int y=to[i];
if(y!=fa[x]&&res[y]){
ans[(i>>1)-1]=(i&1)^q1[(i>>1)-1];
flag=1;
}
}
if(!flag){
ans[(id[x]>>1)-1]=(id[x]&1)^q1[(id[x]>>1)-1];
}
}
}
Answer(ans);
}
T2
对于每个主席，我们其实只关心一种项目：副主席选了就不行，不选就可以。我们令这样的项目集合为 \(S_i\)，令第 \(i\) 个人没选的项目集合为 \(T_i\)，我们其实就是要选出一个副主席 \(j\)，使得\(S_i\) 和 \(T_j\) 的交集最大。
然后这个题有两种实现，复杂度互不相同。
一种是我们先高维后缀和出 \(f_s\) 表示是否存在 \(j\) 使得 \(s \sub T_j\) 。再高位前缀和出 \(g_{s,i}\) 表示是否存在 \(s'\) 使得 \(f_{s'}=true \and |s'|=i\)。总复杂度 \(O(m^2 2^m)\)，为了不重复，我们对每个都记录两个选择即可。
另一种是我们根号分治，令 \(h_{s_1,s_2}\) 表示前一半的集合是 \(s_1\) 的所有人，后一半与 \(s_2\) 的交集最大是多少。这个东西我们动态插入，动态查询，正反序各做一次，就可不重，时间复杂度 \(O(n 2^{m/2})\)。
#include<bits/stdc++.h>
using namespace std;
inline int in(){
int x;
scanf("%d",&x);
return x;
}
const int N=1<<20|5;
struct node{
int a,b;
};
node merge(node p,node q){
if(p.a<q.a)swap(p,q);
p.b=max(p.b,q.a==p.a?q.b:q.a);
return p;
}
int n,m,t[N],cnt[21];
node a[N],b[21][N];
void init(int p){
for(int i=0;i<1<<m;i++)if(__builtin_popcount(i)==p)b[p][i]=a[i];
for(int i=1;i<1<<m;i<<=1)
for(int j=0;j<1<<m;j+=i<<1)
for(int k=0;k<i;k++)
b[p][i+j+k]=merge(b[p][i+j+k],b[p][j+k]);
}
int main(){
n=in(),m=in();
for(int i=1;i<=n;i++){
for(int j=0;j<m;j++){
int x=in();
if(x)t[i]|=1<<j,cnt[j]++;
}
a[t[i]^(1<<m)-1]=merge(a[t[i]^(1<<m)-1],{i,0});
}
for(int i=1;i<1<<m;i<<=1)
for(int j=0;j<1<<m;j+=i<<1)
for(int k=0;k<i;k++)
a[j+k]=merge(a[j+k],a[i+j+k]);
for(int i=0;i<=m;i++)init(i);
for(int i=1;i<=n;i++){
int res=0,s=0;
for(int j=0;j<m;j++){
int now=cnt[j]-(t[i]>>j&1);
if(now>n>>1)res++;
if(now==n>>1)s|=1<<j;
}
int ans=res;
for(int j=0;j<=m;j++){
if(b[j][s].a!=0&&b[j][s].a!=i)ans=res+j;
if(b[j][s].b!=0&&b[j][s].b!=i)ans=res+j;
}
printf("%d\n",ans);
}
return 0;
}
T3
不会！
Day4
T1
很人类智慧，只会74分……
首先我们肯定要把整个串存到矩阵之中，但是我们不知道 \(X,Y\)，我们就无法知晓原串所在的位置，所以直接的想法就是我们拿一些位置来记录 \(X,Y\)，只要解密出 \(X,Y\) 换原原串就是简单的事情了。
这是一个 0/1 矩阵，所以我们肯定把 \(X,Y\) 拆位保存，然后我们就想要找到一种保存方式不被 \(X,Y\) 影响。横着放和竖着放都有可能被覆盖，但是注意到，对于一条斜线，最多只会被覆盖 2 个位置，那么我们抓出 \((0,0) \sim (4,4)\) 这五个点，把其中三个染成 \(X\) 的最高位，那么不论对方怎么覆盖，我们总是可以找到 \(X\) 的最高位——这些位置的众数。我们找到 \(X\) 的最高位以后，我们就可以不受行的影响，于是我们选出一行的相邻的三个，把其中两个涂成 \(Y\) 的最高位，然后同理我们通过众数可以找到 \(Y\) 的最高位。将 \(X,Y\) 的最高位都确定以后我们就可以把 \(X,Y\) 的影响规避了，再找 4 个不被影响的位置存剩下的四位，总共用 9 个位置确定 \(X,Y\)，还剩下 40 个位置拿来存原串，得分 74。想了好久都不会 77/84 。难道做法不是存 \(X,Y\) ?
#include"Anna.h"
#include<bits/stdc++.h>
using namespace std;
namespace{
int mark[8][8];
int Px[4]={2,2,6,6},Py[4]={0,6,0,6};
}
void Anna(int X,int Y,int N,string S){
memset(mark,0,sizeof(mark));
int cnt=0;
for(int i=0;i<8;i++)mark[X][i]=mark[i][Y]=1;
for(int i=0,j=0;j<3;i++){
if(mark[i][i])continue;
mark[i][i]=1;Paint(i,i,X>>2);j++;cnt++;
}
int p=X>>2?0:4;
for(int i=7,j=0;j<2;i--){
if(mark[p][i])continue;
mark[p][i]=1;Paint(p,i,Y>>2);j++;cnt++;
}
int px=Px[(((X>>2)^1)<<1)|((Y>>2)^1)],py=Py[(((X>>2)^1)<<1)|((Y>>2)^1)];
Paint(px,py,X>>1&1),Paint(px,py+1,X&1);
Paint(px+1,py,Y>>1&1),Paint(px+1,py+1,Y&1);
cnt+=4;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
mark[px+i][py+j]=1;
for(int i=0,k=0;i<8;i++){
for(int j=0;j<8;j++){
if(!mark[i][j]){
Paint(i,j,k<N?S[k]-'A':0),cnt++;
k++;
}
}
}
}
#include"Bruno.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
bool mark[8][8];
int Px[4]={2,2,6,6},Py[4]={0,6,0,6};
}
string Bruno(int N,vector<vector<int> > T) {
memset(mark,0,sizeof(mark));
int X=0,Y=0;
int cx=0,cy=0;
for(int i=0;i<5;i++)cx+=T[i][i];
cx=cx>=3;
int p=cx?0:4;
for(int i=7;i>=5;i--)cy+=T[p][i];
cy=cy>=2;
X=cx<<2,Y=cy<<2;
int px=Px[(((X>>2)^1)<<1)|((Y>>2)^1)],py=Py[(((X>>2)^1)<<1)|((Y>>2)^1)];
X|=T[px][py]<<1|T[px][py+1];
Y|=T[px+1][py]<<1|T[px+1][py+1];
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
mark[px+i][py+j]=1;
for(int i=0;i<8;i++)mark[X][i]=mark[i][Y]=1;
for(int i=0,j=0;j<3;i++){
if(!mark[i][i])mark[i][i]=1,j++;
}
for(int i=7,j=0;j<2;i--){
if(!mark[p][i])mark[p][i]=1,j++;
}
string ans="";
for(int i=0,k=0;i<8;i++){
for(int j=0;j<8;j++){
if(!mark[i][j]&&k<N){
ans+=char(T[i][j]+'A');
k++;
}
}
}
return ans;
}
T2
更加人类智慧的一道题目，题意就十分的复杂。
从链的情况入手，要满足要求，其实就是对于每一条边，都要能够到彼岸。比如：对于从 \(i\) 到 \(i+1\) 这一条边，我们要能够使用 \(1\sim i\) 的资源，至少凑出 \(s_{i+1}\) 个警卫。 然后由于每一条边都能到达彼岸，那么每一个前缀对于以后的贡献就肯定都是非负的，于是 \(1\sim i\) 凑警卫，其实就是要把每条船都开到右岸，总的能凑出的警卫数量是 \(\sum_{j=1}^{i-1} a_j -\sum_{j=2}^i s_j\)（\(a_i\) 是第 \(i\) 条船初始安排的警卫的数量）。于是我们现在就有了若干个限制，\(\sum _{j=1}^i a_j \ge prelim_i,\sum_{j=i}^{n-1} a_j \ge suflim_i\)，我们要求在满足以上条件的情况下 \(\sum a_i\) 的最小值。我们令总和为 \(sum\)，然后就可以把第二种限制变为 $sum-\sum_{j=i}^{n-1} a_j \le sum- suflim_i \(，即：\)\sum_{j=1}^{i-1} a_j \le sum-suflim_i$，然后又有第一个限制 \(\sum _{j=1}^{i-1} a_j \ge prelim_{i-1}\)，于是有 \(prelim_{i-1}\le sum-suflim_i\)，这样的必要性是显然的，充分性是因为全满足这样的条件的情况下，我们可以确定出前缀和数组，然后差分出初始序列，所以 \(sum =\max_{i=1}^{n-2} prelim_i+suflim_{i+1}\)。链就做完了。
树的情况类似，只是把前缀和变成了子树和，于是我们就枚举一个点作为中心，然后将其所有子树的 \(lim\) 加起来，求最大值。结果发现除了中心的 \(s\) 被 \(lim\) 算了度数次以外，其余每个点都被算了度数减一次。所以树的答案就是 \(\sum s_i \times (d_i-1)+\max s_i\)。
\(q=0\) 的情况，很明显每一条边的贡献是其两端的 \(s\) 之和，跑最小生成树就行了。
\(q>0\) 的情况，由于这道题的边权是两点之和，猜一下/讨论一下就感觉每一步直接贪心选贡献最大的改就行了！具体地就是每次找一条边，删掉它，然后把两边 \(s\) 最小的点连一起。可以发现每一次一定是加一条 \(s\) 最小值的点 \(mn\) 与其他人的边，于是我们每次以 \(mn\) 为根遍历整棵树就可以找出结果。
复杂度 \(O(nq+m\log m)\)。76 分！
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int in(){
int x;
scanf("%d",&x);
return x;
}
const int N=6e5+5;
int n,m,q,o;
int a[N];
struct edge{
int x,y,z;
}e[N],e1[N];
int fa[N];
int gf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);}
bool mark[N];
int lst[N],to[N],nxt[N],id[N],ec;
inline void ae(int x,int y,int z){
to[++ec]=y,nxt[ec]=lst[x],id[ec]=z,lst[x]=ec;
}
int dfn[N],dfn1[N],dfp[N],tot;
int eid[N],mn0[N],mn1[N],mn2[N];
inline int Min(int x,int y){
if(!x||!y)return x|y;
return a[x]<a[y]?x:y;
}
void dfs(int x,int pre){
dfn[x]=++tot;dfp[tot]=x;
eid[x]=pre;mn0[x]=x;
for(int i=lst[x];i;i=nxt[i]){
if(id[i]==pre)continue;
dfs(to[i],id[i]);mn0[x]=Min(mn0[x],mn0[to[i]]);
}
dfn1[x]=tot;
}
int main(){
n=in(),m=in(),q=in();
ll sum=0;
int mx=0;
for(int i=1;i<=n;i++)a[i]=in(),sum-=a[i],mx=max(mx,a[i]);
sum+=mx;
for(int i=1;i<=m;i++){
int x=in(),y=in();
e[i].x=x,e[i].y=y,e[i].z=a[x]+a[y];
}
sort(e+1,e+m+1,[](edge a,edge b){return a.z<b.z;});
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int x=gf(e[i].x),y=gf(e[i].y);
if(x!=y){
fa[x]=y;
sum+=e[i].z;
e1[++o]=e[i];
mark[o]=1;
}
}
printf("%lld\n",sum);
while(q--){
ec=0;
for(int i=1;i<=n;i++)lst[i]=0;
for(int i=1;i<=o;i++){
if(!mark[i])continue;
ae(e1[i].x,e1[i].y,i);
ae(e1[i].y,e1[i].x,i);
}
tot=0;dfs(1,0);
for(int i=1;i<=n;i++){
mn1[i]=mn2[i]=dfp[i];
}
for(int i=2;i<=n;i++)mn1[i]=Min(mn1[i],mn1[i-1]);
for(int i=n-1;i>=1;i--)mn2[i]=Min(mn2[i],mn2[i+1]);
int mx=0,px,py,pe;
for(int i=2;i<=n;i++){
int x=mn0[i],y=Min(mn1[dfn[i]-1],mn2[dfn1[i]+1]);
int val=e1[eid[i]].z-a[x]-a[y];
if(val>mx)mx=val,px=x,py=y,pe=eid[i];
}
sum-=mx;
if(mx){
mark[pe]=0;
e1[++o]={px,py,a[px]+a[py]};
mark[o]=1;
}
printf("%lld\n",sum);
if(!mx)break;
}
while(q-->0)printf("%lld\n",sum);
return 0;
}
然后考虑优化到 100 分，发现我们的操作每次其实是把整棵树拆分开，这是比较难实现的。于是我们倒着考虑：最后的情况一定是整棵树变成了以 \(mn\) 为中心的菊花图。我们不考虑 \(mn\) 点，那么图这是分为了 \(n-1\) 个连通块。我们倒着考虑每一次 “撤销加边” 的操作，每一次其实是选一个 \(u\)，把 \(mn\) 到 \(u\) 的这条边断掉，然后这时整张图不连通了，就还需要加一条由 \(u\) 所在连通块连向其它连通块的边 \((x,y)\)，再合并两个连通块。这一次撤销操作产生的代价是 \(S_x+S_y-S_{mn}-S_{u}\)。想要代价尽量小，我们就对每个连通块维护其最小出边以及 \(S\) 最大的可选的 \(u\)。于是我们使用线段树来维护每个连通块的边集和点集，在合并连通块的时候使用线段树合并，再用一个可删堆维护每个连通块的代价，每次取出代价最小的连通块。
总复杂度 \(O(n \log n)\)，常数有点大，要跑将近 2s……
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int in(){
int x;
scanf("%d",&x);
return x;
}
const int N=4e5+5,inf=1e9;
int n,m,q;
int a[N],pos[N];
pair<int,int> b[N];
struct edge{
int x,y,z;
}E[N];
int fa[N];
int rt1[N],rt2[N],tot;
struct segnode{
int ls,rs,mn;
}T[N*60];
#define ls(x) T[(x)].ls
#define rs(x) T[(x)].rs
#define mn(x) T[(x)].mn
void ins(int &p,int l,int r,int d){
if(!p)p=++tot,mn(p)=d;
mn(p)=min(mn(p),d);
if(l==r)return;
int mid=l+r>>1;
if(d<=mid)ins(ls(p),l,mid,d);
else ins(rs(p),mid+1,r,d);
}
void del(int p,int l,int r,int d){
if(l==r){mn(p)=inf;return;}
int mid=l+r>>1;
if(d<=mid)del(ls(p),l,mid,d);
else del(rs(p),mid+1,r,d);
mn(p)=min(mn(ls(p)),mn(rs(p)));
}
int merge(int p,int q,int l,int r){
if(!p||!q)return p|q;
if(l==r)return 0;
int mid=l+r>>1;
ls(p)=merge(ls(p),ls(q),l,mid);
rs(p)=merge(rs(p),rs(q),mid+1,r);
mn(p)=min(mn(ls(p)),mn(rs(p)));
return p;
}
bool mark[N];
ll ans[N];
struct setnode{
int id,v,e;ll val;
}f[N];
inline bool operator < (const setnode &a,const setnode &b){
if(a.val!=b.val)return a.val>b.val;
if(a.v!=b.v)return a.v>b.v;
if(a.e!=b.e)return a.e>b.e;
return a.id>b.id;
}
inline bool operator == (const setnode &a,const setnode &b){
return a.val==b.val&&a.v==b.v&&a.e==b.e&&a.id==b.id;
}
struct Set{
priority_queue<setnode> pq1,pq2;
void insert(setnode x){
pq1.push(x);
}
void erase(setnode x){
pq2.push(x);
}
setnode top(){
while(pq2.size()&&pq1.top()==pq2.top())pq1.pop(),pq2.pop();
return pq1.top();
}
}S;
int gf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);}
int main(){
n=in(),m=in(),q=in();
for(int i=1;i<=n;i++)a[i]=in(),b[i]=make_pair(a[i],i);
sort(b+1,b+n+1);
for(int i=1;i<=n;i++)a[n-i+1]=b[i].first,pos[b[i].second]=n-i+1;
int cnt=0;
for(int i=1;i<=m;i++){
int x=pos[in()],y=pos[in()];
if(x>y)swap(x,y);
if(y==n)mark[x]=1,cnt++;
E[i]={x,y,a[x]+a[y]};
}
sort(E+1,E+m+1,[](edge a,edge b){return a.z<b.z;});
mn(0)=inf;
for(int i=1;i<n;i++)if(!mark[i])ins(rt1[i],1,n,i);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
if(E[i].y==n)continue;
ins(rt2[E[i].x],1,m,i);
ins(rt2[E[i].y],1,m,i);
}
ans[n-cnt-1]=1ll*a[n]*(n-2);
for(int i=n-cnt;i<=q;i++)ans[i]=ans[i-1];
for(int i=1;i<=n;i++){
int v=mn(rt1[i]),e=mn(rt2[i]);
f[i].v=v,f[i].e=e;
if(v>n||e>m)continue;
f[i]={i,v,e,E[e].z-a[n]-a[v]};
S.insert(f[i]);
}
for(int i=n-cnt-2;i>=0;i--){
setnode now=S.top();
int x=now.id,y=gf(E[now.e].x)+gf(E[now.e].y)-x;
ans[i]=ans[i+1]+now.val;
S.erase(f[x]);
if(f[y].v<=n&&f[y].e<=m)S.erase(f[y]);
del(rt1[x],1,n,now.v);
rt1[x]=merge(rt1[x],rt1[y],1,n);
rt2[x]=merge(rt2[x],rt2[y],1,m);
fa[y]=x;
int v=mn(rt1[x]),e=mn(rt2[x]);
f[x].v=v,f[x].e=e;
if(v<=n&&e<=m){
f[x]={x,v,e,E[e].z-a[n]-a[v]};
S.insert(f[x]);
}
}
for(int i=0;i<=q;i++)printf("%lld\n",ans[i]+a[1]);
return 0;
}
T3
每次转向都意味着边界的距离大于中间的长度，那么每次转向都会使得中间的长度至少翻倍，于是只会转向 \(O(\log n)\) 次。于是我们每次二分出转向的位置暴力就行了。复杂度 \(O(n \log^2 n)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int in(){
int x;
scanf("%d",&x);
return x;
}
const int N=2e5+5;
int n;
ll p[N],d[N];
ll st1[20][N],st2[20][N];
int findl(int l,int r){
for(int i=19;i>=0;i--){
if(l-(1<<i)+1>=1&&st2[i][l-(1<<i)+1]<=p[r+1])l-=1<<i;
}
return max(l,1);
}
int findr(int l,int r){
for(int i=19;i>=0;i--){
if(r+(1<<i)-1<=n&&st1[i][r]<-p[l-1])r+=1<<i;
}
return min(r,n);
}
int main(){
n=in();
for(int i=1;i<=n;i++)p[i]=in();
p[n+1]=2e9,p[0]=-2e9;
for(int i=0;i<=n;i++)d[i]=p[i+1]-p[i];
for(int i=1;i<=n;i++){
st1[0][i]=d[i]-p[i];
st2[0][i]=d[i-1]+p[i];
}
for(int i=1;i<20;i++)
for(int j=1;j<=n-(1<<i)+1;j++){
st1[i][j]=max(st1[i-1][j],st1[i-1][j+(1<<i-1)]);
st2[i][j]=max(st2[i-1][j],st2[i-1][j+(1<<i-1)]);
}
int Q=in();
while(Q--){
int pos=in(),x,l,r,op;
x=lower_bound(p+1,p+n+1,pos)-p;
if(p[x]-pos>=pos-p[x-1])x--;
long long ans=0;
ans+=abs(pos-p[x]);
if(d[x-1]<=d[x])op=0;
else op=1;
l=r=x;
while(l!=1||r!=n){
int nxt;
if(op==0){
nxt=findl(l,r);
ans+=p[r]-p[nxt];
l=nxt;
}else{
nxt=findr(l,r);
ans+=p[nxt]-p[l];
r=nxt;
}
op^=1;
}
printf("%lld\n",ans);
}
return 0;
}