[ABC348A] Penalty Kick

题目大意

给定一个正整数 $n$，请输出一个字符串，其中下标为 $3$ 的倍数位置为 x，其余为 o。

思路

不想评价了，模拟。

代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
        if (i % 3 == 0) putchar('x');
        else putchar('o');
    return 0;
}

[ABC348B] Farthest Point

题目大意

已知平面上有 $n$ 个点，请对每个点求出距离它欧几里得距离最远的点的编号。

思路

$n$ 很小，直接暴力。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 115;
int n;
double a[N], b[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf%lf", &a[i], &b[i]);
    for (int i = 1; i <= n; i++) {
        double x = a[i], y = b[i], Max = 0; int id = 0;
        for (int j = 1; j <= n; j++) {
            double xx = a[j], yy = b[j];
            double X = x - xx, Y = y - yy;
            double res = sqrt(X * X + Y * Y);
            if (Max < res) Max = res, id = j;
        }
        printf("%d\n", id);
    }
    return 0;
}

[ABC348C] Colorful Beans

题目大意

有 $n$ 粒豆子，每个豆子有美味度 $A_i$ 和颜色 $C_i$，同色豆子无法互相辨认，请求出选择一种颜色的豆子吃掉后最坏能获得的最大美味度。

思路

对每种颜色的最小值取最大值。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 15;
int n;
pair<int, int> a[N];

bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

int main() {
    int ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].first, &a[i].second);
    sort(a + 1, a + 1 + n, cmp);
    for (int i = 1; i <= n; i++)
        if (a[i].second != a[i - 1].second) ans = max(ans, a[i].first);
    printf("%d\n", ans);
    return 0;
}

[ABC348D] Medicines on Grid

题目大意

给定一个 $H \times W$ 的网格图，每个点可能是起点 S、终点 T、障碍物 # 或路 .。

初始能量为 $0$，每次可以向上下左右中的一个方向前进一格，但不能越过网格图或者障碍物。

给定 $n$ 瓶药水的位置 $(X_i,Y_i)$ 和能量值 $E_i$，经过的时候可以把能量修改为 $E_i$（当然也可以不喝药水）。

请问能否到达终点？

思路

开始有趣了。
用 $dp_{i,j}$ 表示从起点走到 $(i,j)$ 的最大能量。如果没有能量限制肯定可以 bfs，有能量限制就考虑用队列。
如果这次到达这个节点的能量大于之前到这个点的能量，则把它入队（可以采用更好的策略更新）。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 215;
int n, m, s;
char mp[N][N];
int a[N][N];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int sx, sy, ex, ey;

int dp[N][N];   //到(x,y)的最大能量 
struct node {
    int x, y, w;
} ;
void solve() {
    queue<node> q; q.push((node){sx, sy, a[sx][sy]});
    dp[sx][sy] = a[sx][sy];
    while (q.size()) {
        node f = q.front(); q.pop();
        int x = f.x, y = f.y, w = f.w;
        for (int i = 0; i < 4; i++) {
            int xx = x + dx[i], yy = y + dy[i], ww = w - 1;
            if (xx == ex && yy == ey) { puts("Yes"); return; }
            ww = max(ww, a[xx][yy]);
            if (xx < 1 || xx > n || yy < 1 || yy > m || ww <= 0 || ww <= dp[xx][yy] || a[xx][yy] == -1) continue;
            dp[xx][yy] = ww;
            q.push((node){xx, yy, ww});
        }
    }
    puts("No");
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf(" %s", mp[i] + 1);
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == 'S') sx = i, sy = j;
            if (mp[i][j] == 'T') ex = i, ey = j;
            if (mp[i][j] == '#') a[i][j] = -1;
        }
    }
    scanf("%d", &s);
    for (int i = 1, x, y, e; i <= s; i++) {
        scanf("%d%d%d", &x, &y, &e);
        a[x][y] = e;
    }
    if (a[sx][sy] == 0) return puts("No"), 0;
    solve();
    return 0;
}

[ABC348E] Minimize Sum of Distances

题目大意

给定一棵 $n$ 个节点的树，第 $i$ 个点有权值 $c_i$。设 $d(a,b)$ 为树上节点 $a$、$b$ 间的距离，再令 $f(x)=\sum\limits_{i=1}^N (C_i \times d(x, i))$，求 $f(x)$ 的最小值。

思路

这题挺逆天的，原题（QwQ）

其实就是换根，考虑每个点与他父亲节点的贡献差，dfs 的时候修改就行了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15, M = N << 1;
int n;
int h[N], e[M], ne[M], idx = 0;
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

long long sz[N], ans[N], sum, c[N];
void dfs(int u, int father, int dep) {
    sz[u] = c[u]; ans[1] += dep * 1ll * c[u];
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == father) continue;
        dfs(v, u, dep + 1);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int father, long long now) {
    ans[u] = now;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == father) continue;
        long long nxt = now;
        nxt -= sz[v], nxt += sum - sz[v];
        dfs2(v, u, nxt);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) h[i] = -1;
    for (int i = 1, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        add(x, y); add(y, x);
    }
    for (int i = 1; i <= n; i++) scanf("%lld", &c[i]), sum += c[i];
    dfs(1, 0, 0); dfs2(1, 0, ans[1]);
    long long Min = 1.5 *1e18;
    for (int i = 1; i <= n; i++) Min = min(Min, ans[i]);
    printf("%lld\n", Min);
    return 0;
}

[ABC348F] Oddly Similar

题目大意

给定 $n$ 个长度为 $m$ 的序列，称两个序列 $A,B$ 相似当且仅当有奇数个 $A_i=B_i$，请问有多少个 $(i,j)$ 满足 $i \lt j$ 且序列 $i$ 和序列 $j$ 相似。

思路

有点意思。

先试图暴力，然后我们发现他是 $O(n^2 m)$ 的，可以过，只要手动 O3 就行了。

然后我们试图对它优化，考虑用 bitset，因为值域很小。
用 $b_{x,i,j}$ 表示第 $j$ 个数组的第 $i$ 位为 $x$。那么接下来要做的就是异或 $b_{a_1,1} \ b_{a_2,2} \ … \ b_{a_n,n}$，统计非 $0$ 的二进制位数量。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2015, M = 1015;

bitset<N> b[M][N], c[N];
int n, m, a[N][N];
long long ans = 0;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%d", &a[i][j]);
            b[a[i][j]][j][i] = 1;   //a这个数存在于第j位，第i个数组 
        }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) c[i] ^= b[a[i][j]][j];
        for (int j = 1; j < i; j++) ans += c[i][j];
    }
    printf("%lld\n", ans);
    return 0;
}

[ABC348G] Max (Sum - Max)

题目大意

给定两个长度为 $n$ 的整数序列 $A,B$，对于 $1$ 到 $n$ 的每一个数 $k$，找出一个由 $1$ 到 $n$ 组成的大小为 $k$ 的集合 $S$，使得 $(\sum \limits _{i \in S} A_i) - \max \limits _{i \in S} B_i$ 最大，求这个最大值。

思路

没搞懂qwq

代码

我太弱了。