PAT 甲级 1112-1115

1112 Stucked Keyboard (20分)

简单模拟。

1113 Integer Set Partition (25分)

贪心选即可。

1114 Family Property (25分)

并查集的水题，有些细节需要注意。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
int n,s[N],sz[N];
int a[N],b[N],vis[N];
struct node{
    int id,s,x,y,f;
}ans[N];
int find(int x){
    return x==s[x]?x:s[x]=find(s[x]);
}
bool cmp(node u,node v){
    return u.y*v.s==v.y*u.s?u.id<v.id:u.y*v.s>v.y*u.s;
}
void Union(int u,int v){
    u=find(u),v=find(v);
    if(v!=u){
        u<v?s[v]=u:s[u]=v;
    }
}
int main(){
    scanf("%d",&n);int tot=0;
    for(int i=0;i<1e5;i++) s[i]=i;
    for(int i=1;i<=n;i++){
        int id,f1,f2;scanf("%d%d%d",&id,&f1,&f2);vis[id]=1;
        if(~f1) Union(id,f1),vis[f1]=1;
        if(~f2) Union(id,f2),vis[f2]=1;
        int k;scanf("%d",&k);
        for(int j=0,x;j<k;j++){
            scanf("%d",&x),Union(x,id);vis[x]=1;
        }
        scanf("%d%d",&a[id],&b[id]);
    }
    for(int i=0;i<1e5;i++){
        if(vis[i]){
            int x=find(i);
            ans[x].id=x;
            ans[x].s++;
            ans[x].x+=a[i];
            ans[x].y+=b[i];
            ans[x].f=1;
        }
    }vector<node>res;
    for(int i=0;i<1e5;i++)     if(ans[i].f) res.pb(ans[i]); 
    sort(res.begin(),res.end(),cmp);printf("%d\n",res.size());
    for(int i=0;i<res.size();i++){
        printf("%04d %d %.3f %.3f\n",res[i].id,res[i].s,(double)res[i].x/res[i].s,(double)res[i].y/res[i].s);
    }
    return 0;
}

1115 Counting Nodes in a BST (30分)

考察了$BST$的建立，学到了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a,b) memset(a,b,sizeof a)
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
struct node{
    int v;
    node *l,*r;
};
node* build(node *x,int v){
    if(!x){
        x=new node();
        x->v=v;
        x->l=x->r=NULL;
    }
    else if(v<=x->v) x->l=build(x->l,v);
    else x->r=build(x->r,v);return x;
}int mx=-1,cnt[N];
void dfs(node *x,int d){
    if(!x){
        mx=max(mx,d);return;
    }
    cnt[d]++;
    dfs(x->l,d+1),dfs(x->r,d+1);
}
int main(){
    node* rt=NULL;
    int n;scanf("%d",&n);for(int i=1,x;i<=n;i++)
        scanf("%d",&x),rt=build(rt,x);
    dfs(rt,0);
    printf("%d + %d = %d\n",cnt[mx-1],cnt[mx-2],cnt[mx-1]+cnt[mx-2]);
    return 0;
}