A卷Day1
T1 card
题意
(n)张卡片，每张有上下(2)个值，在翻转不超过(m)张的条件下最小化极差
数据范围：(1le m<nle 10^6)
solution
考虑二分答案
枚举最小值(x)，那么需要把值小于(x)的翻转一下，值大于(x+mid)的翻转一下。
判断翻转之后是否合法：
- 小于(x)和大于(x+mid)的位置都是单调递增的，可以双指针。
- 前后缀最大值/最小值判断翻转之后的值是否都在([x,x+mid])之内
- 并且计算需要翻转多少位置，与(m)比较
复杂度(O(nlog ext{值域}))
#include <bits/stdc++.h>
using namespace std;
using namespace iobuff;
const int N=2e6+10;
int a[N],b[N],n,m,suf[N],pre[N],suf2[N],pre2[N];
struct Node{int val,pos;bool type;}x[N];
inline bool operator <(Node a1,Node a2){return a1.val<a2.val;}
inline bool check(int mid){
int flag1=1,flag2=1;
for(int i=1;i<=n+n;++i){
int cur=x[i].val+mid,val=x[i].val;
while(a[flag1]<=cur&&flag1<=n)++flag1;
while(a[flag2]<val&&flag2<=n)++flag2;
int cnt=x[i].type,L=flag2-1,R=flag1;
if(pre[L]<val)break;
if(suf[R]>cur||suf2[R]<val||pre2[L]>cur)continue;
cnt+=L;
if(x[i].pos<=L){
if(x[i].type)--cnt;
else continue;
}
cnt+=n-R+1;
if(x[i].pos>=R){
if(x[i].type)--cnt;
else continue;
}
if(cnt<=m)return 1;
}
return 0;
}
int main(){
scan(n);scan(m);
int L=1e9,R=0,mid;pre[0]=2e9;
for(int i=1;i<=n;++i){
scan(a[i]);R=max(R,a[i]);L=min(L,a[i]);
x[i]=(Node){a[i],i,0};
}
for(int i=1;i<=n;++i){
scan(b[i]);R=max(R,b[i]);L=min(L,b[i]);
x[i+n]=(Node){b[i],i,1};
pre[i]=min(pre[i-1],b[i]);
pre2[i]=max(pre2[i-1],b[i]);
}
suf2[n+1]=2e9;
for(int i=n;i>=1;--i)suf[i]=max(suf[i+1],b[i]),suf2[i]=min(suf2[i+1],b[i]);
sort(x+1,x+1+n+n);
int ans=1e9;R=R-L+1;L=0;
while(L<=R){
mid=(L+R)>>1;
if(check(mid))ans=mid,R=mid-1;
else L=mid+1;
}
putint(ans,'
');
flush();
return 0;
}
T2 matrix
题意
有两个(n imes m)矩阵(a,b)，已知(b)，并且(b_{i,j}=a_{i,j}+a_{i+1,j}+a_{i,j+1}+a_{i+1,j+1})
还原(a_{i,j})，要求(0le a_{i,j}le 10^6)
数据范围：(n,mle 300)
solution
显然是差分约束，只要但是手玩一下会发现变量个数不是(2)
观察这个矩阵的性质：
先钦定第(n)行，第(m)列均为(0)，根据(b_{i,j})构造出(a_{i,j})。但是这个(a_{i,j})不一定合法。
考虑进行一些变化使得依旧能满足(b)的限制：如果某一行/列的进行(+x,-x,+x,-xcdots)这样的变化，(b_{i,j})的限制依然满足
设(r_i,c_j)分别表示第(i)行/第(j)列变化的值，那么这个变化量矩阵如下
我们把这个矩阵的每一个数记作(x_{i,j})，即我们要满足(0le a_{i,j}+x_{i,j}le 10^6)
即
其中(x_{i,j})是只关于(r_i,c_j)的变量
但是有加号有减号没法做，考虑把一部分(r_i)和一部分(c_j)全都取相反数
将偶数(i)的(c_i)和奇数(j)的(r_j)取相反数，得到的矩阵如下
现在就都是一正一负了
差分约束即可
#include <bits/stdc++.h>
using namespace std;
using namespace iobuff;
const int N=305,MX=1e6;
int T,n,m,b[N][N];
#define ll long long
ll a[N][N];
struct Edge{int to,next;ll len;}e[N*N*10];
int head[N<<1],ecnt;
inline void adde(int u,int v,ll w){e[++ecnt]=(Edge){v,head[u],w};head[u]=ecnt;}
ll dis[N<<1];int cnt[N<<1],mx;bool inq[N<<1];
inline bool SPFA(){
deque<int> q;
for(int i=1;i<=n+m;++i)q.push_back(i),inq[i]=1,cnt[i]=dis[i]=0;
while(!q.empty()){
int u=q.front();q.pop_front();inq[u]=0;
for(int i=head[u],v;i;i=e[i].next){
v=e[i].to;
if(dis[v]>dis[u]+e[i].len){
dis[v]=dis[u]+e[i].len;
if(!inq[v]){
inq[v]=1;if((++cnt[v])>=mx)return 0;
if(e[i].len<=0)q.push_front(v);
else q.push_back(v);
}
}
}
}
return 1;
}
int main(){
scan(T);
while(T--){
scan(n);scan(m);
mx=min(40,n+m);
for(int i=1;i<n;++i)for(int j=1;j<m;++j)scan(b[i][j]);
memset(a[n]+1,0,m<<2);
for(int i=1;i<=n;++i)a[i][m]=0;
for(int i=n-1;i>0;--i)for(int j=m-1;j>0;--j){
a[i][j]=b[i][j]-a[i+1][j]-a[i][j+1]-a[i+1][j+1];
}
memset(head+1,0,(n+m)<<2);ecnt=0;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(!((i+j)&1)){
adde(j+n,i,MX-a[i][j]);
adde(i,j+n,a[i][j]);
}else{
adde(i,j+n,MX-a[i][j]);
adde(j+n,i,a[i][j]);
}
}
}
if(!SPFA()){
pc('N');pc('O');pc('
');
continue;
}
pc('Y');pc('E');pc('S');pc('
');
for(int i=1,c,r;i<=n;++i,pc('
'))
for(int j=1;j<=m;++j)
putint(a[i][j]+(((i+j)&1)?-dis[i]:dis[i])+(((i+j)&1)?dis[j+n]:-dis[j+n]),' ');
}
flush();
return 0;
}
T3 graph
题意
定义函数(f(u,G))，(u)是(G)中的顶点。
从(1sim n)枚举(v)，如果(u,v)能互相到达，(++ans)，并把点(v)和所有与(v)有关的边从(G)中删除
原图(G)中有(m)条边，设删除前(i)条边之后的图为(G_i)
求
数据范围：(1le nle 1000,1le mle 2 imes 10^5)
solution
观察(f(u,G))
首先可能对答案做出贡献的(vle u)，不然自己都被删了
我们有结论：
如果(v)对(f(u,G))造成贡献，那么一定存在两条路径(u o v)和(v o u)满足路径上的所有点编号(ge v)
证明，考虑反证，如果路径上存在(pin[1,v))：
- (p)造成贡献，那么这条路径会被断掉，不合法
- (p)不造成贡献，那么只存在路径(p o v)或者(v o p)，但是因为(u o v)和(v o u)同时存在，这自相矛盾
结论得证
现在我们考虑对(m)张图求解
我们不要每次删一条边重新做，而是从后往前加边
记(f_{u,v})表示(u o v)不存在(le min(u,v))的点的路径出现的最早时间（注意代码里时间早晚的定义不一样）
那么(v)对(u)第一次做出贡献的时间为(max(f_{v,u},f_{u,v}))。做一个前缀和即可
现在考虑求出(f_{u,v})，这玩意长得就很像Floyd
从高到低枚举中间点(k)，(k)可以对(f_{u,v})当且仅当(min(u,v)le k)（根据上面的结论）
转移即为
复杂度(O(n^3+m))
Floyd 常数极小，加上上面的(frac{3}{4})的常数优化，可以通过
#include <bits/stdc++.h>
using namespace std;
const int M=2e5+10,N=1005,inf=1e9;
int f[N][N],n,m;
inline void Max(int &a,int b){if(b>a)a=b;}
int ans[M];
int main(){
n=read();m=read();
for(int i=1,u,v;i<=m;++i){
u=read();v=read();f[u][v]=i;
}
for(int i=1;i<=n;++i)f[i][i]=m+1;
for(int k=n;k>=1;--k){
for(int i=1;i<=n;++i){
int R=(i<=k)?n:k;
for(int j=1;j<=R;++j)Max(f[i][j],min(f[i][k],f[k][j]));
}
}
for(int i=1;i<=n;++i)for(int j=i;j<=n;++j)++ans[min(f[i][j],f[j][i])];
for(int i=m;i>=1;--i)ans[i]+=ans[i+1];
for(int i=1;i<=m+1;++i)printf("%d ",ans[i]);
return 0;
}
A卷Day2
T1 gem
题意
一棵树，每个节点有(m)种宝石中的一种（一种宝石可能出现在多个节点），每次需要依次收集(P_1,P_2,P_3,cdots,P_c)的宝石。(q)次询问(s o t)的路径上能收集多少宝石。
数据范围：(1le n,qle 2 imes 10^5,1le cle mle 5 imes 10^4)
solution
首先可以按照(w_i)在(P)中第几个出现将收集宝石的顺序转为(1,2,3,cdots,c)
然后从下往上走的时候，可以简单地从离(u)最近的(1)开始倍增往上跳祖先，并且祖先不能超过(LCA)。
但是往下走的时候就不能倍增了。下面给出两种处理方法
我的超级难写的憨憨想法
树链剖分，维护一条链上两个方向的倍增数组，在链内倍增
巨难写，代码就不放了
更好写的解法：二分答案
首先处理完从下往上的答案，即为(ansl_i)，将右端点与其对应的(ansl)离线下来
对于一个询问，二分答案(x)，我们现在已经处理出它的父亲中颜色为(x)的，离它最近的节点（这也就是需要离线的原因）
我们只需判断倍增到(LCA)时能否达到(ansl_i+1)即可
复杂度(O(nlog^2 n))
T2 ranklist
题意
每队初始得分(a_i)，新一轮得分(b_i)。(b_i)初值为(0)，按照不降的顺序更新，要求(sum b_ile m)
(i)队排名在(j)前面当且仅当：在当前时间，(a_i+b_i>a_j+b_j)或者(a_i+b_i=a_j+b_j)且(i<j)
要求如果第(i)个更新的是(b_x)，那么更新之后(x)队为榜首
求可能的最终排名个数
数据范围：(1le nle 13,1le mle 500,0le a_ile 10^4)
solution
这么小的(n)显然考虑状压
(b_i)不降，考虑将其差分。如果(Delta_i>0)，那么相对大小改变的只能是第(i)和第(i-1)个更新的两队。并且之后所有的(b)都会增加，也就是总花费要增加((n-i+1) imes Delta_i)
定义状态：(f_{S,u,k})表示在(S)集合的(b)已经更新，最后一个更新的是(u)，花费恰好为(k)的排列数
设下一个加入的点为(v)，(cost_{v,u})表示(v)在排行榜上超过(u)的最小花费（(cost_{v,u}=max{0,a_u-a_v+(v>u)})）
转移为
#define ll long long
const int N=14,M=503;
int a[N],n,m,popcount[(1<<N)+10],mx,id,c;
ll f[(1<<14)+3][N][M];
int cost[N][N];//cost u,v : u become first after v become first
int main(){
n=read();m=read();mx=-1;
for(int i=1;i<=n;++i){
a[i]=read();
if(a[i]>mx)mx=a[i],id=i;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(i==j)continue;
if(a[i]>a[j])cost[i][j]=0;
else cost[i][j]=a[j]-a[i]+(i>j);
}
}
for(int i=1;i<=n;++i){
c=(mx-a[i]+(i>id))*n;
if(c<=m)f[1<<(i-1)][i][c]=1;
}
popcount[1]=popcount[2]=1;
for(int s=3;s<(1<<n);++s){
popcount[s]=popcount[s&(s-1)]+1;
if((s&(-s))==s)continue;
for(int i=1;i<=n;++i){
if(!(s&(1<<(i-1))))continue;
int t=s^(1<<(i-1));
for(int j=1;j<=n;++j){
if(!(t&(1<<(j-1))))continue;
int base=cost[i][j]*(n-popcount[t]);
for(int k=base;k<=m;++k)
f[s][i][k]+=f[t][j][k-base];
}
}
}
ll ans=0;
for(int i=1;i<=n;++i)for(int j=0;j<=m;++j)ans+=f[(1<<n)-1][i][j];
printf("%lld",ans);
return 0;
}
T3 dominator
题意
给定有向图(G)，(1)可以到达任意节点
定义(u)支配(v)：从(1)出发到(v)的路径中一定经过(u)。定义(v)的受支配集：(u)支配(v)的(u)集合
(q)次询问：加入一条边(x o y)，求支配集变化的点的数量
数据范围：(nle 3000,1le mle 2 imes n,1le qle 2 imes 10^4)
solution
首先支配集只会变小或者不变，如果我们建出支配树，那么如果(u)的支配集改变，也就是可以不经过(u)在支配树上的所有祖先中的一个
考虑简单地(O(nm))构建支配树
首先(O(nm))跑出所有点的支配集，因为树上父亲的子树大小大于儿子的子树大小，按照支配集大小排序，最大的就是根。把受它支配的点的父亲都设为自己。如果一个节点只有一个父亲，那么这个父亲就是确定了的，然后将自己的受支配集的点的父亲更新为自己。
说的不清楚的话就去看代码吧
现在给出结论
新加入 (x o y) 的边，记 (d=LCA(x,y))，那么如果存在一条 (y o u) 的路径满足：不经过(d)及其所有祖先的直接儿子，那么(u)的受支配集变小
首先我们可能出现的新路径只可能是(1 o d o x o y o cdots( o v) o u)，其中(v)是支配树上(u)的祖先之一。那么现在(LCA(d,u))的点的父亲都被经过过，可能不被经过的只可能是(LCA(d,u) o u)的路径上的一点
只要走过(x o y)之后走到了(u)的支配树上祖先上一点，那么支配树上到(u)的路径上的所有点都是必经的，否则就不符合支配树的定义了
如果走到了直接儿子，那么路径中间没有空出节点，所有受支配点依然会被经过
（以上只是感性理解，严谨证明参见洛谷题解）
直接(O(n))标记之后(O(m))BFS即可
bool vis[N],del[N];
int n,m,Q,sz[N],id[N];
inline bool cmp(int a,int b){return sz[a]>sz[b];}
inline void bfs(){
memset(vis+1,0,n);
vis[1]=1;q.clear();q.push(1);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u],v;i;i=e[i].next){
v=e[i].to;if(vis[v]||del[v])continue;
vis[v]=1;q.push(v);
}
}
}
#define pb push_back
vector<int> son[N];
vector<int> tr[N];
int Log2[N],dep[N],fa[N][18];
inline void init(){for(int i=2;i<=n;++i)Log2[i]=Log2[i>>1]+1;}
void dfs(int u,int fat){
dep[u]=dep[fat]+1;
for(int i=1;i<=Log2[dep[u]];++i)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=0,v;i<tr[u].size();++i){
v=tr[u][i];if(v==fat)continue;
dfs(v,u);
}
}
int ans;
void bfs2(int u){
memset(vis+1,0,n);
if(del[u])return;
vis[u]=1;q.clear();q.push(u);
while(!q.empty()){
int u=q.front();q.pop();++ans;
for(int i=head[u],v;i;i=e[i].next){
v=e[i].to;if(vis[v]||del[v])continue;
vis[v]=1;q.push(v);
}
}
}
inline int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
while(dep[x]>dep[y])x=fa[x][Log2[dep[x]-dep[y]]];
if(x==y)return x;
for(int i=Log2[dep[x]];i>=0;--i)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int main(){
n=read();m=read();Q=read();init();
for(int i=1,u,v;i<=m;++i){
u=read();v=read();
adde(u,v);
}
for(int i=2;i<=n;++i)son[1].pb(i),++sz[1];
id[1]=1;
for(int i=2;i<=n;++i){
id[i]=i;del[i]=1;bfs();del[i]=0;
for(int j=1;j<=n;++j){
if(i==j||vis[j])continue;
son[i].pb(j),++sz[i];
}
}
sort(id+1,id+1+n,cmp);
for(int i=1,u;i<=n;++i){
u=id[i];
for(int j=0,v;j<son[u].size();++j)
fa[son[u][j]][0]=u;
}
for(int i=1;i<=n;++i)if(fa[i][0])tr[fa[i][0]].pb(i);
dfs(1,0);
int s,t,d,lca;
while(Q--){
ans=0;
s=read();t=read();lca=LCA(s,t);
if(dep[t]-dep[lca]==1||lca==t){puts("0");continue;}
memset(del+1,0,n);
for(d=lca;d;d=fa[d][0]){
del[d]=1;
for(int i=0;i<tr[d].size();++i)
del[tr[d][i]]=1;
}
bfs2(t);
printf("%d
",ans);
}
return 0;
}
B卷
pair
题意
给定 (n) 个正整数 (a_i) 请你求出有多少个数对 ((i, j)) 满足 (1 le i le n)，(1 le j le n)，(i e j) 且 (a_i) 是 (a_j) 的倍数。
数据范围：(2le nle 2 imes 10^5,1le a_ile 5 imes 10^5)
solution
记录一下每个数出现的次数，暴力枚举倍数，时间复杂度(O(nlog a_i))
const int N=5e5+5;
int cnt[N],n,a[N],mx;
#define ll long long
ll ans;
int main(){
n=read();for(int i=1;i<=n;++i){
a[i]=read();mx=max(a[i],mx);
++cnt[a[i]];
}
for(int i=1;i<=n;++i){
for(int j=a[i];j<=mx;j+=a[i])ans+=cnt[j];
--ans;
}
printf("%lld",ans);
return 0;
}
mod
题意
给定 (n) 个正整数 (a_i)，请你在其中选出三个数 (i, j, k(i e j e k))，使得 ((a_i + a_j) mod a_k) 的值最大。
数据范围：(3le nle 2 imes 10^5,1le a_ile 10^8)
solution
首先考虑(O(n^2log n))暴力
从大到小枚举(a_k)，然后求出所有数(mod a_i)的结果(b_i)，排序，有两种情况对答案造成贡献
- 两个(b)加起来(ge a_k)之后(-a_k)，显然选两个最大的(b)最优
- 两个(b)加起来(<a_k)，再枚举一个(b)，找到(<a_k-b_i)的最大的(b_j)，注意不能为(b_i)，可以双指针（反正排序都有(O(nlog n))了再来个(upper\_bound)也没问题）
考虑优化
- 不枚举相同的(a_k)
- 如果(a_kle)当前最大答案直接结束
这两个优化很显然，下面证明复杂度是正确的
如果我们只考虑小于(a_k)的最大的两个(a)加起来(ge a_k)之后(-a_k)的贡献，得到的应该是复杂度的上界
假设我们一直枚举到了(a_x)，即(a_{x-1}le ans<a_x)。
两边减两个(ans)
设 (d_i=a_i−ans)，那么 (d_i>0)，又因为没有重复的(a_i)，(d)的增长至少是斐波那契数列的增长速度，最多增长(O(log max(a_i)))次，所以复杂度是(O(nlog nlog max(a_i)))
const int N=2e5+5;
int n,a[N],b[N],ans;
int main(){
n=read();for(int i=1;i<=n;++i)a[i]=read();
sort(a+1,a+1+n);
for(int i=n;i>=1&&a[i]>ans;--i){
if(a[i]==a[i+1])continue;
for(int j=1;j<=n;++j)b[j]=a[j]%a[i];
sort(b+1,b+1+n);
ans=max(ans,(b[n]+b[n-1])%a[i]);
for(int j=2,pos;j<=n;++j){
pos=upper_bound(b+1,b+n+1,a[i]-b[j]-1)-b-1;
if(b[j]==b[pos]&&b[pos]!=b[pos+1])--pos;
else if(b[pos]==0&&b[pos+1]!=0)++pos;
ans=max(ans,(b[j]+b[pos])%a[i]);
}
}
printf("%d",ans);
return 0;
}