【题解】ACM算法社周赛-2

B-反向输出一个四位数

// 将四位整数作为字符串读入，直接调用 reverse 函数翻转字符串后输出即可。
void solve()
{
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    cout << s << endl;
}

C-及格分数

// while(cin >> n) 是一种处理多组输入直到文件结束的经典写法
// 根据输入的整数是否大于等于60，输出"Pass"或"Fail"。
void solve()
{
    int n;
    while (cin >> n)
    {
        if (n >= 60)
        {
            cout << "Pass\n";
        }
        else
        {
            cout << "Fail\n";
        }
    }
}

D-总成绩和平均分计算

// 直接用 scanf 读取三个浮点数，在 printf 中直接计算它们的和与平均值，并使用 %.2f 格式化输出。
void solve()
{
    double a, b, c;
    scanf("%lf %lf %lf", &a, &b, &c);
    printf("%.2f %.2f\n", a + b + c, (a + b + c) / 3.0);
}

E-数列下标

//模拟即可，时空复杂度刚好允许
void solve()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i];
    }
    for (int i = 0; i < n; ++i)
    {
        int ok = 0;
        for (int j = i + 1; j < n; ++j)
        {
            if (v[j] > v[i])
            {
                ok = 1;
                cout << j + 1 << " ";
                break;
            }
        }
        if (ok == 0)
        {
            cout << 0 << " ";
        }
    }
}

F-字母大小写转换

//常见的做法就是增删32即可
// 但是可以利用 ASCII 码中大小写字母相差 32 的特性，通过位异或操作 ^ 32 直接进行转换。
// 'A' 的 ASCII 码是 65 (二进制 01000001)
// 'a' 的 ASCII 码是 97 (二进制 01100001)
// 利用位异或 (XOR, ^) 操作的特性：一个数与 00100000 进行异或，会精确地翻转第 5 位，而其他位保持不变。这恰好能实现大小写的转换，无需任何 if-else 判断。
void solve()
{
    char c;
    while (cin >> c)
    {
        cout << char(c ^ 32) << endl;
    }
}

G-素数判断

//使用欧拉筛模板，只要求primes的大小即可。
const int N = 1e8;
vector<int> primes;
bitset<N + 1> is_prime;

void linear_sieve(int n)
{
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (is_prime[i])
        {
            primes.push_back(i);
        }
        for (int p : primes)
        {
            if (i > n / p)
                break;
            is_prime[i * p] = 0;
            if (i % p == 0)
                break;
        }
    }
}
void solve()
{
    int n;
    cin >> n;
    linear_sieve(n);
    cout << primes.size() << endl;
    primes.clear();
}

H-Laptop

// 按内存降序排序，然后线性扫描，若当前笔记本速度小于此前遇到的最大速度，则它被“完虐”。
struct Node {
    int m, s;
};

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

    vector<Node> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].m >> a[i].s;
    }

    // 按内存 m 降序排序
    sort(a.begin(), a.end(), [](const Node& x, const Node& y) {
        return x.m > y.m;
    });

    int ans = 0;
    int max_s = 0; // 维护此前遍历过的最大速度

    for (int i = 0; i < n; ++i) {
        // 如果当前笔记本的速度 < 此前见过的最大速度，则它被完虐
        if (a[i].s < max_s) {
            ans++;
        }
        // 更新最大速度
        max_s = max(max_s, a[i].s);
    }

    cout << ans << endl;

    return 0;
}

I-五子棋大师

//很经典的二维数组模拟题，从去年一直出到现在，感觉提升上码力就能切。
#include <iostream>
#include <vector>
using namespace std;

int board[20][20];
// 方向数组: 右, 下, 右下, 右上
int dr[] = {0, 1, 1, -1};
int dc[] = {1, 0, 1, 1};

// 检查 (r, c) 是否是某个方向上的获胜起点
bool check_win(int r, int c) {
    int color = board[r][c];
    if (color == 0) return false;

    for (int i = 0; i < 4; ++i) {
        int count = 1;
        // 向前数4个
        for (int k = 1; k < 5; ++k) {
            int nr = r + k * dr[i];
            int nc = c + k * dc[i];
            if (nr >= 1 && nr <= 19 && nc >= 1 && nc <= 19 && board[nr][nc] == color) {
                count++;
            } else {
                break;
            }
        }

        if (count == 5) {
            // 检查是否为长连 (检查连线两端)
            int pr = r - dr[i]; // "前"一个点
            int pc = c - dc[i];
            int nr = r + 5 * dr[i]; // "后"一个点
            int nc = c + 5 * dc[i];

            bool prev_same = (pr >= 1 && pr <= 19 && pc >= 1 && pc <= 19 && board[pr][pc] == color);
            bool next_same = (nr >= 1 && nr <= 19 && nc >= 1 && nc <= 19 && board[nr][nc] == color);

            if (!prev_same && !next_same) {
                return true; // 是一个恰好五子的获胜
            }
        }
    }
    return false;
}

void solve() {
    for (int i = 1; i <= 19; ++i) {
        for (int j = 1; j <= 19; ++j) {
            cin >> board[i][j];
        }
    }

    for (int c = 1; c <= 19; ++c) {
        for (int r = 1; r <= 19; ++r) {
            if (check_win(r, c)) {
                cout << board[r][c] << "\n";
                cout << r << " " << c << "\n";
                return;
            }
        }
    }

    cout << 0 << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}