[ABC233A] 10yen Stamp

题目大意

给定 $x,y$，求 $x$ 需要加上多少个 $10$ 才能 $\geq y$。

思路

智障题，直接算。

代码

#include <bits/stdc++.h>
using namespace std;
int a, b;
int main() {
    scanf("%d%d", &a, &b);
    if (a >= b) puts("0");
    else {
        int ans = (b - a) / 10;
        if ((b - a) % 10 > 0) ans++;
        printf("%d\n", ans);
    }
    return 0;
}

[ABC233B] A Reverse

题目大意

给定一个字符串 $s$ 和区间 $[l,r]$，将 $[l,r]$ 字符倒序输出。

思路

弱智题，模拟。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;
int l, r;
char str[N];

int main() {
    scanf("%d%d", &l, &r);
    scanf(" %s", str + 1);
    int n = strlen(str + 1);
    for (int i = 1; i < l; i++) putchar(str[i]);
    for (int i = r; i >= l; i--) putchar(str[i]);
    for (int i = r + 1; i <= n; i++) putchar(str[i]);
    return 0;
}

[ABC233C] Product

题目大意

有 $n$ 个袋子，第 $i$ 个袋子里有 $l_i$ 个球，其中第 $j$ 上写着 $a_{i,j}$。从每个袋子各取出 $1$ 个球，请问使得所有取出小球权值乘积为 $x$ 的取球方案有多少种？

思路

脑残题。发现 $\prod \limits _{i=1} ^{N} L_i \leq 10^5$，然后就可以 dfs 了。

代码

//qwq

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 15;

int n;
long long k;

vector<int> a[N];

long long ans = 0;

void dfs(int u, long long now) {
    if (now > k) return;
    if (u > n) {
        if (now == k) ans++;
        return;
    }
    for (int i = 0; i < a[u].size(); i++) {
        dfs(u + 1, now * 1ll * a[u][i]);
    }
}

int main() {
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        for (int j = 1; j <= x; j++) {
            int p; scanf("%d", &p);
            a[i].push_back(p);
        }
    }
    dfs(1, 1ll);
    printf("%lld\n", ans);
    return 0;
}

[ABC233D] Count Interval

题目大意

给定一个数组 $a$，请问有多少个区间的区间和为 $k$？

思路

这题更智障了，记一个 $a$ 的前缀和 $s$，$\sum \limits _{i=l} ^{r} a_i = s_{r} - s_{l-1}$，即统计 $\sum \limits_{i=1}^{N} \sum \limits_{j=i}^{N} 1 [s_j - s_{i - 1} == x]$，这个式子一眼鉴定为可以 $O(N)$ 计算，也就开个桶记录 $s_{i-1}$ 的出现次数罢了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 15;
int n;
long long k;
long long a[N], s[N];
unordered_map<long long, long long> mp;
long long ans = 0;

int main() {
    scanf("%d%lld", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= n; i++) mp[s[i - 1]]++, ans += mp[s[i] - k];
    printf("%lld\n", ans);
    return 0;
}

[ABC233E] Σ(k=0..10^100)floor(X／10^k)

题目大意

给出整数 $x$，求 $\sum _{k=0} ^{10^{100}} \lfloor \frac{x}{10^k} \rfloor$。

思路

第一眼鉴定为高精度，第二眼鉴定为压位高精度，第三眼鉴定为不需要高精直接计算输出。
由于看到下取整符号，分母又是 $10$ 的次幂，很容易想到考虑每一位对答案的贡献，于是模拟。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 15;

char str[N];
int n, a[N];

int main() {
    scanf("%s", (str + 1)); n = strlen(str + 1);
    for (int i = 1; i <= n; i++) a[i] = str[n - i + 1] - '0';
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += str[i] - '0';
        a[n - i] += sum;
    }
    int x = 1;
    while (x < n || a[x] > 9)
        a[x + 1] += a[x] / 10, a[x] %= 10, x++;
    for (int i = x; i >= 1; i--) printf("%d", a[i]);
    return 0;
}

[ABC233F] Swap and Sort

题目大意

给定一个长度为 $n$ 的排列和 $m$ 种操作，每个操作形如 $(u,v)$，表示交换 $a_u$ 和 $a_v$。
请问是否存在一种方案使得通过适当的操作把排列排序？
请求出一种构造，或报告无解。

思路

赛时口胡，但是没肝出来。

考虑把交换操作映射到图上，让它变成连边。
首先显然考虑到可以求出一个生成树，顺带处理无解情况（即 $i$ 和 $a_i$ 不在同一连通块内）。
然后形成了一个森林，就可以对每个树从叶子节点往上归位。

代码

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

int n, m, a[N];
int h[N], e[M], w[M], ne[M], idx = 0;
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int fa[N];
int d[N];
vector<int> ans;

int find(int x) {
    if (x == fa[x]) return x;
    return fa[x] = find(fa[x]);
}

queue<int> q;

