首页 > 其他分享 >AtCoder-ABC-Ex乱写

AtCoder-ABC-Ex乱写

时间：2024-02-07 14:55:23浏览次数：33  
标签：AtCoder ABC return 乱写 mid long int lsh inline

ABC233Ex Manhattan Christmas Tree

先将 \((x,y)\) 变成 \((x+y,x-y)\)，也就是曼哈顿转切比雪夫，之后曼哈顿距离 \(\le k\) 的在切比雪夫坐标系下就是一个正方形。

用主席树做矩形和，外层套一个二分即可，时间复杂度 \(\mathcal{O}(n \log^2 n)\)。

ABC233Ex 
#include <bits/stdc++.h>

using namespace std;

struct Point {
    int x, y;
    Point(int _x = 0, int _y = 0): x(_x), y(_y) {}
};
bool operator < (const Point &lhs, const Point &rhs) 
    {return lhs.x != rhs.x ? lhs.x < rhs.x : lhs.y < rhs.y; }

const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n; Point P[N];
vector<int> lsh[2];

namespace SegTree {
    const int M = 3e6 + 10;
    int root[N], tot = 0;
    int lc[M], rc[M], C[M];
    inline int New() {++tot; lc[tot] = rc[tot] = C[tot] = 0; return tot; }
    inline void maintain(int u) {C[u] = C[lc[u]] + C[rc[u]]; }
#define mid ((l + r) >> 1)
    void Add(int &shadow, int &u, int l, int r, int p, int x) {
        u = New(); lc[u] = lc[shadow], rc[u] = rc[shadow], C[u] = C[shadow];
        if(l == r) {C[u] += x; return; }
        if(p <= mid) Add(lc[shadow], lc[u], l, mid, p, x);
        else Add(rc[shadow], rc[u], mid + 1, r, p, x);
        maintain(u);
    }
    int Ask(int u, int l, int r, int L, int R) {
        if(!u) return 0;
        if(l >= L && r <= R) return C[u];
        if(mid >= R) return Ask(lc[u], l, mid, L, R);
        else if(mid < L) return Ask(rc[u], mid + 1, r, L, R);
        else return Ask(lc[u], l, mid, L, R) + Ask(rc[u], mid + 1, r, L, R);
    }
#undef mid
}

inline bool check(int x, int y, int mid, int k) {
    int siz = 0;
    int l, r; l = upper_bound(lsh[1].begin(), lsh[1].end(), y - mid - 1) - lsh[1].begin() + 1;
    r = upper_bound(lsh[1].begin(), lsh[1].end(), y + mid) - lsh[1].begin();
    int p = upper_bound(P + 1, P + n + 1, Point(x + mid, INF)) - P - 1;
    siz += SegTree::Ask(SegTree::root[p], 1, n, l, r);
    p = upper_bound(P + 1, P + n + 1, Point(x - mid - 1, INF)) - P - 1;
    siz -= SegTree::Ask(SegTree::root[p], 1, n, l, r);
    return siz >= k;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i ++) {
        int x, y; cin >> x >> y;
        P[i].x = x + y, P[i].y = x - y;
        lsh[0].emplace_back(x + y), lsh[1].emplace_back(x - y);
    }
    sort(lsh[0].begin(), lsh[0].end()), sort(lsh[1].begin(), lsh[1].end());
    lsh[0].erase(unique(lsh[0].begin(), lsh[0].end()), lsh[0].end());
    lsh[1].erase(unique(lsh[1].begin(), lsh[1].end()), lsh[1].end());

    sort(P + 1, P + n + 1);
    for(int i = 1; i <= n; i ++) 
        P[i].y = lower_bound(lsh[1].begin(), lsh[1].end(), P[i].y) - lsh[1].begin() + 1;

    for(int i = 1; i <= n; i ++) 
        SegTree::Add(SegTree::root[i - 1], SegTree::root[i], 1, n, P[i].y, 1);

    int T; cin >> T;
    while(T --) {
        int x, y, t_x, t_y, k; cin >> t_x >> t_y >> k;
        x = t_x + t_y, y = t_x - t_y;
        int L = 0, R = 200000;
        while(L < R) {
            int mid = (L + R) >> 1;
            if(check(x, y, mid, k)) R = mid;
            else L = mid + 1;
        }
        cout << L << '\n';
    }

    return 0;
}

