「GXOI / GZOI2019」简要题解

「GXOI / GZOI2019」简要题解

LOJ#3083. 「GXOI / GZOI2019」与或和

https://loj.ac/problem/3083

题意:求一个矩阵的所有子矩阵的与和 和 或和。

分析:

• 或和与是一个东西，只要把所有数都异或上\((1<<31)-1\)然后再从总答案中减掉就能互相转化，考虑求与。
• 枚举每一位，转化成算有多少个全\(1\)子矩形，单调栈经典问题。总时间复杂度\(\mathrm{O}(n^2\log n)\)。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define N 1050
#define mod 1000000007
int mask=(1ll<<31)-1,n,a[N][N];
int b[N][N],up[N],S[N],tp;
ll work() {
	int i,j,k;
	ll re=0;
	for(k=0;k<=30;k++) {
		for(i=1;i<=n;i++) up[i]=0;
		for(i=1;i<=n;i++) {
			ll now=0;
			tp=0;
			S[0]=0;
			for(j=1;j<=n;j++) {
				b[i][j]=a[i][j]&(1<<k);
				if(!b[i][j]) up[j]=0;
				else up[j]++;
				if(!b[i][j]) tp=0,S[0]=j,now=0;
				else {
					while(tp&&up[S[tp]]>=up[j]) now-=ll(up[S[tp]])*(S[tp]-S[tp-1]),tp--;
					S[++tp]=j; now+=ll(up[j])*(S[tp]-S[tp-1]);
					now%=mod; re=(re+now*(1<<k))%mod;
				}
			}
		}
	}
	return re%mod;
}
int main() {
	scanf("%d",&n);
	ll tot=0;
	int i,j;
	for(i=1;i<=n;i++) for(j=1;j<=n;j++) {
		scanf("%d",&a[i][j]);
		tot=(tot+i*j);
	}
	tot%=mod;
	ll ans1=work();
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)a[i][j]^=mask;
	ll ans2=work();
	ans2=(tot*mask%mod-ans2)%mod;
	printf("%lld %lld\n",(ans1+mod)%mod,(ans2+mod)%mod);
}

LOJ#3084. 「GXOI / GZOI2019」宝牌一大堆

https://loj.ac/problem/3084

分析:

• 对于七对子和国土无双，可以拿出来\(\mathrm{O}(13^2+35\log 35)\) 处理。
• 剩下的情况，可以看成是\(1\)组雀头和\(4\)组杠子或面子。
• 直接设\(f[i][j][k][l][x][y]\)表示前\(i\)张牌，\(i-2,i-1,i\)分别作为顺子的最后一张拿走了\(j,k,l\)张牌，总共的杠子+面子数为\(x\)，雀头数为\(y\)。
• 然后\(l\)这维不用存并且\(i\)可以滚动掉，同时可以发现这个是跑不满的。
• 注意转移的时候不要超过\(1\)和\(4\)的限制。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 55
ll mi[N],C[N][N];
int a[N],b[N];
inline void upd(ll &x,ll y) {x=x>y?x:y;}
int trans(char *w) {
	if(strlen(w+1)==2) {
		int i;
		if(w[2]=='m') i=1;
		else if(w[2]=='p') i=2;
		else i=3;
		return (i-1)*9+w[1]-'0';
	}else {
		if(w[1]=='E') return 28;
		if(w[1]=='S') return 29;
		if(w[1]=='W') return 30;
		if(w[1]=='N') return 31;
		if(w[1]=='Z') return 32;
		if(w[1]=='B') return 33;
		if(w[1]=='F') return 34;
	}
	return -1;
}
ll ch(int x,int v) {
	return C[a[x]][v]*mi[b[x]*v];
}
ll f[35][3][3][5][2];
ll wk1() {
	memset(f,0,sizeof(f));
	f[0][0][0][0][0]=1;
	int i,j,k,x,y,z,w;
	for(i=0;i<35;i++) {
		for(j=0;j<3;j++) if(!j||(i<=27&&i%9!=0&&i%9!=1)) {
			for(k=0;k<3;k++) if(!k||(i<=27&&i%9!=8&&i%9!=0)) if(a[i+1]>=j+k) {
				for(x=j+k;x<=4;x++) {
					for(y=0;y<2;y++) if(f[i][j][k][x][y]) {
						for(z=0;z<=2&&j+k+z<=a[i+1]&&x+z<=4;z++) {
							for(w=0;j+k+z+w*3<=a[i+1]&&x+z+w<=4;w++) {
								int t=j+k+z+w*3;
								upd(f[i+1][k][z][x+z+w][y],f[i][j][k][x][y]*ch(i+1,t));
								if(!y&&t+2<=a[i+1]) upd(f[i+1][k][z][x+z+w][1],f[i][j][k][x][y]*ch(i+1,t+2));
							}
						}
						if(a[i+1]-j-k==4&&x<4) upd(f[i+1][k][0][x+1][y],f[i][j][k][x][y]*ch(i+1,4));
					}
				}
			}
		}
	}return f[34][0][0][4][1];
}
ll c[N];
ll wk2() {
	int i;
	for(i=1;i<=34;i++)c[i]=ch(i,2);
	sort(c+1,c+35);ll re=1;
	for(i=28;i<=34;i++)re*=c[i];return re*7;
}
int d[20]={0,1,9,10,18,19,27,28,29,30,31,32,33,34};
ll wk3() {
	ll re=0;int i,j;
	for(i=1;i<=13;i++) {
		ll tmp=ch(d[i],2);for(j=1;j<=13;j++)if(i!=j)tmp*=ch(d[j],1);re=max(re,tmp);
	}return re*13;
}
void solve() {
	int i,j;
	for(i=1;i<=34;i++) a[i]=4,b[i]=0;
	for(mi[0]=i=1;i<=18;i++) mi[i]=mi[i-1]<<1;;
	for(i=0;i<=4;i++)for(C[i][0]=j=1;j<=i;j++)C[i][j]=C[i-1][j]+C[i-1][j-1];
	while(1) {
		char w[10];
		scanf("%s",w+1);
		if(w[1]=='0') break;
		a[trans(w)]--;
	}
	while(1) {
		char w[10];
		scanf("%s",w+1);
		if(w[1]=='0') break;
		b[trans(w)]=1;
	}
	printf("%lld\n",max(wk1(),max(wk2(),wk3())));
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--) solve();
}

