首页 > 其他分享 >ATcoder ABC 351 补题记录（A~F）

ATcoder ABC 351 补题记录（A~F）

时间：2024-06-08 22:32:43浏览次数：21  
标签：ATcoder ABC int Add times add 补题 mod define

A

按照顺序直接模拟即可。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define em emplace_back
#define F(i,x,y) for(int i=x;i<=y;i++)
#define G(i,x,y) for(int i=x;i>=y;i--)
#define W(G,i,x) for(auto&i:G[x])
#define W_(G,i,j,x) for(auto&[i,j]:G[x])
#define add(x,y) z[x].em(y)
#define add_(x,y) add(x,y),add(y,x)
#define Add(x,y,d) z[x].em(y,d)
#define Add_(x,y,z) Add(x,y,z),Add(y,x,z);
#ifdef int
#define inf (7611257611378358090ll/2)
#else
#define inf 0x3f3f3f3f
#endif
using namespace std;
const int N = 1000100;
int a[N], n;
signed main() {
    int n, m, cnt = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int h;
        cin >> h;
        m -= h;
        if (m >= 0) {
            cnt++;
        } else {
            break;
        }
    }
    cout << cnt << '\n';
}

B

直接比较大写字母和小写字母的数量即可。

时间复杂度为 \(O(n)\)。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define em emplace_back
#define F(i,x,y) for(int i=x;i<=y;i++)
#define G(i,x,y) for(int i=x;i>=y;i--)
#define W(G,i,x) for(auto&i:G[x])
#define W_(G,i,j,x) for(auto&[i,j]:G[x])
#define add(x,y) z[x].em(y)
#define add_(x,y) add(x,y),add(y,x)
#define Add(x,y,d) z[x].em(y,d)
#define Add_(x,y,z) Add(x,y,z),Add(y,x,z);
#ifdef int
#define inf (7611257611378358090ll/2)
#else
#define inf 0x3f3f3f3f
#endif
using namespace std;
const int N = 1000100;
int a[N];
signed main() {
    string s;
    cin >> s;
    int c1 = 0, c2 = 0;
    for (auto &x : s) {
        if (islower(x)) c1++;
        else c2++;
    }
    if (c1 < c2) {
        for (auto &x : s) x = toupper(x);
        cout << s << '\n';
    } else {
        for (auto &x : s) x = tolower(x);
        cout << s << '\n';
    }
}

C

模拟题。

考虑对于一个 \(3^n\times 3^n\) 的矩阵，可以将其分割为 \(9\) 个 \(3^{n-1}\times 3^{n-1}\) 的矩阵，其中这 \(9\) 个矩阵又构成了 \(3\times 3\) 的大矩阵。

因此直接计算出 \(9\) 个矩阵的左上角和右下角的坐标，然后除了中间的一个矩阵以外其他的矩阵继续递归处理即可。

时间复杂度为 \(O(3^{2n})\)。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define em emplace_back
#define F(i,x,y) for(int i=x;i<=y;i++)
#define G(i,x,y) for(int i=x;i>=y;i--)
#define W(G,i,x) for(auto&i:G[x])
#define W_(G,i,j,x) for(auto&[i,j]:G[x])
#define add(x,y) z[x].em(y)
#define add_(x,y) add(x,y),add(y,x)
#define Add(x,y,d) z[x].em(y,d)
#define Add_(x,y,z) Add(x,y,z),Add(y,x,z);
#ifdef int
#define inf (7611257611378358090ll/2)
#else
#define inf 0x3f3f3f3f
#endif
using namespace std;
const int N = 1000100;
int a[N], n;
char s[5999][5999];
void dfs(int n, int x = 1, int y = 1) {
    if (n == 0) {
        s[x][y] = '#';
    } else {
        int key = 1;
        for (int i = 1; i < n; i++) {
            key = key * 3;
        }
        dfs(n - 1, x, y);
        dfs(n - 1, x + key, y);
        dfs(n - 1, x + key + key, y);
        dfs(n - 1, x, y + key);
        dfs(n - 1, x + key + key, y + key);
        dfs(n - 1, x, y + key + key);
        dfs(n - 1, x + key, y + key + key);
        dfs(n - 1, x + key + key, y + key + key);
    }
}
signed main() {
    cin >> n;
    if (!n) {
        cout << "#\n";
    } else {
        int key = 1;
        for (int i = 0; i < n; i++) {
            key *= 3;
        }
        for (int i = 1; i <= key; i++) {
            for (int j = 1; j <= key; j++) {
                s[i][j] = '.';
            }
        }
        dfs(n);
        for (int i = 1; i <= key; i++, cout << '\n') {
            for (int j = 1; j <= key; j++) {
                cout << s[i][j];
            }
        }
    }
}

