Logo xoyo的博客

博客

2025假期赛题解

2025-08-25 15:47:55 By xoyo

A. LEAP YEARS

签到题，很朴素的平闰年问题，加上对年份时间的判断，2024 前 was ，2024年 is ，2024 后 will be ,代码如下.

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

const int N = 2310;
int ye[N];

int main(){
    for(int i = 1582; i <= 2300; i ++ )
        if(i % 4 == 0 && i % 400 != 0 || i % 400 == 0)ye[i] = 1;

    int t;
    cin >> t;
    while(t -- ){
        int n;
        cin >> n;
        cout << n << " ";

        if(n < 2024)cout << "was a ";
        else if(n == 2024)cout << "is a ";
        else cout << "will be a ";

        if(ye[n])cout << "leap year.";
        else cout << "common year.";
        puts("");
    }    

    return 0;
}

B. DISCOUNTS

主要考察每个答案的处理方式，细节在于空格和两位小数

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

string s;
int zh, l, fr, t, n;

int main(){
    getline(cin, s);
    cin >> zh >> l >> fr;
    cin >> t;
    cout << s << endl;
    while(t -- ){
        cin >> n;
        printf("Buy %d, pay for %d, get %d free. Save $%d.%02d.", n, n - n / (fr + 1), n / (fr + 1), n / (fr + 1) * l >=100?n / (fr + 1) * zh + n / (fr + 1) * l / 100 : n / (fr + 1) * zh, n / (fr + 1) * l % 100);
//        购买个数就是n 
//        免费的个数是第fr + 1个
//        购买的个数减去免费的个数就是付费的个数(注意先输出购买的个数再输出免费的个数) 
//        花的钱就是分和元分别乘购买个数，然后把能换算成元的零钱全都换算成元，也就是每有 100 美分变成 1 美元，然后美分只留下换算不了的部分也就是取余 100 ，用点隔开视作小数
    }
    return 0;
}

C. CRIME SCENES

考察二维数组的应用，这里用一个数组dist[x][y]表示在（x,y）处有几件物品，前半段输入时记录进dist数组，后半部分输入时取用对应坐标的数组位置的计数器累加进答案

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

const int N = 110;
int dist[N][N];
int x, y;
int ans;
int n, m;

int main(){//记录每个位置物品数量
    cin >> x >> y;
    cin >> n;
    for(int i = 0; i < n; i ++ ){
        int a, b;
        cin >> a >> b;
        dist[a][b] ++ ;
    }

    cin >> m;
    while(m -- ){//查找
        int a, b;
        cin >> a >> b;
        ans += dist[a][b];
    }

    cout << ans << endl;

    return 0;
}

D. FOOTBALL POOLS

十六行输入，先输入八行比赛队伍名，再输入对应八行比分，有胜者则计 1 分，平局但有进球计 2 分，均未进球 3 分，把平局的对局记录进数组并计数，按序输出即可，如果得分是 8 说明没有平局，输出“No scoring draws”.

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

string s[10];
string t[10];
int ans, idx = -1;

int main(){
    for(int i = 0; i < 8; i ++ ){
        getline(cin, s[i]);
    }
    for(int i = 0; i < 8; i ++ ){
        int x, y;
        cin >> x >> y;
        if(x != y)ans ++ ;
        else if(x == 0)ans += 2;
        else{
            ans += 3;
            t[ ++ idx] = s[i];
        }
    }

    printf("Points scored: %d\n", ans);
    if(ans == 8){puts("No scoring draws");return 0;}
    else
    for(int i = 0; i <= idx; i ++ ){
        cout << t[i] << endl;
    }
    return 0;
}

E. CHECK DIGITS

按照题意以此操作即可

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

long long ans, idx, t;

