广州二中NOI模拟赛（三十五）

返回首页 返回模拟赛列表

tip：如果题目图片看不清楚，可以百度“在线图片转文字”转换一下

A.异或

看到若干个数异或最大值，很容易想到了线性基，但由于有个区间限制，又不太好搞，毕竟线性基这玩意儿不具有可差分性，那就非常糟糕

于是想到一个馊主意：线段树维护线性基

具体地，线段树的每个区间，保存这个区间所有数的线性基。建树时向上合并线性基；查询时将相应区间的线性基合并起来做询问

仔细分析一下，嗯……线段树一个log，线性基合并2个log（虽然不满），所以总的就是3个log，然后数据范围10^6……

现场实测这只能拿26分，当然如果用了题目里给你的超级IO优化，然后子任务8加个特判，可以卡到31分

26分代码如下

#include<bits/stdc++.h>
using namespace std;

int read()
{
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}

void put(int x)
{
	if(x/10) put(x/10);
	putchar(x%10+'0');
}

int M;
const int N=1000010;
struct Basis
{
	int b[35],size;
	Basis(){memset(b,0,sizeof(b));size=0;}
	void insert(int x)
	{
		if(size==30) return;
		for(int i=M;i>=0;i--)
			if(x&(1<<i))
			{
				if(!b[i]){b[i]=x;size++;break;}
				else x^=b[i];
			}
	}
	int query(int x)
	{
		for(int i=M;i>=0;i--)
			if((x^b[i])>x) x^=b[i];
		return x;
	}
	void merge(Basis a)
	{
		if(size==30) return;
		for(int i=M;i>=0;i--)
			if(a.b[i]) insert(a.b[i]);
	}
};

Basis val[N<<2];
int a[N],n;

void build(int o,int l,int r)
{
	if(l==r){val[o].insert(a[l]);return;}
	int mid=(l+r)/2;
	build(o*2,l,mid);
	build(o*2+1,mid+1,r);
	val[o]=val[o*2];
	val[o].merge(val[o*2+1]);
}

Basis query(int o,int l,int r,int nl,int nr,int d)
{
	if(l==nl&&r==nr) return val[o];
	int mid=(l+r)/2;
	if(nr<=mid) return query(o*2,l,mid,nl,nr,d);
	else if(nl>mid) return query(o*2+1,mid+1,r,nl,nr,d);
	else
	{
		Basis ans=query(o*2,l,mid,nl,mid,d);
		ans.merge(query(o*2+1,mid+1,r,mid+1,nr,d));
		return ans;
	}
}

int main()
{
	n=read();
	bool flag=true;
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		if(a[i]>=16) flag=false;
	}
	M=flag?4:30;
	build(1,1,n);
	int q=read(),l,r,d;
	while(q--)
	{
		l=read();r=read();d=read();
		Basis ans=query(1,1,n,l,r,d);
		put(ans.query(d));putchar('\n');
	}
	return 0;
}

其实本题没有那么复杂

正解是离线询问，并且只维护一个线性基

把询问按照右端点升序排序，一边维护线性基，一边处理询问

线性基的维护方式需要改变一下，需要保存这一位线性基来自原序列的哪一个位置

每处理到第p个位置，就完成右端点为p的询问，询问时也要做一些改变。普通的线性基询问时只要异或了更大，就异或上去，但现在还需要判定：这一位的线性基是否来自l后面的位置（l指询问左端点）

因此我们不难想到一个贪心策略：维护线性基时，如果后面位置的数可行，就尽量让线性基来自更后面的位置，这一点在下面代码的insert函数中有体现

时间复杂度O((n+q)log a)

再吐槽一句：题目给的IO优化好牛逼啊！普通的手写快读1.4s读完的东西，它0.05s就读完了！

#include<bits/stdc++.h>
using namespace std;

