PAT頂級2021-09題解

怎么出的這么水啊…感覺全世界都AK了啊(霧)

(也可能是姥姥錯誤估計了難度)

T1

題目大意：按照順序給你一些點，讓你插入一個二叉堆里，輸出按層次遍歷的節點編號(N<=30)

讀懂題目就能過了…動態開點寫寫就沒問題了，遍歷使用bfs就可，

C++代碼實作如下：

#include<bits/stdc++.h>
#define maxn 100005
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return w==1?x:-x;
}

int n,ls[maxn],rs[maxn],cnt,a[maxn],w[maxn];
struct node{int x,id;}p[maxn];
queue <int> q;
vector <int> v;

inline bool cmp(node a,node b){return a.id<b.id;}

inline void ins(int u,int val,int val2)
{
	if(val>w[u])
	{
		if(!rs[u]) {rs[u]=++cnt; w[cnt]=val; a[cnt]=val2; return;}
		else return ins(rs[u],val,val2);
	}
	else if(val<w[u])
	{
		if(!ls[u]) {ls[u]=++cnt; w[cnt]=val; a[cnt]=val2; return;}
		else return ins(ls[u],val,val2);
	}
}

int main()
{
	n=read(); rep(i,1,n) p[i].x=read(),p[i].id=read(); sort(p+1,p+n+1,cmp);
	a[1]=p[1].id; w[1]=p[1].x; cnt=1; rep(i,2,n) ins(1,p[i].x,p[i].id);
	q.push(1);
	while(!q.empty())
	{
		int u=q.front(); q.pop(); v.pb(u);
		if(ls[u]) q.push(ls[u]);
		if(rs[u]) q.push(rs[u]);
	}
	for(int i=0;i<v.size()-1;i++) printf("%d ",w[v[i]]);
	printf("%d",w[v[v.size()-1]]); puts("");
	for(int i=0;i<v.size()-1;i++) printf("%d ",a[v[i]]);
	printf("%d",a[v[v.size()-1]]);
	return 0;
}

T2

題目大意：給出一張有邊權的圖，有兩問:
1.求出邊權為正的點的連通塊大小，連通塊中最小的id，連通塊中最小的邊權，
2.邊權為負即為，連接這兩個點的代價(為正代價為0)，對于不存在的邊連接代價是1e4，問將所有點連接起來的，最小代價是多少，
n , m < = 1 e 5 n,m<=1e5 n,m<=1e5

兩問完全沒有關系…
第一問直接并查集寫一寫，注意一下合并的id順序是，從大的往小的合并即可，剩下的模擬實作，
第二問把一個連通塊當成一個點，直接跑Kruskal最小生成樹就沒了，

C++代碼實作如下：

#include<bits/stdc++.h>
#define maxn 1000005
#define ll long long
#define ins insert
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return w==1?x:-x;
}

int n,m,mn[maxn],sz[maxn],f[maxn],bel[maxn],U[maxn],V[maxn],W[maxn],cnt,c2,ff[maxn];
struct node{int a,b,c;}p[maxn];
struct node2{int u,v,w;}e[maxn];

inline bool cmp(node a,node b)
{
	if(a.a!=b.a) return a.a>b.a;
	else if(a.b!=b.b) return a.b>b.b;
	else return a.c<b.c;
}

inline bool cmp2(node2 a,node2 b){return a.w<b.w;}

inline int F(int x)
{
	if(f[x]==x) return x;
	return f[x]=F(f[x]);
}

inline int FF(int x)
{
	if(ff[x]==x) return x;
	return ff[x]=FF(ff[x]);
}