int main(){
    while(cin >> ans){
        if(!ans)return 0;
        idx = ans;
        t = 0;
        for(int i = 2; idx > 0; i ++ , idx /= 10){
            t += (idx % 10) * i;
        }
        t = 11 - t % 11;
        if(t == 11 )t = 0;
        if(t != 10){
            ans *= 10;
            ans += t;
        }
        else {cout << ans << " -> " << "rejected" << endl;continue;}
        cout << ans / 10 << " -> " <<  ans << endl;

    }

    return 0;
}

F. HEX SEARCH

依次判断，遍历两遍，先把不是十六进制合法字符的部分输出出来，然后每行计算剩余十六进制字符连接起来的的十六进制数转换成十进制是多少

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

const int N = 15;
char e[N][N];
int ans;
int n;
bool t = false;

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ){//输入过程中直接把非十六进制字符输出出来，注意没有的情况，打个标记取消换行
        for(int j = 1; j <= n; j ++ ){
        cin >> e[i][j];
        if(!(e[i][j] >= '0' && e[i][j] <= '9' || e[i][j] >= 'A' && e[i][j] <= 'F'))cout << e[i][j],t = true;
        }

    }
    if(t)puts("");

    for(int i = 1; i <= n; i ++ ){//计算十六进制字符连接成十六进制数的值
        int k = 0;
        ans = 0;
        for(int j = n;j >= 1; j -- ){
            int idx = 0;
            if(e[i][j] >= 'A' && e[i][j] <= 'F')idx = e[i][j] - 'A' + 10;
            else if(e[i][j] >= '0' && e[i][j] <= '9')idx = e[i][j] - '0';
            else idx = -1;
            if(idx != -1){
                ans += (int)pow((double)16, (double)k) * idx;
                k ++ ;
            }
        }
        if(k)cout << ans << endl;
    }

    return 0;
}

G. THE GEESE OF LOOWATER

简单的贪心，对于每个头我们要用最小的代价砍掉.

身高高的骑士开价高，所以如果拿高身高的骑士去砍小头就是浪费人才了，例如有一个头的直径是20，骑士有100,和21两个，显然选择21的骑士.

所以分别对头的直径和骑士的身高进行排序，从小到大依次尝试，如果砍完头了就输出答案，如果骑士没了还有头就输出“Loowater is doomed!”.

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

const int N = 20010; 
int n, m;
int he[N], kn[N];
int ans;

int main(){
        scanf("%d%d",&n,&m);
        ans = 0;

        for(int i = 0; i < n; i ++ )
        cin >> he[i];
        for(int i = 0; i < m; i ++ )
        cin >> kn[i];

        sort(he, he + n);
        sort(kn, kn + m);

        int idx = 0;
        for(int i = 0; i < m; i ++ ){
            if(kn[i] >= he[idx] && idx < n)idx ++ , ans += kn[i];
        }
        if(idx == n)cout << ans << endl;
        else puts("Loowater is doomed!");
    return 0;
}

H. CROQUET FREE TURNS

直接暴力讨论所有情况输出即可，注意单词拼写和球员输出顺序

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

string na[5];
int sc[5];
bool ch = true;

