AtCoder Beginner Contest 339

A - TLD (abc339 A)

题目大意

给一个网址,问它的后缀是多少。

解题思路

找到最后的'.'的位置,然后输出后面的字符串即可。

python可以一行。

神奇的代码
print(input().split('.')[-1])


B - Langton's Takahashi (abc339 B)

题目大意

二维网格,上下左右相连,左上原点。初始全部为白色,位于原点,面朝上。

进行\(n\)次操作,每次操作,将当前格子颜色黑白反转,然后

  • 如果原来是白色,则顺时针旋转\(90\)度,前进一个格子。
  • 如果原来是黑色,则逆时针旋转\(90\)度,前进一个格子。

解题思路

网格大小只有\(100 \times 100\)\(n\)\(1000\),每步模拟的复杂度是 \(O(1)\),因此直接模拟即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w, n;
    cin >> h >> w >> n;
    vector<vector<int>> tu(h, vector<int>(w));
    int x = 0, y = 0, dir = 0;
    array<int, 4> dx = {-1, 0, 1, 0};
    array<int, 4> dy = {0, 1, 0, -1};
    while (n--) {
        tu[x][y] ^= 1;
        if (tu[x][y] == 0) {
            dir = (dir - 1 + 4) % 4;
        } else {
            dir = (dir + 1 + 4) % 4;
        }
        x = (x + dx[dir] + h) % h;
        y = (y + dy[dir] + w) % w;
    }
    for (auto& i : tu) {
        for (auto& j : i)
            cout << ".#"[j];
        cout << '\n';
    }

    return 0;
}



C - Perfect Bus (abc339 C)

题目大意

公交车,经过很多公交站,依次给定每个公交站时公交车的变化人数,由于初始时公交车人数不知道,问最后公交车可能人数的最小值。注意途中不能有负数的人。

解题思路

最小化最终的人数相当于最小化最开始的公交车人数。

可以先假设一开始\(0\)人,然后模拟经过这些公交站的上下人数变化,维护最小值。

如果最小值\(min < 0\),说明期间有公交车人数小于 \(0\),即假定开始人数\(0\)不合法,太少了,需要更多的人,多多少呢?就是多\(-min\)人就足够了,这样最小值就是\(0\),符合题目要求了。

如果\(min> 0\),说明开始\(0\)人已经足够了,但又不能更小,因此最后的结果即为答案了。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    LL minn = 0;
    LL sum = 0;
    while (n--) {
        int x;
        cin >> x;
        sum += x;
        minn = min(minn, sum);
    }
    LL ans = sum - minn;
    cout << ans << '\n';

    return 0;
}



D - Synchronized Players (abc339 D)

题目大意

二维网格,有障碍物,两个人。

问最小的操作数,使得两人位于同一个格子。

操作为:选定上下左右一个方向,使两人均往同方向移动一格。如果目的地是障碍物或出界,则不动。

解题思路

网格大小只有\(60 \times 60\),两人所处位置的状态数只有 \(60^4 = 10^7 < 5e8\),此即为朴素搜索的复杂度上限,因此直接\(BFS\)即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int inf = 1e9 + 7;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<string> tu(n);
    for (auto& i : tu)
        cin >> i;
    array<int, 4> dx = {0, 0, 1, -1};
    array<int, 4> dy = {1, -1, 0, 0};
    typedef array<int, 4> s;
    queue<s> q;
    vector<int> dis(n * n * n * n, inf);
    s st;
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            if (tu[i][j] == 'P') {
                st[0 + cnt * 2] = i;
                st[1 + cnt * 2] = j;
                tu[i][j] = '.';
                ++cnt;
            }
        }
    q.push(st);
    auto tr = [&](s x) {
        return x[0] * n * n * n + x[1] * n * n + x[2] * n + x[3];
    };
    dis[tr(st)] = 0;
    int ans = -1;
    auto ok = [&](int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n && tu[x][y] != '#';
    };
    while (!q.empty()) {
        auto u = q.front();
        int w = dis[tr(u)];
        auto [x1, y1, x2, y2] = u;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx1 = x1 + dx[i];
            int ny1 = y1 + dy[i];
            int nx2 = x2 + dx[i];
            int ny2 = y2 + dy[i];
            if (!ok(nx1, ny1)) {
                nx1 = x1;
                ny1 = y1;
            }
            if (!ok(nx2, ny2)) {
                nx2 = x2;
                ny2 = y2;
            }
            int v = tr({nx1, ny1, nx2, ny2});
            if (dis[v] > w + 1) {
                dis[v] = w + 1;
                q.push({nx1, ny1, nx2, ny2});
            }
            if (nx1 == nx2 && ny1 == ny2) {
                ans = dis[v];
                break;
            }
        }
        if (ans != -1)
            break;
    }
    cout << ans << '\n';

    return 0;
}