bool dfs(int u, int father, int color) {
    if (a[u] == color) return true;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == father) continue;
        if (dfs(v, u, color)) {
            ans.push_back(w[i]), swap(a[u], a[v]);
            return true;
        }
    }
    return false;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), h[i] = -1, fa[i] = i;
    scanf("%d", &m);
    for (int i = 1, u, v; i <= m; i++) {
        scanf("%d%d", &u, &v);
        if (find(u) != find(v)) {
            add(u, v, i); add(v, u, i);
            d[u]++, d[v]++;
            fa[find(u)] = find(v);
        }
    }

    for (int i = 1; i <= n; i++)
        if (find(i) != find(a[i])) return puts("-1"), 0;

    for (int i = 1; i <= n; i++) if (d[i] == 1) q.push(i);

    while (q.size()) {
        int f = q.front(); q.pop();
        dfs(f, f, f);
        for (int i = h[f]; ~i; i = ne[i]) {
            int v = e[i];
            if (--d[v] == 1) q.push(v);
        }
    }

    printf("%d\n", ans.size());
    for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
    return 0;
}

[ABC233G] Strongest Takahashi

题目大意

给定一个 $N \times N$ 的地图 $S$，每个点可能是障碍物 # 或空地 .。

你可以进行若干次如下操作：

1. 选取一个正整数 $D$，满足 $1 \leq D \leq N$，在地图中选择一个 $D \times D$ 的子矩阵。
2. 花费 $D$ 代价摧毁矩阵内所有障碍物。

求摧毁所有障碍物的最小代价。

思路

对于一个长 $a$ 宽 $b$ 的矩形，代价为 $\max(a,b)$，那么想到对每一个矩形枚举横纵分割线，通过两个小部分的答案来更新这一层的答案。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n;
char ch[N][N];

int f[N][N][N][N];

int main() {
    scanf("%d", &n);
    memset(f, 0x3f3f3f3f, sizeof f);
    for (int i = 1; i <= n; i++) scanf("%s", ch[i] + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            f[i][j][i][j] = (ch[i][j] == '#');
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int x = 1; x <= n; x++)
                for (int y = 1; y <= n; y++) {
                    int xx = x + i, yy = y + j;
                    if (xx > n || yy > n) continue;
                    if (i == j) f[x][y][xx][yy] = min(f[x][y][xx][yy], i + 1);
                    for (int k = x; k < xx; k++) f[x][y][xx][yy] = min(f[x][y][xx][yy], f[x][y][k][yy] + f[k + 1][y][xx][yy]);
                    for (int k = y; k < yy; k++) f[x][y][xx][yy] = min(f[x][y][xx][yy], f[x][y][xx][k] + f[x][k + 1][xx][yy]);
                }
    printf("%d\n", f[1][1][n][n]);
    return 0;
}

[ABC233Ex] Manhattan Christmas Tree

这题真是太酷啦

题目大意

给定平面直角坐标系中的 $N$ 个点 $(x_i, y_i)$，有 $Q$ 次询问，每次询问距离 $(a_i,b_i)$ 曼哈顿距离 第 $k$ 近的点的距离。

思路

距离某个点曼哈顿距离小于 $k$ 的点集在坐标系上体现为一个斜着的正方形。
曼哈顿距离不好处理横纵坐标的关系，所以考虑把它转化成切比雪夫距离，这样也可以把正方形旋转四十五度。

曼哈顿转化切比雪夫 $(x,y) -> (x + y, x - y)$
切比雪夫转化曼哈顿 $(x,y) -> (\frac{x + y}{2}, \frac{x - y}{2})$

于是就可以二分答案，然后统计区域内的点数（二位数点，主席树）。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 15, M = 1e5, K = (M << 1) + 1;
vector<int> pos[K + 15];
int n, m;
int rt[(N << 1) + 15];

struct Tree {
    int ls, rs;
    int sum;
} tr[N << 5];
int tot = 0;

void change(int &u, int l, int r, int x) {
    tr[++tot] = tr[u], u = tot;
    if (l == r) { tr[u].sum++; return; }
    int mid = l + r >> 1;
    if (x <= mid) change(tr[u].ls, l, mid, x);
    else change(tr[u].rs, mid + 1, r, x);
    tr[u].sum = tr[tr[u].ls].sum + tr[tr[u].rs].sum;
}

int query(int u1, int u2, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return tr[u2].sum - tr[u1].sum;
    int mid = l + r >> 1, ans = 0;
    if (ql <= mid) ans += query(tr[u1].ls, tr[u2].ls, l, mid, ql, qr);
    if (qr > mid) ans += query(tr[u1].rs, tr[u2].rs, mid + 1, r, ql, qr);
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i <= n; i++) {
        scanf("%d%d", &x, &y);
        pos[x + y + 1].push_back(x - y + M + 1);
    }

    for (int i = 1; i <= K; i++) {
        rt[i] = rt[i - 1];
        for (int j : pos[i]) change(rt[i], 1, K, j);
    }

    scanf("%d", &m);
    for (int i = 1, a, b, k; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &k);
        int x = a + b + 1, y = a - b + M + 1;
        int l = 0, r = K, ans = 0;
        while (l < r) {
            int mid = l + r >> 1;
            int u = rt[max(0, x - mid - 1)], v = rt[min(K, x + mid)];
            int res = query(u, v, 1, K, max(1, y - mid), min(y + mid, K));
            if (res < k) l = mid + 1;
            else r = mid, ans = mid;
        }
        printf("%d\n", ans);
    }
    return 0;
}