int main(){
    for(int i = 0; i < 4; i ++ )
        cin >> na[i] >> sc[i];

    if(sc[0] > sc[1])swap(na[0], na[1]),swap(sc[0], sc[1]);
    if(sc[2] > sc[3])swap(na[2], na[3]),swap(sc[2], sc[3]);

    if(sc[1] > sc[2] && sc[3] > sc[0]){
        double x = sc[1] - sc[2];
        x /= 2;
        if(x > (int)x)x = (int)x + 1, ch = false;
        double y = sc[3] - sc[0];
        y /= 2;
        if(y > (int)y){
            y = (int)y;
            if(ch)y ++ ;
        }
        cout << na[3] << " receives " << y << " free turns from " << na[0] << '.' << endl;
        cout << na[1] << " receives " << x << " free turns from " << na[2] << '.' << endl;
    }
    else if(sc[0] > sc[3]){
        double x = sc[1] - sc[2];
        x /= 2;
        if(x > (int)x)x = (int)x + 1, ch = false;
        double y = sc[0] - sc[3];
        y /= 2;
        if(y > (int)y){
            y = (int)y;
            if(ch)y ++ ;
        }
        if(y != 0)
        cout << na[0] << " receives " << y << " free turns from " << na[3] << '.' << endl;
        else cout << "No free turns between " << na[0] << " and " << na[3] << '.' << endl;
        if(x != 0)
        cout << na[1] << " receives " << x << " free turns from " << na[2] << '.' << endl;
        else cout << "No free turns between " << na[1] << " and " << na[2] << '.' << endl;
    }
    else if(sc[2] > sc[1]){
        double x = sc[2] - sc[1];
        x /= 2;
        if(x > (int)x)x = (int)x + 1, ch = false;
        double y = sc[3] - sc[0];
        y /= 2;
        if(y > (int)y){
            y = (int)y;
            if(ch)y ++ ;
        }
        if(y != 0)
        cout << na[3] << " receives " << y << " free turns from " << na[0] << '.' << endl;
        else cout << "No free turns between " << na[3] << " and " << na[0] << '.' << endl;
        if(x != 0)
        cout << na[2] << " receives " << x << " free turns from " << na[1] << '.' << endl;
        else cout << "No free turns between " << na[2] << " and " << na[1] << '.' << endl;
    }else if(sc[1] == sc[2] && sc[3] != sc[0]){
        double y = sc[3] - sc[0];
        y /= 2;
        if(y > (int)y){
            y = (int)y;
            y ++ ;
        }
        int x = 0;
        cout << na[3] << " receives " << y << " free turns from " << na[0] << '.' << endl;
        if(sc[1] < sc[2])swap(na[1], na[2]);
        cout << "No free turns between " << na[1] << " and " << na[2] << '.' << endl;
    }
    else if(sc[3] == sc[0] && sc[1] != sc[2]){
        double x = sc[1] - sc[2];
        x /= 2;
        if(x > (int)x){
            x = (int)x;
            x ++ ;
        }
        int y = 0;
        if(sc[0] < sc[3])swap(na[0], na[3]);
        cout << "No free turns between " << na[0] << " and " << na[3] << '.' << endl;
        cout << na[1] << " receives " << x << " free turns from " << na[2] << '.' << endl;
    }
    else {
        if(sc[0] < sc[3])swap(na[3], na[0]);
        if(sc[1] < sc[2])swap(na[1], na[2]);
        cout << "No free turns between " << na[0] << " and " << na[3] << '.' << endl;
        cout << "No free turns between " << na[1] << " and " << na[2] << '.' << endl;
    }

    return 0;
}

I. Watersheds

可以用搜索，但是看到这个题立马有并查集的感觉了，于是用并查集完成了.

先创建一个结构体包含 x，y 坐标用来存储该位置的根.

struct f{//根坐标数组 
    int x, y;
}p[N][N];

定义并查集函数.

f find(int a, int b){//并查集 
    if(p[a][b].x != a || p[a][b].y != b)p[a][b] = find(p[a][b].x, p[a][b].y);
    return p[a][b];
}

然后就是并查集最开始的常规处理，给每个位置的 x，y 附上本身的一个坐标。 接下来开始并查集，先从每个点出发，按照北西东南的顺序找到最低点的位置，找到是否存在更低的位置，如果有，选出最低点的坐标让当前的坐标的根指向水流的目标位置，即低点是高点的根.

for(int i = 1; i <= n; i ++ ){
  for(int j = 1; j <= m; j ++ ){
    int xm, ym, minn = 11000;
    for(int k = 0; k <= 3; k ++ ){
      int xx = i + dx[k], yy = j + dy[k];
      if(xx < 1 || xx > n || yy < 1 || yy > m)continue;//防止越界 
      if(minn > e[xx][yy]){//保存较低点的位置 
        xm = xx;
        ym = yy;
        minn = e[xx][yy];
      }
    }
    if(minn < e[i][j])//如果存在比当前位置更低的点才会往下流 
    p[find(i, j).x][find(i, j).y] = find(xm, ym);
  }
}

