目录

• A - Binarize It
• B - g2g c u l8r
• C - Tip to be Palindrome
• D - Soccer Standings
• E - NIH Budget
• F - Interstellar Love
• G - Plate Spinning
• H - The Eternal Quest for Caffeine
• I - Pegasus Circle Shortcut
• J - Lowest Common Ancestor

2021年度训练联盟热身训练赛第二场

A - Binarize It

签到题

#include <iostream>

using namespace std;

int main()
{
    int n, t, a[20] = {1};
    for (int i = 1; i < 20; i++)
    {
        a[i] = 1<<i;
    }
    cin >> n;
    while (n--)
    {
        cin >> t;
        printf("Input value: %d\n", t);
        for (int i = 1; i < 20; i++)
        {
            if (a[i] >= t)
            {
                printf("%d\n\n", a[i]);
                break;
            }
        }
    }
    return 0;
}

B - g2g c u l8r

用map很简单，后面的处理用到了getline和stringstream

#include <iostream>
#include <algorithm>
#include <sstream>
#include <map>

using namespace std;

int main()
{
    map<string, string> Map;
    string s, t;
    int n;
    cin >> n;
    while (n--)
    {
        cin >> s;
        getchar();//这句话比较重要
        getline(cin, t);
        Map[s] = t;
    }
    cin >> n;
    getchar();//这句话比较重要
    while (n--)
    {
        int cnt = 0;
        getline(cin, t);
        stringstream ss(t);
        while (ss >> s)
        {
            if (cnt)
            {
                cout << " ";
            }
            if (Map[s] != "")
            {
                cout << Map[s];
            }
            else
            {
                cout << s;
            }
            cnt++;
        }
        cout << endl;
    }
    return 0;
}

C - Tip to be Palindrome

理解了题目之后就是签到题了。

小费是占账单20%以上的整数，期望最后总账单（原来账单加小费）是个回文的数，输出原账单、小费和总账单。

#include <iostream>

using namespace std;

bool judge(int);

int main()
{
    int n, t;
    cin >> n;
    while (n--)
    {
        cin >> t;
        int i = t + ceil(t*0.2);
        for (; i <= 12021; i++)
        {
            if (judge(i))
            {
                printf("Input cost: %d\n%d %d\n\n", t, i-t, i);
                break;
            }
        }
    }
    return 0;
}
bool judge(int x)
{
    int a[10] = {}, i = 0;
    for (; i < 10 && x; x/=10, i++)
    {
        a[i] = x%10;
    }
    for (int j = 0; j <= i/2; j++)
    {
        if (a[j] != a[i-j-1])
        {
            return 0;
        }
    }
    return 1;
}

D - Soccer Standings

纯模拟，读清楚题，理解清楚之后就容易写了，只需要维护一个结构体，重载运算符<，进行排序后直接输出，over。

题目中有几个点要好好看：

1. “name， points， wins， losses， draws， goals scored， goals allowed”
   队伍名、得分、赢局数、输局数、平局数、进球数、对手进球数。
2. the total number of goals scored against them (goals allowed, for short).
   也就是上面的goals allowed的定义。
3. Teams are ordered according to points, from highest to lowest. In the event of a tie in points, the team that has a higher goal difference comes first. The goal difference is defined as the total number of goals scored by the team minus the total number of goals scored against them.
   If there is still a tie (i.e., two or more teams have the same points and the same goal differences), the team with higher total goals scored comes first. If even this is tied, the team whose name comes first in alphabetical order goes first.
   这是排序规则。详细见代码重载运算符<。

#include <iostream>
#include <algorithm>
#include <map>
#include <cstring>

using namespace std;

struct Team
{
    string name;
    int wins;
    int losses;
    int draws;
    int goals_scored;
    int goals_allowed;
    int points;
    bool operator<(Team & b) const {
        if (points != b.points) {
            return points > b.points;
        }
        if (goals_scored - goals_allowed != b.goals_scored - b.goals_allowed) {
            return goals_scored - goals_allowed > b.goals_scored - b.goals_allowed;
        }
        if (goals_scored != b.goals_scored) {
            return goals_scored > b.goals_scored;
        }
        return name < b.name;
    }
    void print() {
        cout << name;
        printf(" %d %d %d %d %d %d\n", points, wins, losses, draws, goals_scored, goals_allowed);
    }
    void Clear() {
        points = wins = losses = draws = goals_scored = goals_allowed = 0;
    }
} teams[50];