LOJ#3085. 「GXOI / GZOI2019」特技飞行

https://loj.ac/problem/3085

分析:

• 注意到\(c\)和\(a,b\)无关，直接数个点就行了。
• 然后我们感性理解一下如果所有特技都「对向交换」，那么一定是合法的。
• 于是就有了一个极值，另一个极值是要最小化「对向交换」的数量。
• 考虑排序后的数组的每个置换，可以发现最少交换次数为置换大小-1，且不同置换之间不影响，那么这部分的数量就是n-置换数。
• (bit还得拆成四个精度搞来搞去太麻烦，直接上kdt跑得还挺快)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef double f2;
#define N 500050
const f2 eps = 1e-10;
int n,Y0[N],Y1[N],st,ed,is[N],tot,id[N],to[N],K,vis[N];
ll A,B,C;
char buf[100000],*p1,*p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {
	int x=0; char s=nc();
	while(s<'0') s=nc();
	while(s>='0') x=(((x<<2)+x)<<1)+s-'0',s=nc();
	return x;
}
set<pair<int,int> >S;
set<pair<int,int> >::iterator it;
f2 mn[N][2],mx[N][2];
int flg[N],wh,ch[N][2],ok[N];
struct Point {
	f2 p[2];
	Point() {}
	Point(f2 x_,f2 y_) {p[0]=x_,p[1]=y_;}
	bool operator < (const Point &u) const {
		return p[wh]==u.p[wh]?p[!wh]<u.p[!wh]:p[wh]<u.p[wh];
	}
}a[N];
bool cmp(int x,int y) {
	return Y1[x]<Y1[y];
}
f2 Abs(f2 x) {return x>0?x:-x;}
void pushup(int p,int x) {
	mn[p][0]=min(mn[p][0],mn[x][0]);
	mn[p][1]=min(mn[p][1],mn[x][1]);
	mx[p][0]=max(mx[p][0],mx[x][0]);
	mx[p][1]=max(mx[p][1],mx[x][1]);
}

