首页 > 其他分享 >Codeforces Round 921 (Div. 2)

Codeforces Round 921 (Div. 2)

时间：2024-02-07 22:45:16浏览次数：30  
标签：int sqrt2 ll Codeforces long cin using 921 Div

https://codeforces.com/contest/1925

恶心round，从C题开始每题都是一眼看出做法但是细节挺多的题，烦的一比。

A. We Got Everything Covered! *800

给定 \(n,k\)，若所有长度为 \(n\) 且仅由字母表中前 \(k\) 个小写字母组成的串都是 \(s\) 的子序列，则称 \(s\) 是 "Everything Covered" 的。请构造串 \(s\)。

这样构造：abcdabcdabcd

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void sol() {
    int n, k;
    cin >> n >> k;
    while (n--) {
        for (int i = 0; i < k; i++)
            cout << char('a' + i);
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T; while (T--)
        sol();
}

B. A Balanced Problemset? *1200

把 \(x\) 分成 \(n\) 个大于零的数之和，这些数的 \(gcd\) 最大是多少？

\(x\le 10^{8}\)

这些数都能表示成它们的 \(gcd\) 的倍数，\(gcd\) 必是 \(x\) 的因子，枚举因子即可。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void sol() {
    int x, n;
    cin >> x >> n;
    vector<int> d;
    for (int i = 1; i <= x / i; i++) {
        if (x % i) continue;
        d.push_back(i);
        if (i != x / i) d.push_back(x / i);
    }
    sort(d.begin(), d.end());
    for (int di : d) {
        if (di >= n) return cout << x / di << '\n', void();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T; while (T--)
        sol();
}

C. Did We Get Everything Covered? *1500

判断给定串是不是 "Everything Covered" 的。如果不是，构造反例。

这样构造反例：每次选“最晚出现的字符”

感觉这个人的方法比我帅多了 https://zhuanlan.zhihu.com/p/680178758

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void sol() {
    int n, k, m;
    string s;
    cin >> n >> k >> m >> s;
    vector<int> p(k, m), f(m); //后缀中首次出现位置最晚的字符出现的位置
    for (int i = m - 1; ~i; i--) {
        p[s[i] - 'a'] = i;
        for (int j : p) f[i] = max(f[i], j);
    }
    
    string ans;
    for (int i = 0; i < m; i++) {
        if (f[i] < m) {
            ans += s[f[i]];
            i = f[i];
            if (ans.size() == n)
                return cout << "YES\n", void();
        } else {
            vector<bool> occ(k);
            for (int j = i; j < m; j++)
                occ[s[j] - 'a'] = true;
            int c = 0; while (occ[c]) c++;
            while (ans.size() < n) ans += char(c + 'a');
            cout << "NO\n" << ans << '\n';
            return;
        }
    }
    while (ans.size() < n) ans += 'a';
    cout << "NO\n" << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T; cin >> T; while (T--)
        sol();
}

D. Good Trip *1900

有 \(n\) 个同学，其中有 \(m\) 对朋友，第 \(i\) 对朋友有友谊值 \(f_i\)。老师每次随机（从所有 \(C_n^2\) 对中）选一对人，共选 \(k\) 次。一对朋友被选中后，答案加上他们当前的友谊值，然后他们的友谊值增加 \(1\)。问答案的期望。

\(n,m\le 1e5, k\le 2e5\)

考虑第 \(i\) 对朋友对答案的贡献。\(f_i\) 被加入答案的概率为 \(P(1)\)，\(f_i+1\) 被加入答案的概率为 \(P(2)\)，以此类推。

\(P(x)\) 为第 \(i\) 对朋友被选择的次数 \(\ge x\) 的概率，\(P(x)=\sum_{j=x}^k C_k^j p^j(1-p)^{k-j}\)，其中 \(p=1/C_n^2\)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
const int N = 2e5 + 5;

ll fac[N], ifac[N];

ll qmi(ll a, ll b) {
    ll s = 1;
    for (; b; b >>= 1) {
        if (b & 1) s = s * a % P;
        a = a * a % P;
    }
    return s;
}

ll C(ll n, ll k) {
    if (n < k) return 0;
    return fac[n] * ifac[k] % P * ifac[n - k] % P;
}

void sol() {
    ll n, m, k;
    cin >> n >> m >> k;
    
    ll sp = 0, sip = 0, ans = 0;
    
    ll p = qmi(n * (n - 1) / 2 % P, P - 2), q = (1 - p + P) % P;
    
    for (ll i = k, s = 0; i; i--) {
        (s += C(k, i) * qmi(p, i) % P * qmi(q, k - i) % P) %= P;
        (sp += s) %= P;
        (sip += i * s % P) %= P;
    }
    
    for (int i = 0; i < m; i++) {
        ll a, b, f;
        cin >> a >> b >> f;
        ans += (f - 1) * sp % P + sip;
    }
    cout << (ans % P + P) % P << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fac[0] = 1;
    for (int i = 1; i < N; i++)
        fac[i] = fac[i - 1] * i % P;
    ifac[N - 1] = qmi(fac[N - 1], P - 2);
    for (int i = N - 1; i; i--)
        ifac[i - 1] = ifac[i] * i % P;
    
    int T; cin >> T; while (T--)
        sol();
}
 

E. Space Harbour *2100

树状数组或者线段树 区间加差分数组、区间求和，把模板题代码拉过来微调一下就行

牛牛的等差数列（树状数组，区间加等差数列、区间求和）

我写的是树状数组维护二阶差分

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BIT {
    int n; vector<ll> tr;
    BIT(int n): n(n), tr(n + 1) {}
    int lowbit(int x) { return x & -x; }
    void add(int p, ll x) { for (; p <= n; p += lowbit(p)) tr[p] += x; }
    ll ask(int p) { ll s = 0; for (; p > 0; p -= lowbit(p)) s += tr[p]; return s; }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    BIT c(n), kc(n), kkc(n);
    auto add = [&](int p, ll x) { //对c数组的单点加
        c.add(p, x); kc.add(p, x * p); kkc.add(p, x * p * p);
    };
    auto upd = [&](int l, int r, ll a, ll d) { //a数组区间加等差数列
        add(l, a);
        add(l + 1, d - a);
        add(r + 1, -(a + d * (r - l + 1)));
        add(r + 2, (a + d * (r - l)));
    };
    auto ask = [&](int n) {
        ll s = c.ask(n) * (n + 1) * (n + 2);
        s -= (2 * n + 3) * kc.ask(n);
        s += kkc.ask(n);
        return s / 2;
    };
    
    vector<pair<int, int>> harbour(m);
    for (int i = 0; i < m; i++) cin >> harbour[i].first;
    for (int i = 0; i < m; i++) cin >> harbour[i].second;
    sort(harbour.begin(), harbour.end()); //题目没说港口是有序的...
    
    auto modify = [&](int x1, int v1, int x2, ll ty = 1) { //del=-1表示删除序列
        upd(x1 + 1, x2, ty * v1 * (x2 - x1 - 1), -ty * v1);
    };
    
    set<pair<int, int>> S;
    for (int i = 0; i < m; i++) {
        if (i > 0)
            modify(harbour[i - 1].first, harbour[i - 1].second, harbour[i].first);
        S.insert(harbour[i]);
    }
    
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, v; cin >> x >> v;
            auto it = S.lower_bound({x, v});
            auto [x2, v2] = *it;
            auto [x1, v1] = *prev(it);
            modify(x1, v1, x2, -1);
            modify(x1, v1, x);
            modify(x, v, x2);
            S.insert({x, v});
        } else {
            int l, r; cin >> l >> r;
            cout << ask(r) - ask(l - 1) << '\n';
        }
    }
    
    return 0;
}
 

