Codeforces Round #516 (Div. 2)

A

题意是增加边的长度使这三条边可以组成三角形，所以只要将较小的两条边之和增加到比最大边大1即可

#include <cstdio>
#include <algorithm>

int ans;
int a[5];

int main()
{
    scanf("%d %d %d", &a[1], &a[2], &a[3]);
    std::sort(a + 1, a + 4);
    if (a[3] >= a[1] + a[2]) ans = a[3] - (a[1] + a[2]) + 1;
    printf("%d\n", ans);
    return 0;
}

B

原位为1的位是0或1皆可，原位为0的位只能为0，所以统计1的个数为n，答案就是$2^n$2n

#include <cstdio>
#include <algorithm>

int t;

int quick_pow(int a, int b) {
    int ans = 1;
    for (; b; a = a * a, b >>= 1)
        if (b & 1)
            ans = ans * a;
    return ans;
}

int main()
{
    scanf("%d", &t);
    while (t--) {
        int n, cnt = 0;
        scanf("%d", &n);
        while(n) {
            if (n & 1) cnt++;
            n >>= 1;
        }
        printf("%d\n", quick_pow(2, cnt));
    }
    return 0;
}

C

虽然不能严格证明，但是相同的字符放在一起贡献是最大的

#include <cstdio>
#include <algorithm>
#include <cstring>

const int MAXN = 1e5 + 2;

int n;

char str[MAXN];

int main()
{
    scanf("%d", &n);
    scanf("%s", str);
    std::sort(str, str + n);
    for (int i = 0; i < n; i++)
        printf("%c", str[i]);
    return 0;
}

D

01BFS，用双调队列，通过把向上和向下走的点放到队首，向左和向右走的放到队尾来保证先遍历完上下再遍历左右

#include <cstdio>
#include <algorithm>
#include <queue>

const int MAXN = 2000 + 2;

struct Node {
    int x, y, l, r;
};

int n, m, r, c, x, y, ans;
int step_x[4] = {-1, 1, 0, 0}, step_y[4] = {0, 0, -1, 1};
char maze[MAXN][MAXN];
bool vis[MAXN][MAXN];

void bfs() {
    std::deque<Node> q;
    q.push_back((Node) {r, c, x, y});

    while (!q.empty()) {
        Node tmp = q.front(); q.pop_front();
        if (vis[tmp.x][tmp.y] || tmp.l < 0 || tmp.r < 0) continue;
        vis[tmp.x][tmp.y] = true;   ans++;
        for (int i = 0; i < 4; i++) {
            int wx = tmp.x + step_x[i], wy = tmp.y + step_y[i];
            if (wx < 1 || wx > n || wy < 1 || wy > m || maze[wx][wy] == '*' || vis[wx][wy]) continue;
            if (i == 0 || i == 1) q.push_front((Node) {wx, wy, tmp.l, tmp.r});
            else if (i == 2) q.push_back((Node) {wx, wy, tmp.l - 1, tmp.r});
            else if (i == 3) q.push_back((Node) {wx, wy, tmp.l, tmp.r - 1});
        }

    }
}

int main()
{
    scanf("%d %d %d %d %d %d", &n, &m, &r, &c, &x, &y);
    for (int i = 1; i <= n; i++)
        scanf("%s", maze[i] + 1);
    bfs();
    printf("%d\n", ans);
}