int build(int l,int r,int f,int k) {
	if(l>r) return 0;
	int mid=(l+r)>>1;
	wh=k;
	nth_element(a+l,a+mid,a+r+1);
	int p=mid;
	mn[p][0]=mx[p][0]=a[p].p[0];
	mn[p][1]=mx[p][1]=a[p].p[1];
	if(l<mid) ch[p][0]=build(l,mid-1,p,!k),pushup(p,ch[p][0]);
	if(r>mid) ch[p][1]=build(mid+1,r,p,!k),pushup(p,ch[p][1]);
	return p;
}
void update(int x,int y,int z,int p) {
	if(!p||flg[p]||x+z<mn[p][0]||x-z>mx[p][0]||y+z<mn[p][1]||y-z>mx[p][1]) return ;
	//if(!p) return ;
	if(max(max(max(abs(x-mn[p][0]),abs(x-mx[p][0])),abs(y-mn[p][1])),abs(y-mx[p][1]))-eps<z) {
		flg[p]=1; return ;
	}
	if(!ok[p]&&max(abs(a[p].p[0]-x),abs(a[p].p[1]-y))-eps<z) {
		ok[p]=1;
	}
	update(x,y,z,ch[p][0]); update(x,y,z,ch[p][1]);
}
int dfs(int p) {
	if(flg[p]) {
		ok[p]=1;
		ok[ch[p][0]]=ok[ch[p][1]]=flg[ch[p][0]]=flg[ch[p][1]]=1;
	}
	int re=ok[p];
	if(ch[p][0]) re+=dfs(ch[p][0]);
	if(ch[p][1]) re+=dfs(ch[p][1]);
	return re;
}
int main() {
	scanf("%d%lld%lld%lld%d%d",&n,&A,&B,&C,&st,&ed);
	int i,j;
	for(i=1;i<=n;i++) Y0[i]=rd();
	for(i=1;i<=n;i++) Y1[i]=rd();
	for(i=n;i;i--) {
		for(it=S.begin();it!=S.end()&&(it->first < Y1[i]);it++) {
			j=it->second;
			f2 t=f2(Y0[j]-Y0[i])/(Y1[i]-Y1[j]);
			f2 x=(t*ed+st)/(t+1);
			f2 y=(t*Y1[j]+Y0[j])/(t+1);
			f2 tx=x,ty=y;
			x=tx+ty;
			y=tx-ty;
			a[++tot]=Point(x,y);
		}
		S.insert(make_pair(Y1[i],i));
	}
	int rt=build(1,tot,0,0);
	K=rd();
	for(i=1;i<=K;i++) {
		int x,y,z;
		x=rd(),y=rd(),z=rd();
		int tx=x,ty=y;
		x=tx+ty;
		y=tx-ty;
		update(x,y,z,rt);
	}
	ll ans=dfs(rt)*C;
	ll ans1=ans+tot*A,ans2=ans+tot*A;
	for(i=1;i<=n;i++) id[i]=i;
	sort(id+1,id+n+1,cmp);
	ll u=n;
	for(i=1;i<=n;i++) if(!vis[i]) {
		u--;
		for(j=i;!vis[j];j=id[j]) vis[j]=1;
	}
	ans2+=(tot-u)*(B-A);
	if(ans1>ans2) swap(ans1,ans2);
	printf("%lld %lld\n",ans1,ans2);
}

LOJ#3086. 「GXOI / GZOI2019」逼死强迫症

https://loj.ac/problem/3086

分析:

