首页 > 其他分享 >AtCoder Beginner Contest 335

AtCoder Beginner Contest 335

时间：2024-01-19 15:45:16浏览次数：39  
标签：AtCoder Beginner 335 auto mo cin long int dp

A - 2023 (abc335 A)

题目大意

给定一个字符串，将最后一位改成4。

解题思路

模拟即可。

神奇的代码 
#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);
    string s;
    cin >> s;
    s.back() = '4';
    cout << s << '\n';

    return 0;
}

B - Tetrahedral Number (abc335 B)

题目大意

给定\(n\)，按字典序输出非负整数\(i,j,k\)，使得 \(i+j+k\leq n\)

解题思路

\(n\)只有 \(21\)，直接 \(O(n^3)\)枚举判断即可。

神奇的代码 
#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;
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= n; ++j)
            for (int k = 0; k <= n; ++k)
                if (i + j + k <= n)
                    cout << i << ' ' << j << ' ' << k << '\n';

    return 0;
}

C - Loong Tracking (abc335 C)

题目大意

二维网格，贪吃蛇，移动，进行\(q\)次操作，分两种

  • 指定贪吃蛇下一步移动的方向
  • 指定\(i\)，输出贪吃蛇的第 \(i\)个部位的坐标。

解题思路

每移动一次，只有头部到了新的坐标，其他部分的坐标都变成前一个。

如果我们把每个部分的坐标按顺序放在一个队列里，队尾是头部坐标，队头是尾部坐标，每次移动相当于一次出队和一次入队。

但stl的队列queue不支持随机访问，因此用vector模拟这个队列即可。

出队其实没有必要操作，不断push_back即可。问第\(i\)个部位坐标就从队尾倒着数即可。

神奇的代码 
#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, q;
    cin >> n >> q;
    vector<array<int, 2>> pos(n);
    for (int i = 0; i < n; ++i) {
        pos[i] = {n - i, 0};
    }
    map<char, array<int, 2>> dir{
        {'U', {0, 1}}, {'D', {0, -1}}, {'L', {-1, 0}}, {'R', {1, 0}}};
    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            string s;
            cin >> s;
            auto [x, y] = pos.back();
            auto [dx, dy] = dir[s[0]];
            x += dx;
            y += dy;
            pos.push_back({x, y});
        } else if (op == 2) {
            int s;
            cin >> s;
            auto [x, y] = *(pos.end() - s);
            cout << x << ' ' << y << '\n';
        }
    }

    return 0;
}

D - Loong and Takahashi (abc335 D)

题目大意

给定一个\(n \times n\)的二维网格，\(n\)奇数，给每个格子一个数字\(\in [1, n^2 - 1]\)，要求每个数字仅使用一次，且相邻数字的格子相邻，且正中间的格子不能是数字，而是T。

给出一种构造方法。

解题思路

按照样例的构造方式，一个螺旋回字构造即可。

每次一个螺旋回字构造就填充最外围的一圈，起点依次为\((1,1) \to (2,2) \to (3,3)\) ，最后恰好到正中间，因此能恰好填满。

神奇的代码 
#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;
    int mid = n / 2;
    vector<vector<int>> tu(n, vector<int>(n, 0));
    int num = 1;
    array<array<int, 2>, 4> dir{{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}};
    int cur = 0;
    int x = 0, y = 0;
    while (x != mid || y != mid) {
        tu[x][y] = num;
        auto [dx, dy] = dir[cur];
        int nx = x + dx, ny = y + dy;
        while (nx < 0 || nx >= n || ny < 0 || ny >= n || tu[nx][ny] != 0) {
            cur = (cur + 1) % 4;
            auto [dx, dy] = dir[cur];
            nx = x + dx, ny = y + dy;
        }
        ++num;
        x = nx, y = ny;
    }

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            if (i == mid && j == mid)
                cout << 'T' << ' ';
            else
                cout << tu[i][j] << " \n"[j == n - 1];
        }

    return 0;
}

E - Non-Decreasing Colorful Path (abc335 E)

题目大意