int main()
{
	freopen("t1.in","r",stdin);
	n=read(); m=read(); rep(i,1,n) f[i]=i,sz[i]=1,ff[i]=i,mn[i]=inf;
	rep(i,1,m)
	{
		U[i]=read(); V[i]=read(); W[i]=read();
		if(W[i]>=0)
		{
			int tx=F(U[i]),ty=F(V[i]);
			if(tx!=ty)
			{
				if(tx<ty) f[ty]=tx,sz[tx]+=sz[ty],mn[tx]=min(mn[tx],min(mn[ty],W[i]));
				else f[tx]=ty,sz[ty]+=sz[tx],mn[ty]=min(mn[ty],min(mn[tx],W[i]));
			}
			else mn[tx]=min(mn[tx],W[i]);
		}
	}
	rep(i,1,n) if(i==F(i))
	{
		p[++cnt].a=mn[i],p[cnt].b=sz[i],p[cnt].c=i;
		if(mn[i]==inf) p[cnt].a=0;
	}
	sort(p+1,p+cnt+1,cmp);
	rep(i,1,cnt)
	{
		if(i!=cnt) printf("%d-%d ",p[i].c,p[i].a);
		else printf("%d-%d",p[i].c,p[i].a);
	}
	puts("");
	
	rep(i,1,m)
	{
		if(W[i]<0)
		{
			int tx=F(U[i]),ty=F(V[i]);
			if(tx!=ty) e[++c2]={tx,ty,-W[i]};
		}
	}
	sort(e+1,e+c2+1,cmp2); ll ans=0,nw=0;
	rep(i,1,n) if(F(i)==i) nw++; nw--;
	rep(i,1,c2)
	{
		int tx=FF(e[i].u),ty=FF(e[i].v);
		if(tx!=ty) {ans+=e[i].w,ff[tx]=ty,nw--;}
	}
	cout<<(ll)ans+10000*nw<<endl;
	return 0;
}

(其實也只是單純的大模擬而已…)

T3

題目大意：兩個人玩游戲，每次一個人操作讓自己的分數+a[i]，不是輪流操作,每個人的一次操作要求，操作完后自己的分數不低于另外一個人，給出了a陣列長度為n，問有多少種合法的游戲序列?
n < = 100000 , a [ i ] < = 3 n<=100000,a[i]<=3 n<=100000,a[i]<=3

考慮 d p [ i ] [ j ] dp[i][j] dp[i][j]表示選完了前i個數，第一個人比第二個人多j分的方案數
因為 ? 3 < = j < = 3 -3<=j<=3 ?3<=j<=3，所以我們把j全部+3來避免負數，
然后對于轉移的情況分類討論就做完了，(情況很裸，大家看看代碼就明白了)

#include<bits/stdc++.h>
#define maxn 1000005
#define ll long long
#define ins insert
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

inline int read()
{
	int x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return w==1?x:-x;
}

const ll mod=1000000007;
ll dp[maxn][10],ans,n,a[maxn];

inline ll ADD(ll x,ll y){return x+y>=mod?x+y-mod:x+y;}

int main()
{
	freopen("t1.in","r",stdin);
	dp[0][3]=1; n=read(); rep(i,1,n) a[i]=read();
	rep(i,1,n)
	{
		rep(j,0,6)
		{
			if(j<3)
			{
				if(j+a[i]>=3) dp[i][j+a[i]]=ADD(dp[i][j+a[i]],dp[i-1][j]);
				if(j-a[i]>=0) dp[i][j-a[i]]=ADD(dp[i][j-a[i]],dp[i-1][j]);
				if(j-a[i]<0&&dp[i-1][j]) ans=(ans+dp[i-1][j])%mod;
			}
			else if(j>3)
			{
				if(j-a[i]<=3) dp[i][j-a[i]]=ADD(dp[i][j-a[i]],dp[i-1][j]);
				if(j+a[i]<=6) dp[i][j+a[i]]=ADD(dp[i][j+a[i]],dp[i-1][j]);
				if(j+a[i]>6&&dp[i-1][j]) ans=(ans+dp[i-1][j])%mod;
			}
			else if(j==3)
			{
				dp[i][j-a[i]]=ADD(dp[i][j-a[i]],dp[i-1][j]);
				dp[i][j+a[i]]=ADD(dp[i][j+a[i]],dp[i-1][j]);
			}
		}
	}
	rep(i,0,6) ans=(ans+dp[n][i])%mod;
	cout<<ans<<endl;
	return 0;
}

不到1.5h就AK了…當時已經有3個AK的了(好像)emm…
祝PAT越辦越好吧((霧
或許可以出個神級玩玩?(跑)