【HCOI-(-1)】测试赛 题解

· · 个人记录

广告

欢迎去 hydro 里 ZhanPJ 的域，比赛题目同步更新，也有一些被自己打掉的 idea 的题目在里面。

亲属关系

根据提议模拟即可。

#include <iostream>
#include <cstdio>
using namespace std;
bool map[105][105][5];
int gender[105];
int main(){
//  freopen(".\\test\\concern-20.in","r",stdin);
//  freopen(".\\test\\concern-20.out","w",stdout);
    int n,m,T,u,v,g;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&gender[i]);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&g);
        if(g==1){
            map[u][v][gender[u]]=1;
            map[v][u][gender[v]]=1;
        }else if(g==2){
            map[u][v][2]=1;
            map[v][u][3]=1;
        }else if(g==3){
            map[u][v][3]=1;
            map[v][u][2]=1;
        }
    }
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&u,&g);
        bool flag=1;
        for(int i=1;i<=n;i++){
            if(map[u][i][g]){
                printf("%d ",i);
                flag=0;
            }
        }
        if(flag)printf("NULL");
        printf("\n");
    }

    return 0;
}

人品

考虑贪心：将功率大的机器尽可能给需要提升人品的人。

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int a[100005],b[100005];
template<typename Type>inline void read(Type &x){
    Type y=1;x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        y=(ch=='-'?-1:y);
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    x*=y;
}
bool cmp(int a,int b){return a>b;}
int main(){
    int T,n,m,ans;
    read(T);
    while(T--){
        ans=0;
        read(n);read(m);
        for(int i=1;i<=n;i++)read(a[i]);
        for(int j=1;j<=m;j++)read(b[j]);
        sort(a+1,a+n+1);
        sort(b+1,b+m+1,cmp);
        for(int i=1,j=1;i<=n;i++){
            if(a[i]>0)continue;
            a[i]=-a[i];
            double answer=ceil(a[i]*1.0/b[j]);
            ans=max(ans,int(answer));j++;
        }
        printf("%d\n",ans);
    }

    return 0;
}

游戏

根据提示：红黑树的时间复杂度稳定，为 log_2n，计算可得时间复杂度约为 O((m+n)log_2n)，超时。

考虑空间换时间。我们发现单词前面的几个字母可能一致，那么我们可以将这几个单词视为同一个根节点下的不同子节点演化出来的，建树查询复杂度一致，令 S(s_{i}) 表示单词长度，则时间复杂度为 O((n+m)S(s_{i}))，其中 S(s_{i}) 最大为 10，忽略常数即 O(n+m)。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXC=26+5;
const int N=500050;
struct node{
    char ch;
    bool myself=0;//标记直到这个字母，才成立单词，比如字典中只有 ass 但是读取 as，此时 as 不成立。
    int next[MAXC];
}tree[2*N];
int top=0;
int yz[256];
char s[25],ans[25];
void intree(int id,char s[]){
    if(strlen(s)==0){tree[id].myself=1;return ;}
    if(tree[id].next[yz[s[0]]]==0){
        top++;
        tree[id].next[yz[s[0]]]=top;
        tree[top].ch=s[0];
    }
    intree(tree[id].next[yz[s[0]]],s+1);
}
bool findtree(int id,char s[]){
    if(strlen(s)==0)return tree[id].myself;
    if(tree[id].next[yz[s[0]]]==0)return false;
    return findtree(tree[id].next[yz[s[0]]],s+1);
}
int main(int argc,char **argv){
    //if(argc>=2)freopen(argv[1],"r",stdin);
    //if(argc>=3)freopen(argv[2],"w",stdout);

    int n,m,len;
    scanf("%d%d",&n,&m);
    for(int i='A',j=1;i<='Z';i++,j++)yz[i]=j;
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        len=strlen(s);
        for(int i=0;i<len;i++){//全部大写
            if(s[i]>='a'&&s[i]<='z')s[i]=s[i]-'a'+'A';
        }
        intree(0,s);
    }
    for(int i=1;i<=m;i++){
        scanf("%s",s);
        strcpy(ans,s);
        len=strlen(s);
        for(int i=0;i<len;i++){//全部大写
            if(s[i]>='a'&&s[i]<='z')s[i]=s[i]-'a'+'A';
        }
        if(s[0]=='.'||s[0]=='?'||s[0]==','||s[0]=='!'||findtree(0,s))printf("%s ",ans);//或运算符优先级问题,节约时间复杂度
    }

    return 0;
}

ikun的斗争

因为要把所有的人遍历一遍，所以我们考虑最小生成树。

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,k;
int father[5005];
struct node{
    int u,v,data;
}edge[200005];
long long ans;
bool cmp(node a,node b){return a.data<b.data;}
bool cmp2(node a,node b){return a.data>b.data;}
int find(int x){
    while(x!=father[x])x=father[x]=father[father[x]];
    return x;
}
bool kruskal(){//不保证图联通
    ans=0;
    int G_edge=0;
    for(int i=1;i<=n+1;i++)father[i]=i;
    for(int i=1;i<=m;i++){
        int u=find(edge[i].u),v=find(edge[i].v);
        if(u==v)continue;
        ans+=edge[i].data;
        father[v]=u;
        if(++G_edge==n)return 1;
    }
    return 0;
}
template<typename Type>inline void read(Type &x){
    Type y=1;x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        y=(ch=='-'?-1:y);
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    x*=y;
}
int main(){
    int T;
    read(T);
    while(T--){
        read(n);read(k);read(m);
        for(int i=1;i<=m;i++)read(edge[i].u),read(edge[i].v),read(edge[i].data);
        sort(edge+1,edge+m+1,cmp);
        if(!kruskal())printf("Go west.\nNo Answer!\n");
        else{
            if(ans>k)printf("Go west.\n%lld\n",ans-k);
            else printf("Nice!\n%lld\n",ans);
            sort(edge+1,edge+m+1,cmp2);
            kruskal();
            printf("%lld\n",ans);
        }
    }

    return 0;
}