ACM | ACM Test 231228

A 点赞

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。本题就要求你写个程序，通过统计一个人点赞的纪录，分析这个人的特性。

输入格式：

输入在第一行给出一个正整数 \(N（≤1000）\) ，是该用户点赞的博文数量。随后N行，每行给出一篇被其点赞的博文的特性描述，格式为 \(“K F_1,⋯F_K”\) ，其中 \(1≤K≤10\) ，\(F_i（i=1,⋯,K）\) 是特性标签的编号，我们将所有特性标签从 \(1\) 到 \(1000\) 编号。数字间以空格分隔。

输出格式：

统计所有被点赞的博文中最常出现的那个特性标签，在一行中输出它的编号和出现次数，数字间隔1个空格。如果有并列，则输出编号最大的那个。

输入样例：

4
3 889 233 2
5 100 3 233 2 73
4 3 73 889 2
2 233 123

输出样例：

233 3

Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,t,count[1010],max=0,temp;
    cin>>t;
    memset(count,0,sizeof(count));
    while(t--){
        cin>>n;
        while(n--){
            cin>>temp;
            count[temp]++;
        }
    }
    for(int i=0;i<1010;i++){
        if(count[i]>=count[max]){
            max=i;
        }
    }
    cout<<max<<" "<<count[max]<<endl;
    return 0;
}

B 最佳情侣身高差

专家通过多组情侣研究数据发现，最佳的情侣身高差遵循着一个公式：（女方的身高）×1.09 =（男方的身高）。如果符合，你俩的身高差不管是牵手、拥抱、接吻，都是最和谐的差度。

下面就请你写个程序，为任意一位用户计算他/她的情侣的最佳身高。

输入格式：

输入第一行给出正整数 \(N（≤10）\) ，为前来查询的用户数。随后N行，每行按照“性别 身高”的格式给出前来查询的用户的性别和身高，其中“性别”为“F”表示女性、“M”表示男性；“身高”为区间 [1.0, 3.0] 之间的实数。

输出格式：

对每一个查询，在一行中为该用户计算出其情侣的最佳身高，保留小数点后2位。

输入样例：

2
M 1.75
F 1.8

输出样例：

1.61
1.96

Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    while(n--){
        double h;
        char gender;
        cin>>gender>>h;
        if(gender=='M'){
            printf("%.2lf\n",h/1.09);
        }
        if(gender=='F'){
            printf("%.2lf\n",h*1.09);
        }
    }
    return 0;
}

C 人以群分

社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。

输入格式：

输入第一行给出一个正整数 \(N（2≤N≤10^5）\)。随后一行给出 \(N\) 个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过 \(2^{31}\) 。

输出格式：

按下列格式输出：

Outgoing #: N1
Introverted #: N2
Diff = N3

其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。

输入样例1：

10
23 8 10 99 46 2333 46 1 666 555

输出样例1：

Outgoing #: 5
Introverted #: 5
Diff = 3611

输入样例2：

13
110 79 218 69 3721 100 29 135 2 6 13 5188 85

输出样例2：

Outgoing #: 7
Introverted #: 6
Diff = 9359

Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    int ee=0,ii=0,diff=0;
    if(n%2==0){
        for(int i=0;i<n/2;i++){
            ii+=a[i];
        }
        for(int i=n/2;i<n;i++){
            ee+=a[i];
        }
        diff=ee-ii;
        printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d\n",n/2,n/2,diff);
    }else{
        for(int i=0;i<n/2;i++){
            ii+=a[i];
        }
        for(int i=n/2+1;i<n;i++){
            ee+=a[i];
        }
        if(abs(ee-ii+a[n/2])>abs(ee-ii-a[n/2])){
            ee+=a[n/2];
            printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d\n",n/2+1,n/2,ee-ii);
        }else{
            ii+=a[n/2];
            printf("Outgoing #: %d\nIntroverted #: %d\nDiff = %d\n",n/2,n/2+1,ee-ii);
        }
    }
    return 0;
}

D 悄悄关注

新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。

输入格式：

输入首先在第一行给出某用户的关注列表，格式如下：

人数N 用户1 用户2 …… 用户N

其中N是不超过 \(5000\) 的正整数，每个用户 \(i（i=1, ..., N）\) 是被其关注的用户的ID，是长度为4位的由数字和英文字母组成的字符串，各项间以空格分隔。

之后给出该用户点赞的信息：首先给出一个不超过10000的正整数M，随后M行，每行给出一个被其点赞的用户ID和对该用户的点赞次数（不超过1000），以空格分隔。注意：用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户，在点赞信息中也没有重复用户。