• 设\(f_{i,j}\)表示有\(i\)列，放了\(j\)个\(1\times 1\)的格子的方案数，特别的我们令\(j=1\)的情况下表示\(i-1\)列多出来一个格子。
• 转移推推就可以了
• \(f_{i,0}=f_{i-1,0}+f_{i-2,0}\)
• \(f_{i,1}=f_{i-1,0}+f_{i-2,0}+f_{i-2,1}\)
• \(f_{i,2}=f_{i-1,2}+f_{i-2,2}+2f_{i-2,1}\)
• 然后搞一个\(6\times 6\)的矩阵矩乘一下就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
#define N 1000050
#define mod 1000000007
typedef long long ll;
struct Mat {
	ll a[6][6];
	Mat() {memset(a,0,sizeof(a));}
	Mat operator * (const Mat &u) const {
		Mat re; int i,j,k;
		for(i=0;i<6;i++)for(k=0;k<6;k++)for(j=0;j<6;j++) {
			re.a[i][j]+=a[i][k]*u.a[k][j];
		}
		for(i=0;i<6;i++)for(j=0;j<6;j++)re.a[i][j]%=mod;
		return re;
	}
}G[33];
Mat qp(Mat x,int y) {
	Mat I;
	int i;
	for(i=0;i<6;i++) I.a[i][i]=1;
	for(i=0;i<=30;i++) if(y&(1<<i)) I=I*G[i];
	return I;
}
int main() {
	int i;
	Mat x;
	int t;
	x.a[0][0]=x.a[0][1]=x.a[1][0]=x.a[2][0]=x.a[2][1]=x.a[2][3]=1;
	x.a[3][2]=x.a[4][4]=x.a[4][5]=x.a[5][4]=1;
	x.a[4][3]=2;
	G[0]=x;
	for(i=1;i<=30;i++) G[i]=G[i-1]*G[i-1];
	scanf("%d",&t);
	while(t--) {
		int y;scanf("%d",&y);
		if(y<=2) {puts("0"); continue;}
		Mat t=qp(x,y-1);
		ll ans=(t.a[4][0]+t.a[4][1]+t.a[4][2]);
		printf("%lld\n",ans%mod);
	}
}

LOJ #3087. 「GXOI / GZOI2019」旅行者

https://loj.ac/problem/3087

题意：有向图，给K个点，求两两之间最短的最短路。

分析:

• 二进制分组,然后跑最短路即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
#define N 100050
#define M 600050
char buf[100000],*p1,*p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {
	int x=0; char s=nc();
	while(s<'0') s=nc();
	while(s>='0') x=(((x<<2)+x)<<1)+s-'0',s=nc();
	return x;
}
typedef long long ll;
int head[N],to[M],nxt[M],val[M],vis[N],n,cnt,S,m,K,a[N];
ll dis[N];
priority_queue<pair<ll,int> >q;
inline void add(int u,int v,int w) {
	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
void dij() {
	int i;
	memset(dis+1,0x3f,S<<3);
	memset(vis+1,0,S<<2);
	dis[S]=0;
	q.push(make_pair(0,S));
	while(!q.empty()) {
		int x=q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(i=head[x];i;i=nxt[i]) if(dis[to[i]]>dis[x]+val[i]) {
			dis[to[i]]=dis[x]+val[i];
			q.push(make_pair(-dis[to[i]],to[i]));
		}
	}
}
void solve() {
	n=rd(),m=rd(),K=rd();
	int i,x,y,z,j;
	S=n+1;
	memset(head+1,0,S<<2);
	cnt=0;
	for(i=1;i<=m;i++) {
		x=rd(),y=rd(),z=rd();
		add(x,y,z);
	}
	for(i=1;i<=K;i++) a[i]=rd();
	random_shuffle(a+1,a+K+1);
	random_shuffle(a+1,a+K+1);
	random_shuffle(a+1,a+K+1);
	int tmp=cnt;
	ll ans=1ll<<60;
	for(i=0;i<5;i++) {
		cnt=tmp;
		for(j=1;j<=K;j++) if((j>>i)&1) add(S,a[j],0);
		dij();
		for(j=1;j<=K;j++) if(!((j>>i)&1)) ans=min(ans,dis[a[j]]);
		head[S]=0;

		cnt=tmp;
		for(j=1;j<=K;j++) if(!((j>>i)&1)) add(S,a[j],0);
		dij();
		for(j=1;j<=K;j++) if((j>>i)&1) ans=min(ans,dis[a[j]]);
		head[S]=0;
	}
	printf("%lld\n",ans);
}
int main() {
	int T;
	scanf("%d",&T);
	while(T--)solve();
}

LOJ#3088. 「GXOI / GZOI2019」旧词

https://loj.ac/problem/3088

题意:

一棵树，每次给出\(x,y\)，求\(\sum\limits_{i\le x}\mathrm{dep(lca(i,y))^k}\)

分析:

• 询问按\(x\)排序，一个一个插。
• \(k=1\)是个比较经典的问题，插入时\(1\)到\(x\)链\(+1\)，查询时查\(y\)到\(1\)的链和即可。
• 分析本质，加的这个\(1\)就是\(dep_x-dep_{fa_x}\)
• 很容易把他扩展到\(k​\)任意的情况，每条边的权值就是\(dep_x^K-dep_{fa_x}^K​\)
• 树剖+线段树搞一搞，时间复杂度\(\mathrm{O(n\log n^2)}​\)。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
#define N 50050
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
char buf[100000],*p1,*p2;
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {
	int x=0; char s=nc();
	while(s<'0') s=nc();
	while(s>='0') x=(((x<<2)+x)<<1)+s-'0',s=nc();
	return x;
}
typedef long long ll;
int head[N],to[N],nxt[N],fa[N],top[N],dep[N],siz[N],son[N],dfn[N],idf[N],cnt;
int n,Q,K;
ll h[N],w[N],sum[N<<2],tag[N<<2],sv[N<<2],ans[N];
struct A {
	int x,y,id;
	bool operator < (const A &u) const {
		return x<u.x;
	}
}q[N];
ll qp(ll x,ll y) {
	ll re=1;for(;y;y>>=1,x=x*x%mod)if(y&1)re=re*x%mod;return re;
}
inline void add(int u,int v) {
	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
void d1(int x) {
	int i;siz[x]=1;
	for(i=head[x];i;i=nxt[i]) {
		dep[to[i]]=dep[x]+1;
		d1(to[i]);siz[x]+=siz[to[i]];
		if(siz[to[i]]>siz[son[x]]) son[x]=to[i];
	}
}
void d2(int x,int t) {
	top[x]=t; int i; dfn[x]=++dfn[0]; idf[dfn[0]]=x;
	if(son[x]) d2(son[x],t);
	for(i=head[x];i;i=nxt[i]) if(to[i]!=son[x]) d2(to[i],to[i]);
}
void build(int l,int r,int p) {
	if(l==r) {sv[p]=w[idf[l]]; return ;}
	int mid=(l+r)>>1;
	build(l,mid,ls),build(mid+1,r,rs);
	sv[p]=(sv[ls]+sv[rs])%mod;
}
inline void giv(int p,ll d) {
	sum[p]=(sum[p]+d*sv[p])%mod; tag[p]+=d;
}
inline void pushdown(int p) {
	if(tag[p]) {
		giv(ls,tag[p]),giv(rs,tag[p]); tag[p]=0;
	}
}
void update(int l,int r,int x,int y,int p) {
	if(x<=l&&y>=r) {giv(p,1); return ;}
	int mid=(l+r)>>1;
	pushdown(p);
	if(x<=mid) update(l,mid,x,y,ls);
	if(y>mid) update(mid+1,r,x,y,rs);
	sum[p]=(sum[ls]+sum[rs])%mod;
}
ll query(int l,int r,int x,int y,int p) {
	if(x<=l&&y>=r) return sum[p];
	int mid=(l+r)>>1; ll re=0;
	pushdown(p);
	if(x<=mid) re=query(l,mid,x,y,ls);
	if(y>mid) re=(re+query(mid+1,r,x,y,rs))%mod;
	return re;
}
void fix(int x) {
	for(;top[x]!=1;x=fa[top[x]]) {
		update(1,n,dfn[top[x]],dfn[x],1);
	}
	update(1,n,1,dfn[x],1);
}
ll ask(int x) {
	ll re=0;
	for(;top[x]!=1;x=fa[top[x]]) {
		re+=query(1,n,dfn[top[x]],dfn[x],1);
	}re+=query(1,n,1,dfn[x],1);
	return re%mod;
}
int main() {
	n=rd(),Q=rd(),K=rd();
	int i;
	for(i=2;i<=n;i++) fa[i]=rd(),add(fa[i],i);
	dep[1]=1,d1(1),d2(1,1);
	for(i=1;i<=n;i++) h[i]=qp(i,K);
	for(i=n;i;i--) h[i]=h[i]-h[i-1];
	for(i=1;i<=n;i++) w[i]=(h[dep[i]]+mod)%mod;
	build(1,n,1);
	for(i=1;i<=Q;i++) {
		q[i].x=rd(),q[i].y=rd(); q[i].id=i;
	}
	sort(q+1,q+Q+1);
	int j=1;
	for(i=1;i<=Q;i++) {
		for(;j<=n&&j<=q[i].x;j++) {
			fix(j);
		}
		ans[q[i].id]=ask(q[i].y);
	}
	for(i=1;i<=Q;i++) printf("%lld\n",(ans[i]+mod)%mod);
}

总结：一场难度低于\(\mathrm{noip}\)的省选，\(d1t3\)的置换部分还是不错的。