此时出现了问题，将每个位置的根输出出来检查后发现第一个位置的根还在 （2,1） 而 （2,1） 已经流到 （3,1） 了，也就是高点的水流向未处理的位置会导致他作为子节点没有新的子节点会帮他更新，但是考虑到所以父子节点的链接已经完成，故再做一遍并查集即可解决。.

for(int i = 1; i <= n; i ++ ){//二次并查集避免高位节点在前不更新根节点 
  for(int j = 1; j <= m; j ++ ){
  p[i][j] = find(i, j);
  }
}

此时并查集的处理已然完成，接下来就是转换成字母输出，这里选择按照根进行分类，建立 idx 数组存储，通过ans变量计数，如果该根第一次出现则记为 ans++ ，输出的时候也通过根查找 idx 数组加上其值

memset(idx, -1, sizeof idx);//初始化 
ans = 0;

for(int i = 1;i <= n; i ++ ){//寻找不同的根并打上标记 
  for(int j = 1; j <= m; j ++ ){
    int xx = p[i][j].x, yy = p[i][j].y;
    if(idx[xx][yy] == -1)idx[xx][yy] = ans ++ ;
  }
}
for(int i = 1;i <= n; i ++ ){//依据标记输出 
  for(int j = 1; j <= m; j ++ ){
    int xx = p[i][j].x, yy = p[i][j].y;
    printf("%c ", 'a' + idx[xx][yy]);
  }
  puts("");
}
}

然后就完成了.

代码

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

const int N = 110;
int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};//方向北西东南 
int e[N][N], idx[N][N], ans = 0;
int t;
int n, m;

struct f{//根坐标数组 
    int x, y;
}p[N][N];

f find(int a, int b){//并查集 
    if(p[a][b].x != a || p[a][b].y != b)p[a][b] = find(p[a][b].x, p[a][b].y);
    return p[a][b];
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            cin >> e[i][j];
            p[i][j].x = i, p[i][j].y = j;
        }
    }

    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m; j ++ ){
            int xm, ym, minn = 11000;
            for(int k = 0; k <= 3; k ++ ){
                int xx = i + dx[k], yy = j + dy[k];
                if(xx < 1 || xx > n || yy < 1 || yy > m)continue;//防止越界 
                if(minn > e[xx][yy]){//保存较低点的位置 
                    xm = xx;
                    ym = yy;
                    minn = e[xx][yy];
                }
            }
            if(minn < e[i][j])//如果存在比当前位置更低的点才会往下流 
            p[find(i, j).x][find(i, j).y] = find(xm, ym);
        }
    }

    for(int i = 1; i <= n; i ++ ){//二次并查集避免高位节点在前不更新根节点 
        for(int j = 1; j <= m; j ++ ){
        p[i][j] = find(i, j);
        }
    }

    memset(idx, -1, sizeof idx);//初始化 
    ans = 0;

    for(int i = 1;i <= n; i ++ ){//寻找不同的根并打上标记 
        for(int j = 1; j <= m; j ++ ){
            int xx = p[i][j].x, yy = p[i][j].y;
            if(idx[xx][yy] == -1)idx[xx][yy] = ans ++ ;
        }
    }
    for(int i = 1;i <= n; i ++ ){//依据标记输出 
        for(int j = 1; j <= m; j ++ ){
            int xx = p[i][j].x, yy = p[i][j].y;
            printf("%c ", 'a' + idx[xx][yy]);
        }
        puts("");
    }
    return 0;
}

J. Snaggle

递归模拟，顺着读算式，写一个 Snaggle 算法函数，每次读到左括号就调用该函数.

