首页 > 其他分享 >Codeforces Round 962 (Div. 3) 补题记录(A~G)

Codeforces Round 962 (Div. 3) 补题记录(A~G)

时间:2024-07-27 09:28:53浏览次数:8  
标签:limits 962 int sum Codeforces long 补题 scanf lld

这场 Div. 3 难度高于平时。

A

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int a[N];
signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) {
        int n;
        scanf("%lld", &n);
        int cnt = n / 4;
        n %= 4;
        if (n) ++cnt;
        printf("%lld\n", cnt);
    }
    return 0;
}

B

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
int a[3010][3010];
signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) {
        int n, m;
        scanf("%lld%lld", &n, &m);
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%1lld", &a[i][j]);
        for (int i = 1; i <= n; i += m, puts(""))
            for (int j = 1; j <= n; j += m)
                printf("%lld", a[i][j]);
    }
    return 0;
}

C

clist 评分 \(1112\)。

维护 \(26\) 个字母的前缀和,然后计算给定区间两个字符串每一个字母的差的和,除以 \(2\) 就是答案。

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

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
char s[N], t[N];
int box[N][26], bb[N][26];
signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) {
        int n, q;
        scanf("%lld%lld%s%s", &n, &q, s + 1, t + 1);
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 26; ++j)
                box[i][j] = box[i - 1][j], bb[i][j] = bb[i - 1][j];
            ++box[i][s[i] - 'a'], ++bb[i][t[i] - 'a'];
        }
        while (q--) {
            int l, r;
            scanf("%lld%lld", &l, &r);
            int sum = 0;
            for (int i = 0; i < 26; ++i)
                sum += abs(box[r][i] - box[l - 1][i] - bb[r][i] + bb[l - 1][i]);
            printf("%lld\n", sum >> 1);
        }
    }
    return 0;
}

D

clist 评分 \(1420\)。

问题转化为求下列表达式的值:

\[\large \sum\limits_{x=1}^{n-2}\sum\limits_{y=1}^{n-x-y}[xy+x(n-x-y)+y(n-x-y)\le n] \]

其中 \([statments]\) 为艾弗森括号,若 \(statments\) 的值为 \(\texttt{true}\) 则 \([statments]\) 的值为 \(1\),否则为 \(0\)。

然后发现后面表达式是一个调和级数的形式,也就是说总的有效的答案数为 \(n\log n\) 级别。

因此直接暴力枚举即可。时间复杂度为 \(O(n\log n)\)。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100;
char s[N], t[N];
int box[N][26], bb[N][26];
signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) {
        int n, x, cnt = 0;
        scanf("%lld%lld", &n, &x);
        for (int i = 1; i < x; ++i) {
            for (int j = 1; j < x - i; ++j) {
                int remain = (n - i * j) / (i + j);
                if (i * j >= n)
                    break;
                remain = min(remain, x - i - j);
                if (remain > 0)
                    cnt += remain;
            }
        }
        printf("%lld\n", cnt);
    }
    return 0;
}

E

clist 评分 \(1615\)。

令 \(check(l,r)\) 表示 \(l\sim r\) 一段区间是否满足条件。

因此可以开始推式子:

\(\large \sum\limits_{i=1}^n \sum\limits_{j=i+1}^n \sum\limits_{x=i}^j \sum\limits_{y=x}^j [check(x,y)]\)

\(\large \sum\limits_{x=1}^n \sum\limits_{y=x+1}^n \sum\limits_{i=1}^x \sum\limits_{j=y}^n [check(x,y)]\)

发现 \(check(x,y)\) 已经和后面的 \(i\),\(j\) 没有关系了,把 \(check(x,y)\) 提到前面。

\(\large\sum\limits_{x=1}^n\sum\limits_{y=x+1}^n([check(x,y)]\sum\limits_{i=1}^x\sum\limits_{j=y}^n 1)\)

\(\large\sum\limits_{x=1}^n\sum\limits_{y=x+1}^n[check(x,y)]\times x\times(n-y+1)\)

然后根据括号的套路,将 \(1\) 看作 \(1\),\(0\) 看作 \(-1\) 跑一边前缀和。

把 \(x\) 从 \(n\) 到 \(1\) 倒着枚举,令 \(S_i\) 表示 \(i\) 的前缀和。则计算左端点是 \(x\) 对答案造成的总贡献就是所有满足 \(y>x\) 且 \(S_y=S_{x-1}\) 的 \(x\times(n-y+1)\)。把 \(x\) 提取出来,后面的 \(n-y+1\) 和 \(x\) 没有关系可以直接扔到一个 map 里算答案。