给定一张无向图，点有点权。

找一条从\(1\to n\)的路径，其点权不递减，且不同的数的个数最多。不存在则输出\(0\)。

解题思路

注意到这个路径要求点权是一个不严格递增的情况，这明显存在一个决策的方向性，即点权大的一定从点权小的求得答案，当点权小的答案都求完了，那么该点权大的答案也求完了，即固定了，知晓了。

因此就直接设\(dp[i]\)表示到达点 \(i\)时的最大的答案（不同的数的个数最多），按照点权从小到大转移，若点权相同则按照答案从大到小转移。用优先队列维护转移顺序即可。往后转移。初始条件为\(dp[1] = 1\)

也可以根据点权构造边权，注意到图如果有环，其边权一定都是\(0\)，缩环后变成一张DAG（有向无环图），直接拓扑 \(DP\)即可，其实跟上面是一样的。

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

const int inf = 1e9;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    vector<vector<array<int, 2>>> edge(n);
    auto add = [&](int u, int v) {
        if (a[u] <= a[v])
            edge[u].push_back({v, -(a[u] != a[v])});
    };
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        add(u, v);
        add(v, u);
    }
    vector<int> dis(n, inf);
    dis[0] = -1;
    priority_queue<array<int, 3>> q;
    q.push({-a[0], -dis[0], 0});
    while (!q.empty()) {
        auto [_, d, u] = q.top();
        q.pop();
        if (dis[u] != -d)
            continue;
        for (auto [v, w] : edge[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({-a[v], -dis[v], v});
            }
        }
    }
    debug(dis);
    cout << max(0, -dis.back()) << '\n';

    return 0;
}

F - Hop Sugoroku (abc335 F)

题目大意

给定一个\(n\)个数的数组\(a\)， 你在\(0\)处。当你在 \(i\)处时，你可以移动到 \(j = i+a_i \times k < n\)处，\(k\)为正整数，也可以不移动。

问你可以移动到的位置的集合数量。

解题思路

注意到每次移动一定是往右边移动，具有明显的决策方向性，可以设\(dp[i]\)表示移动到第 \(i\)个位置时，移动位置的集合数量（即这个集合中的最大值为 \(i\)的集合数量）。

转移式则为\(dp[i] = \sum_{j \% a_j == i \% a_j} dp[j]\)，初始条件为 \(dp[0] = 1\)。

上述\(dp\)的复杂度为 \(O(n^2)\)，考虑如何优化转移。

但思考下会发现上述转移最坏情况就是 \(O(n)\)，当 \(a_j\)全部为\(1\)时 ，就要对每个\(j\)都累加。但因为是对每个 \(j\)都累加，事实上我们可以预先处理出前缀和，这样就可以 \(O(1)\)。

考虑这个前缀和的形式是怎样的，我们对\(a_j\)的值进行了枚举，假设为 \(x\)，那满足转移条件的 \(j\) 则为\(j \% x == i \% x = y\)，我们要把这些 \(j\)的 \(dp[j]\)累加，即 \(sum[x][y] = \sum_{j \% x == y} dp[j]\) ，这样\(dp[i] = \sum_{x=1}^{\max a}sum[x][i \% x]\)。

但因为\(\max a\)是 \(2e5\)，和\(n\)同一个数量级，上述转移 复杂度还是\(O(n^2)\)。

但注意到如果\(a_j\)比较大时，满足条件的\(j\) 的数量是很少的，这种情况下我们可以暴力转移，这个转移是往后转移，即当前为\(i\)，则 \(dp[j] += dp[i](j = i + a_i \times k)\)。

这期间就有个分界点，我们设分界点为\(mid = \sqrt{n}\)

  • 当\(a_i > mid\)时，我们暴力更新后面的\(dp[j]\)，这样的\(j\)的数量（即 \(k\)的数量）不超过\(\frac{n}{\sqrt{n}} = \sqrt{n}\)个。更新的复杂度是\(O(n \sqrt{n})\)
  • 当\(a_i \leq mid\)时，由于转移的数量 \(j\)很多，我们就先不转移，先保存在 \(sum\)数组里（可以看成是懒标记），即 \(sum[a_i][i \% a_i] += dp[i]\)。更新的复杂度是\(O(1)\)