ABC234Ex Enumerate Pairs

浪费我感情的精巧暴力题。

把整个第一象限划分成一堆 \(k \times k\) 的正方形，显然符合条件的点对要么在同一个正方形中，要么在两个有公共点的正方形中。

于是我们就可以对每个点，只检查以它所在正方形为中心的 \(3 \times 3\) 个正方形内部的点，接下来我们证明复杂度是有保证的。

将一个正方形再等分为 \(4\) 个 \(\frac{k}{2} \times \frac{k}{2}\) 的小正方形，每个区域内部的点对必然满足条件。设这个正方形内部共有 \(a+b+c+d=w\) 个点，其中 \(a,b,c,d\) 为四个小区域内部的点数，不妨设 \(a \ge b \ge c \ge d\)，那么这个正方形内部的，符合条件的点对数量就有 \(\binom{a}{2}+\binom{b}{2}+\binom{c}{2}+\binom{d}{2}\)。

注意到 \(4a \ge a+b+c+d=w\)，因此 \(\binom{a}{2} = \frac{a(a-1)}{2} \ge \frac{w(w-4)}{32}\)，因此每个正方形内部的点数是 \(\mathcal{O}(\sqrt{A})\)，其中 \(A\) 是答案数量，于是暴力枚举的时间复杂度本质是是 \(\mathcal{O}(n\sqrt{A})\)，其中 \(A\) 是答案数量。

ABC234Ex 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Point {
    ll x, y;
    Point(ll _x = 0, ll _y = 0): x(_x), y(_y) {}
};

const int N = 2e5 + 10;
const ll B = 1e9 + 1;
int n; long long k; Point P[N];
map<ll, vector<int>> Map;
vector<pair<int, int>> ans;