时间复杂度为 \(O(n\log n)\)。如果使用 gp_hash_table 一类哈希表可以做到理论 \(O(n)\)。一定一定记得取模。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100, mod = 1e9 + 7;
char s[N];
int sum[N];
signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);
        for (int i = 1; i <= n; ++i)
            if (s[i] == '1') sum[i] = sum[i - 1] + 1;
            else sum[i] = sum[i - 1] - 1;
        int res = 0;
        map<int, int> mp;
        for (int x = n; x; --x) {
            res += mp[sum[x - 1]] * x % mod;
            mp[sum[x]] += (n - x + 1);
            mp[sum[x]] %= mod;
            res %= mod;
        }
        printf("%lld\n", res % mod);
    }
    return 0;
}

F

clist 评分 \(1996\)。

不是这明显是虚高啊!这不比 E 简单?

首先考虑一个 \(O((n+k)\log n)\) 的暴力。开一个堆来维护当前 \(n\) 个元素的值。每一次从堆里取出当前值最大的元素,并将这个元素的值更新重新放回堆里。

然后看到每一次取出堆里最大的元素,因此可以发现答案一定存在一个阈值 \(p\),其中选取的数一定全部 \(\ge p\)。更具体的说:值 \(>p\) 的可以选取的数一定全部选取,值 \(<p\) 的可以选取的数一定全都不选取。值 \(=p\) 的数会选取一部分。

容易发现 \(p\) 具有单调性,因此考虑二分答案。计算 \(p\) 是否在 \(k\) 次以内可以取完可以使用等差数列求和。注意一下恰好为 \(p\) 的边界情况即可。时间复杂度为 \(O(n\log n)\) 可以通过。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500100, mod = 1e9 + 7;
int a[N], b[N];
int calc(int shouxiang, int gongcha, int xiangshu) {
    int moxiang = shouxiang - gongcha * (xiangshu - 1);
    return (shouxiang + moxiang) * xiangshu / 2;
}
signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) {
        int n, k;
        scanf("%lld%lld", &n, &k);
        for (int i = 1; i <= n; ++i)
            scanf("%lld", &a[i]);
        for (int i = 1; i <= n; ++i)
            scanf("%lld", &b[i]);
        int l = 0, r = 1e9, best = 0;
        while (l <= r) {
            int mid = l + r >> 1;
            int cnt = 0;
            for (int i = 1; i <= n; ++i) {
                if (a[i] >= mid)
                    cnt += (a[i] - mid) / b[i] + 1;
            }
            if (cnt >= k)
                best = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        int sum = 0;
        for (int i = 1; i <= n; ++i) {
            if (a[i] >= best + 1) {
                int p = (a[i] - (best + 1)) / b[i] + 1;
                sum += calc(a[i], b[i], p);
                k -= p;
            }
        }
        sum += k * best;
        printf("%lld\n", sum);
    }
    return 0;
}

G

clist 评分 \(2384\)。

好逆天一题。考虑随机赋权哈希。

容易发现给出的问题即为一个大小为 \(n\) 的简单环。从 \(a\) 到 \(b\)(\(a\neq b\))的不同简单路径数量一定为 \(2\)。把她放到一个圆上考虑,即为选取一段优弧或者劣弧并将其覆盖。对于这样的一组 \(a\),\(b\),考虑在整数范围内随机赋权 \(p\),并让 \(a\) 和 \(b\) 的点权全都异或上 \(p\)。然后跑一边前缀哈希。此时可以惊人的发现,若两个不同的区间所对应的权相同,那么她们一定位于同一个可选块内!!因此只需要找出最长的连续可选块,然后此时贪心的让这一段区间不被覆盖,设这段长度为 \(p\) 则最优答案为 \(n-p\)。时间复杂度为 \(O(n)\)。

#include <iostream>
#include <cstdio>
#include <random>
#include <map>
#define int long long
const int N = 500100, mod = 1e9 + 7;
int val[N];
std::mt19937_64 mt;
std::uniform_int_distribution<int> qwq(1, 400000000000000000);
signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) {
        int n, m;
        scanf("%lld%lld", &n, &m);
        for (int i = 0; i <= n; ++i)
            val[i] = 0;
        for (int i = 0; i < m; ++i) {
            int a, b;
            scanf("%lld%lld", &a, &b);
            int t = qwq(mt);
            val[a] ^= t, val[b] ^= t;
        }
        std::map<int, int> mp;
        int mx = 0;
        for (int i = 1; i <= n; ++i)
            mx = std::max(mx, ++mp[val[i] ^= val[i - 1]]);
        printf("%lld\n", n - mx);
    }
}

