TOI202105 潛力組

Maze.cpp

#include <bits/stdc++.h>

#define MAXN 505

using namespace std;

int N;
char maze[MAXN][MAXN];
int ans[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

struct Node
{
    int x, y, step;
};

void bfs(int x, int y)
{
    queue<Node> Q;
    Q.push({x, y, 0});
    vis[x][y] = 1;
    while (!Q.empty())
    {
        auto node = Q.front();
        Q.pop();
        x = node.x;
        y = node.y;
        int step = node.step + 1;
        for (int i = 0; i < 4; i++)
        {
            int n_x = x + dx[i];
            int n_y = y + dy[i];
            if (!vis[n_x][n_y] && (maze[n_x][n_y] == '0' || maze[n_x][n_y] == 'E'))
            {
                Q.push({n_x, n_y, step});
                vis[n_x][n_y] = 1;
                ans[n_x][n_y] = step;
            }
        }
    }
}

int main()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
            cin >> maze[i][j];
    }
    memset(vis, 0, sizeof(vis));
    memset(ans, 0, sizeof(ans));
    for (int i = 0; i <= N + 1; i++)
    {
        maze[i][0] = '#';
        maze[i][N + 1] = '#';
    }
    for (int j = 0; j <= N + 1; j++)
    {
        maze[0][j] = '#';
        maze[N + 1][j] = '#';
    }
    bfs(1, 1);
    if (vis[N][N])
        cout << ans[N][N];
    else
        cout << "-1";
}

Tsunami.cpp

#include <bits/stdc++.h>

#define MAXN 500005

typedef long long LL;

using namespace std;

LL N, K;
LL p_sum[MAXN];

bool chk(LL s)
{
    // cout << "s: " << s << endl;
    LL cnt = 0;
    // # of (p_sum[j] - p_sum[i] > s)
    // # of (p_sum[j] > s + p_sum[i])
    for (int i = 0; i <= N; i++)
    {
        int idx = upper_bound(p_sum + i + 1, p_sum + N + 1, s + p_sum[i]) - p_sum;
        cnt += N - idx + 1;
    }
    // cout << "cnt: " << cnt << endl;
    return cnt > K - 1;
}

int main()
{
    cin >> N >> K;
    p_sum[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> p_sum[i];
        p_sum[i] += p_sum[i - 1];
    }
    LL l = 0, r = p_sum[N] + 1;
    while (l < r)
    {
        // cout << "l: " << l << " r: " << r << endl;
        LL mid = (l + r) / 2;
        if (chk(mid))
            l = mid + 1;
        else
            r = mid;
    }
    cout << l;
    return 0;
}

Zero.cpp

#include <bits/stdc++.h>

using namespace std;

int N;
int a[105];

int main()
{
    cin >> N;
    int sum = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    if (sum % 2 != 0)
    {
        cout << "0";
        return 0;
    }
    set<int> p_num, num;
    map<int, string> p_exp, exp;
    p_num.insert(a[0]);
    p_exp[a[0]] = "";
    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            int mul = 1 - 2 * j;
            bool plus = (mul == 1);
            for (auto &x : p_num)
            {
                int tmp = x + a[i] * mul;
                num.insert(tmp);
                string e = p_exp[x] + (plus ? "+" : "-");
                if (exp[tmp].length() == i)
                    exp[tmp] = min(exp[tmp], e);
                else
                    exp[tmp] = e;
            }
        }
        swap(p_num, num);
        swap(p_exp, exp);
        num.clear();
        exp.clear();
    }

    // for (auto &x : p_num)
    //     cout << x << " ";

    // for (auto &[x, y] : exp)
    //     cout << x << " " << y << endl;

    if (p_num.find(0) == p_num.end())
        cout << "0";
    else
    {
        cout << "1" << endl;
        cout << a[0];
        for (int i = 1; i < N; i++)
            cout << p_exp[0][i - 1] << a[i];
    }
    return 0;
}