inline bool check(Point a, Point b) {
    long long d = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    return d <= k * k;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> k;
    for(int i = 1; i <= n; i ++) {
        cin >> P[i].x >> P[i].y;
        ll buc = (P[i].x / k) * B + (P[i].y / k);
        Map[buc].emplace_back(i);
    }
    for(int i = 1; i <= n; i ++) {
        ll buc = (P[i].x / k) * B + (P[i].y / k);
        static ll delta[] = {-B, -B - 1, -1, B - 1, B, B + 1, 1, -B + 1, 0};
        for(auto d : delta) {
            if(!Map.count(buc + d)) continue;
            vector<int> &vec = Map[buc + d];
            for(auto x : vec) 
                if(x < i && check(P[i], P[x])) ans.push_back({x, i});
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(auto pr : ans)
        cout << pr.first << ' ' << pr.second << '\n';

    return 0;
}

ABC235Ex Painting Weighted Graph

把Kruskal重构树建出来，但是要稍微修改一下：将原来的二叉树改成多叉树，也就是不存在两个权值相同的点为父子关系，在连通性上的表现就是：将边权相同的边一起加入到图中。

例如若有三个点 \(1,2,3\)，两两之间有权值为 \(1\) 的边，我们建出的Kruskal重构树并不形如 \(1,2\) 的父亲是 \(4\)，\(3,4\) 的父亲是 \(5\)，而是 \(1,2,3\) 共有一个父亲 \(4\)。

对于一个最终可以到达的状态，不妨就在最小的操作次数内到达它：一次操作可以看作是在我们的Kruskal重构树上选择一个点并将它子树内的所有叶子染色，因此若两个染色关系为祖先后代关系，那么深度较大的染色无效。

然后就可以在树上做dp了，设 \(dp_{u,i}\) 表示在 \(u\) 的子树内操作了 \(i\) 次，并且所有操作都有效，得到的最终状态数量，容易用背包转移。

根据树上背包的结论，这部分的时间复杂度为 \(\mathcal{O}(nk)\)，总时间复杂度 \(\mathcal{O}(nk + (n+m) \log m)\)。

ABC235Ex 
#include <bits/stdc++.h>

using namespace std;

struct edge {
    int u, v, w;
    edge() {}
    edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}
};
bool operator < (const edge &lhs, const edge &rhs) {return lhs.w < rhs.w; }

const int N = 1e5 + 10, K = 510, MOD = 998244353;
inline int Plus(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b; }
inline int Minus(int a, int b) {return a - b < 0 ? a - b + MOD : a - b; }
inline int ksm(long long a, int b) {
    long long r = 1;
    for(; b; b >>= 1, a = a * a % MOD)
        if(b & 1) r = r * a % MOD;
    return r;
}
int n, m, k; vector<edge> edges;

int p[N], id[N], tot;
int find(int x) {return x == p[x] ? x : p[x] = find(p[x]); }

vector<int> G[2 * N];
inline void add(int a, int b) {G[a].emplace_back(b); }

inline void calc(set<int> &merged) {
    for(auto u : merged)
        if(u == find(u)) add(tot + 1, id[u]), id[u] = ++tot;
    for(auto u : merged)
        if(u != find(u)) add(id[find(u)], id[u]);
    merged.clear();
}

int dp[2 * N][K], siz[2 * N];
inline void solve(int u, int v) {
    static int f[K];
    for(int i = 0; i <= min(siz[u] + siz[v], k); i ++)
        f[i] = 0;
    for(int i = 0; i <= min(siz[u], k); i ++)
        for(int j = 0; j <= min(siz[v], k - i); j ++)
            f[i + j] = Plus(f[i + j], 1ll * dp[u][i] * dp[v][j] % MOD);
    siz[u] += siz[v];
    for(int i = 0; i <= min(siz[u], k); i ++)
        dp[u][i] = f[i];
}
void dfs(int u) {
    dp[u][0] = 1, siz[u] = 1;
    for(auto v : G[u]) 
        dfs(v), solve(u, v);
    if(G[u].size() != 0 && G[u].size() <= k) {
        dp[u][G[u].size()] = Minus(dp[u][G[u].size()], 1);
    }
    dp[u][1] = Plus(dp[u][1], 1);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m >> k; edges.resize(m);
    for(int i = 0; i < m; i ++)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    sort(edges.begin(), edges.end());

    tot = n;
    for(int i = 1; i <= n; i ++)
        p[i] = id[i] = i;
    set<int> merged;
    for(int i = 0; i < m; i ++) {
        if(i > 0 && edges[i].w != edges[i - 1].w) 
            calc(merged);
        int a = edges[i].u, b = edges[i].v;
        if(find(a) == find(b)) continue;
        merged.insert(find(a)), merged.insert(find(b));
        p[find(a)] = find(b);
    }
    calc(merged);

    dp[0][0] = 1; int root = 0;
    for(int i = 1; i <= n; i ++) 
        if(find(i) == i) 
            dfs(id[i]), solve(root, id[i]);
    int ans = 0;
    for(int i = 0; i <= k; i ++)
        ans = Plus(ans, dp[root][i]);
    cout << ans << '\n';

    return 0;
}

ABC236Ex Distinct Multiples

若 \(A_i=A_j\) 则在 \(i,j\) 两点之间连边，那么一个合法方案就是没有边的方案。

所有边将整张图划分为了一堆连通块，设边集 \(U=\{(i,j):1 \le i < j \le n\}\)，\(f_i\) 表示恰有 \(i\) 条边的方案数，\(g_i\) 表示钦定有 \(i\) 条边的方案数，那么

\[g_i=\sum_{j=i}^{\frac{n(n-1)}{2}}\binom{j}{i}f_j \nonumber \]

二项式反演立即得到

\[f_i=\sum_{j=i}^{\frac{n(n-1)}{2}}(-1)^{j-i}\binom{j}{i}g_j \nonumber \]

答案即 \(f_0\)，有

\[f_0=\sum_{i=0}^{\frac{n(n-1)}{2}}(-1)^ig_i \nonumber \]

只需要算出 \(g\) 就好了，考虑枚举最终构成的连通块形状 \(P\)（\(P\) 是一个集族，每个元素是一个点集，并且所有元素的并集为所有点）。对于点集 \(S\)，记 \(\operatorname{lcm}(S)\) 表示这些 \(i \in S\) 的 \(A_i\) 的 \(\operatorname{lcm}\)，那么答案可以写作

\[\sum_P \left( \prod_{S \in P} \left\lfloor \frac{M}{\operatorname{lcm}(S)} \right\rfloor \right)\sum_{E \subseteq U}[E\text{构成的连通块恰为}P](-1)^{|E|} \nonumber \]

对于后面那个 \(\sum_{E \subseteq U}[E\text{构成的连通块恰为}P](-1)^{|E|}\)，只和 \(P\) 中每个点集的点数有关，设 \(k\) 个点之间连边构成一个连通块的 \((-1)^{ \text{边数个数} }\) 之和为 \(h_k\)，那么它就等于

\[\prod_{S \in P} h_{|S|} \nonumber \]

而 \(h\) 是可以算的：没有连通限制时，\((-1)^{ \text{边数个数} }\) 之和为 \([k=1]\)，也就是 \([x^k]\exp h = [k=1]\)，取 \(\ln\) 得到 \(h=\ln x\)，也就是 \(h_k=(-1)^{k-1}(k-1)!\)。

于是答案就是

\[\sum_{P}\left( \prod_{S \in P}\left\lfloor \frac{M}{\operatorname{lcm}(S)} \right\rfloor \right)\left( \prod_{S \in P}(-1)^{|S|-1}(|S|-1)! \right) \nonumber \]

子集卷积 \(\exp\) 优化可以做到 \(\mathcal{O}((n^2 + \log m)2^n)\)，暴力枚举子集做转移是 \(\mathcal{O}(3^n+2^n \log m)\) 的。

$\mathcal{O}(3^n+2^n \log m)$ 
#include <bits/stdc++.h>

using namespace std;

const int N = 16, MOD = 998244353;
inline int Plus(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b; }
inline int Minus(int a, int b) {return a - b < 0 ? a - b + MOD : a - b; }
int n; long long m, D[N], w[N + 10];

inline long long lcm(long long a, long long b) {
    if(a > m || b > m) return m + 1;
    __int128 ans = (__int128)a / __gcd(a, b) * b;
    return ans > m ? m + 1 : ans;
}
inline int pcnt(int x) {return __builtin_popcount(x); }
long long L[1 << N], f[1 << N], g[1 << N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i ++)
        cin >> D[i];
    L[0] = 1;
    for(int i = 1; i < (1 << n); i ++)
        L[i] = lcm(L[i ^ (i & -i)], D[__lg(i & -i)]);
    for(int i = 0; i < (1 << n); i ++)
        g[i] = (m / L[i]) % MOD;

    w[1] = 1;
    for(int i = 2; i <= n; i ++)
        w[i] = 1ll * w[i - 1] * (i - 1) % MOD;
    for(int i = 0; i <= n + 1; i += 2)
        w[i] = Minus(0, w[i]);
    f[0] = 1;
    for(int i = 1; i < (1 << n); i ++) {
        int u = __lg(i & -i);
        for(int j = i; j; j = (j - 1) & i) {
            if(!(j >> u & 1)) continue;
            f[i] = Plus(f[i], 1ll * f[i ^ j] * g[j] % MOD * w[pcnt(j)] % MOD);
        }
    }
    cout << f[(1 << n) - 1] << '\n';

    return 0;
}
$\mathcal{O}((n^2 + \log m)2^n)$ 
#include <bits/stdc++.h>