D

考虑经典套路。这里重定义 \(|n|\) 表示 \(n\) 的位数，即 to_string(n).size()（请使用 C++11 及以上版本）。\(S_n\) 表示 \(N=n\) 时的答案。

首先考虑 \(|n|\le 1\) 的情况。此时沿用 P4884 的解决方案。有 \(S_n=n\times \frac{10^n-1}{9}\)。

问题是 \(|n|>1\) 时的情况。容易发现此时等式 \(\large S_n=n\times \frac{10^{n\times|n|}}{10^k-1}\) 成立。证明显然。

然后考虑计算这个东西。当 \(n=10^{18}\) 时 \(n\times |n|=10^{18}\times 19=1.9\times 10^{18}>2^{64}-1\) 是很恶心的一点，所以请使用 __int128 来计算答案。其实也可以使用 atcoder::modint998244353 来计算答案。

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define em emplace_back
#define F(i,x,y) for(int i=x;i<=y;i++)
#define G(i,x,y) for(int i=x;i>=y;i--)
#define W(G,i,x) for(auto&i:G[x])
#define W_(G,i,j,x) for(auto&[i,j]:G[x])
#define add(x,y) z[x].em(y)
#define add_(x,y) add(x,y),add(y,x)
#define Add(x,y,d) z[x].em(y,d)
#define Add_(x,y,z) Add(x,y,z),Add(y,x,z);
#ifdef int
#define inf (7611257611378358090ll/2)
#else
#define inf 0x3f3f3f3f
#endif
using namespace std;
const int mod = 998244353;
int ksm(int a, __int128 b, int c) {
    if (!b) return 1;
    int ans = ksm(a, b / 2, c);
    ans = ans * ans % c;
    if (b & 1) ans = ans * a % c;
    return ans;
}
signed main() {
    int n;
    cin >> n;
    int len = to_string(n).size();
    int key = ksm(10, (__int128)(len) * n, mod);
    key = (key + mod - 1) % mod;
    int ii = ksm((ksm(10, len, mod) + mod - 1) % mod, mod - 2, mod);
    // cout << "dbg " << ii << ' ' << key << '\n';
    cout << (n % mod) * ii % mod * key % mod << '\n';
}

E

不理解为什么题目保证边数不大于点数。这个题 \(m>n\) 不是也可以做吗。

首先建反图，然后考虑使用 Tarjan 算法将有向图中的每一个强连通分量在新图中缩为一个点，然后剩下一个 DAG 森林考虑搞一下。

设 \(f_i\) 表示可以到达新图 \(i\) 点的点的数量，\(g_i\) 表示以新图 \(i\) 点结尾的不同的路径的总数目。

那么对于每一条 \(j\to i\) 的边，必然有：

  • \(f_i=f_i+f_j\)。
  • \(g_i=g_i+f_j\times \text{CNT}_i\)。

其中 \(\text{CNT}_i\) 表示新图中 \(i\) 点在原图中对应的强连通分量中点的数目。

因为新的图是 DAG 森林，所以每一次从入度为 \(0\) 的结点开始转移，在拓扑排序的过程中就可以直接求出答案。

因为不同的 \(i\) 对应的 \(g_i\) 对应的路径是互不重复的，所以答案就是 \(\sum\limits_{i=1}^ng_i\)，不需要容斥。

时间复杂度为 \(O(n+m)\)。如果写丑了可能会出问题。