标签:limits,962,int,sum,Codeforces,long,补题,scanf,lld
From: https://www.cnblogs.com/yhbqwq/p/18326632

相关文章

  • Codeforces Round 961
    省流:运气好没有掉分)B2Bonquet(HardVertion)(CF1995B2)事实上B1都写挂了(尖叫)处理花瓣数相差不超过1的花,可以用map存储每种花的数量,顺序遍历即可(其实是不想排序统计,好麻烦);那么如何计算最终答案呢。。。此处省略我赛时乱七八糟的一堆复杂做法,比较简单的写法是先找到一个可行的......
  • Codeforces 913 div3 A-G
    A题意分析把给定的坐标的那一行和那一列的其他所有坐标都输出来C++代码#include<iostream>usingnamespacestd;intmain(){ intt; cin>>t; while(t--){ strings; cin>>s; for(inti=1;i<=8;i++){ if(i+'0'!=s[1])cout<<s[0]<<i<<end......
  • CodeForces 1883A Morning
    题目链接:CodeForces1883A【Morning】思路    模拟,特判当密码中的某个元素为0时,用10减去当前光标的位置,并修改光标的位置为当前元素,再操作依次显示当前元素。对于其他情况则直接使用光标的位置减去目标位置,修改光标位置为当前元素,然后再操作一次显示当前元素。代码#......
  • CodeForces 1883B Chemistry
    题目链接:CodeForces1883B【Chemistry】思路    判断最多删去k个字符后剩下的部分为回文字符串,所以优先删除将个数为奇数个的相同字符删为偶数,当最后留下的字符串中,奇数个数的相同字符种类小于等于1时才会是回文字符串,如:aaabbbccc,此时个数为奇数的相同字符种类有三种,分......
  • 题解:Codeforces Round 961 (Div. 2) C
    C.Squaringtimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputikrpprppfoundanarray\(a\)consistingofintegers.Helikesjustice,sohewantstomake\(a\)fair —thatis,makeitnon......
  • Codeforces Round 958 (Div. 2)
    A.*900水。B.*900发现可以用操作把一串0缩成一个0,1同理。都缩完之后会变成一个01交替的串。比较0和1的个数即可。C.*1300,贪心猜结论。记\(n\)的二进制下有\(x\)个1,\(k\)即为\(x+1\),可以证明这是最长的。从小到大把每一位1去掉后输出剩下的数即可......
  • 平邑2024高算(补题)
    Day1risk题目描述解法考虑最后的集结,不妨考虑找出所有集结过程中可能经过的边,不难发现是一棵树,所以答案就是最小生成树。代码点击查看代码structnode{ intu,v,w;}e[3000001];intn,m;intfa[3000001];intfind(intx){ returnx==fa[x]?fa[x]:fa[x]=find(......
  • CodeForces - 1842H
    *3000,大牛题。分析题目的转化首先题目中\(x_i+x_j\le1\)和\(x_i+x_j\ge1\)不好处理,我们不妨将\(x_i\)都减去\(0.5\),结果不变,那么原题则转化成了\(x_i+x_j\leor\ge0\),发现现在只在乎\(x_i\)之间的绝对值大小关系与正负,这样就可以求出总方案数和合法的方案数,所以......
  • 题解:Codeforces Round 961 (Div. 2) B1&B2
    本题含有B1和B2两个难度版本。由于关系相近,我把他们放在同一篇博客中,可自行选择观看B1.Bouquet(EasyVersion)timelimitpertest:1.5secondsmemorylimitpertest:512megabytesinput:standardinputoutput:standardoutputThisistheeasyversionoftheprobl......
  • Codeforces 929 div3 D
    题目:D.TurtleTenacity:ContinualMods题目链接:https://codeforces.com/contest/1933/problem/D算法:数论、贪心。一开始没思路,后面看了别人的题解才搞懂的。思路:1.将原数组a从大到小排序后可以得到的数组b有两种情况。一种是b0!=b1,另一种则是b0=b1(下标从0开始)。对于第一......