using namespace std;

const int N = 16, MOD = 998244353;
inline int Plus(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b; }
inline int Minus(int a, int b) {return a - b < 0 ? a - b + MOD : a - b; }
int n; long long m, D[N], w[N + 10];
int inv[N + 1], fac[N + 1], ifac[N + 1];

inline long long lcm(long long a, long long b) {
    if(a > m || b > m) return m + 1;
    __int128 ans = (__int128)a / __gcd(a, b) * b;
    return ans > m ? m + 1 : ans;
}
inline int pcnt(int x) {return __builtin_popcount(x); }
long long L[1 << N];
int f[N + 1][1 << N], g[N + 1][1 << N];

inline void FWT(int A[], int n, int type) {
    for(int h = 2; h <= n; h <<= 1)
        for(int i = 0; i < n; i += h)
            for(int j = i; j < i + (h >> 1); j ++) {
                if(type == 1) A[j + (h >> 1)] = Plus(A[j + (h >> 1)], A[j]);
                else A[j + (h >> 1)] = Minus(A[j + (h >> 1)], A[j]);
            }
}
inline void exp(int f[], int g[], int n) {
    for(int i = 0; i <= n; i ++) g[i] = 0;
    g[0] = 1;
    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= i; j ++)
            g[i] = Plus(g[i], 1ll * j * f[j] % MOD * g[i - j] % MOD);
        g[i] = 1ll * g[i] * inv[i] % MOD;
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m;
    inv[1] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    for(int i = 2; i <= n; i ++) {
        inv[i] = Minus(0, 1ll * (MOD / i) * inv[MOD % i] % MOD);
        fac[i] = 1ll * fac[i - 1] * i % MOD;
        ifac[i] = 1ll * ifac[i - 1] * inv[i] % MOD;
    }
    
    for(int i = 0; i < n; i ++)
        cin >> D[i];
    L[0] = 1;
    for(int i = 1; i < (1 << n); i ++)
        L[i] = lcm(L[i ^ (i & -i)], D[__lg(i & -i)]);
    for(int i = 0; i < (1 << n); i ++)
        f[__builtin_popcount(i)][i] = (m / L[i]) % MOD;

    w[1] = 1;
    for(int i = 2; i <= n; i ++)
        w[i] = 1ll * w[i - 1] * (i - 1) % MOD;
    for(int i = 0; i <= n + 1; i += 2)
        w[i] = Minus(0, w[i]);
    for(int i = 0; i < (1 << n); i ++)
        f[__builtin_popcount(i)][i] = 1ll * f[__builtin_popcount(i)][i] * w[pcnt(i)] % MOD;
    for(int i = 0; i <= n; i ++) 
        FWT(f[i], 1 << n, 1);
    
    for(int mask = 0; mask < (1 << n); mask ++) {
        static int F[N + 1], G[N + 1];
        for(int i = 0; i <= n; i ++)
            F[i] = f[i][mask];
        exp(F, G, n);
        for(int i = 0; i <= n; i ++)
            g[i][mask] = G[i];
    }
    FWT(g[n], 1 << n, -1);
    cout << g[n][(1 << n) - 1] << '\n';

    return 0;
}

