20260310紫题训练A - Quare个人认为全场最水题容易发现边双肯定是若干个环连接而成环之间通过相同结点连接那么就可以考虑DPDPDP,设g[s]g[s]g[s]为集合为sss的答案,简单状压转移即可#includebits/stdc.h # define Maxn 15 # define Maxm 45 # define inf 2e91 using namespace std; int T,n,m,u,v,w,lg[112|1]; int dis[Maxn][Maxn],ldis[Maxn][Maxn]; int f[Maxn][112|1][Maxn],g[112|1]; int main() { // freopen(sample.in,r,stdin); scanf(%d,T); for(int i0;i12;i) lg[1i]i; while(T--) { scanf(%d%d,n,m); for(int i1;in;i) for(int j1;jn;j) dis[i][j]ldis[i][j]inf; for(int i1;im;i) { scanf(%d%d%d,u,v,w); if(dis[u][v]w) ldis[u][v]dis[u][v],dis[u][v]w; else if(ldis[u][v]w) ldis[u][v]w; dis[v][u]dis[u][v],ldis[v][u]ldis[u][v]; } memset(f,127,sizeof(f)); for(int i1;in;i) f[i][1(i-1)][i]0; for(int s1;s(1n);s) { if(((s)(-s))s) continue; for(int st0;stn;st) { if((sst)1) { for(int i0;in;i) { if((i!st)((si)1)) { for(int j0;jn;j) { if((i!j)((sj)1)) { if(f[j1][s^(1i)][st1]!f[0][0][0]dis[i1][j1]!inf) f[i1][s][st1]min(f[i1][s][st1],f[j1][s^(1i)][st1]dis[i1][j1]); } } } } } } } memset(g,127,sizeof(g)); for(int s1;s(1n);s) { if(((s)(-s))s) continue; int x(s)(-s),y(s-x)(-(s-x)); if(s-x-y0) { if(dis[lg[x]1][lg[y]1]!infldis[lg[x]1][lg[y]1]!inf) g[s]dis[lg[x]1][lg[y]1]ldis[lg[x]1][lg[y]1]; continue; } for(int st0;stn;st) { if((sst)1) { for(int i0;in;i) { if((si)1) { if(dis[i1][st1]!inf) g[s]min(g[s],f[i1][s][st1]dis[i1][st1]); } } } } for(int ts(s-1);t;t(t-1)s) { for(int i0;in;i) { if((ti)1) { for(int j0;jn;j) { if((tj)1) { if(ijg[s^t^(1i)]!g[0]g[t]!g[0]) g[s]min(g[s],g[t]g[s^t^(1i)]); if(i!jf[i1][s^t^(1i)^(1j)][j1]!f[0][0][0]g[t]!g[0]) g[s]min(g[s],f[i1][s^t^(1i)^(1j)][j1]g[t]); } } } } } } if(g[(1n)-1]g[0]) printf(impossible\n); else printf(%d\n,g[(1n)-1]); } return 0; }B - 球队收益 / 球队预算本人赛时思路如下猜测只要每个人的胜场数之和为mmm则为合法于是设f[i][j]f[i][j]f[i][j]为前iii个胜jjj场的答案设ru[i]ru[i]ru[i]为iii还要打的场数考虑状态转移形似f[i][j]mink0ru[if[i−1][j−k]w[i][k]f[i][j]\min_{k0}^{ru[i}f[i-1][j-k]w[i][k]f[i][j]mink0ru[if[i−1][j−k]w[i][k]发现w[i][k]w[i][k]w[i][k]单峰而f[i]f[i]f[i]单增于是叠加后同为单峰直接三分时间复杂度O(nmlogm)O(nmlogm)O(nmlogm)乍看没问题实际问题很大首先第一句的猜测就错了其次f[i]f[i]f[i]尽管单增但函数图像实际为离散的直线并非严格一次函数所以叠加非单峰下面讲正解首先如果猜测是错的那么每一场比赛我们必须准确的分出一场胜场而能较好适配这种限制的算法只有一个——网络流于是拆边建图跑费用流就好#includebits/stdc.h # define Maxn 5015 # define Maxm 1015 # define ll long long # define inf 1e18 using namespace std; int n,m,a[Maxn],b[Maxn],c[Maxn],d[Maxn]; int u,v,ru[Maxn]; int st,ed,N,head[MaxnMaxm],tot2; ll sum,ans; struct Node{int to,next,w;ll cost;}e[(Maxm*3Maxm*2)1]; void add(int u,int v,int w,ll cost) {e[tot]{v,head[u],w,cost},head[u]tot;} void addedge(int u,int v,int w,ll cost) {add(u,v,w,cost),add(v,u,0,-cost);} bool vis[MaxnMaxm],Vis[MaxnMaxm]; int cur[MaxnMaxm]; ll dis[MaxnMaxm]; queueint q; bool spfa() { for(int i1;iN;i) dis[i]inf,cur[i]head[i]; dis[st]0,q.push(st); while(!q.empty()) { int hq.front();q.pop(),vis[h]0; for(int ihead[h];i;ie[i].next) { if(e[i].wdis[e[i].to]dis[h]e[i].cost) { dis[e[i].to]dis[h]e[i].cost; if(!vis[e[i].to]) vis[e[i].to]1,q.push(e[i].to); } } }return dis[ed]!inf; } ll dfs(int rt,ll flow) { if(rted) {ansdis[rt]*flow;return flow;} ll res0;Vis[rt]1; for(int ihead[rt];i;ie[i].next) { if((!Vis[e[i].to])e[i].wdis[e[i].to]dis[rt]e[i].cost) { ll nowflowdfs(e[i].to,min(flow,1ll*e[i].w)); if(!nowflow) dis[e[i].to]inf; else { e[i].w-nowflow; e[i^1].wnowflow; flow-nowflow; resnowflow; if(!res) {Vis[rt]0;return res;} } } }Vis[rt]0;return res; } int main() { // freopen(sample.in,r,stdin); scanf(%d%d,n,m),stn1,edn2,Nn2; for(int i1;in;i) scanf(%d%d%d%d,a[i],b[i],c[i],d[i]); for(int i1;im;i) { scanf(%d%d,u,v); ru[u],ru[v]; N,addedge(st,N,1,0),addedge(N,u,1,0),addedge(N,v,1,0); } for(int i1;in;i) sum1ll*c[i]*(1ll*a[i]*a[i])1ll*d[i]*(1ll*(ru[i]b[i])*(ru[i]b[i])); for(int i1;in;i) { for(int j1;jru[i];j) { ll v2ll*(1ll*a[i]*c[i]-1ll*ru[i]*d[i]-1ll*b[i]*d[i]); vc[i]d[i]2ll*(j-1)*(c[i]d[i]); addedge(i,ed,1,v); } } while(spfa()) dfs(st,inf); printf(%lld\n,sumans); return 0; }C - 轻重路径赛事拿道题其实没什么思路实际上此时我们其实可以考虑题目里不起眼的小细节——二叉树看似没用实际上加上重链剖分这一强相关信息可以发现∀i\forall i∀i为轻儿子,Sz[fa[i]]Sz[fa[i]]Sz[fa[i]]2∗Sz[i]2*Sz[i]2∗Sz[i]于是当删除了一个叶节点时新增的轻儿子不超lognlognlogn,于是问题转化为如何快速找出这些点但仍没有思路于是故技重施利用Sz[i]Sz[i]Sz[i]和Sz[fa[i]]Sz[fa[i]]Sz[fa[i]]的翻倍性质进行求解发现Sz[i]Sz[i]Sz[i]Sz[rt]/2Sz[rt]/2Sz[rt]/2于是二分找出深度最小的Sz[i]Sz[i]Sz[i]满足Sz[i]Sz[i]Sz[i]Sz[rt]/2Sz[rt]/2Sz[rt]/2找到后将新点作为新根继续找时间复杂度O(nlog4n)O(nlog^4n)O(nlog4n),实际上可以做到O(nlog3n)O(nlog^3n)O(nlog3n)#includebits/stdc.h # define Maxn 200005 # define ll long long using namespace std; bool vis[Maxn]; int n,q,RT,x,l[Maxn],r[Maxn]; int Fa[Maxn][25],sz[Maxn],son[Maxn],dep[Maxn]; int tr[Maxn],p[Maxn],dfn; ll sum; void update(int x,int v) { for(int ix;in;i(i)(-i)) tr[i]v; } int query(int x) { int res0; for(int ix;i;i-(i)(-i)) restr[i]; return res; } int Ask_Sz(int x) { if(!x) return 0; return query(p[x]sz[x]-1)-query(p[x]-1); } int find(int x,int Dep) { for(int i20;i0;i--) { if(!Fa[x][i]) continue; if(dep[Fa[x][i]]Dep) xFa[x][i]; }return x; } void dfs(int rt,int fa) { dep[rt]dep[fa]1; p[rt]dfn; update(p[rt],1); Fa[rt][0]fa; for(int i1;i20;i) Fa[rt][i]Fa[Fa[rt][i-1]][i-1]; if(l[rt]) dfs(l[rt],rt),sz[rt]sz[l[rt]]; if(r[rt]) dfs(r[rt],rt),sz[rt]sz[r[rt]]; son[rt](sz[l[rt]]sz[r[rt]])?l[rt]:r[rt]; sz[rt],sumson[rt]; } int main() { scanf(%d,n); for(int i1;in;i) scanf(%d%d,l[i],r[i]),vis[l[i]]vis[r[i]]1; for(int i1;in;i) if(!vis[i]) RTi; dfs(RT,0); scanf(%d,q); printf(%lld\n,sum); while(q--) { scanf(%d,x); update(p[x],-1); int rtRT; while(1) { int SzAsk_Sz(rt); int sldep[rt]1,srdep[x],mid,p-1; while(slsr) { mid(slsr)1; int posfind(x,mid); if(Ask_Sz(pos)*2Sz) ppos,srmid-1; else slmid1; } // printf(%d ,p); if(p-1) break; int X1p,X2; if(l[Fa[X1][0]]X1) X2r[Fa[X1][0]]; else X2l[Fa[X1][0]]; if(son[Fa[X1][0]]X1) { if(Ask_Sz(X1)Ask_Sz(X2)-1) sum-X1X2,son[Fa[X1][0]]X2; else if((!Ask_Sz(X1))(!Ask_Sz(X2))) sum-X1; } rtp; } printf(%lld\n,sum); } return 0; }