E - Smooth Subsequence (abc339 E)

题目大意

给定一个数组\(a\)和一个数\(D\),删去若干个数,使得剩余数俩俩差不超过\(D\)

问删去个数的最小值。

解题思路

考虑当前这个数\(a_r\),如果要保留它,我们则要找到左边也保留的数\(a_l\),且它们的差值不超过\(D\),且 \([l+1,...,r-1]\)都要删去。

发现只用考虑上一个保留数在哪,这是个非常简洁的状态,且具有递归性,所以一个朴素的 \(dp[i] = \max_{j < i \& |a_j - a_i| \leq D}(dp[j]) + 1\)

朴素转移是\(O(n^2)\),其中转移复杂度是 \(O(n)\)

考虑优化转移。

注意到转移条件是一个经典的二维偏序问题,因此用线段树维护转移即可。下标是\(a_j\),值是\(dp[j]\)

即当前\(dp[j]\)求出来后,将 \(dp[j]\)插入到线段树里,即将 \(a_j\)位置的值赋予 \(dp[j]\)

这样在求\(dp[i]\)时,线段树里的值都是 \(j < i\)\(dp[i]\)的值,自然满足第一个 \(j < i\)的条件,因为线段树的下标是 \(a_j\),而 \(|a_j - a_i| \leq D\)相当于一个区间 \([a_i - D, a_i + D]\),要求的就是这个区间的\(dp\)最大值,因为线段树维护的就是\(dp[j]\),故区间查询最大值、单点修改即可。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 5e5 + 10;

class segment {
#define lson (root << 1)
#define rson (root << 1 | 1)
  public:
    int maxx[N << 2];

    void build(int root, int l, int r) {
        if (l == r) {
            maxx[root] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(lson, l, mid);
        build(rson, mid + 1, r);
        maxx[root] = max(maxx[lson], maxx[rson]);
    }

    void update(int root, int l, int r, int pos, int val) {
        if (l == r) {
            maxx[root] = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid)
            update(lson, l, mid, pos, val);
        else
            update(rson, mid + 1, r, pos, val);
        maxx[root] = max(maxx[lson], maxx[rson]);
    }

    int query(int root, int l, int r, int ll, int rr) {
        if (ll > rr)
            return 0;
        if (ll <= l && r <= rr) {
            return maxx[root];
        }
        int mid = (l + r) >> 1;
        int ans = 0;
        if (ll <= mid)
            ans = max(ans, query(lson, l, mid, ll, rr));
        if (rr > mid)
            ans = max(ans, query(rson, mid + 1, r, ll, rr));
        return ans;
    }
} sg;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    int maxa = ranges::max(a);
    sg.build(1, 1, maxa);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int L = max(1, a[i] - d), R = min(a[i] + d, maxa);
        int dp = sg.query(1, 1, maxa, L, R) + 1;
        sg.update(1, 1, maxa, a[i], dp);
        ans = max(ans, dp);
    }
    cout << ans << '\n';

    return 0;
}



F - Product Equality (abc339 F)

题目大意

给定\(n\)个数 \(a_i\),问 \((i,j,k)\)的数量,使得 \(a_i \times a_j = a_k\)

注意 \(a_i \leq 10^{1000}\)

解题思路

因为\(n \leq 1000\),不考虑\(a_i\)大小的话,可以先统计\(cnt[i]\)表示值为 \(i\)的数量,然后 花 \(O(n^2)\)枚举 \(i,j\),计算 \(a_i \times a_j\),则对应的 \(k\)的数量即为 \(cnt[a_i \times a_j]\)

而由于 \(a_i\)很大, \(a_i \times a_j\)的计算比较棘手,就算用 FFT也有\(1000\)的常数, \(O(n^3)\)过不了。

怎么办呢?考虑如何避免大数的计算,一个常用的手法就是取模

如果\(a_i \times a_j = a_k\),那么也有 \((a_i \% mo \times a_j \% mo) \% mo = a_k \% mo\)

如果我们将模数 \(mo=1e9 + 7\)之类的数,那么取模后的结果就完全可以进行相乘,然后用上述的 \(O(n^2)\)枚举。

但是有可能原本不同的值取模后变成相同的值,注意相乘的结果个数是 \(O(10^6)\),模数\(O(1e9)\)的话, 可能会出现的概率有点高,因此可以取两个模数,即双hash的方式。