F. Fractal Origami *2400 分母有理化

折纸，正方形的纸边长为 \(1\)，每次把四个角往内折，得到新的更小的正方形。最后展开，折痕分为峰和谷两类，峰与谷的长度之比 \(M/V\) 一定是 \(A+B\sqrt2\) 的形式，\(A,B\) 均为有理数。请输出 \(B\)。

找规律，列式子，分母有理化

拿张纸巾折了几次，发现第 \(2\) 次 \(M,V\) 均增加 \(2\)，第 \(3\) 次 \(M,V\) 均增加 \(2\sqrt2\)。大胆猜测每次 \(M,V\) 均增加上次增加长度的 \(\sqrt2\) 倍。然后就是臭不可闻的列式子+疯狂有理化

\[M = \frac{2(\sqrt 2 ^{n-1}-1)}{\sqrt2-1} = 2(\sqrt 2 ^{n-1}-1)(\sqrt2 + 1) = 2(\sqrt2^n-1+\sqrt2^{n-1}-\sqrt2) \\V = M + 2\sqrt2 = 2(\sqrt2^n-1+\sqrt2^{n-1}) \\ \frac{M}{V} = \frac{\sqrt2^n-1+\sqrt2^{n-1}-\sqrt2}{\sqrt2^n-1+\sqrt2^{n-1}} \]

当 \(n\) 为奇数时，

\[\frac{M}{V} = \frac{2^{(n-1)/2}\sqrt2-1+2^{(n-1)/2}-\sqrt2}{2^{(n-1)/2}\sqrt2-1+2^{(n-1)/2}} \]

当 \(n\) 为偶数时，

\[\frac{M}{V} = \frac{2^{n/2}-1+2^{(n-2)/2}\sqrt2-\sqrt2}{2^{n/2}-1+2^{(n-2)/2}\sqrt2} \]

太丑了，设一下继续算