namespace IO
{
	const int S=1<<16;
	//Input Correlation
	char buf[S],*H,*T;
	inline char Get()
	{
		if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
		if(H==T) return -1;return *H++;
	}
	inline int read()
	{
		int x=0;char c=Get();
		while(!isdigit(c)) c=Get();
		while(isdigit(c)) x=x*10+c-'0',c=Get();
		return x;
	}
	//Output Correlation
	char obuf[S],*oS=obuf,*oT=oS+S-1,c,qu[55];int qr;
	inline void flush()
	{
		fwrite(obuf,1,oS-obuf,stdout);
		oS=obuf;
	}
	inline void putc(char x)
	{
		*oS++ =x;
		if(oS==oT) flush();
	}
	template <class I>
	inline void print(I &x)
	{
		if(!x) putc('0');
		while(x) qu[++ qr]=x%10+'0',x /= 10;
		while(qr) putc(qu[qr--]);
	}
}

using namespace IO;
const int N=1000010;
int a[N],n,q;
int base[35];
struct Qry{int l,r,d,id;} qry[N];
int ans[N];

bool operator < (const Qry &a,const Qry &b){return a.r<b.r||a.r==b.r&&a.l<b.l;}

inline void insert(int p)
{
	for(int i=30;i>=0;i--)
		if(a[p]&(1<<i))
		{
			if(!base[i]){base[i]=p;break;}
			if(base[i]<p) swap(base[i],p);
			a[p]^=a[base[i]];
		}
}

int main()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	q=read();
	for(int i=1;i<=q;i++)
	{
		qry[i].l=read();
		qry[i].r=read();
		qry[i].d=read();
		qry[i].id=i;
	}
	sort(qry+1,qry+1+q);
	int now=1;
	for(int i=1;i<=n;i++)
	{
		insert(i);
		while(qry[now].r==i)
		{
			int l=qry[now].l,d=qry[now].d;
			for(int j=30;j>=0;j--)
				if(l<=base[j]&&(d^a[base[j]])>d)
					d^=a[base[j]];
			ans[qry[now].id]=d;
			now++;
		}
	}
	for(int i=1;i<=q;i++) print(ans[i]),putc('\n');
	flush();
	return 0;
}

B.公交旅行

非常简单的一道题，放在NOIP中也不为过。但是我考场上写错了一个细节！然后样例过了！然后爆零！！！

直接建图不太现实，那就考虑每条边保存两个信息：该路线的站点总数a，以及这条边的起点在路线中的编号b（从0开始）

那么跑最短路，每到一条边，将当前时间对这条边的a取个模，再用b去减一下，得到等待时间，再加上1，就是到达边指向的点的时间

时间复杂度O(SPFA)

#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;

int read()
{
	int x=0;char c=getchar();
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+c-'0',c=getchar();
	return x;
}

void put(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x/10) put(x/10);
	putchar(x%10+'0');
}

struct Edge{int to,a,b,next;} e[1000010];
int h[100010],sum=0,n,m;
int stop[200010];
bool vis[100010];
int dis[100010];

inline void add_edge(int u,int v,int a,int b)
{
	sum++;
	e[sum].to=v;
	e[sum].a=a;
	e[sum].b=b;
	e[sum].next=h[u];
	h[u]=sum;
}

void SPFA()
{
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++) dis[i]=INF;
	queue<int> q;
	q.push(1);vis[1]=1;dis[1]=0;
	while(!q.empty())
	{
		int u=q.front();
		for(int tmp=h[u];tmp;tmp=e[tmp].next)
		{
			int v=e[tmp].to,base=dis[u]%e[tmp].a;
			int dist=(e[tmp].b-base+e[tmp].a)%e[tmp].a+1;
			if(dis[u]+dist<dis[v])
			{
				dis[v]=dis[u]+dist;
				if(!vis[v]) vis[v]=1,q.push(v);
			}
		}
		vis[u]=0;q.pop();
	}
}

int main()
{
	n=read();m=read();
	int t,x;
	for(int i=1;i<=m;i++)
	{
		t=read();
		for(int j=0;j<t;j++)
			stop[j]=read();
		stop[t]=stop[0];
		for(int j=0;j<t;j++)
			add_edge(stop[j],stop[j+1],t,j);
	}
	SPFA();
	for(int i=2;i<=n;i++)
		put(dis[i]==INF?-1:dis[i]),putchar(' ');
	return 0;
}

C.硬币游戏

这题的暴力好难打啊，场上非常懵逼，然后就没拿分