void update(int a, int b, int goal1, int goal2);

int main()
{
    map<string, int> Map;
    int n, t, g, goal1, goal2;
    cin >> n;
    for (int p = 1; p <= n; p++)
    {
        string t1, t2;
        cin >> t >> g;
        for (int i = 1; i <= t; i++)
        {
            cin >> teams[i].name;
            Map[teams[i].name] = i;
            teams[i].Clear();
        }
        
        for (int i = 1; i <= g; i++)
        {
            cin >> t1 >> goal1 >> t2 >> goal2;
            int a = Map[t1], b = Map[t2];
            update(a, b, goal1, goal2);
        }
        sort(teams+1, teams+t+1);
        
        printf("Group %d:\n", p);
        for (int i = 1; i <= t; i++)
        {
            teams[i].print();
        }
        printf("\n");
    }
    return 0;
}

void update(int a, int b, int goal1, int goal2)
{
    teams[a].goals_scored  += goal1;
    teams[a].goals_allowed += goal2;
    teams[b].goals_scored  += goal2;
    teams[b].goals_allowed += goal1;
    if (goal1 > goal2)
    {
        teams[a].wins++;
        teams[b].losses++;
        teams[a].points += 3;
    }
    else if (goal1 < goal2)
    {
        teams[a].losses++;
        teams[b].wins++;
        teams[b].points += 3;
    }
    else
    {
        teams[a].draws++;
        teams[b].draws++;
        teams[a].points++;
        teams[b].points++;
    }
}

E - NIH Budget

分组背包模板题，看的书上的代码，发现这一句

memset(f, 0xcf, sizeof(f));应该改成 memset(f, 0, sizeof(f));

#include <iostream>
#include <algorithm>
#include <sstream>
#include <map>
#include <cstring>

using namespace std;

int f[100005], v[15][5], w[15][5];
int main()
{
    int n;
    cin >> n;
    for (int p = 1; p <= n; p++)
    {
        int d, b;
        cin >> d >> b;
        for (int j = 1; j <= d; j++)
        {
            for (int k = 1; k <= 4; k++)
            {
                cin >> v[j][k] >> w[j][k];
            }
        }
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= d; i++)
        {
            for (int j = b; j >= 0; j--)
            {
                for (int k = 1; k <= 4; k++)
                {
                    if (j >= v[i][k])
                    {
                        f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                    }
                }
            }
        }
        if (f[b] < 0) f[b] = 0;
        printf("Budget #%d: Maximum of %d lives saved.\n\n", p, f[b]);
    }
    return 0;
}

F - Interstellar Love

判断有无环时，可以通过判断结点数 -1 是不是等于边数来看。

#include <iostream>
#include <cstring>

using namespace std;

bool Map[1005][1005], vis[1005];
int f[1005], cnt[1005], cnt2[1005], n, s, c, x, y;

void init()
{
    memset(Map, 0, sizeof(Map));
    memset(f, 0, sizeof(f));
    memset(cnt, 0, sizeof(cnt));
    memset(cnt2, 0, sizeof(cnt2));
    for (int i = 1; i <= 1000; i++)
    {
        f[i] = i;
        cnt[i] = 1; // 结点数初始化为1
    }
}

int Find(int x)
{
    if (x != f[x])
    {
        f[x] = Find(f[x]);
    }
    return f[x];
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        init();
        int ans1 = 0, ans2 = 0;
        cin >> s >> c;
        for (int j = 1; j <= c; j++)
        {
            cin >> x >> y;
            Map[x][y] = Map[y][x] = 1;
            int a = Find(x), b = Find(y);
            if (a != b)
            {
                f[b] = a;
                cnt[a] += cnt[b]; // 结点个数
            }
            cnt2[a] += cnt2[b]+1; // 边的个数
        }
        for (int j = 1; j <= s; j++)
        {
            if (f[j] == j && cnt[j] > 1)
            {
                ans1++;
                if (cnt[j] != cnt2[j]+1)
                {
                    ans2++;
                }
            }
        }
        printf("Night sky #%d: %d constellations, of which %d need to be fixed. \n\n", i, ans1, ans2);
    }
    return 0;
}