#include<bits/stdc++.h>
#define int long long
#define said(...)
#define pb push_back
#define em emplace_back
#define F(i,x,y) for(int i=x;i<=y;++i)
#define G(i,x,y) for(int i=x;i>=y;--i)
#define W(G,i,x) for(auto&i:G[x])
#define W_(G,i,j,x) for(auto&[i,j]:G[x])
#define add(x,y) z[x].em(y)
#define add_(x,y) add(x,y),add(y,x)
#define Add(x,y,d) z[x].em(y,d)
#define Add_(x,y,z) Add(x,y,z),Add(y,x,z);
#define inf (7611257611378358090ll/2)
using namespace std;
const int N = 500100;
const int mod = 998244353;

stack<int> stk;
vector<int> z[N], scc[N];
int idx, tot, instk[N], dfn[N], low[N], bel[N], cnt[N], dis[N], vis[N], en[N], deg[N];
struct Edg { int u, v; } ed[N];
void dfs(int u) {
    dfn[u] = low[u] = ++idx;
    stk.push(u), instk[u] = true;
    W(z, j, u) {
        if (!dfn[j]) {
            dfs(j);
            low[u] = min(low[u], low[j]);
        } else if (instk[j]) {
            low[u] = min(low[u], dfn[j]);
        }
    }
    if (dfn[u] == low[u]) {
        tot++;
        while (stk.top() != u) {
            int t = stk.top();
            stk.pop(), instk[t] = false;
            bel[t] = tot, scc[tot].pb(t);
        }
        int t = stk.top();
        stk.pop(), instk[t] = false;
        bel[t] = tot, scc[tot].pb(t);
    }
}
int a[N], dp[N], gg[N];
auto main() [[O3]] -> signed {
    int n;
    cin >> n;
    F(i, 1, n) {
        int x;
        cin >> x;
        a[i] = x;
        z[i].push_back(x);
    }
    F(i, 1, n) {
        if (!dfn[i]) {
            dfs(i);
        }
    }
    F(i, 1, n) {
        z[i].clear();
    }
    F(i, 1, n) {
        if (bel[i] != bel[a[i]]) {
            deg[bel[i]]++;
            z[bel[a[i]]].push_back(bel[i]);
        }
    }
    queue<int> q;
    F(i, 1, tot) {
        if (!deg[i]) {
            q.push(i);
        }
        gg[i] = scc[i].size();
        dp[i] = scc[i].size() * scc[i].size();
    }
    while (q.size()) {
        int f = q.front();
        q.pop();
        for (auto &g : z[f]) {
            gg[g] = (gg[g] + gg[f]) % mod;
            dp[g] = (dp[g] + scc[g].size() * gg[f] % mod) % mod;
            if (!--deg[g]) {
                q.push(g);
            }
        }
    }
    cout << accumulate(dp + 1, dp + tot + 1, 0ll) << '\n';
}

F

区间修改区间查询很显然的线段树。

考虑对于线段树的每一个结点维护 \(A\) 的和，\(B\) 的和，\(A\) 的懒标记，\(B\) 的懒标记，当前区间内的答案的和。

首先 push_up 的时候直接将 \(A\)，\(B\) 的和和答案的和全部直接把左右儿子的值加起来即可。

修改的时候：

  • 若当前修改的是 \(A\) 的值，则答案从 \(a_l\times b_l+a_{l+1}\times b_{l+1}+\ldots+a_r\times b_r\) 变为了 \((a_l+v)\times b_l+(a_{l+1}+v)\times b_{l+1}+\ldots+(a+r+v)\times b_r\)。显然后面的式子为 \((a_l\times b_l+a_{l+1}\times b_{l+1}+\ldots+a_r\times b_r)+v\times (b_l+b_{l+1}+b_{l+2}+\ldots+b_r)=(a_l\times b_l+a_{l+1}\times b_{l+1}+\ldots+a_r\times b_r)+v\times B\)。所以更新答案的时候直接把 \(A\) 加上 \((r-l+1)\times v\)，总和加上 \(v\times B\) 即可。
  • 若当前修改的为 \(B\) 的值，则和 \(A\) 的情况一样，\(B\) 加上 \((r-l+1)\times v\)，总和加上 \(v\times A\) 即可。

下传标记直接按照 \(A\)，\(B\) 的顺序下传即可，时间复杂度为 \(O(n\log n)\)。注意不要爆 long long。