这样，对于后续的一个\(i\)的 \(dp[i]\)的值，注意到原始转移式是\(dp[i] = \sum_{j \% a_j == i \% a_j} dp[j]\)，我们已经把情况一（即\(a_j > mid\)）的\(dp[j]\)累加进 \(dp[i]\)里了，还剩下\(a_j \leq mid\)的没累加进来，因此此时再 \(dp[i] += \sum_{j = 1}^{mid}sum[j][i \% j]\)即可。更新的复杂度是\(O(n \sqrt{n})\)

最终的时间复杂度是\(O(n\sqrt{n})\)。

注意到上述转移里，我们把\(j\)和 \(a_j\)是割裂开了，考虑 \(a_j\)的所有取值情况，然后分成两类分别处理。

这其实也是一类经典的\(dp\)优化方法，即根号分治\(dp\)，即存在两种形式的转移，且在不同数量级下时间复杂度各有优势，然后结合起来， \(\sqrt{n}\)是一个经典的分界点

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

const int mo = 998244353;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int half = sqrt(n);
    vector<vector<int>> sum(half, vector<int>(half, 0));
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    vector<int> dp(n);
    dp[0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j < half; ++j) {
            dp[i] += sum[j][i % j];
            if (dp[i] >= mo)
                dp[i] -= mo;
        }
        if (a[i] >= half) {
            for (int j = i + a[i]; j < n; j += a[i]) {
                dp[j] += dp[i];
                if (dp[j] >= mo)
                    dp[j] -= mo;
            }
        } else {
            sum[a[i]][i % a[i]] += dp[i];
            if (sum[a[i]][i % a[i]] >= mo)
                sum[a[i]][i % a[i]] -= mo;
        }
    }
    int ans = 0;
    for (auto& i : dp) {
        ans += i;
        if (ans >= mo)
            ans -= mo;
    }
    cout << ans << '\n';

    return 0;
}

G - Discrete Logarithm Problems (abc335 G)

题目大意

给定一个数组\(a\)和一个质数\(P\)，求 \((i,j)\)的数量，满足以下条件

  • 存在 \(k\)，使得 \(a_i ^ k \equiv a_j (\mod P)\)

解题思路

这题难在需要有数论知识。

首先因为有质数\(P\)，会存在一个原根 \(g\)，使得 \(g^0 \sim g^{P-2}\)的值恰好取遍了 \(1 \sim P-1\) ，由费马小定理知\(g^{P-1} \equiv g^0 \equiv 1(\mod P)\)就回到了起点。上述的幂是对\(P\)取模的。

因此\(a_i\)可以找到个 \(x\)，使得 \(g^x \equiv a_i (\mod P)\)，对应的\(a_j\)则对应\(y\)。

除此之外，关于阶的概念：一个数的阶是一个最小的正整数\(m\)，使得 \(a_i ^ m \equiv 1 (\mod P)\) ，其实就是循环节的长度，一般记为\(ord(a_i)\)。

然后是一个简单但深刻的定理：

  • 如果存在\(k\)，使得\(a_i^k \equiv a_j(\mod P)\)，则有 \(ord(a_j) | ord(a_i)\)

如何通俗点理解呢？考虑阶的定义，\(g^{xm} \equiv 1 \equiv g^0(\mod P)\)，关心指数部分的话，即为 \(xm \equiv 0 (\mod P-1)\) ，即\(xm = n(P-1)\)。

注意到\(m\)是最小的，怎么最小呢？我们要让 \(xm\)是 \(P-1\)的倍数，我们将 \(x\)和 \(P-1\)质因数分解， \(x\)缺少的那些质因数就是造成\(x\)不是 \(P-1\)的倍数的原因，这缺少的部分就由 \(m\)补上，那这个 \(m\)就是最小的了。注意这里的\(m\)就是一个数的阶\(order\)。它就是 \(x\)相对于 \(P-1\)缺少的那部分质因数，所以也必定是 \(P-1\)的因子

