【考试总结】2022-03-14
神必的集合
题目里面说的 神必的集合 本质上就是线性空间，数线性空间和计算 最简线性基 是等价的
不难发现最后的 \(\langle v_1,\dots v_m\rangle\subseteq S\)，所以可以将题目里面给出的 \(v_i\) 建立线性空间
设 \(f_{i,j}\) 表示考虑了 \(1\sim i\) 这些位置的元的情况，已经放置的主元个数为 \(j\) 的方案数
对于一个新的位置，如果它在原来已经有的线性基里面有主元，那么它必须放置一个主元，主元的值也和已有的线性基中对应主元的值一样，方案数是 \(1\)
否则可以放置自由元，方案数是 \(1\)；也可以放置主元，值在这位必须是 \(i\)，但是前面的自由元位置上可以任选，且前面的主元必须是 \(0\) 可以得到方案数
注意还要判定这位填主元是不是合法，这个根据线性基求 \(k\) 大的逆过程来考虑，如果限制的排名 \(\rm rank\) 的第 \(j\) 位和 \(v\) 的第 \(i\) 位不一样那么无法满足限制了
需要将 \(rank\leftarrow rank-1\) 来进行后续操作，最后的主元数量是不能少于最大的 \(rank\) 的最高位的，这是因为否则能异或出来的数字的个数根本不够就提不上排名了
时间复杂度 \(\Theta(nm+n^2)\)
Code Display
const int N=200;
int x[N],y[N],b[N],n,m,dp[N][N];
inline void ins(int x){
for(int i=n;i>=1;--i) if(x>>(i-1)&1){
if(~b[i]) x^=b[i];
else return b[i]=x,void();
}
}
signed main(){
freopen("set.in","r",stdin); freopen("set.out","w",stdout);
n=read(); m=read();
memset(b,-1,sizeof(b));
int hig=-1;
rep(i,1,m){
x[i]=read()-1,y[i]=read();
if(!x[i]&&y[i]) puts("0"),exit(0);
if(!y[i]&&x[i]) puts("0"),exit(0);
if(!x[i]){--i,--m; continue;}
ins(y[i]);
hig=max(hig,63ll-__builtin_clzll(x[i]));
}
vector pw(100); pw[0]=1;
for(int i=1;i<100;++i) pw[i]=add(pw[i-1],pw[i-1]);
dp[0][0]=1;
for(int i=0;i>i&1)==(x[c]>>j&1);
if(~b[i+1]){
if(corr) ckadd(dp[i+1][j+1],dp[i][j]);
}else{
if(corr) ckadd(dp[i+1][j+1],mul(dp[i][j],pw[i-j])); //positions : i+1; vectors: j+1; undecided: i-j;
ckadd(dp[i+1][j],dp[i][j]);
}
}
}
int ans=0;
for(int i=hig+1;i<=n;++i) ckadd(ans,dp[n][i]);
print(ans);
return 0;
}
法阵
可行的 \((x,y)\) 一定满足 \(a_x,a_y\ge \max\limits_{i=l+1}^{r-1}\{ a_i \}\)，否则可以经过固定左端点可以让 \(y-x\) 变小的同时和更大
维护一个单调递减的栈，那么合法的 \((x,y)\) 的对数出现在：将 \(y\) 压入栈的时候，弹出的若干元素；如果 \(y\) 最后出现在单调栈里面，那么它和它前面的一个元素也满足条件
每个元素只会被弹出一次，同时最后单调栈中相邻的元素对数 \(\le n\)，所以总的 \((x,y)\) 是 \(\Theta(n)\) 级别的
从右向左扫描线至 \(i\)，使用线段树对每个 \(x=i\) 的对找到合法的 \(z\) 即可，使用一个支持查询区间最大值和区间取 \(\max\) 的数据结构即可
Code Display
const int N=5e5+10;
int n,a[N],stk[N],top;
struct Seg{
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
int self[N<<2],Mx[N<<2],tag[N<<2];
inline void build(int p,int l,int r){
if(l==r) return self[p]=a[l],void(); int mid=(l+r)>>1;
build(lson); build(rson);
self[p]=max(self[rs],self[ls]);
}
inline void push_up(int p){Mx[p]=max(Mx[ls],Mx[rs]);}
inline void push_tag(int p,int v){
ckmax(Mx[p],self[p]+v);
ckmax(tag[p],v);
return ;
}
inline void push_down(int p){
if(tag[p]){
push_tag(ls,tag[p]);
push_tag(rs,tag[p]);
tag[p]=0;
} return ;
}
inline void upd(int st,int ed,int v,int p=1,int l=1,int r=n){
if(st<=l&&r<=ed) return push_tag(p,v);
int mid=(l+r)>>1; push_down(p);
if(st<=mid) upd(st,ed,v,lson); if(ed>mid) upd(st,ed,v,rson);
return push_up(p);
}
inline int query(int st,int ed,int p=1,int l=1,int r=n){
if(st<=l&&r<=ed) return Mx[p];
int mid=(l+r)>>1; push_down(p);
if(ed<=mid) return query(st,ed,lson); if(st>mid) return query(st,ed,rson);
return max(query(st,ed,lson),query(st,ed,rson));
}
#undef ls
#undef rs
#undef lson
#undef rson
}T;
vector Pair[N];
int ans[N];
vector >qu[N];
signed main(){
freopen("fz.in","r",stdin); freopen("fz.out","w",stdout);
n=read();
rep(i,1,n) a[i]=read(); T.build(1,1,n);
for(int i=1;i<=n;++i){
while(top&&a[stk[top]]<=a[i]) Pair[stk[top--]].push_back(i);
if(top) Pair[stk[top]].emplace_back(i);
stk[++top]=i;
}
int Q=read();
for(int i=1;i<=Q;++i){
int l=read(),r=read();
qu[l].emplace_back(r,i);
}
for(int i=n;i>=1;--i){
while(Pair[i].size()){
int y=Pair[i].back(); Pair[i].pop_back();
if(2*y-i<=n) T.upd(2*y-i,n,a[i]+a[y]);
}
for(auto q:qu[i]) ans[q.sec]=T.query(i,q.fir);
}
rep(i,1,Q) print(ans[i]);
return 0;
}
旅行
按照 传染 一题一样的方法建出点分树，只不过这次在堆里面排序的比较关键字变成了 dis[i]+c[i]，松弛没被求出 \(\rm dis\) 的点即可解决 \(m=n-1\) 的部分
对于经过非树边的更新，它一定经过了非树边的某个端点，对每个非树边的某个端点求出来每个点到其的距离，\(x\) 能松弛 \(y\) 的判定方式是 d[x]>=dis[u][x]+dis[u][y]
和点分树一样排序，使用指针维护即可，没有写 \(\Theta(1)\text {LCA}\) 所以复杂度是 \(\Theta(n\log^2n+n(m-n))\)
Code Display
const int N=2e5+10;
vector G[N];
int c[N],d[N],n,m,dis[N];
int f[N],siz[N],rt,nsum,fa[N],pter[N];
bool vis[N];
vector > sub[N];
struct Distance_Query{
int fa[N],dep[N],top[N],siz[N],son[N],tim,dfn[N];
inline void dfs1(int x,int fat){
dep[x]=dep[fa[x]=fat]+(siz[x]=1);
for(auto t:G[x]) if(t!=fat){
dfs1(t,x); siz[x]+=siz[t];
if(siz[t]>siz[son[x]]) son[x]=t;
} return ;
}
inline void dfs2(int x,int topf){
top[x]=topf; dfn[x]=++tim; if(son[x]) dfs2(son[x],topf);
for(auto t:G[x]) if(!dfn[t]) dfs2(t,t);
return ;
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]] >q;
inline void slack(int x){
int cur=x;
while(cur){
int d1=Dis.ask(x,cur);
if(d1<=d[x]){
while(pter[cur]d[x]) break;
int node=sub[cur][pter[cur]].fir;
if(!vis[node]){
vis[node]=1;
dis[node]=dis[x]+c[x];
q.push(make_pair(-dis[node]-c[node],node));
}
++pter[cur];
}
}
cur=fa[cur];
} return ;
}
int untu[60],indic[60],untv[60],unt;
signed disu[60][N],ord[60][N],dfn[60][N];
vector g[N];
signed main(){
freopen("travel.in","r",stdin); freopen("travel.out","w",stdout);
n=read(); m=read(); Dsu.init();
for(int i=1;i<=m;++i){
int u=read(),v=read();
g[u].emplace_back(v);
g[v].emplace_back(u);
if(Dsu.find(u)!=Dsu.find(v)){
G[u].push_back(v); G[v].push_back(u);
Dsu.merge(u,v);
}else{
untu[++unt]=u; untv[unt]=v;
}
}
for(int id=1;id<=unt;++id){
for(int i=1;i<=n;++i) disu[id][i]=0x3f3f3f3f;
queue Que; Que.push(untu[id]);
disu[id][untu[id]]=0;
while(Que.size()){
int fr=Que.front(); Que.pop();
dfn[id][ord[id][++indic[id]]=fr]=indic[id];
for(auto t:g[fr]) if(disu[id][t]>disu[id][fr]+1){
disu[id][t]=disu[id][fr]+1;
Que.push(t);
}
}
indic[id]=1;
}
rep(i,1,n) d[i]=read(),c[i]=read();
Dis.init();
nsum=n; f[0]=n+1;
findrt(1,0);
build(rt);
memset(vis,0,sizeof(vis));
memset(dis,0x3f,sizeof(dis)); dis[vis[1]=1]=0;
q.push(make_pair(dis[1]+c[1],1));
while(q.size()){
int fr=q.top().sec; q.pop();
slack(fr);
for(int id=1;id<=unt;++id){
int d1=disu[id][fr];
if(d[fr]>=d1){
while(indic[id]<=n){
int node=ord[id][indic[id]];
if(disu[id][node]+d1>d[fr]) break;
if(!vis[node]){
vis[node]=1;
dis[node]=dis[fr]+c[fr];
q.push(make_pair(-dis[node]-c[node],node));
}
++indic[id];
}
}
}
}
rep(i,2,n) print(dis[i]);
return 0;
}