改了两天，终于将T1,T3毒瘤题改完了...
T1 施工（单调栈优化DP）
考场上只想到了n*hmaxn*hmaxn的DP，用线段树优化一下变成n*hmaxn*log但显然不是正解
正解是很**的单调栈
可以想象到最优情况一定是将两端高于中间的一段平原填成一段平的坑，不然如果坑内存在高度差那么我们即使只将一部分抬升也肯定没有用处，并且如果中间的坑已经高于了两端，再向上升也肯定不优，然后就中间的坑可以很很小，也可以很长，对于这个模型我们首先想到n^2*h的DP
设当前表示的f[i]表示当前到了i节点并且i节点高度不变时的花费，那么能转移到他的其实只有高于i节点高度的点，那么我们
其实可以考虑用单调栈维护
然后对于h的最优高度化简后是一个二次函数的形式，然后直接求解就好，然后求二次函数时要注意解的范围，也要注意解是否为整数，然后打了很久..........
1 #include<bits/stdc++.h> 2 #define int long long 3 #define MAXN 110000 4 #define inf 0x7ffffffffff 5 using namespace std; 6 int read(){ 7 int x=0;char cc=getchar(); 8 while(cc<'0'||cc>'9'){cc=getchar();} 9 while(cc>='0'&&cc<='9'){x=(x<<1)+(x<<3)+(cc^48);cc=getchar();} 10 return x; 11 } 12 struct node{int l,r,sum1,sum2;}t[MAXN*4]; 13 int f[3][MAXN];int a[MAXN];int n;int maxn=0;int c=0; 14 void build(int k,int l,int r){ 15 t[k].l=l;t[k].r=r; 16 t[k].sum1=inf;t[k].sum2=inf; 17 if(l==r)return ; 18 int mid=(l+r)>>1; 19 build(k*2,l,mid);build(k*2+1,mid+1,r); 20 return ; 21 } 22 int now=1;int last=0; 23 void change(int k,int x){ 24 if(t[k].l==t[k].r){ 25 t[k].sum1=f[now][x]-x*c; 26 t[k].sum2=f[now][x]+x*c; 27 return ; 28 } 29 int mid=(t[k].l+t[k].r)>>1; 30 if(x<=mid){change(k*2,x);} 31 else change(k*2+1,x); 32 t[k].sum1=min(t[k*2].sum1,t[k*2+1].sum1); 33 t[k].sum2=min(t[k*2].sum2,t[k*2+1].sum2); 34 } 35 int ask=inf; 36 void query(int k,int l,int r,int me){ 37 if(t[k].l>=l&&t[k].r<=r){ 38 if(me==1){ask=min(ask,t[k].sum1);} 39 else{ask=min(ask,t[k].sum2);} 40 return ; 41 } 42 int mid=(t[k].l+t[k].r)>>1; 43 if(l<=mid)query(k*2,l,r,me); 44 if(r>mid)query(k*2+1,l,r,me); 45 } 46 signed main(){ 47 //freopen("t1.in","r",stdin); 48 //freopen("tree.out","w",stdout); 49 memset(f,0x3f3f3f3f,sizeof(f)); 50 n=read();c=read(); 51 for(int i=1;i<=n;++i){a[i]=read(),maxn=max(maxn,a[i]);} 52 build(1,0,maxn); 53 for(int i=a[1];i<=maxn;++i){ 54 f[now][i]=(i-a[1])*(i-a[1]); 55 change(1,i); 56 } 57 swap(now,last); 58 for(int i=2;i<=n;++i){ 59 for(int j=a[i];j<=maxn;++j){ 60 /*for(int k=a[i-1];k<=maxn;++k){ 61 f[now][j]=min(f[last][k]+c*abs(j-k),f[now][j]); 62 //printf("f[%lld][%lld]=%lld k=%lld f=%lld ",i,j,f[now][j],k,f[last][k]); 63 } 64 f[now][j]+=(j-a[i])*(j-a[i]);*/ 65 if(a[i-1]<=j){ 66 ask=inf;query(1,a[i-1],j,1); 67 f[now][j]=min(f[now][j],ask+j*c); 68 ask=inf;query(1,j+1,maxn,2); 69 f[now][j]=min(f[now][j],ask-j*c); 70 f[now][j]+=(j-a[i])*(j-a[i]); 71 } 72 else{ 73 ask=inf;query(1,a[i-1],maxn,2); 74 f[now][j]=ask-c*j; 75 f[now][j]+=(j-a[i])*(j-a[i]); 76 } 77 change(1,j); 78 } 79 swap(now,last); 80 memset(f[now],0x3f3f3f3f,sizeof(f[now])); 81 } 82 swap(now,last); 83 int minn=inf; 84 for(int i=a[n];i<=maxn;++i){ 85 minn=min(f[now][i],minn); 86 } 87 printf("%lld ",minn); 88 }
1 #include<bits/stdc++.h> 2 #define MAXN 2010000 3 #define inf 0x7ffffff 4 using namespace std; 5 double logg[MAXN]; 6 int read(){ 7 int x=0;char cc=getchar(); 8 while(cc<'0'||cc>'9'){cc=getchar();} 9 while(cc>='0'&&cc<='9'){x=(x<<1)+(x<<3)+(cc^48);cc=getchar();} 10 return x; 11 } 12 long long minn(long long x,long long y){return (x<y)?x:y;} 13 int ff[21][MAXN];long long a[MAXN];int n; 14 int RMB(int l,int r){ 15 int t=logg[r-l+1]/logg[2ll]; 16 return max(ff[t][l],ff[t][r-(1<<t)+1]); 17 } 18 void init(){ 19 for(int i=1;i<=n;++i)ff[0][i]=a[i]; 20 for(int j=1;j<=20;++j){ 21 for(int i=1;i+(1<<j)-1<=n;++i){ 22 ff[j][i]=max(ff[j-1][i],ff[j-1][i+(1<<(j-1))]); 23 } 24 } 25 } 26 int top=0;long long len=0; 27 long long sum1[MAXN],sum2[MAXN]; 28 long long f[MAXN];int st[MAXN];int c=0; 29 int jud(int x){ 30 if(x==(n+1)||x==0)return n+2; 31 return x; 32 } 33 int jud1(int x,int y){ 34 if(x==0&&y==n+1)return 0; 35 else if(x==0||y==n+1)return c; 36 return (2*c); 37 } 38 long long cal(int x,int y){ 39 long long ans=0; 40 long long s0=(y-x+1); 41 long long s1=-(sum2[y]-sum2[x-1])*2-jud1(x-1,y+1); 42 long long s2=sum1[y]-sum1[x-1]+a[jud(y+1)]*c+a[jud(x-1)]*c; 43 double kx=-((double)s1/(double)(2*s0)); 44 if(kx>minn((double)a[x-1],(double)a[y+1])){ 45 kx=minn((double)a[x-1],(double)a[y+1]); 46 } 47 else if(kx<(double)RMB(x,y))kx=(double)RMB(x,y); 48 if((-s1)%(2*s0)==0){ 49 len=(long long)kx; 50 ans=s0*len*len+s1*len+s2; 51 return ans; 52 } 53 else{ 54 long long len1=floor(kx);long long len2=ceil(kx); 55 if(len2>minn(a[x-1],a[y+1]))len2=minn(a[x-1],a[y+1]); 56 else if(len1<RMB(x,y))len1=RMB(x,y); 57 long long ans1=s0*len1*len1+s1*len1+s2; 58 long long ans2=s0*len2*len2+s1*len2+s2; 59 if(ans1>ans2){ 60 len=len2; 61 return ans2; 62 } 63 else{ 64 len=len1; 65 return ans1; 66 } 67 } 68 } 69 long long ans_len=0; 70 signed main(){ 71 memset(f,0x3f3f3f3f,sizeof(f)); 72 n=read();c=read(); 73 for(int i=1;i<=n;++i){ 74 a[i]=read(); 75 sum1[i]=sum1[i-1]+a[i]*a[i]; 76 sum2[i]=sum2[i-1]+a[i]; 77 } 78 init(); 79 for(int i=1;i<=n;++i){ 80 logg[i]=log(i)/log(2); 81 } 82 sum1[n+1]=sum1[n];sum2[n+1]=sum2[n]; 83 st[++top]=0;a[0]=inf;a[n+1]=inf-1; 84 st[++top]=1;f[1]=0;f[0]=0; 85 for(int i=2;i<=n+1;++i){ 86 if(i!=n+1)f[i]=min(f[i],f[i-1]+abs(a[i-1]-a[i])*c); 87 else f[i]=f[i-1]; 88 while(a[st[top]]<=a[i]){ 89 int to=st[top]; 90 if(to+1<=i-1){ 91 long long kxx=cal(to+1,i-1); 92 if(f[to]+kxx<f[i]){ 93 ans_len=len;f[i]=f[to]+kxx; 94 } 95 } 96 top--; 97 } 98 int to1=st[top]; 99 if(to1+1<=i-1){ 100 long long kxx=cal(to1+1,i-1); 101 if(f[to1]+kxx<f[i]){ 102 ans_len=len;f[i]=f[to1]+kxx; 103 } 104 } 105 st[++top]=i; 106 } 107 printf("%lld ",f[n+1]); 108 }
T2 蔬菜
正解？？？？然后就打暴力吧，二维莫队，时间复杂度不会
1 #include<bits/stdc++.h> 2 #define int long long 3 #define MAXN 210 4 using namespace std; 5 int read(){ 6 int x=0;char cc=getchar(); 7 while(cc<'0'||cc>'9'){cc=getchar();} 8 while(cc>='0'&&cc<='9'){x=(x<<1)+(x<<3)+(cc^48);cc=getchar();} 9 return x; 10 } 11 int a[MAXN][MAXN];int ans=0;int n,m,q; 12 int tong[MAXN*MAXN];int vis[MAXN*MAXN]; 13 struct node{int x1,x2,y1,y2,id,ans;}e[1000000]; 14 int l_x,r_x,l_y,r_y; 15 bool cmp(node a,node b){ 16 if(a.x1!=b.x1)return a.x1<b.x1; 17 if(a.y1!=b.y1)return b.y1<b.y1; 18 if(a.x2!=b.x2)return a.x2<b.x2; 19 return a.y2<b.y2; 20 } 21 bool cmp1(node a,node b){return a.id<b.id;} 22 void work_x(int i){ 23 while(l_x<e[i].x1){ 24 for(int j=l_y;j<=r_y;++j){ 25 ans-=tong[a[l_x][j]]*tong[a[l_x][j]]; 26 tong[a[l_x][j]]--; 27 ans+=tong[a[l_x][j]]*tong[a[l_x][j]]; 28 } 29 l_x++; 30 } 31 while(r_x>e[i].x2){ 32 for(int j=l_y;j<=r_y;++j){ 33 ans-=tong[a[r_x][j]]*tong[a[r_x][j]]; 34 tong[a[r_x][j]]--; 35 ans+=tong[a[r_x][j]]*tong[a[r_x][j]]; 36 } 37 r_x--; 38 } 39 while(r_x<e[i].x2){ 40 r_x++; 41 for(int j=l_y;j<=r_y;++j){ 42 ans-=tong[a[r_x][j]]*tong[a[r_x][j]]; 43 tong[a[r_x][j]]++; 44 ans+=tong[a[r_x][j]]*tong[a[r_x][j]]; 45 } 46 } 47 } 48 void work_y(int i){ 49 while(l_y<e[i].y1){ 50 for(int j=l_x;j<=r_x;++j){ 51 ans-=tong[a[j][l_y]]*tong[a[j][l_y]]; 52 tong[a[j][l_y]]--; 53 ans+=tong[a[j][l_y]]*tong[a[j][l_y]]; 54 } 55 l_y++; 56 } 57 while(l_y>e[i].y1){ 58 l_y--; 59 for(int j=l_x;j<=r_x;++j){ 60 ans-=tong[a[j][l_y]]*tong[a[j][l_y]]; 61 tong[a[j][l_y]]++; 62 ans+=tong[a[j][l_y]]*tong[a[j][l_y]]; 63 } 64 } 65 while(r_y<e[i].y2){ 66 r_y++; 67 for(int j=l_x;j<=r_x;++j){ 68 ans-=tong[a[j][r_y]]*tong[a[j][r_y]]; 69 tong[a[j][r_y]]++; 70 ans+=tong[a[j][r_y]]*tong[a[j][r_y]]; 71 } 72 } 73 while(r_y>e[i].y2){ 74 for(int j=l_x;j<=r_x;++j){ 75 ans-=tong[a[j][r_y]]*tong[a[j][r_y]]; 76 tong[a[j][r_y]]--; 77 ans+=tong[a[j][r_y]]*tong[a[j][r_y]]; 78 } 79 r_y--; 80 } 81 } 82 signed main(){ 83 n=read();m=read();q=read(); 84 for(int i=1;i<=n;++i){ 85 for(int j=1;j<=m;++j){ 86 a[i][j]=read();tong[++tong[0]]=a[i][j]; 87 } 88 } 89 sort(tong+1,tong+tong[0]+1); 90 tong[0]=unique(tong+1,tong+tong[0]+1)-tong-1; 91 for(int i=1;i<=n;++i){ 92 for(int j=1;j<=m;++j){ 93 a[i][j]=lower_bound(tong+1,tong+tong[0]+1,a[i][j])-tong; 94 } 95 } 96 for(int i=1;i<=q;++i){ 97 e[i].id=i;e[i].x1=read();e[i].y1=read();e[i].x2=read();e[i].y2=read();//printf("------ "); 98 } 99 memset(tong,0,sizeof(tong)); 100 sort(e+1,e+q+1,cmp); 101 for(int i=e[1].x1;i<=e[1].x2;++i){ 102 for(int j=e[1].y1;j<=e[1].y2;++j){ 103 ans-=tong[a[i][j]]*tong[a[i][j]]; 104 tong[a[i][j]]++; 105 ans+=tong[a[i][j]]*tong[a[i][j]]; 106 } 107 } 108 l_x=e[1].x1;r_x=e[1].x2;l_y=e[1].y1;r_y=e[1].y2;e[1].ans=ans; 109 for(int i=2;i<=q;++i){ 110 work_x(i);work_y(i); 111 e[i].ans=ans; 112 } 113 sort(e+1,e+q+1,cmp1); 114 for(int i=1;i<=q;++i){ 115 printf("%lld ",e[i].ans); 116 } 117 }
T3 联盟
树上直径的好题，改了一个晚上+两节自习
首先关于树上直径有个性质：
距离所有点的最远距离最小的点是直径的中点
那么这题拆的边肯定是直径上的边啦（想起了一道叫影子的题）
但是我们需要求出两个联通块的直径，但是好像我们只会n^2处理.......
但是我们发现假如我们断的边不是直径上的边那么断开后一个联通块的直径一定是原直径
我们可以将直径拎直，然后以两个端点DP，求出了两个数组，分别表示两个联通块的子树的直径，
设断开的联通块直径分别为L1,L2
对于直径边，新连的直径一定是L1,L2,(L1/2(向上取整)+L2/2(向上取整))+1，的最大值
所以直接判断，然后最后随便找出两个断点，找出新连的边即可
（没有处理多直径的情况，不会.....）
然后还有很多细节，非常****
注意操作3中选的节点一定是直径上的点，而不是BFS中dis==len/2的点，画画图会发现，非直径上的点是不成立的
1 #include<bits/stdc++.h> 2 #define int long long 3 #define MAXN 510000 4 using namespace std; 5 int head[MAXN],tot=0; 6 int read(){ 7 int f=1;int x=0;char cc=getchar(); 8 while(cc<'0'||cc>'9'){cc=getchar();} 9 while(cc>='0'&&cc<='9'){x=(x<<1)+(x<<3)+(cc^48);cc=getchar();} 10 return x*f; 11 } 12 struct node{int to,n;}e[MAXN*2];int uu[MAXN],vv[MAXN]; 13 void add(int u,int v){e[++tot].to=v;e[tot].n=head[u];head[u]=tot;} 14 int maxn,dis[MAXN]; 15 int pre[MAXN]; 16 int vis[MAXN]; 17 int n; 18 int l1[MAXN],l2[MAXN];int loop[MAXN]; 19 int root1,root2; 20 void DP(int x,int fa,int me){ 21 for(int i=head[x];i;i=e[i].n){ 22 int to=e[i].to; 23 if(to==fa)continue; 24 DP(to,x,me); 25 maxn=max(maxn,dis[x]+dis[to]+1); 26 loop[x]=max(loop[x],dis[x]+dis[to]+1); 27 if(me==1){l1[x]=max(l1[x],dis[x]+dis[to]+1);l1[x]=max(l1[x],loop[to]);loop[x]=max(loop[x],l1[x]);} 28 else {l2[x]=max(l2[x],dis[x]+dis[to]+1);l2[x]=max(l2[x],loop[to]);loop[x]=max(loop[x],l2[x]);} 29 dis[x]=max(dis[x],dis[to]+1); 30 } 31 } 32 queue<int>q; 33 vector<int>v; 34 int rt[MAXN];int len=0;int me_root[3];int biao_x,biao_y; 35 void BFS(int x,int me){ 36 memset(dis,0,sizeof(dis)); 37 memset(pre,0,sizeof(pre)); 38 memset(vis,0,sizeof(vis)); 39 while(!q.empty())q.pop(); 40 dis[x]=0;vis[x]=1;q.push(x); 41 while(!q.empty()){ 42 int top=q.front();q.pop(); 43 for(int i=head[top];i;i=e[i].n){ 44 int to=e[i].to; 45 if(vis[to]==1)continue; 46 if(top==biao_x&&to==biao_y)continue; 47 if(to==biao_x&&top==biao_y)continue; 48 vis[to]=1;dis[to]=dis[top]+1;pre[to]=top; 49 q.push(to); 50 } 51 } 52 int maxn=0;int maxn_id=x; 53 for(int i=1;i<=n;++i){ 54 if(dis[i]>maxn){ 55 maxn=dis[i];maxn_id=i; 56 } 57 } 58 len=maxn; 59 if(me==1){root1=maxn_id;} 60 else if(me==2){ 61 root2=maxn_id;v.push_back(maxn_id);rt[maxn_id]=1;len=maxn; 62 while(maxn_id!=x){ 63 maxn_id=pre[maxn_id]; 64 v.push_back(maxn_id); 65 rt[maxn_id]=1; 66 } 67 } 68 else if(me==3){ 69 if(len==0){me_root[++me_root[0]]=x; return ;} 70 for(int kx=maxn_id;kx!=0;kx=pre[kx]){ 71 int i=kx; 72 if(len%2==0){ 73 if(dis[i]==len/2){ 74 me_root[++me_root[0]]=i; 75 break; 76 } 77 } 78 else{ 79 if(dis[i]==((len-1)/2)+1){ 80 me_root[++me_root[0]]=i; 81 break; 82 } 83 } 84 } 85 } 86 } 87 map<pair<int,int>,int>h; 88 int ans1=0;int anss=0x7ffffffff; 89 int ans[MAXN];int toot[3]; 90 signed main(){ 91 n=read(); 92 for(int i=1;i<=n-1;++i){ 93 int u,v; 94 u=read();v=read(); 95 uu[i]=u;vv[i]=v; 96 h[make_pair(uu[i],vv[i])]=i; 97 h[make_pair(vv[i],uu[i])]=i; 98 add(u,v);add(v,u); 99 } 100 BFS(1,1); 101 biao_x=0;biao_y=0; 102 BFS(root1,2); 103 maxn=0;memset(dis,0,sizeof(dis));memset(loop,0,sizeof(loop)); 104 DP(root2,0,2); 105 maxn=0;memset(dis,0,sizeof(dis));memset(loop,0,sizeof(loop)); 106 DP(root1,0,1); 107 for(int i=0;i<v.size()-1;++i){//从root2开始 108 int mex=v[i];int mey=v[i+1]; 109 int mm1=l2[mey]; 110 int mm0=l1[mex]; 111 int means=0; 112 means=max(mm1,mm0); 113 if(mm1%2==0&&mm1!=0){mm1/=2;}else if(mm1!=0) {mm1++,mm1/=2;} 114 if(mm0%2==0&&mm0!=0){mm0/=2;}else if(mm0!=0) {mm0++,mm0/=2;} 115 means=max(means,mm1+mm0+1); 116 if(means<anss){ans[0]=0;ans[++ans[0]]=h[make_pair(mex,mey)];toot[0]=mex;toot[1]=mey;} 117 else if(means==anss){ans[++ans[0]]=h[make_pair(mex,mey)];toot[0]=mex;toot[1]=mey;} 118 anss=min(anss,means); 119 } 120 for(int i=1;i<=n-1;++i){ 121 int mex=uu[i];int mey=vv[i];int mm0,mm1,means; 122 if(rt[mex]&&rt[mey])continue; 123 mm1=min(l1[mex],l1[mey]);mm0=len; 124 means=max(mm1,mm0); 125 if(mm1%2==0&&mm1!=0){mm1/=2;}else if(mm1!=0) {mm1++,mm1/=2;} 126 if(mm0%2==0&&mm0!=0){mm0/=2;}else if(mm0!=0){mm0++,mm0/=2;} 127 means=max(means,mm1+mm0+1); 128 if(means<anss){ans[0]=0;ans[++ans[0]]=h[make_pair(mex,mey)];toot[0]=mex;toot[1]=mey;} 129 else if(means==anss){ans[++ans[0]]=h[make_pair(mex,mey)];} 130 anss=min(anss,means); 131 } 132 sort(ans+1,ans+ans[0]+1); 133 printf("%lld ",anss); 134 printf("%lld ",ans[0]); 135 for(int i=1;i<=ans[0];++i){ 136 printf("%lld ",ans[i]); 137 } 138 cout<<endl; 139 biao_x=toot[0];biao_y=toot[1]; 140 BFS(toot[0],1); 141 BFS(root1,3); 142 biao_x=toot[0];biao_y=toot[1]; 143 BFS(toot[1],1); 144 BFS(root1,3); 145 printf("%lld %lld %lld %lld ",toot[0],toot[1],me_root[1],me_root[2]); 146 }