这里得到了另一个简单但也深刻的定理，也是最后求一个数的阶的理论依据：

  • \(ord(a_i) | P-1\)

对于 \(a_j\)来说，就是 \(ym^{\prime}=kxm^{\prime} = n^{\prime}(P-1)\)。我们知道\(xm\)已经是 \(P-1\)的倍数了，那 \(kxm\)也必定是 \(P-1\)的倍数，但这里的\(m\)不一定是最小的，因为 \(k\)也带来了一些 \(P-1\)的质因数，因此 \(m^\prime\)会比 \(m\)更小，它去掉了 \(k\)包括的 \(P-1\)的一些质因数，也即 \(m^{\prime} | m\)，即\(ord(a_j) | ord(a_i)\)。

因此，如果我们求出了每个\(a_i\)的阶，剩下的就是求一个数的倍数有多少个。

如何快速求一个数的阶呢？注意到 \(ord(a_i) | P-1\)，我们先假设其阶\(m=P-1\)，此时必有 \(a_i^{P-1} \equiv 1(\mod P)\)，但此时可能不是最小的，因为关于 \(P-1\)的质因数有多余的（跟上面的 \(kxm\)的 \(m\)不是最小的一个道理），我们要把多余的质因数去掉。

如何去除呢？其实只要枚举去除哪个质数，去除该质数的指数是多少即可。当去除的过多时，就不满足\(a_i^{m} \equiv 1(\mod P)\) ，但还能去除时，则还会满足该等式。所谓最小的\(m\)，意味着任何一个更小的数，都不会满足该等式。

注意到 \(P\)只有 \(1e13\)，质因数种类最多只有 \(\log P\)个，每个质数的幂最大也只有 \(\log P\) ，因此可以在\(O(\log^3 P)\)的复杂度内求出一个数的阶（还有一个\(\log\)是快速幂）。

因此一开始先对\(P-1\)质因数分解，然后求出每个数的阶，此时显然不能\(O(n^2)\)枚举阶，判断倍数关系。

注意到 \(P-1\)只有\(10^{13}\)，最多只有 \(12\)个左右的质数，因此其因数个数最多只有 \(2^12\)，是\(d=O(10^3)\)的数量级，因为阶一定是\(P-1\)的倍数，虽然有 \(O(n)\)个，但不同的阶的数量不超过 \(O(d)\)，因此我们可以统计每个阶的数量，直接 \(O(d^2)\)枚举每个阶的数量，判断倍数累加答案即可。

注意判阶数时的快速幂可能会爆long long。

最终的时间复杂度是\(O(n\log^3 P) + d^2(P-1))\)

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

