省选模拟31


A. 神必的集合

发现就是神必的集合就是线性基

于是先将线性基变成最简形式

此时如果要求第 \(k\) 大,就只需要将 \(k\) 二进制分组

然后找到是 \(1\) 的位置,再把那些位置异或起来就是第 \(k\) 大了

可以用这个过程来检验限制

于是设 \(f_{i,j}\) 表示考虑了前 \(i\) 为,插入了 \(j\) 个主元的方案

再考虑转移,先用 \(m\) 个限制插入进一个线性基

如果当前这一位在线性基内,那就检验一下能否成为第 \(j\) 个主元

如果不在,那么可以插入也可以不插入

插入的话其他除了主元的位置都可以随便选,要乘上 \(2^{j-i}\) 的系数

Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define mod 998244353
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,m,ans,c;
int a[70],x[210],y[210];
int f[70][70];
bool jud;
inline void md(int &x){x=(x>=mod)?x-mod:x;}
inline void ins(int x){
	for(int i=62;~i;i--) if(x&(1ll<>j)&1) c=max(c,j+1);
		}
	}
	f[0][0]=1;
	for(int i=0;i>j)&1)&&(!((y[k]>>i)&1))) jud=0;
			if(((y[k]>>i)&1)&&(!((x[k]>>j)&1))) jud=0;
		}
		if(a[i]){
			if(jud) md(f[i+1][j+1]+=f[i][j]);
		}else{
			if(jud) md(f[i+1][j+1]+=(f[i][j]*((1ll<<(i-j))%mod)%mod));
			md(f[i+1][j]+=f[i][j]);
		}
	}
	for(int i=c;i<=n;i++) md(ans+=f[n][i]);
	printf("%lld\n",ans);
	return 0;
}

B. 法阵

\(x,y\) 之间存在一个比他们任意一个大的数,那么把 \(x\)\(y\) 替换成这个数一定更优

于是可以用单调栈找出所有这样的对数,然后就可以计算出 \(z\) 选择的范围

使用线段树就可以完成匹配