\[\frac{M}{V} = \frac{(x-1)\sqrt2+y}{x\sqrt2+y} = \frac{y}{2x^2-y^2}\sqrt2+一个有理数 \]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 999999893;
const int N = 2e5 + 5;

ll fac[N], ifac[N];

ll qmi(ll a, ll b) {
    ll s = 1;
    for (; b; b >>= 1) {
        if (b & 1) s = s * a % P;
        a = a * a % P;
    }
    return s;
}

void sol() {
    ll n;
    cin >> n;
    ll x = qmi(2, n / 2 - !(n & 1)), y = qmi(2, n / 2) - 1;
    cout << (y * qmi((2 * x * x % P - y * y % P) % P, P - 2) % P + P) % P << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);    
    int T; cin >> T; while (T--)
        sol();
}
 

标签：int,sqrt2,ll,Codeforces,long,cin,using,921,Div
From： https://www.cnblogs.com/wushansinger/p/18011426

相关文章

  • Codeforces Round 923 (Div. 3)(A~F)
    目录ABCDEFA#include<bits/stdc++.h>#defineintlonglong#definerep(i,a,b)for(inti=(a);i<=(b);++i)#definefep(i,a,b)for(inti=(a);i>=(b);--i)#definepiipair<int,int>#definepllpair<longlong,longlong>#de......
  • Codeforces-Hello-2024-Round
    比赛链接A.WalletExchange签到，某个人操作的时候只要一方有金币就行，所以最终赢的应该是拿到最后一个硬币的人，当\(a+b\equiv1\pmod2\)的时候Alice获胜，否则Bob获胜。时间复杂度\(\mathcal{O}(1)\)。codeforA#include<bits/stdc++.h>usingnamespacestd;inli......
  • CF1401E Divide Square 题解
    解题思路其实多看几组也能发现块数等于交点的数量加上两个端点都在边上的线段数量再加一。证明如下（图见样例）：对于两条只有一个端点位于边上的线段，因为保证有一个端点位于边上，那么这两条线段的交点一定会和已存在的点、边构成一个新的矩形；对于其中有一条为两个端点均位于边上的......
  • Codeforces Round 920 (Div. 3)（A~F）
    目录ABCDEFA按题意模拟即可#include<bits/stdc++.h>#defineintlonglong#definerep(i,a,b)for(inti=(a);i<=(b);++i)#definefep(i,a,b)for(inti=(a);i>=(b);--i)#definepiipair<int,int>#definepllpair<longlong,longlong......
  • Codeforces div2 C题补题
    Codeforcesdiv2C题补题1922C.ClosestCitiesC.ClosestCities很容易看出，端点的两个城市的最近城市就是他的直接后继和直接前驱，而中间的城市的最近城市就是他前驱和后继中距离绝对值最小的那个，因此我们可以先预处理出每个城市对应的最近城市，用map存储。然后因为区间可以从......
  • 从BigDecimal的divide的异常说起
    在过去做项目的某一天中，突然有小伙伴说两个BigDecimal的数据相除（divide）报错了，觉得不可能，然后问他是怎么编写的，他说很简单呀，就是new了2个BigDecimal，然后相除的结果赋值给另外一个BigDecimal对象。听起来觉得没有问题，正常来说，2个Integer(int)，2个Double(double）都不会报错，然后问是什么......
  • Codeforces Round 913 (Div. 3) G.
    题目链接G.把灯看成节点，灯之间的关系看成有向边得到基环树森林若节点的入度为0，那么它一定要用一次开关，这是可以确定的所以用拓扑，把这些确定贡献的节点删去然后就剩下了若干个环若环上有奇数个权值为1的节点，那么不可能全部关上对于环上一个打开的灯，它要么直接用自己的开关......
  • Codeforces Round 921 (Div. 1) 题解
    HelloAd-HocForces！A字符集为前\(k\)个小写字母，给定长度为\(m\)的字符串，求所有的长度为\(n\)的字符串是否是这个字符串的子串。（此处字串不连续）如果不是需要给出反例。\(1\len,k\le26\)，\(1\lem\le1000\)。\(\sumn,\summ\le10^6\)sol.D1A就是神秘贪心，汗流浃背......
  • Codeforces Round 917 (Div. 2)
    https://codeforces.com/contest/1917A.LeastProduct*800给定整数数组，可以把数组中的数\(a_i\)改为\(0\sima_i\)中的任意整数，最小化所有数的乘积，在此基础上使操作次数最少讨论一下负数的个数和\(0\)的个数#include<bits/stdc++.h>usingnamespacestd;usingll......
  • left 3 Codeforces Round 913 (Div. 3)
    题目链接A.把同行同列除了起点都输出即可#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=2e5+10;voidsolve(){charc;inta;cin>>c>>a;for(inti=1;i<=8;i++){if(i==a)continue;cout<<c<......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99