当前位置:首页 > 技术 > 正文内容

Codeforces Round #822 (Div. 2) A-F

Lotus2022-10-06 21:30技术

比赛链接

A

题解

知识点:贪心。

注意到任意三根木棍的相等最优解是最长减最小,因此从小到大排序,三个三个取,取最小值。

时间复杂度 \(O(n\log n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll a[307];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    ll ans = a[3] - a[1];
    for (int i = 3;i <= n;i++) {
        ans = min(ans, a[i] - a[i - 2]);
    }
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

B

题解

知识点:构造。

注意到第 \(i\) 行的房间最多明亮值为 \(i\) ,又发现只需要两侧房间安排火把已经满足一行最大值,因此直接两侧房间 \(1\) 其他都是 \(0\)

时间复杂度 \(O(n^2)\)

空间复杂度 \(O(1)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= i;j++) {
            if (j == 1 || j == i) cout << 1 << ' ';
            else cout << 0 << ' ';
        }
        cout << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

题解

知识点:贪心,数学。

从小到大,把每一个要删除的数当作 \(k\) 枚举倍数,如果是要删除的数花费一次 \(k\) 删掉,如果已经删过则无视,如果不是要删除的数则停止换下一个 \(k\)

时间复杂度 \(O(n\log n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int vis[1000007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        char c;
        cin >> c;
        vis[i] = c == '1';
    }
    ll sum = 0;
    for (int i = 1;i <= n;i++) {
        if (vis[i] == 1) continue;
        for (int j = i;j <= n;j += i) {
            if (vis[j] == 1) break;
            if (vis[j] == 0) {
                vis[j] = 2;
                sum += i;
            }
        }
    }
    cout << sum << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

题解

知识点:贪心,枚举。

先选择一个方向直走,比如先走左侧,走到不能再走为止,把尽头的生命值 \(lnw\) 记录下。

此时考虑回头,但显然在左侧尽头回头不是一定最优的,应该在走左侧过程中生命值和最大处回头才是最优的,因为这样在走右侧时可以走最多的路,因此在走左侧的过程中也要记录左侧的生命和最大值 \(lmx\)

同理从 \(lmx\) 回头走右侧时,也是走到尽头记录右侧最大生命值 \(rmx\) 和尽头生命值 \(rnw\) 。此时从 \(rmx\) 回头走左侧,应该直接从上一次的左侧尽头位置 \(lnw\) 继续走。

如此来回往复,直到两侧不能继续走或者到达两端为止。

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

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[200007];
bool solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int i = k - 1, j = k + 1;
    ll lmx = 0, lnw = 0, rmx = 0, rnw = 0;
    while (1 <= i && j <= n) {
        bool ok = false;
        while (1 <= i) {
            if (a[k] + lnw + rmx + a[i] < 0) break;
            ok = true;
            lnw += a[i--];
            lmx = max(lmx, lnw);
        }
        while (j <= n) {
            if (a[k] + lmx + rnw + a[j] < 0) break;
            ok = true;
            rnw += a[j++];
            rmx = max(rmx, rnw);
        }
        if (!ok) break;
    }
    if (i == 0 || j == n + 1) cout << "YES" << '\n';
    else cout << "NO" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

E

题解

知识点:构造,数学。

注意到,

\[\begin{aligned} & & a_{i_1,j_1} + a_{i_2,j_2} \not \equiv a_{i_1,j_2} + a_{i_2,j_1} \pmod n\\ &\Leftrightarrow & a_{i_2,j_2} - a_{i_2,j_1} \not \equiv a_{i_1,j_2} - a_{i_1,j_1} \pmod n \end{aligned} \]

猜测一行元素具有线性关系,设 \(i_1\) 行线性系数为 \(k_1\)\(i_2\) 行线性系数为 \(k_2\) ,于是有:

\[\begin{aligned} &\Leftrightarrow & (j_2-j_1)\cdot k_2 \not \equiv (j_2-j_1)\cdot k_1 \pmod n \end{aligned} \]

根据定理:当 \(k > 0\) 时,若 \(kx \equiv ky \pmod n\) ,则 \(x \equiv y\pmod {\frac{n}{gcd(k,n)}}\)

于是有:

\[\begin{aligned} &\Leftrightarrow & k_2 \not \equiv k_1 \pmod n \end{aligned} \]

因此,只要每行之间的线性系数在 \(\mod n\) 意义下不同余,且在 \((i,i)\) 处经过 \(b_i\) 即可。

显然,\(i \in [1,n]\) 时即能保证互不同余,可以当作系数,因此有公式 \(b_{i,j} = (i \cdot (j-i) + b_i) \mod n\)

时间复杂度 \(O(n^2)\)

空间复杂度 \(O(n^2)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int a[357][357], b[357];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> b[i];
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            a[i][j] = ((i * (j - i) + b[i]) % n + n) % n;
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

F

题解

知识点:记忆化搜索,线性dp,数学,位运算。

先是一个结论:定义函数 \(parity(a)\) 表示 \(a\) 二进制位 \(1\) 的个数的奇偶性(奇数返回 \(1\) ,偶数返回 \(0\)),那么 \(S_i = parity(i)\)

证明非常简单:

  1. 由于 \(S\) 的生成方法是每次都从原来的一份取反得到 \(S'\) 放到 \(S\) 末尾,所以第 \(k(k\geq 1)\) 次扩展后 \(S\) 的编号一定是 \([0,2^{k-1}]\)
  2. 对于第 \(k+1\) 次新生成的 \(S'\) 中的每一位编号 \(i'\) ,满足 \(i’ = i + 2^k\) ,因为编号 \(i\) 的第 \(k\) 位之前一定是 \(0\),所以这次变换实际上是将编号 \(i\) 的第 \(k\) 位变为 \(1\) 作为编号 \(i'\)
  3. 显然,所有数字都是从编号 \(0\) 开始数次变换得到的,每次变换都会将编号的一位 \(0\) 变为 \(1\) ,因此我们记录二进制 \(1\) 的数量就能得知这个编号从 \(0\) 变换了多少次。
  4. \(S_0 = 0\) ,所以编号 \(i\) 有偶数个 \(1\) 就是变了偶数次,故 \(S_i=0\) ,否则 \(S_i = 1\) 。即 \(S_i = parity(i)\)

有了这个结论,我们就可以对问题进行量化。记原问题答案为 \(f(n,m)\) ,有 \(f(n,m) = \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\)

\(m = 0\) 时,显然有 \(f(n,0) = 0\)

\(m\) 为奇数时,先对末尾判断再对 \(m-1\) 讨论(偶数讨论方便一点),有 \(f(n,m) = f(n,m-1) + [parity(i) \neq parity(n+i)]\)

\(m\) 为偶数时:

  • \(n\) 为偶数,有如下关系:

    \[\begin{aligned} && &parity(2k) \neq parity(n+2k) \\ &\Leftrightarrow& &parity(2k+1) \neq parity(n+2k+1)\\ \end{aligned} \]

    因为偶数末尾总是 \(0\) ,加 \(1\) 不会影响其余的二进制位,所以 \(1\) 的数量明确加 \(1\) ,奇偶性一定同时改变。

    \[\begin{aligned} && &parity(2k) \neq parity(n+2k) \\ &\Leftrightarrow& &parity(k) \neq parity(\frac{n}{2}+k) \end{aligned} \]

    因为偶数末尾总是 \(0\) ,删去这个 \(0\) 后,数字奇偶性不变。

    那么有如下公式:

    \[\begin{aligned} f(n,m) &= \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\\ &= 2\sum_{k = 0}^{\frac{m}{2}-1} [parity(2k) \neq parity(n+2k)]\\ &= 2\sum_{k = 0}^{\frac{m}{2}-1} [parity(k) \neq parity(\frac{n}{2}+k)]\\ &= 2f(\frac{n}{2},\frac{m}{2}) \end{aligned} \]

  • \(n\) 为奇数,有如下关系:

    \[\begin{aligned} && &parity(2k) \neq parity(n+2k) \\ &\Leftrightarrow& &parity(2k) = parity(n+2k-1)\\ &\Leftrightarrow& &parity(k) = parity(\frac{n-1}{2}+k)\\ \end{aligned} \]

    以及,

    \[\begin{aligned} && &parity(2k+1) \neq parity(n+2k+1) \\ &\Leftrightarrow& &parity(2k) = parity(n+2k+1)\\ &\Leftrightarrow& &parity(k) = parity(\frac{n+1}{2}+k)\\ \end{aligned} \]

    证明同上。

    \[\begin{aligned} f(n,m) &= \sum_{i = 0}^{m-1} [parity(i) \neq parity(n+i)]\\ &= \sum_{k = 0}^{\frac{m}{2}-1} ([parity(2k) = parity(n+2k-1)] + [parity(2k) = parity(n+2k+1)])\\ &= \sum_{k = 0}^{\frac{m}{2}-1} ([parity(k) = parity(\frac{n-1}{2}+k)] + [parity(k) = parity(\frac{n+1}{2}+k)])\\ &= m - f(\frac{n-1}{2},\frac{m}{2}) - f(\frac{n+1}{2},\frac{m}{2}) \end{aligned} \]

至此,我们就可以通过记忆化搜索进行求解了。

时间复杂度 \(O(\log n \log m)\)

空间复杂度 \(O(\log n \log m)\)

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

bool check(ll a, ll b) {
    return __builtin_parityll(a) != __builtin_parityll(b);
}

map<pair<ll, ll>, ll> mp;
ll f(ll n, ll m) {
    if (m == 0) return 0;
    if (mp.count({ n,m })) return mp[{n, m}];
    if (m & 1) return mp[{n, m}] = f(n, m - 1) + check(m - 1, n + m - 1);
    if (n & 1) return mp[{n, m}] = m - f(n / 2, m / 2) - f((n + 1) / 2, m / 2);
    else return mp[{n, m}] = 2 * f(n / 2, m / 2);
}

bool solve() {
    ll n, m;
    cin >> n >> m;
    cout << f(n, m) << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

扫描二维码推送至手机访问。

版权声明:本文来源于网络,仅供学习,如侵权请联系站长删除。

本文链接:https://news.layui.org.cn/post/287.html

分享给朋友:

“Codeforces Round #822 (Div. 2) A-F” 的相关文章

第三章 知己知彼

知彼知己,百战不殆;不知彼而知己,一胜一负;不知彼,不知己,每战必殆。《谋攻篇》 前面两章其实重点是在掰扯数智化,IT研发本身的数字化其实除了DevOps这一种手段之外还有很多,比如Low Code、RPA等等,AI都可以自动写代码了,还有啥是不可能的呢!不过本人能力有限,这点斤两也就敢玩玩DevOps,其他的碰都就不敢碰,接下来聚焦到DevOps的一些见解上。 3.1 剑锋所指      ...

JS奇淫技巧:数值的七种写法

JS奇淫技巧:数值的七种写法 JS奇淫技巧:挑战前端黑科技,数值的七种写法,能全看懂的一定是高手 你知道吗?在JS编程中,数值可以有很多种写法。 第一种写法: 一般情况而言,数值就是数值。 比如: var a = 1; 你可知,这个1可以有很多种变形的写法,甚至是变态的写法。 第二种写法: var a= +!!{}; console.log(a); 即:1变成了+!!{}。 数值1为什么能...

十分钟速成DevOps实践

摘要:以华为云软件开发平台DevCloud为例,十分钟简单体验下DevOps应用上云实践——H5经典小游戏上云。 本文分享自华为云社区《​​《DevOps实践秘籍》十分钟速成DevOps实践​​》,作者:AppCloud小助手 。 DevOps是什么? DevOps是Development和Operations的组合词,简单点理解就是研发运维一体化的方法论,目的是通过自动化“软件交付”和“架构变...

打造企业自己代码规范IDEA插件(中)

一些基本概念 在开始独立研发公司自己的代码规范检查规则之前,先介绍一些相关的基本概念。阿里巴巴代码规范很多规则其实都是基于开源框架PMD进行的研发。PMD用官方的话语介绍来说:PMD是一个源代码分析器。它可以发现常见的编程缺陷,如未使用的变量、空catch块、不必要的对象创建等。它支持多种语言。它可以用自定义规则进行扩展。它使用JavaCC和Antlr将源文件解析为抽象语法树(AST),并对其运...

devops学习笔记-jenkins实现基础CI/CD操作

在之前的devops工具链中完成了jenkins以及gitlab配置之后,可以实现基础的CI/CD操作。 操作流程 整体的操作的流程如下所示: 在开发环境配置好代码之后,将代码上传到gitlab,jenkins拉取gitlab的代码,由maven插件build,打包好后,构建 docker镜像,上传到目标服务器中运行,可以通过tag选择版本代码。 本地编写代码 使用idea编写一个基础的spr...

Android平台实现mp4文件实时推送RTMP|轻量级RTSP服务|GB28181平台

好多开发者有这样的诉求,想把本地录制的MP4文件,以实时流数据的形式,推送到RTMP服务器,注入轻量级RTSP服务,或者对接到GB28181平台,这块前几年我们就有对接。 本次以MediaExtractor为例,先利用MediaExtractor,把mp4文件的音视频数据分离,然后调用我们publisher模块,实现编码后的数据对接到RTMP服务器、轻量级RTSP服务或GB28181平台即可,废...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。