ABC237Ex Hakata

根据经典结论：本质不同的回文子串个数只有 \(\mathcal{O}(|S|)\) 个，我们可以将这些串 \(\mathcal{O}(|S|^3)\) 全部找出来，若串 \(x\) 是串 \(y\) 的子串，那么就连有向边 \((x,y)\)，答案即为这个图的最长反链。

根据Dilworth定理，所求即为最小链覆盖，建二分图，若有原边 \((x,y)\)，那么连 \(x\) 的左部点到 \(y\) 的右部点，跑二分图最大匹配，答案就是左部点个数减去最大匹配。

时间复杂度 \(\mathcal{O}(|S|^3)\)。

ABC237Ex 
#include <bits/stdc++.h>

using namespace std;


string S;
set<string> Set;
inline bool check(string s) {
    for(int i = 0; i < s.size(); i ++)
        if(s[i] != s[(int)s.size() - 1 - i]) return false;
    return true;
}
inline bool cover(string &x, string &y) {
    if(x.size() > y.size()) return false;
    for(int i = 0; i + x.size() <= y.size(); i ++) {
        bool flag = true;
        for(int j = 0; j < x.size(); j ++)
            if(x[j] != y[i + j]) {flag = false; break; }
        if(flag) return true;
    }
    return false;
}
vector<string> vec;