用扫描线的思路离线下来,从右往左依次移动左端点,再加入新的 \((x,y)\)

Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define lson rt<<1
#define rson rt<<1|1
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,m;
int a[500010],stk[500010],p;
int ans[500010];
vector>vec[500010],u[500010];
struct seg{int mx,v,atag;}st[500010*4];
inline void pushup(int rt){st[rt].mx=max(st[lson].mx,st[rson].mx);}
inline void pushdown(int rt){
	if(st[rt].atag){
		st[lson].atag=max(st[lson].atag,st[rt].atag);
		st[rson].atag=max(st[rson].atag,st[rt].atag);
		st[lson].mx=max(st[lson].mx,st[lson].v+st[lson].atag);
		st[rson].mx=max(st[rson].mx,st[rson].v+st[rson].atag);
		st[rt].atag=0;
	}
}
void build(int rt,int l,int r){
	if(l==r) return st[rt].v=a[l],void();
	int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	st[rt].v=max(st[lson].v,st[rson].v);
}
void upd(int rt,int l,int r,int L,int R,int k){
	if(L<=l&&r<=R){
		st[rt].atag=max(st[rt].atag,k);
		st[rt].mx=max(st[rt].mx,st[rt].v+st[rt].atag);
		return ;
	}
	int mid=(l+r)>>1;pushdown(rt);
	if(L<=mid) upd(lson,l,mid,L,R,k);
	if(R>mid) upd(rson,mid+1,r,L,R,k);
	pushup(rt);
}
int query(int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R) return st[rt].mx;
	int mid=(l+r)>>1,res=0;pushdown(rt);
	if(L<=mid) res=max(res,query(lson,l,mid,L,R));
	if(R>mid) res=max(res,query(rson,mid+1,r,L,R));
	return res;
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("fz.in","r",stdin);
	freopen("fz.out","w",stdout);
	n=read();for(int i=1;i<=n;i++) a[i]=read();build(1,1,n);
	m=read();for(int i=1,l,r;i<=m;i++){l=read(),r=read();vec[l].emplace_back(make_pair(r,i));}
	for(int i=1;i<=n;i++){
		while(p&&a[stk[p]]

C. 旅行

考虑优化暴力连边,可以使用点分治

分别建出距离分治中心为 \(i\) 的虚点,再把点都连上去

发现多出去的变至多 \(51\) 一条,于是可以用类似的思路暴力连边

以任意一个端点为中心,再用上面点分治的做法连边

Code
#include
#define int long long//OVERFLOW !!! MEMORY LIMIT !!!
#define rint signed
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
int n,m,id;
int x[200100],y[200100];
int dis[16000010];
int d[200010],c[200010],a[200010],mxd;
int dep[200010],siz[200010],mx[200010],S,rt;
int head[16000010],ver[32000010],to[32000010],edge[32000010],tot;
vectorg[200010];
bool vis[200010],v[16000010],in[200100];
priority_queue>q;
int fa[200010];
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
inline bool merge(int x,int y){
	x=getfa(fa[x]),y=getfa(fa[y]);
	if(x==y) return false;
	fa[x]=y;return true;
}
inline void add(int x,int y,int z){ver[++tot]=y;edge[tot]=z;to[tot]=head[x];head[x]=tot;}
void getrt(int x,int fa){
	siz[x]=1,mx[x]=0;
	for(auto y:g[x]) if(!vis[y]&&y!=fa){
		getrt(y,x);
		siz[x]+=siz[y];
		mx[x]=max(mx[x],siz[y]);
	}
	mx[x]=max(mx[x],S-siz[x]);
	if(mx[x]=0) add(x,a[min(mxd,d[x]-dep[x])],c[x]);
	for(auto y:g[x]) if(!vis[y]&&y!=fa) dfs2(y,x);
}
inline void work(int x){
	mxd=0;
	cerr<q;
	for(int i=1;i<=n;i++) dis[i]=inf;dis[S]=0;q.push(S);
	while(!q.empty()){
		int x=q.front();q.pop();
		for(auto y:g[x]) if(dis[y]>dis[x]+1) dis[y]=dis[x]+1,q.push(y);
	}
}
signed main(){
#ifdef LOCAL
	freopen("in","r",stdin);
	freopen("out","w",stdout);
#endif
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	id=n=read(),m=read();
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,x,y;i<=m;i++){x=read(),y=read();::x[i]=x;::y[i]=y;}
	for(int i=1;i<=n;i++) d[i]=read(),c[i]=read();
	for(int i=1;i<=m;i++) if(merge(x[i],y[i])){
		in[i]=1;
		g[x[i]].emplace_back(y[i]);
		g[y[i]].emplace_back(x[i]);
	}
	S=n;mx[rt=0]=inf;getrt(1,0);solve(rt);
	for(int i=1;i<=m;i++) if(!in[i]){
		g[x[i]].emplace_back(y[i]);
		g[y[i]].emplace_back(x[i]);
	}
	for(int i=1,mxs;i<=m;i++) if(!in[i]){
		bfs(x[i]);mxs=0;for(int j=1;j<=n;j++) mxs=max(mxs,dis[j]);
		for(int j=0;j<=mxs;j++) a[j]=++id;
		for(int j=1;j<=n;j++) add(a[dis[j]],j,0);
		for(int j=1;j<=mxs;j++) add(a[j],a[j-1],0);
		for(int j=1;j<=n;j++) if(d[j]-dis[j]>=0) add(j,a[min(d[j]-dis[j],mxs)],c[j]);
	}
	for(int i=1;i<=id;i++) dis[i]=inf;dis[1]=0;q.push(make_pair(0,1));
	while(!q.empty()){
		int x=q.top().second;q.pop();if(v[x]) continue;v[x]=1;
		for(int i=head[x];i;i=to[i]){
			int y=ver[i];
			if(dis[y]>dis[x]+edge[i]){
				dis[y]=dis[x]+edge[i];
				q.push(make_pair(-dis[y],y));
			}
		}
	}
	for(int i=2;i<=n;i++) printf("%lld\n",dis[i]);
	return 0;
}