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

本次比赛为ACM算法社第一次比赛，主要以语法学习、提升信心为主

这是代码基础模板

#include <bits/stdc++.h>
#define all(arr) arr.begin(), arr.end()
#define endl '\n'
#define int long long
using namespace std;
template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
    for (auto &x : v)
        is >> x;
    return is;
}

//void solve() {}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    while (t--)
        solve();
    return 0;
}

B-最大的差

//把列表中最大的值减去列表中最小的值即可，可以O(n)算法，也可以排序后用最大值减去最小值
void solve()
{
    int n;
    cin >> n;
    vector<int> v(n);
    cin >> v;
    sort(all(v));//排序数组
    cout << v.back() - v.front() << endl;//最大值（最后面的）减去最小值（最前面的）
}

C-默契

//判断是否相等即可
void solve()
{
    int a, b;
    cin >> a >> b;
    if (a == b)
    {
        cout << "Tacit！" << endl;
    }
    else
    {
        cout << "No Tacit!" << endl;
    }
}

D-签到++

//本质上就是尽可能让更多人AC,但是要注意向下取整，C++中直接除以就是向下取整
void solve()
{
    int a, b, c;
    cin >> a >> b >> c;
    cout << c / a << endl;
}

E-泉信的a+b

//输出a+b即可。
void solve()
{
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
}

F-津津的储蓄计划

//模拟每个月钱的流入、流出和储蓄，记录过程中的状态，最后计算总资产。
void solve()
{
    vector<int> v(12);
    cin >> v;
    int have = 0;
    int givemom = 0;

    for (int i = 0; i < 12; ++i)
    {
        have += 300;
        have -= v[i];
        if (have < 0)
        {
            cout << -1 * (i + 1) << endl;
            return;
        }
        givemom += have / 100;
        have %= 100;
    }
    cout << givemom * 120 + have << endl;
}

G-判断素数

//只要常规判断素数即可，可用试除法优化。
void solve()
{
    int n;
    cin >> n;
    if (n == 1)
    {
        NO;
        return;
    }
    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            NO;
            return;
        }
    }
    YES;
}

H-素数个数

//使用欧拉筛模板，只要求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();
}

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;
}