11.10 模拟赛小记

特附今日闲话。

100+95+0+20.

A.数字操作(num)

赛时其实是看了一下样例和数据范围的一档说均为质数，无端的想到 gcd 于是就秒掉了。

其实因为这个减数、统计不重复的过程就类似于辗转相除吧。然后就没了。没什么说的，存一下码好了。

#include<bits/stdc++.h>
using namespace std;
int T,n;
int gcd(int x,int y){
	if(!y) return x;
	return gcd(y,x%y);
}
void solve(){
	scanf("%d",&n);
	int k=0,mx=0,ans=0;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		if(!k) k=x;
		else k=gcd(k,x);
		mx=max(mx,x);
	}
	for(int i=k;i<=mx;i+=k) ans++;
	printf("%d\n",ans);
}
int main(){
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	scanf("%d",&T);
	while(T--) solve();
} 

B.最短路(path)

次短路统计的板子喔，大概就是分两维的 dij。在 9.26 的这一场比赛 里做过这道题所以切了。考场一直在担心 dij 能不能跑过去，后来才意识到本题常见做法只有 dij 了...

你问我为什挂了 5 分？因为没有判次短路是不是严格符合要求（比最短路小 1）。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;
const ll mod=998244353;
int n,m;
ll cnt[N][2];
int vis[N][2],d[N][2];
int idx,e[N],nxt[N],head[N];
void add(int x,int y){
	e[++idx]=y;
	nxt[idx]=head[x];
	head[x]=idx;
}
void dij(){
	priority_queue<pair<pair<int,int>,int> > q;
	memset(d,0x3f,sizeof d);
	q.push(make_pair(make_pair(0,1),0));
	d[1][0]=0;
	cnt[1][0]=1;
	while(q.size()){
		int x=q.top().first.second,t=q.top().second;
		q.pop();
		if(vis[x][t]) continue;
		vis[x][t]=1;
		for(int i=head[x];i;i=nxt[i]){
			if(d[e[i]][0]>d[x][t]+1){
				d[e[i]][1]=d[e[i]][0],cnt[e[i]][1]=cnt[e[i]][0];
				q.push(make_pair(make_pair(-d[e[i]][1],e[i]),1));
				d[e[i]][0]=d[x][t]+1,cnt[e[i]][0]=cnt[x][t];
				q.push(make_pair(make_pair(-d[e[i]][0],e[i]),0));
			}
			else if(d[e[i]][0]==d[x][t]+1) cnt[e[i]][0]=(cnt[e[i]][0]+cnt[x][t])%mod;
			else if(d[e[i]][1]>d[x][t]+1){
				d[e[i]][1]=d[x][t]+1,cnt[e[i]][1]=cnt[x][t];
				q.push(make_pair(make_pair(-d[e[i]][1],e[i]),1));
			}
			else if(d[e[i]][1]==d[x][t]+1) cnt[e[i]][1]=(cnt[e[i]][1]+cnt[x][t])%mod;
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y); 
		add(x,y);
		add(y,x);
	}
	dij();
	if(d[n][0]+1!=d[n][1]||!d[n][0]||d[n][0]==0x3f3f3f3f) puts("0");
	else printf("%lld\n",cnt[n][1]);
}

C.火花(fire)

正解还没补，大概是离线下来线段树 + 并查集。我觉得我赛前只需要尽力补一补暴力能力。

赛时，好像最后一个小时脑子都是糊涂的。想当然的写了个链的性质赛后就发现假了。20pts 的爆搜又不会写。

所以赶紧补了一下树上搜。现在会了。这是 20pts 的码。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+110;
int n,q,k;
ll ans;
int vis[N];
int idx,e[N],w[N],nxt[N],head[N];
void add(int x,int y,int z){
	e[++idx]=y;
	w[idx]=z;
	nxt[idx]=head[x];
	head[x]=idx;
}
void dfs(int x){
	vis[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		if(w[i]>k) continue;
		if(!vis[e[i]]){
			ans+=w[i];
			dfs(e[i]);
		}
	}
} 
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		int x,z;
		scanf("%d%d",&x,&z);
		add(x,i,z);
	}
	scanf("%d",&q);
	while(q--){
		int u;
		scanf("%d%d",&u,&k);
		dfs(u);
		printf("%lld\n",ans);
		memset(vis,0,sizeof vis);
		ans=0;
	}
}

D.互斥(exc)

同上，感觉不需要补了，这是 30pts 的暴力。赛时为什么暴力还挂成 20pts 了呢，因为快速幂忘记开 long long 炸掉了。

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=2e5+10;
const ll mod=998244353;
int n,a,b;
ll ans;
int t[N];
map<ull,int> vis;
bool check(int m){
	if(m==1) return 1;
	for(int i=1;i<=m;i++)
		for(int j=i+1;j<=m;j++)
			if(t[i]*a==t[j]||t[j]*a==t[i]||t[i]*b==t[j]||t[j]*b==t[i]) return 0;
	return 1;
}
void js(int m){
	ull tot=0;
	for(int i=1;i<=m;i++) tot=tot*131+t[i]*131;
	if(!vis[tot]){vis[tot]=1;ans++;}
}
void dfs(int x,int tot){
	if(check(tot)) js(tot);
	if(x==n+1) return;
	t[tot+1]=x;
	dfs(x+1,tot+1);
	t[tot+1]=0;
	dfs(x+1,tot);
}
ll ksm(ll a,ll b){
	ll tot=1;
	while(b){
		if(b&1) tot=(tot*a)%mod;
		b>>=1;
		a=(a*a)%mod;
	}
	return tot%mod;
}
int main(){
	scanf("%d%d%d",&n,&a,&b);
	if(a==1&&b==1){
		printf("%lld",ksm(2,n));
		return 0;
	}
	if(n<=15){
		dfs(1,0);
		printf("%lld",ans);
		return 0;
	}
}