这个想法跟\(2021ICPC\)济南的一题,给了行列式的绝对值,问其符号是正是负的解决方法是一样的,同样数很大不能直接算出,但由于正负的取模结果是不一样的,因此也是取模后计算比较。

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL mo1 = 954169327;
const LL mo2 = 906097321;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<string> a(n);
    for (auto& i : a)
        cin >> i;
    auto mod1 = [&](string s) {
        LL ret = 0;
        for (auto& i : s) {
            ret = ret * 10 + (i - '0');
            ret %= mo1;
        }
        return ret;
    };
    auto mod2 = [&](string s) {
        LL ret = 0;
        for (auto& i : s) {
            ret = ret * 10 + (i - '0');
            ret %= mo2;
        }
        return ret;
    };
    vector<LL> b1(n), b2(n);
    map<LL, int> cnt1;
    map<LL, int> cnt2;
    for (int i = 0; i < n; ++i) {
        b1[i] = mod1(a[i]);
        cnt1[b1[i]]++;
        b2[i] = mod2(a[i]);
        cnt2[b2[i]]++;
    }
    LL ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            LL k1 = (b1[i] * b1[j]) % mo1;
            LL k2 = (b2[i] * b2[j]) % mo2;
            LL t1 = 0, t2 = 0;
            if (cnt1.count(k1)) {
                t1 = cnt1[k1];
            }
            if (cnt2.count(k2)) {
                t2 = cnt2[k2];
            }
            ans += min(t1, t2);
        }
    cout << ans << '\n';

    return 0;
}



G - Smaller Sum (abc339 G)

题目大意

给定\(n\)个数 \(a_i\),回答 \(q\)个询问。

每次询问给定 \(l, r, x\),求\(\sum_{l \leq i \leq r \& a_i \leq x} a_i\)

强制在线。

解题思路

如果可以离线的话,莫队可以解决。

但这里强制在线,注意到求和式子同样是一个二维偏序问题。

我们可以先把上式拆成两式相减:

\[\sum_{i \leq r \& a_i \leq x} a_i - \sum_{i \leq l - 1 \& a_i \leq x} a_i \]

这个的形式就跟\(E\)题的转移式一模一样,只是这里是求和,E题的求最大值。

因此可以用线段树求解,下标是\(a_i\),值也是 \(a_i\)

但这里需要保存,维护了\([1,l-1]\)状态的线段树和\([1,r]\)状态的线段树 ,因此需要可持久化线段树,即主席树维护即可。

每次询问就两棵历史版本的线段树的一个区间查询的差就是答案。

时间复杂度是\(O(q\log \max a_i)\)

主席树板子是贴的,贴贴快乐

神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int M = 1e6 + 8;
const int ls = 1e9;
namespace tree {
#define mid ((l + r) >> 1)
#define lson l, mid
#define rson mid + 1, r
const int MAGIC = M * 30;
struct P {
    LL sum;
    int ls, rs;
} tr[MAGIC] = {{0, 0, 0}};
int sz = 1;
int N(LL sum, int ls, int rs) {
    if (sz == MAGIC)
        assert(0);
    tr[sz] = {sum, ls, rs};
    return sz++;
}
int ins(int o, int x, LL v, int l = 1, int r = ls) {
    if (x < l || x > r)
        return o;
    const P& t = tr[o];
    if (l == r)
        return N(t.sum + v, 0, 0);
    return N(t.sum + v, ins(t.ls, x, v, lson), ins(t.rs, x, v, rson));
}
LL query(int o, int ql, int qr, int l = 1, int r = ls) {
    if (ql > r || l > qr)
        return 0;
    const P& t = tr[o];
    if (ql <= l && r <= qr)
        return t.sum;
    return query(t.ls, ql, qr, lson) + query(t.rs, ql, qr, rson);
}
} // namespace tree

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a)
        cin >> x;
    vector<int> root(n);
    for (int i = 0; i < n; ++i) {
        root[i] = tree::ins(i ? root[i - 1] : 0, a[i], a[i]);
    }
    int q;
    cin >> q;
    LL ans = 0;
    while (q--) {
        LL l, r, x;
        cin >> l >> r >> x;
        l ^= ans;
        r ^= ans;
        x ^= ans;
        --l, --r;
        ans = tree::query(root[r], 1, x);
        if (l)
            ans -= tree::query(root[l - 1], 1, x);
        cout << ans << '\n';
    }

    return 0;
}



热门相关:万古第一帝   盛唐小园丁   影帝偏要住我家   铁血大明   虎狼之师