主函数分为两种情况，一种是输入只有一个数字，直接转换成整型即可；第二种是有 Snaggle 算式，开局一定是左括号，也就是如果第一位是左括号从第二位开始调用 Snaggle 函数. Snaggle 函数中用e数组开三位表示三个数字，也进行分类讨论，读到左括号是再次往里调用 Snaggle 函数，返回值存进e数组对应位置，遇到空格就说明开始下一个数字了，同时还要注意处理小数和负数，整化 Snaggle 函数后回归的位置也很重要，要到右括号的下一位.

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

string s;
double ans;
int res, ress;

double sol(int x){//Snaggle 函数
    int idx = 0;
    double e[3] = {0, 0, 0};
    double t = 1;
    double f = 1;
    for(int i = x; s[i] != ')'; i ++ ){
        if(s[i] == '('){ //遇到左括号递归Snaggle 函数
            e[idx] = sol(i + 1);
            i = ress;
        }
        if(s[i] == ')'){res = i - 1;break;}
        if(s[i] == ' ')e[idx] = f * e[idx], f = 1, idx ++ , t = 1;
        else if(s[i] == '-')f = -1;
        else{
            if(s[i] >= '0' && s[i] <= '9' && t == 1){
                e[idx] *= 10;
                e[idx] += s[i] - '0';
            }
            else if(s[i] == '.')t = 0.1;
            else{
                e[idx] += t * (s[i] - '0');
                t /= 10;
            }
        }
        res = i;//记录结束位置
    }
    e[2] *= f;
    ress = res + 2;记录右括号后一位，返回后直接移动
    return e[0] * (e[1] + e[2]) + (1 - e[0]) * (e[1] - e[2]);
}

int main(){
    while(getline(cin, s)){
        ans = 0;
        ress = 0;
        if(s == "()")break;

        if(s[0] != '('){
            double t = 1;
            for(int i = 0; s[i] != '\0'; i ++ ){
                if(s[i] >= '0' && s[i] <= '9' && t == 1){
                ans *= 10;
                ans += s[i] - '0';
                }
            else if(s[i] == '.')t = 0.1;
            else{
                ans += t * (s[i] - '0');
                t /= 10;
                }
            }
        }
        else ans = sol(1);

        printf("%.2lf\n", ans);
    }

    return 0;
}

K. Microspikes

看到题目描述后显然使用差分进行批量处理，再使用前缀和展现每个时刻的用电情况，处理完成后顺序寻找微峰值即可

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

const int N = 1e5 + 10;
int e[N];
int n, maxx, t;
int a, k, p;
int ans;

struct f{
    int v, ti;
}num[N];

int main(){
    cin >> n >> maxx >> t;

    while(cin >> a >> k >> p){//将输入的变化差分处理
        if(!a && !k && !p)break;

        int l = num[a].ti, r = num[a].ti + k;
        e[l] += num[a].v;
        e[r] -= num[a].v;
        num[a].ti += k;
        num[a].v += p;
    }

    for(int i = 1; i <= N; i ++ ){//输入结束后最后一次电压变化持续到结束
        e[num[i].ti] += num[i].v;
    }

    for(int i = 1; i <= n; i ++ ){//前缀和处理，将每个时刻电量换算出来
        e[i] += e[i - 1];
    }

    bool f = false;
    for(int i = 1; i <= n; i ++ ){//寻找微峰值
        int x1, x2;
        if(!f && e[i] > maxx){
            f = true;
            x1 = i;
        }
        else if(f && e[i] <= maxx){
            f = false;
            x2 = i - 1;
            if(x2 - x1 <= t)ans ++ ;
        }
    }

    cout << ans << endl;

    return 0;
}

2025假期赛新鲜出炉！

2025-08-22 09:54:16 By xoyo

比赛已开放报名，比赛链接：http://go.helloworldroom.com/contest/261

时长为周六早上八点到周日晚上八点。

比赛分为三个难度：

第一层为1-4题，是较为基础的语法题；

第二层为5-8题，对语法题的难度进行了些许提升；

第三层为9-11题，需要动用一些算法知识。

欢迎大家踊跃报名！！！

xoyo Avatar
中文 English

服务器时间: 2025-08-27 03:08:14