#include<bits/stdc++.h>
#define int long long
#define said(...)
#define pb push_back
#define em emplace_back
#define F(i,x,y) for(int i=x;i<=y;++i)
#define G(i,x,y) for(int i=x;i>=y;--i)
#define W(G,i,x) for(auto&i:G[x])
#define W_(G,i,j,x) for(auto&[i,j]:G[x])
#define add(x,y) z[x].em(y)
#define add_(x,y) add(x,y),add(y,x)
#define Add(x,y,d) z[x].em(y,d)
#define Add_(x,y,z) Add(x,y,z),Add(y,x,z);
#define inf (7611257611378358090ll/2)
using namespace std;
const int N = 200100;
const int mod = 998244353;

int a[N], b[N];
struct Node {
    int l, r, a, b, taga, tagb, sum;
    void init(int p) {
        l = r = p;
        a = ::a[p];
        a %= mod;
        b = ::b[p];
        b %= mod;
        taga = tagb = 0;
        sum = a * b % mod;
    }
    void c1(int v) {
        v %= mod;
        taga += v, a += (r - l + 1) * v;
        sum += v * b; sum %= mod;
        taga %= mod, a %= mod;
        // sum += b * v;
    }
    void c2(int v) {
        v %= mod;
        tagb += v, b += (r - l + 1) * v;
        sum += v * a % mod; sum %= mod;
        tagb %= mod, b %= mod;
        // sum = a * b;
    }
} z[N << 2];
Node operator+(const Node &l, const Node &r) {
    Node res;
    res.l = l.l, res.r = r.r;
    res.a = l.a + r.a, res.b = l.b + r.b, res.sum = l.sum + r.sum;
    res.a %= mod, res.b %= mod, res.sum %= mod;
    res.taga = res.tagb = 0;
    return res;
}
void build(int l, int r, int rt) {
    if (l == r) {
        return z[rt].init(l);
    }
    int mid = l + r >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
void pud(int rt) {
    if (z[rt].taga != 0) {
        z[rt << 1].c1(z[rt].taga);
        z[rt << 1 | 1].c1(z[rt].taga);
        z[rt].taga = 0;
    }
    if (z[rt].tagb != 0) {
        z[rt << 1].c2(z[rt].tagb);
        z[rt << 1 | 1].c2(z[rt].tagb);
        z[rt].tagb = 0;
    }
}
void modify1(int l, int r, int rt, int ll, int rr, int v) {
    if (ll <= l && r <= rr) {
        return z[rt].c1(v);
    }
    int mid = l + r >> 1;
    pud(rt);
    if (ll <= mid) {
        modify1(l, mid, rt << 1, ll, rr, v);
    }
    if (mid < rr) {
        modify1(mid + 1, r, rt << 1 | 1, ll, rr, v);
    }
    z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
void modify2(int l, int r, int rt, int ll, int rr, int v) {
    if (ll <= l && r <= rr) {
        return z[rt].c2(v);
    }
    int mid = l + r >> 1;
    pud(rt);
    if (ll <= mid) {
        modify2(l, mid, rt << 1, ll, rr, v);
    }
    if (mid < rr) {
        modify2(mid + 1, r, rt << 1 | 1, ll, rr, v);
    }
    z[rt] = z[rt << 1] + z[rt << 1 | 1];
}
int query(int l, int r, int rt, int ll, int rr, int v) {
    if (ll <= l && r <= rr) {
        return z[rt].sum;
    }
    int mid = l + r >> 1;
    pud(rt);
    int s = 0;
    if (ll <= mid) {
        s = (s + query(l, mid, rt << 1, ll, rr, v)) % mod;
    }
    if (mid < rr) {
        s = (s + query(mid + 1, r, rt << 1 | 1, ll, rr, v)) % mod;
    }
    return s % mod;
}
auto main() [[O3]] -> signed {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    build(1, n, 1);
    while (q--) {
        int o, l, r, x;
        cin >> o >> l >> r;
        if (o < 3) {
            cin >> x;
        }
        if (o == 1) {
            modify1(1, n, 1, l, r, x);
        } else if (o == 2) {
            modify2(1, n, 1, l, r, x);
        } else {
            cout << query(1, n, 1, l, r, x) << '\n';
        }
    }
}

G

咕咕咕。

标签：ATcoder,ABC,int,Add,times,add,补题,mod,define
From： https://www.cnblogs.com/yhbqwq/p/18239046

相关文章

  • [ABC354F] Useless for LIS
    写在最前面的话：如果你懂这道题的线段树或者树状数组解法，那么本题解对你可能没有帮助。题目传送门（Luogu）题目传送门（AtCoder）[ABC354F]UselessforLIS题面翻译给定一个长度为\(n\)的序列\(a\)。求出所有\(i\)使得存在任意一个\(a\)的最长上升子序列包含\(i\)。多测。......
  • 「杂题乱刷」AT_abc160_e
    代码康复训练2024.6.7无所谓，随便贪。直接取前\(x\)大的红苹果，前\(y\)大的绿苹果和和所有无色苹果合起来取最大的\(x+y\)个苹果的值加起来即可。容易证明一定合法。代码：点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出......
  • atcoder ABC 353-A题详解
    atcoderABC353-A题详解ProblemStatementThereareNbuildingsalignedinarow.Thei-thbuildingfromthelefthasaheightofHi.Determineifthereisabuildingtallerthanthefirstonefromtheleft.Ifsuchabuildingexists,findtheposition......
  • [ABC107D] Median of Medians 题解
    题目大意：一个长度为$M$的序列的中位数为这个序列从小到大排序后第$\lfloor\fracM2\rfloor+1$个数，将这个序列的所有子段的中位数放入一个序列中，求这个序列的中位数。设一个序列$a$的中位数为$x$，那么$a$中至少会有一半的数大于等于$x$，并且$x$是$a$中满足这个条件......
  • [ABC036D] 塗り絵 题解
    题意题面讲挺清楚的就不简化了。思路树上求方案数，很明显是树上dp。设$dp_{i,0/1}$表示第$i$个点涂成白/黑色的方案数。当前结点如果为白色，那么它的子节点涂成什么颜色都没关系，根据分步乘法原理，将它子结点涂成白/黑色的方案数之和乘起来即可；当前结点如果为黑色，那么它的子......
  • [ABC126D] Even Relation 题解
    题意对一棵有$N$个点，$N-1$条边的树进行黑白染色，使得每两个距离为偶数的点颜色都一致。思路首先让我们回顾一下加法的性质：偶$+$偶$=$偶奇$+$奇$=$偶偶$+$奇$=$奇不难看出，距离为偶数的关系是可以传递的，而距离为奇数的关系不行。我们只需要做一遍dfs，对一个......
  • ABC356
    Alink把\(1\)$l-1$和$r+1$\(n\)部分顺序输出\(l\)~\(r\)部分逆序输出。点击查看代码#include<bits/stdc++.h>usingnamespacestd;intn,l,r;signedmain(){ cin>>n>>l>>r; for(inti=1;i<l;++i) cout<<i<<"......
  • [ABC191E] Come Back Quickly 题解
    题面：给你一个$n$个点$m$条边的有向图，第$i$条边$a_i$，$b_i$，$c_i$，表示一条单向边从$a_i$到$b_i$，长度为$c_i$，可能会有重边和自环。问能否从第$i$号点出发然后回到该点形成一个环？可以则输出最短时间，否则输出$-1$。思路：不难发现本题考查的是最短路。观察题面，发现边数......
  • [ABC126F] XOR Matching 题解
    很好的构造题。题意请构造一个长度为$2^{m+1}$的序列$a$，该序列满足：$\foralli\in[1,2^{m+1}],a_i\in[0,2^m-1]$且每个数都恰好出现两次。对于任意一对$(i,j)$满足$a_i=a_j$，$a_i\oplusa_{i+1}\oplus\cdots\oplusa_{j-1}\oplusa_j=k$。$\oplus$表......
  • 题解：ABC270G Sequence in mod P
    题目传送门思路题目给出了一个数列\[x_{i+1}\equiv{a\timesx_i+b}\pmod{p}\]并想要求最小的\(x_i=G\)，那我们可以考虑求出这个数列的通项公式。具体的，观察到原式可以转化成一个等比数列的形式，所以我们可以先设一个常数\(k\)，使得\[x_{i+1}+k=a(x_i+k)\]替换进原先的式子......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99