怎么出的这么水啊…感觉全世界都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越办越好吧((雾
或许可以出个神级玩玩?(跑)