struct Dinic {
    static const int N = 410, INF = 0x3f3f3f3f;
    struct edge {
        int from, to, cap, flow;
        edge(int u, int v, int c, int f): from(u), to(v), cap(c), flow(f) {}
    };
    vector<edge> edges; vector<int> G[N];
    inline void AddEdge(int u, int v, int c) {
        static int M;
        edges.emplace_back(edge(u, v, c, 0)), edges.emplace_back(edge(v, u, 0, 0));
        M = edges.size(); G[u].emplace_back(M - 2), G[v].emplace_back(M - 1);
    }
    int s, t, dist[N], cur[N];
    inline bool BFS() {
        memset(dist, 0, sizeof dist);
        dist[s] = 1; queue<int> Q; Q.push(s);
        while(!Q.empty()) {
            int u = Q.front(); Q.pop();
            for(auto i : G[u]) {
                edge &e = edges[i];
                if(dist[e.to] || e.flow == e.cap) continue;
                dist[e.to] = dist[u] + 1; Q.push(e.to);
            }
        }
        return dist[t];
    }
    int dfs(int u, int F) {
        if(u == t || F <= 0) return F;
        int flow = 0;
        for(int &i = cur[u]; i < G[u].size(); i ++) {
            auto &e = edges[G[u][i]];
            if(dist[e.to] == dist[e.from] + 1 && e.flow < e.cap) {
                int f = dfs(e.to, min(F, e.cap - e.flow));
                flow += f, F -= f, e.flow += f, edges[G[u][i] ^ 1].flow -= f;
                if(!F) break;
            }
        }
        return flow;
    }
    int MaxFlow(int s, int t) {
        this->s = s, this->t = t;
        int res = 0;
        while(BFS()) {
            memset(cur, 0, sizeof cur);
            res += dfs(s, INF);
        }
        return res;
    }
} solver;

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> S;
    for(int i = 0; i < S.size(); i ++) {
        for(int len = 1; len <= i + 1; len ++)
            if(check(S.substr(i - len + 1, len))) 
                Set.insert(S.substr(i - len + 1, len));
    }
    vec.resize(Set.size()); int i = 0;
    for(auto it = Set.begin(); it != Set.end(); it = Set.erase(it)) 
        vec[i ++] = *it;

    int n = vec.size(); int s = 2 * n, t = s + 1;
    for(int i = 0; i < n; i ++)
        solver.AddEdge(s, i, 1), solver.AddEdge(i + n, t, 1);
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < n; j ++) {
            if(j == i || !cover(vec[i], vec[j])) continue;
            solver.AddEdge(i, j + n, 1);
        }
    }
    cout << n - solver.MaxFlow(s, t) << '\n';

    return 0;
}

标签：AtCoder,ABC,return,乱写,mid,long,int,lsh,inline
From： https://www.cnblogs.com/313la/p/18010433