long long qpower(__int128 a, __int128 b, long long mo) {
    __int128 qwq = 1;
    while (b) {
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    LL mo;
    cin >> n >> mo;
    LL phi = mo - 1, tmp = phi;
    vector<LL> a(n);
    for (auto& i : a)
        cin >> i;
    vector<LL> prime;
    int half = sqrt(phi) + 1;
    for (int i = 2; i <= half; ++i) {
        if (phi % i == 0) {
            prime.push_back(i);
            while (phi % i == 0)
                phi /= i;
        }
    }
    if (phi != 1)
        prime.push_back(phi);
    phi = tmp;
    map<LL, int> cnt;
    auto order = [&](LL x) {
        LL m = phi;
        for (auto& i : prime) {
            while (m % i == 0 && qpower(x, m / i, mo) == 1) {
                m /= i;
            }
        }
        return m;
    };
    for (auto& i : a) {
        cnt[order(i)]++;
    }
    LL ans = 0;
    for (auto& i : cnt) {
        for (auto& j : cnt) {
            if (i.first % j.first == 0) {
                ans += 1LL * i.second * j.second;
            }
        }
    }
    cout << ans << '\n';

    return 0;
}

标签：AtCoder,Beginner,335,auto,mo,cin,long,int,dp
From： https://www.cnblogs.com/Lanly/p/17974808

相关文章

  • CodeForces & AtCoder rating 规则简述
    译者：rui_er，转载请注明出处。（备份自2020年11月2日的同名博客）本博客为了方便自己查阅，同时也方便大家了解，但因为我英语很菜，所以难免有翻译错的地方，还请评论区纠正。未注明资料来源的均为常识积累。1CodeForcesrating规则1.1CodeForcesrating与名字颜色换算设\(r\)......
  • AtCoder ABC 273 复盘
    AARecursiveFunction模拟，递归、递推、累乘都可以。我用的累乘。ACCodeBBrokenRounding也是模拟，每次将\(X\leftarrowX\div10^{i-1}\)后判断\(X\bmod10\)是否\(\geq5\)，若是，\(X\leftarrowX+10\)；若不是，不进行操作。最后再将\(X\div10\)输出。ACCodeC(K+1)-......
  • AtCoder ABC 270 复盘
    A1-2-4TestACCodeBHammerACCodeCSimplepathACCodeDStones完全背包的应用。ACCodeEAppleBasketsonCircle有一点数学，又有一点贪心，还有二分。首先将每个篮子取走\(\min_{1\leqi\leqn}(A_i)\)个苹果，然后再不断扫描数组，按照题意取走苹果。ACCode......
  • AtCoder ABC 267 复盘
    ASaturdayACCodeBSplit?ACCodeCIndex×A(Continuousver.)本题可以采用类似滑动窗口的做法，使得时间复杂度降至\(O(n+m)\)。ACCodeDIndex×A(NotContinuousver.)本题是典型的01背包问题，只需要对值进行相应的修改即可。ACCodeEErasingVertices2本题......
  • AtCoder Beginner Contest 336
    题目链接：AtCoderBeginnerContest336A-LongLoong题意：输出Long，其中'o'的数量等于n解题思路：签到（其实没看清楚题目wa了一发）查看代码voidsolve(){ intn; cin>>n; cout<<'L'; while(n--)cout<<'o'; cout<<"ng";}......
  • AtCoder ABC 279 复盘
    AwwwvvvvvvACCodeBLOOKUPACCodeCRANDOMACCodeDFreefall分析一下样例1，可以发现答案存在一个\(\sqrt{g}\)，然后就联想到三分。这里图像是开口朝上的。注意要开longlong！（但我的代码需要__int128才行，玄学）ACCodeECheatingAmidakuji分析过程，可以发现第\(i\)次......
  • Atcoder 336 C
    题目链接https://atcoder.jp/contests/abc336/tasks/abc336_c一开始没有想到第N个数字与N之间的关系，但是在思考的过程中似乎发现了这几个数字与"5"有什么奇怪的联系。但是我想到这里时还没有将这道题和进制转换建立联系，只是觉得可以根据“5”的规律来推出第N个数字的各......
  • AtCoder Grand Contest 046 F Forbidden Tournament
    洛谷传送门AtCoder传送门太厉害了！！！！！！首先竞赛图有个性质，若存在环则一定存在三元环。先把DAG的情况（一条链）特判了。然后缩点。发现非链底的部分不能存在大小\(>1\)的SCC。所以枚举非链底的部分有多少点，转化为SCC的情况。发现对于任意点（设为\(1\)号点），它的前驱连成一条链......
  • Atcoder Beginner Contest 330 题解
    AtCoderBeginnerContest330题解A-CountingPasses签到voidShowball(){intn,l;cin>>n>>l;intcnt=0;for(inti=0;i<n;i++){intx;cin>>x;cnt+=(x>=l);}cout<<cnt<<endl;}B-Minimize......
  • AtCoder Beginner Contest 336
    B-CTZ难度:⭐题目大意给定一个数n,输出其二进制最后有几个连续的0;解题思路模拟一下就行;神秘代码#include<bits/stdc++.h>#defineintlonglong#defineIOSios::sync_with_stdio(false);cin.tie(0);cout.tie(0);#defineendl'\n'usingnamespacestd;......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99