有一个神奇的问题转化：将每个信封看做一条边，只要选定的边不构成环，就是合法的

问题变成了：给定r对边，每对边中选一条，使之成为一个森林，最大化选的边数

那么解决方法也非常暴力，就是贪心加边，如果这条边不能加，就考虑这对边中的另一条能不能加。

考虑这条边能不能加时，能直接加当然是最好，不能直接加的话，就考虑把已经选定了的一些边换成它们那对边中的另一条，然后判断换了之后这条边能不能直接加上去，这个过程用BFS实现

总时间复杂度O(r³)

#include<bits/stdc++.h>
using namespace std;

const int S=1<<16;
char buf[S],*H,*T;
inline char Get()
{
	if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
	if(H==T) return -1;return *H++;
}
inline int read()
{
	int x=0;char c=Get();
	while(!isdigit(c)) c=Get();
	while(isdigit(c)) x=x*10+c-'0',c=Get();
	return x;
}

const int N=10010;
struct Edge{int to,next,id;} eg[N*100];
int e[310][3][3],chs[N];
int h[N],sum,nc,np=0;
bool vis[N];
int col[N],fa[N],pt[N];
int pre[N],dep[N],cc[N];
queue<int> q;

void add_edge(int u,int v,int id)
{
	eg[++sum].to=v;
	eg[sum].id=id;
	eg[sum].next=h[u];
	h[u]=sum;
}

void dfs(int u,int la)
{
	fa[u]=la;col[u]=nc;
	for(int tmp=h[u];~tmp;tmp=eg[tmp].next)
	{
		int v=eg[tmp].to;
		if(v==la) continue;
		dep[v]=dep[u]+1;
		pre[v]=eg[tmp].id;
		dfs(v,u);
	}
}

void gao1(int id,int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	while(dep[u]>dep[v])
	{
		int ed=pre[u];
		if(!vis[ed]) vis[ed]=1,cc[ed]=id,q.push(ed);
		u=fa[u];
	}
	while(u!=v)
	{
		int ed=pre[u];u=fa[u];
		if(!vis[ed]) vis[ed]=1,cc[ed]=id,q.push(ed);
		ed=pre[v];v=fa[v];
		if(!vis[ed]) vis[ed]=1,cc[ed]=id,q.push(ed);
	}
}

void gao2(int x)
{
	if(!x) return;
	chs[x]^=1;
	gao2(cc[x]);
}

bool add(int p,int c)
{
	int u=e[p][c][0],v=e[p][c][1];
	sum=-1;nc=0;
	for(int i=1;i<=np;i++) col[pt[i]]=0,h[pt[i]]=-1;
	for(int i=1;i<p;i++)
		if(chs[i]!=-1)
			add_edge(e[i][chs[i]][0],e[i][chs[i]][1],i),
			add_edge(e[i][chs[i]][1],e[i][chs[i]][0],i);
	for(int i=1;i<p;i++) vis[i]=0;
	for(int i=1;i<=np;i++)
		if(!col[pt[i]])
		{
			nc++;
			dep[pt[i]]=0;
			dfs(pt[i],0);
		}
	if(col[u]!=col[v]) return true;
	while(!q.empty()) q.pop();
	gao1(0,u,v);
	while(!q.empty())
	{
		int ed=q.front();q.pop();
		int u=e[ed][chs[ed]^1][0],v=e[ed][chs[ed]^1][1];
		if(col[u]!=col[v]){gao2(ed);return true;}
		gao1(ed,u,v);
	}
	return false;
}

int main()
{
	for(int T=read();T;T--)
	{
		int r=read();np=0;
		for(int i=1;i<=r;i++)
			pt[++np]=e[i][0][0]=read()+1,
			pt[++np]=e[i][0][1]=read()+1,
			pt[++np]=e[i][1][0]=read()+1,
			pt[++np]=e[i][1][1]=read()+1;
		int ans=r;
		for(int i=1;i<=r;i++)
			if(add(i,0)) chs[i]=0;
			else if(add(i,1)) chs[i]=1;
			else ans--,chs[i]=-1;
		printf("%d\n",ans<<1);
	}
	return 0;
}