输出格式：

我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人，很可能是其悄悄关注的人。根据这个假设，请你按用户ID字母序的升序输出可能是其悄悄关注的人，每行1个ID。如果其实并没有这样的人，则输出“Bing Mei You”。

输入样例1：

10 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao
8
Magi 50
Pota 30
LLao 3
Ammy 48
Dave 15
GAO3 31
Zoro 1
Cath 60

输出样例1：

Ammy
Cath
Pota

输入样例2：

11 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao Pota
7
Magi 50
Pota 30
LLao 48
Ammy 3
Dave 15
GAO3 31
Zoro 29

输出样例2：

Bing Mei You

Code

#include<bits/stdc++.h>
using namespace std;

bool check(string* array, string target,int len){
    for(int i=0;i<len;i++){
        if(array[i]==target){
            return true;
        }
    }
    return false;
}

int main(){
    int n;
    cin>>n;
    string follow[n];
    for(int i=0;i<n;i++){
        cin>>follow[i];
    }
    int m;
    cin>>m;
    vector<pair<string,int> > like;
    string t1;
    int t2;
    int sum=0;
    for(int i=0;i<m;i++){
        cin>>t1>>t2;
        like.push_back({t1,t2});
        sum+=t2;
    }
    double ave=1.0*sum/m;
    // cout<<ave<<endl;
    vector<string> ans;
    for(int i=0;i<m;i++){
        if(like[i].second>ave && !check(follow,like[i].first,n)){
            ans.push_back(like[i].first);
        }
    }
    if(ans.empty()){
        cout<<"Bing Mei You"<<endl;
    }else{
        sort(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++){
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}

E 功夫传人

一门武功能否传承久远并被发扬光大，是要看缘分的。一般来说，师傅传授给徒弟的武功总要打个折扣，于是越往后传，弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子（或者是吃到了灵丹、挖到了特别的秘笈），会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。

这里我们来考察某一位祖师爷门下的徒子徒孙家谱：假设家谱中的每个人只有\(1\)位师傅（除了祖师爷没有师傅）；每位师傅可以带很多徒弟；并且假设辈分严格有序，即祖师爷这门武功的每个第\(i\)代传人只能在第\(i-1\)代传人中拜1个师傅。我们假设已知祖师爷的功力值为 \(Z\)，每向下传承一代，就会减弱\(r%\)，除非某一代弟子得道。现给出师门谱系关系，要求你算出所有得道者的功力总值。

输入格式：

输入在第一行给出3个正整数，分别是：\(N（≤10^5）\)——整个师门的总人数（于是每个人从0到N−1编号，祖师爷的编号为0）；\(Z\)——祖师爷的功力值（不一定是整数，但起码是正数）；\(r\) ——每传一代功夫所打的折扣百分比值（不超过\(100\)的正数）。接下来有\(N\)行，第\(i\)行\(（i=0,⋯,N−1）\)描述编号为i的人所传的徒弟，格式为：\(K_i ID[1] ID[2] ⋯ ID[K_i]\)其中\(K_i\)是徒弟的个数，后面跟的是各位徒弟的编号，数字间以空格间隔。\(K_i\)为零表示这是一位得道者，这时后面跟的一个数字表示其武功被放大的倍数。

输出格式：

在一行中输出所有得道者的功力总值，只保留其整数部分。题目保证输入和正确的输出都不超过 \(10^{10}\)。

输入样例：

10 18.0 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3

输出样例：

404

Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    double z,r;
    cin>>n>>z>>r;
    double power[n];
    power[0]=z;
    int count,stu;
    double sum=0.0;
    vector<vector<int> > v(n);
    unordered_map<int,int> burst;
    for(int i=0;i<n;i++){
        cin>>count;
        if(count==0){
            cin>>stu;
            burst[i]=stu;
        }else for(int j=0;j<count;j++){
                cin>>stu;
                v[i].push_back(stu);
            }
    }
    queue<int> q;
    q.push(0);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        if(v[now].size()==0){
            sum+=power[now]*burst[now];
        }else for(int i=0;i<v[now].size();i++){
            q.push(v[now][i]);
            power[v[now][i]]=power[now]*(1-r/100);
        }
    }
    // for(int i=0;i<n;i++){
    //     cin>>count;
    //     if(count==0){
    //         cin>>stu;
    //         sum+=power[i]*stu;
    //     }else{
    //         for(int j=0;j<count;j++){
    //             cin>>stu;
    //             power[stu]=power[i]*(1-(r/100));
    //         }
    //     }
    // }
    printf("%d\n",(int)sum);
    return 0;
}