相关文章

  • 我也要板刷 AtCoder！
    板刷AtCoderARCC！[ARC171C]SwaponTreeProblem给定一棵\(n\)个节点的树，每个点有个权值\(a_i\)，初始时\(a_i=i\)。你可以执行任意操作：选择一条边\((u,v)\)，交换\(a_u\)和\(a_v\)，并将这条边删掉。问通过上述操作，最后\((a_1,a_2,\cdots,a_n)\)有多少种不同的排列方......
  • 【多线程例题】使用三个线程，分别可以打印A，B，C。要求实现三个线程协同打印，顺序打印出ABC
    顺序打印-进阶版方法一：三个线程竞争同一个锁，通过count判断是否打印三个线程分别打印A，B，C方法一：通过count计数打印（三个线程上同样的锁，打印一个，召唤所有锁，如果不满足条件，则wait等待，锁自动解锁）方法二：/***有三个线程，分别只能打印A，B和C*要求按顺序打印ABC，打印10次*输出示......
  • ABC335 A~E 题解
    A题目大意输入一个字符串，把这个字符串的最后一位改成4后输出这个字符串。解题思路直接模拟即可AC代码#include<iostream>#include<math.h>#include<time.h>#include<stdio.h>#include<algorithm>#definelllonglonginlinevoidwork(){std::strings;s......
  • AtCoder Beginner Contest 339
    AtCoderBeginnerContest339A-TLD签到B-Langton'sTakahashi发现步数和网格范围都不大，直接模拟即可C-PerfectBus题目的合法性在于不能为负数，那么初始人数就有了二分性。二分的找出初始的最小人数，然后跑一边即可#include<bits/stdc++.h>usingnamespacestd;#d......
  • ABC240Ex Sequence of Substrings
    题意简述有长度为\(n\)的01串，你现在要选出\(k\)个两两无交子串，使得将\(k\)个子串按照出现位置排序后，后者的字典序严格比前者大。最大化\(k\)。\(\bm{n\le2\times10^4}\)。分析首先的首先观察数据范围可知此题应该是个线性根号对数的时间复杂度首先有个显然的\(O(n......
  • Japan Registry Services (JPRS) Programming Contest 2024 (AtCoder Beginner Contes
    JapanRegistryServices(JPRS)ProgrammingContest2024(AtCoderBeginnerContest339)A-TLD代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;usingpii=pair<ll,ll>;#definefifirst#definesesecondusingi128=__......
  • AtCoder Beginner Contest 339
    A找到最后一个点的位置，使用substr函数。B模拟，记得边界是循环的。C容易发现答案为：\[\min_p(\sum_{i=1}^{p}a_i)+\sum_{i=1}^{n}a_i\]D由于不同状态数只有\(60^4\)，容易搜索，但是我去吃饭了，所以没能快速切掉。E有一个显然的dp，然后考虑每一个\(a_i\)可以转移到\(a_j\)......
  • 按大小顺序依次输出abc的值
    include<stdio.h>intmain(){inta,b,c;printf("请输入三个整数：");scanf("%d%d%d",&a,&b,&c);if(a>b&&a>c){if(b>c){printf("从大到小输出三个数：%d%d%d",a,b,c);}else{printf("从大到小输出三个数：%d%d%d&q......
  • [ABC238F] Two Exams 题解
    题目链接题意有\(N\)个人，有两个\(1\simN\)排列\(P,Q\)，在其中选择\(K\)个数，要满足：如果\(P_x<P_y\)且\(Q_x<Q_y\)则不能选了\(y\)而不选\(x\)。思路首先按照\(P\)从小到大排序，这样的话只用考虑\(Q\)。设\(f_{i,j,k}\)表示从前\(i\)个数中选\(j\)个，其中......
  • abc339 详解
    第一篇整场题解纪念我第一次AK的abc！A从后往前找到第一个'.'然后输出'.'到字符串结尾构成的字符串。#include<iostream>usingnamespacestd;intmain(intargc,constchar*argv[]){stringstr;cin>>str;intlen=(int)str.length();stri......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99