2021 省选 A 卷选讲
坐标江苏，场外选手嘿嘿（
特别感谢 d j q djq djq & y h t yht yht（不然我啥也不会？
就 “ “ “详解 ” ” ”四题，d2t1&d2t2直接放代码了（问就是因为懒
Day 1 T1 Card
先离散化两个数组，然后二分答案（一个！单 l o g log log！二分的是最后的答案（
· 只需要维护一个前缀 m a x / m i n max/min max/min、后缀 m a x / m i n max/min max/min就行了
· 所有 l o w e r b o u n d / u p p e r b o u n d lower_bound/upper_bound lowerbound/upperbound都可以预处理
#include<bits/stdc++.h>
#define LL long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define INF 2147483647
using namespace std;
inline int read(){
int v=0,f=1;
char c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0'&& c<='9'){
v=v*10+c-'0';
c=getchar();
}
return v*f;
}
const int Maxn=2000005;
int n,a[Maxn],b[Maxn],m;
int minpre[Maxn],maxpre[Maxn],minsuf[Maxn],maxsuf[Maxn];
int lst[Maxn],fst[Maxn];
vector<int> V;
bool check(int d){
int j=0;
for (int i=0;i<V.size();i++){
while (j<V.size() && V[j]-V[i]<=d){
j++;
}
int Al=fst[i+1],Ar=lst[j];
if (Al>Ar){
if (m>=n && V[maxpre[n]-1]-V[minpre[n]-1]<=d) return true;
continue;
}
if (n-(Ar-Al+1)>m){
continue;
}
if (maxpre[Al-1]<=j && minpre[Al-1]>i && maxsuf[Ar+1]<=j && minsuf[Ar+1]>i){
return true;
}
}
return false;
}
int main(){
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
n=read();m=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<=n;i++) b[i]=read();
for (int i=1;i<=n;i++) V.pb(a[i]),V.pb(b[i]);
sort(V.begin(),V.end());
for (int i=1;i<=n;i++){
a[i]=lower_bound(V.begin(),V.end(),a[i])-V.begin()+1;
b[i]=lower_bound(V.begin(),V.end(),b[i])-V.begin()+1;
}
for (int i=1;i<=n;i++){
fst[a[i]]=i;lst[a[i]]=i;
}
fst[n+n+1]=n+1;
for (int i=n+n;i>=1;i--){
if(!fst[i]) fst[i]=fst[i+1];
}
lst[0]=0;
for (int i=1;i<=n+n;i++){
if (!lst[i]) lst[i]=lst[i-1];
}
minpre[0]=1e9;maxpre[0]=0;
for (int i=1;i<=n;i++){
minpre[i]=min(minpre[i-1],b[i]);
maxpre[i]=max(maxpre[i-1],b[i]);
}
minsuf[n+1]=1e9;maxsuf[n+1]=0;
for (int i=n;i>=1;i--){
minsuf[i]=min(minsuf[i+1],b[i]);
maxsuf[i]=max(maxsuf[i+1],b[i]);
}
int lo=-1,hi=1e9;
while (hi-lo>1){
int mid=lo+hi>>1;
if (check(mid)) hi=mid;
else lo=mid;
}
printf("%d\n",hi);
return 0;
}
Day 1 T2 Matrix
差分约束题
如果已知了第一行和第一列的所有数，可以知道其他的所有格子；
然后你把对值域的限制写成这些未知数的不等式，就把第一行和第一列的所有数看称未知数，发现 ( x , y ) (x,y) (x,y)这个点的不等式只和 ( 1 , 1 ) (1,1) (1,1), ( x , 1 ) (x,1) (x,1), ( y , 1 ) (y,1) (y,1)有关，也就是每个不等式只有三项，然后考虑把 ( 1 , 1 ) (1,1) (1,1)搞掉变成两项就是差分约束了
UPD:被卡常了 程序不放了（
Day 1 T3 Graph
-
n 3 + n m n^3+nm n3+nm（不确定对不对？
考虑每个点的贡献实际上是把所有小于这个点删掉之后它图中所在的强连通分量大小，然后对所有i-n建一张图，问题就变成给定一个原点和带权有向图
然后求每个点的最短瓶颈路（瓶颈路就是定义成所有边最大值的最短路），直接类似最短路用 d i j k s t r a dijkstra dijkstra做就是 O ( n m l o g n ) O(nmlogn) O(nmlogn)的
然后这是一张稠密图，稠密图的 d i j k s t r a dijkstra dijkstra可以优化到 O ( n 2 + m ) O(n^2+m) O(n2+m)
然后复杂度就变成 n 3 + n m n^3+nm n3+nm的
（因为点数不是满的，所以 n 3 n^3 n3常数其实会有个 1 / 2 1/2 1/2
-
绝对正解： n 3 / w n^3/w n3/w
并行处理所有 n n n 张图的情况，然后对每张图按编号反序插入所有边，然后在连通性发生改变时 b i t s e t bitset bitset 优化 d f s dfs dfs
#include<bits/stdc++.h>
using namespace std;
const int N=500005;
int n,m,u[N],v[N],i,mx,j,ans,as[N],p[1005][1005];
bitset<1005> g[1005],a[1005],b[1005],t,st,c[1005];
void dfs(int i,int x,int y)
{
int j;
a[i][x]=b[x][i]=c[x][i]=1;
p[i][x]=min(p[i][x],y);
++ans;
//cout<<'+'<<' '<<i<<' '<<x<<endl;
bitset<1005> e=(a[i]^st)&g[x];
for(j=e._Find_first();j!=e.size();j=e._Find_next(j))
dfs(i,j,y);
}
void cal()
{
for(i=1;i<=n;++i)
g[i].reset(),a[i].reset(),b[i].reset(),c[i].reset();
for(i=1;i<=n;++i)
{
for(j=1;j<=i;++j)
c[j][i]=a[i][j]=1;
b[i][i]=1;
}
st.set();
ans=n;
for(i=m;i>=1;--i)
{
//cout<<i<<endl;
g[u[i]][v[i]]=1;
t=b[u[i]]&(c[v[i]]^st);
for(j=t._Find_first();j!=t.size();j=t._Find_next(j))
dfs(j,v[i],i);
}
for(i=1;i<=n;++i)
for(j=i;j<=n;++j)
if(!a[i][j])
p[i][j]=0;
}
int main()
{
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
scanf("%d %d",&n,&m);
for(i=1;i<=m;++i)
scanf("%d %d",&u[i],&v[i]);
for(i=1;i<=n;++i)
for(j=i;j<=n;++j)
p[i][j]=m+1;
cal();
for(i=1;i<=m;++i)
swap(u[i],v[i]);
cal();
for(i=1;i<=n;++i)
for(j=i;j<=n;++j)
++as[p[i][j]];
for(i=m+1;i>=1;--i)
as[i]+=as[i+1];
for(i=1;i<=m+1;++i)
printf("%d ",as[i]);
}
Day 2 T1 Gem
倍增 + + +二分
#include<bits/stdc++.h>
#define LL long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define INF 2147483647
using namespace std;
inline int read(){
int v=0,f=1;
char c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
v=v*10+c-'0';
c=getchar();
}
return v*f;
}
const int Maxn=200005;
int n,m,c,P[Maxn],st[Maxn],ed[Maxn],w[Maxn],UpF[Maxn][20],UpR[Maxn][20],par[Maxn][20];
int pos[Maxn],kc,tree[Maxn*100],lson[Maxn*100],rson[Maxn*100],rt[Maxn],ko,dep[Maxn];
vector<int> col[Maxn];
vector<int> G[Maxn];
void dfs(int x,int p){
par[x][0]=p;st[x]=++kc;
for (int i=0;i<G[x].size();i++){
int v=G[x][i];
if (v!=p){
dep[v]=dep[x]+1;
dfs(v,x);
}
}
ed[x]=kc;
}
bool ispar(int u,int v){
return (u==-1)||(st[u]<=st[v] && ed[v]<=ed[u]);
}
int lca(int u,int v){
if (ispar(u,v)) return u;
for (int i=19;i>=0;i--){
if (!ispar(par[u][i],v)) u=par[u][i];
}
return par[u][0];
}
void modify(int p,int l,int r,int lo,int hi,int val){
if (lo<=l && r<=hi){
tree[p]=max(tree[p],val);
return;
}
int mid=l+r>>1;
if (lo<=mid){
if (!lson[p]){
lson[p]=++ko;
}
modify(lson[p],l,mid,lo,min(hi,mid),val);
}
if (hi>mid){
if (!rson[p]) rson[p]=++ko;
modify(rson[p],mid+1,r,max(lo,mid+1),hi,val);
}
}
int Query(int p,int l,int r,int pos){
if (l==r) return tree[p];
if (!p) return -1;
int mid=l+r>>1;
int ans=tree[p];
if (pos<=mid){
ans=max(ans,Query(lson[p],l,mid,pos));
}
else{
ans=max(ans,Query(rson[p],mid+1,r,pos));
}
return ans;
}
bool check(int u,int v,int l,int r){
int tmp=Query(rt[P[r]],1,n,st[u]);
// cerr<<tmp<<endl;
if (tmp==-1) return false;
int dlt=dep[u]-tmp;
for (int i=0;i<20;i++) if (dlt>>i&1) u=par[u][i];
//cerr<<u<<endl;
if (!ispar(v,u)) return false;
int d=r-l;
for (int i=0;i<20;i++){
if (d>>i&1){
if (UpR[u][i]==-1) return false;
u=UpR[u][i];
}
}
return ispar(v,u);
}
int Solve(int s,int t){
int l=lca(s,t);
//s->l l->t
int tmp=Query(rt[P[1]],1,n,st[s]);
//cerr<<"HH"<<tmp<<endl;
int lp=1;
if(tmp!=-1){
int dlt=dep[s]-tmp;
for (int i=0;i<20;i++){
if (dlt>>i&1) s=par[s][i];
}
if (ispar(l,s)){
for (int i=19;i>=0;i--){
if (UpF[s][i]!=-1 && ispar(l,UpF[s][i])) s=UpF[s][i];
}
lp=pos[w[s]]+1;
}
}
//cerr<<"FUCK"<<lp<<endl;
//l->t starting from lp;
if (lp==c+1) return c;
int lo=0,hi=c-lp+2;
while (hi-lo>1){
int mid=lo+hi>>1;
if (check(t,l,lp,lp+mid-1)){
lo=mid;
}
else{
hi=mid;
}
}
return lp+lo-1;
}
int main(){
freopen("gem.in","r",stdin);
freopen("gem.out","w",stdout);
n=read();m=read();c=read();
for (int i=1;i<=m;i++) pos[i]=-1;
for (int i=1;i<=c;i++) P[i]=read(),pos[P[i]]=i;
for (int i=1;i<=n;i++) w[i]=read(),col[w[i]].pb(i);
for (int i=0;i<n-1;i++){
int u,v;
u=read();v=read();
G[u].pb(v);G[v].pb(u);
}
dfs(1,-1);
for (int i=1;i<20;i++){
for (int j=1;j<=n;j++){
if (par[j][i-1]==-1) par[j][i]=-1;
else par[j][i]=par[par[j][i-1]][i-1];
}
}
for (int i=0;i<Maxn*100;i++){
tree[i]=-1;
}
for (int i=1;i<=m;i++){
rt[i]=++ko;
for (int j=0;j<col[i].size();j++){
int u=col[i][j];
modify(rt[i],1,n,st[u],ed[u],dep[u]);
}
}
for (int i=1;i<=n;i++){
if (pos[w[i]]==-1 || pos[w[i]]==c){
UpF[i][0]=-1;
}
else{
int hh=Query(rt[P[pos[w[i]]+1]],1,n,st[i]);
if (hh==-1) UpF[i][0]=-1;
else{
int dlt=dep[i]-hh;
int tmp=i;
for (int j=0;j<20;j++){
if (dlt>>j&1) tmp=par[tmp][j];
}
UpF[i][0]=tmp;
}
}
//cout<<UpF[i][0]<<' ';
}
// cout<<endl;
for (int i=1;i<=n;i++){
if (pos[w[i]]==-1 || pos[w[i]]==1){
UpR[i][0]=-1;
}
else{
int hh=Query(rt[P[pos[w[i]]-1]],1,n,st[i]);
if (hh==-1) UpR[i][0]=-1;
else{
int dlt=dep[i]-hh;
int tmp=i;
for (int j=0;j<20;j++){
if (dlt>>j&1) tmp=par[tmp][j];
}
UpR[i][0]=tmp;
}
}
// cout<<UpR[i][0]<<' ';
}
// cout<<endl;
for (int i=1;i<20;i++){
for (int j=1;j<=n;j++){
if (UpF[j][i-1]==-1) UpF[j][i]=-1;
else UpF[j][i]=UpF[UpF[j][i-1]][i-1];
if (UpR[j][i-1]==-1) UpR[j][i]=-1;
else UpR[j][i]=UpR[UpR[j][i-1]][i-1];
}
}
//cout<<check(5,1,1,2)<<endl;
//return 0;
int q=read();
while (q--){
int s,t;
s=read();t=read();
printf("%d\n",Solve(s,t));
}
return 0;
}
Day 2 T2 Ranklist
考虑一种排列实际上限制了一个bi+1-bi的最小值，然后根据这个delta的最小值我们可以贪心的求出至少需要分配多少题（这个delta只和相邻两个ai有关）所以我们只需要状压dp的时候记录最后一个选了哪个和当前所有delta的贡献和
#include<bits/stdc++.h>
#define LL long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define INF 2147483647
using namespace std;
inline int read(){
int v=0,f=1;
char c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
v=v*10+c-'0';
c=getchar();
}
return v*f;
}
int n,m,a[15];
int dp[8192][13][505];
int pc[8192];
int main(){
freopen("ranklist.in","r",stdin);
freopen("ranklist.out","w",stdout);
n=read();m=read();
int Mx=-1,pos;
for (int i=0;i<n;i++){
a[i]=read();
if (a[i]>Mx) Mx=a[i],pos=i;
}
for (int i=1;i<(1<<n);i++) pc[i]=pc[i&(i-1)]+1;
for (int i=0;i<n;i++){
int cst=Mx-a[i]+(pos<i);
if (cst*n<=m)dp[(1<<i)][i][cst*n]=1;
}
LL ans=0;
for (int i=0;i<(1<<n);i++){
for (int j=0;j<n;j++){
if (i>>j&1){
for (int k=0;k<=m;k++){
if (dp[i][j][k]){
if (i==(1<<n)-1) ans+=dp[i][j][k];
for (int l=0;l<n;l++){
if (i>>l&1) continue;
int dlt=a[j]-a[l]+(j<l);
if (dlt<0) dlt=0;
if (k+dlt*(n-pc[i])<=m){
dp[i|(1<<l)][l][k+dlt*(n-pc[i])]+=dp[i][j][k];
}
}
}
}
}
}
}
printf("%lld\n",ans);
return 0;
}
Day 2 T3 Dominator
已知支配的结构是个树，先 d f s dfs dfs 出 b a n ban ban 掉每个点之后 1 1 1 能到的点集，用这个可以 n 2 n^2 n2 求出支配树，然后对每个点 v v v 算出 b a n ban ban 掉 p a r [ v ] par[v] par[v] 之后的能抵达 v v v 的点集，然后用这俩单次询问 O ( n ) O(n) O(n)
（因为 v v v 受支配集改变充要条件是 v v v 的祖先中某个 p a r par par 改变
#include<bits/stdc++.h>
#define LL long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define INF 2147483647
using namespace std;
inline int read(){
int v=0,f=1;
char c=getchar();
while (c<'0' || c>'9'){
if (c=='-') f=-1;
c=getchar();
}
while (c>='0' && c<='9'){
v=v*10+c-'0';
c=getchar();
}
return v*f;
}
const int Maxn=3005;
int n,m,q;
vector<int> G[Maxn];
vector<int> D[Maxn];
int dom[Maxn][Maxn],ar[Maxn][Maxn],dep[Maxn],vis[Maxn],ban,siz[Maxn];
void dfs(int x){
vis[x]=1;
for (int i=0;i<G[x].size();i++){
int v=G[x][i];
if (!vis[v]){
dep[v]=dep[x]+1;
dfs(v);
}
}
}
void dfs2(int x){
vis[x]=1;
for (int i=0;i<G[x].size();i++){
int v=G[x][i];
if (!vis[v]){
dfs2(v);
}
}
}
void dfs3(int x){
if (ban==x) return;
vis[x]=1;
for (int i=0;i<G[x].size();i++){
int v=G[x][i];
if (!vis[v]){
dfs3(v);
}
}
}
int ord[Maxn];
bool cmp(int x,int y){
return siz[x]>siz[y];
}
void build(int x){
vis[x]=1;
vector<int> V;
for (int i=1;i<=n;i++){
if (dom[x][ord[i]]) V.pb(ord[i]);
}
for (int i=0;i<V.size();i++){
if (!vis[V[i]]){
D[x].pb(V[i]);
// cerr<<"DT"<<x<<' '<<V[i]<<endl;
build(V[i]);
}
}
}
int dep_D[Maxn],O[Maxn*3],kO,pos[Maxn],Mn[Maxn*3][15],lgg[Maxn*3],st[Maxn],ed[Maxn],prt[Maxn];
void dfs4(int x){
O[kO++]=x;pos[x]=kO-1;
st[x]=kO;
for (int i=0;i<D[x].size();i++){
int v=D[x][i];
dep_D[v]=dep_D[x]+1;
prt[v]=x;
dfs4(v);
O[kO++]=x;
}
ed[x]=kO;
}
void _init_lca(){
for (int i=2;i<Maxn*3;i++) lgg[i]=lgg[i>>1]+1;
dfs4(1);
for (int i=0;i<kO;i++){
Mn[i][0]=O[i];
}
for (int i=1;i<15;i++){
for (int j=0;j<kO;j++){
int nj=j+(1<<(i-1));
if (nj>=kO) Mn[j][i]=Mn[j][i-1];
else{
if (dep_D[Mn[j][i-1]]<dep_D[Mn[nj][i-1]]){
Mn[j][i]=Mn[j][i-1];
}
else{
Mn[j][i]=Mn[nj][i-1];
}
}
}
}
}
int lca(int u,int v){
u=pos[u],v=pos[v];
if (u>v) swap(u,v);
int l=lgg[v-u+1];
int x=Mn[u][l],y=Mn[v-(1<<l)+1][l];
if (dep_D[x]<dep_D[y]) return x;
return y;
}
bool ispar(int u,int v){
return st[u]<=st[v] && ed[v]<=ed[u];
}
void dfs5(int u){
vis[u]=1;
for (int i=0;i<G[u].size();i++){
int v=G[u][i];
if (ban==v || !ispar(ban,v)) continue;
if (prt[v]==ban) continue;
if (!vis[v]) dfs5(v);
}
}
int main(){
freopen("dominator.in","r",stdin);
freopen("dominator.out","w",stdout);
n=read();m=read();q=read();
for (int i=0;i<m;i++){
int u,v;
u=read();v=read();
G[u].pb(v);
}
dfs(1);
for (int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
dfs2(i);
for (int j=1;j<=n;j++) ar[i][j]=vis[j];
memset(vis,0,sizeof(vis));
ban=i;
dfs3(1);
for (int j=1;j<=n;j++){
if (!vis[j]) dom[i][j]=1,siz[i]++;
}
}
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;i++) ord[i]=i;
sort(ord+1,ord+1+n,cmp);
build(1);
_init_lca();
while (q--){
int s,t;
s=read();t=read();
swap(s,t);
int l=lca(s,t);
if (l==s || prt[s]==l){
printf("0\n");
continue;
}
memset(vis,0,sizeof(vis));
ban=l;
dfs5(s);
int ans=0;
for (int i=1;i<=n;i++) if(vis[i]) ans++;
printf("%d\n",ans);
}
return 0;
}
扯点题外话：yht 估分580（听说 djq 估分 550-575，dxm 555？ （反正都得%就是了…
![C语言第四章自述2第四章 选择结构程序设计[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)