G - Plate Spinning

n×0.5×5>p时是肯定掉的，但是n=1时是个例外，n=1时肯定不会掉

#include <iostream>

using namespace std;

int main()
{
    int a, n, p;
    cin >> a;
    for (int i = 1; i <= a; i++)
    {
        cin >> n >> p;
        printf("Circus Act %d:\n", i);
        if (n == 1 || n * 5 <= p * 2)
        {
            cout << "Chester can do it!" << endl << endl;
        }
        else
        {
            cout << "Chester will fail!" << endl << endl;
        }
    }
    return 0;
}

H - The Eternal Quest for Caffeine

看不懂题，我尽力了。。

I - Pegasus Circle Shortcut

啊啊啊，这一句太重要了

if (fabs(O.x) + fabs(O.y) + fabs(S.x) + fabs(S.y) + fabs(E.x) + fabs(E.y) < 1e-9)
{
	return 0;
}

弧长公式：

s和e是圆上两点，O是圆心

#include <iostream>
#include <cmath>

using namespace std;

struct Point
{
    double x;
    double y;
};

double length(Point a, Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
double arc_length(Point a, Point b, Point O)
{
    return 2*asin(length(a, b)/(2*length(a, O)))*length(a, O);
}

int main()
{
    Point O, S, E, t;
    int cnt = 0, n;
    while (cin >> O.x >> O.y >> S.x >> S.y >> E.x >> E.y)
    {
        if (fabs(O.x) + fabs(O.y) + fabs(S.x) + fabs(S.y) + fabs(E.x) + fabs(E.y) < 1e-9)
        {
            return 0;
        }
        cnt++;
        
        double arc = arc_length(S, E, O);
        double pathlength = 0;
        
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> t.x >> t.y;
            pathlength += length(S, t);
            S = t;
        }
        pathlength += length(S, E);
        
        if (arc < pathlength)
        {
            printf("Case #%d: Stick to the Circle.\n\n", cnt);
        }
        else
        {
            printf("Case #%d: Watch out for squirrels!\n\n", cnt);
        }
    }
    return 0;
}

J - Lowest Common Ancestor

写出两个数的二进制会发现，最近公共祖先就是公共前缀转换成16进制。

将16进制和二进制的转换用map实现，注意16转2时去掉先导零以及2转16时辅助用的先导零

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

void getans(int);
void init();

string s, t;
map<char, string> Map1; // 16 转 2
map<string, char> Map2; // 2 转 16

int main()
{
    init(); // 设置 Map1和 Map2
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> s >> t;
        getans(i);
    }
    return 0;
}

void init()
{
    string a[16] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
    char b[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
    for (int i = 0; i < 16; i++)
    {
        Map1[b[i]] = a[i];
        Map2[a[i]] = b[i];
    }
}

void getans(int k)
{
    printf("Case #%d: ", k);
    string a, b;
    // 转二进制
    int len1 = s.size(), len2 = t.size(), i = 0;
    for (i = 0; i < len1; i++)
    {
        a += Map1[s[i]];
    }
    for (i = 0; i < len2; i++)
    {
        b += Map1[t[i]];
    }
    
    // 去掉先导零
    i = 0;
    while (a[i] == '0') i++;
    a = a.substr(i);

    i = 0;
    while (b[i] == '0') i++;
    b = b.substr(i);

    // 找到公共前缀的分界线
    len1 = a.size(), len2 = b.size();
    for (i = 0; i < len1 && i < len2; i++)
    {
        if (a[i] != b[i])
        {
            break;
        }
    }
    // 答案的二进制存到 ans里
    string ans(a, 0, i);
    // 加先导零
    while (ans.size()%4)
    {
        ans = '0' + ans;
    }
    len1 = ans.size();
    for (int i = 0; i < len1; i += 4)
    {
        a = ans.substr(i, 4); // 每四位二进制转化成一位16进制
        cout << Map2[a];
    }
    printf("\n\n");
}