首页 > 其他分享 >Codeforces Round #831 (Div. 1 + Div. 2) A-E

Codeforces Round #831 (Div. 1 + Div. 2) A-E

时间:2022-10-30 21:25:05浏览次数:86  
标签:831 cout int 复杂度 Codeforces long solve Div dp

比赛链接

A

题解

知识点:数学。

\(2\) 特判加 \(7\),其他加 \(3\) 直接偶数。

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

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

代码

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

using namespace std;

bool solve() {
    int n;
    cin >> n;
    if (n == 2) cout << 7 << '\n';
    else cout << 3 << '\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

题解

知识点:贪心。

注意到,最优能做到周长等于底边之和乘 \(2\) 加上高度最大值乘 \(2\) 。

我们把短的边当作底边,长的边当作高,这样长的边的贡献会最少。

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

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

代码

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

using namespace std;

bool solve() {
    int n;
    cin >> n;
    ll sum = 0;
    int mx = 0;
    for (int i = 1;i <= n;i++) {
        int x, y;
        cin >> x >> y;
        sum += min(x, y);
        mx = max({ mx,x,y });
    }
    cout << 2 * (sum + mx) << '\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

题解

知识点:贪心,枚举。

从小到大排序后,我们发现单独放一个 \(a[1]\) 或 \(a[n]\) 在 bag3 (或 bag1 )最优,这样就能一次覆盖一段最长的,其他情况因为取在中间,不会超过 \(a[n]-a[1]\) 。

不妨假设单独放了个 \(a[n]\) 在 bag3,再把剩下的分成两段 \([a[1],a[i-1]],[a[i],a[n-1]]\) 分别放在 bag2,1 (较远的放中间),如此得到解 \(a[n] - a[i-1] + a[i] - a[i-1]\) 。同理 \(a[1]\) 单独放,有解 \(a[i] - a[1] + a[i] - a[i-1]\) 。

枚举这两种的所有情况,取最大值。

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

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

代码

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

using namespace std;

int a[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    ll ans = 0;
    for (int i = 2;i <= n;i++) {
        ans = max({ ans,2LL * a[i] - a[i - 1] - a[1],-2LL * a[i - 1] + a[n] + a[i] });
    }
    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;
}

D

题解

知识点:贪心,数学。

神奇的华容道。

遍历一遍,能出的直接出,当前不能出的放在除了起点终点之外的地方以后再出,但要保证放之后至少还有两个空位,即只能放 \(nm-4\) 个卡片,否则下一个进来以后就满了动不了,其他情况都能随意移动卡片(华容道qwq)。

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

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

代码

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

using namespace std;

int a[100007];
bool solve() {
    int n, m, k;
    cin >> n >> m >> k;
    priority_queue<int> pq;
    int p = k;
    for (int i = 1;i <= k;i++) cin >> a[i];
    for (int i = 1;i <= k;i++) {
        while (!pq.empty() && pq.top() == p) pq.pop(), p--;
        if (a[i] == p) p--;
        else {
            pq.push(a[i]);
            if (pq.size() >= n * m - 3) return false;
        }
    }
    cout << "YA" << '\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 << "TIDAK" << '\n';
    }
    return 0;
}

E

题解

知识点:树形dp。

设 \(dp[u][0/1]\) 表示对于以 \(u\) 为根的子树,子序列包括/不包括 \(u\) 时的答案。

分两种情况讨论:

  1. \(dp[u][0]\) 时,那么子节点 \(v_i\) 的最长不下降子序列是可以任意合并的,即子节点的答案 \(\max (dp[v_i][0],dp[v_i][1])\) 能加在一起。因为 \(a[v_i]\) 互相大小没有限制,所以可以自定义后拼在一起。那么答案便是 \(\sum \max (dp[v_i][0],dp[v_i][1])\) 。

  2. \(dp[u][1]\) 时,由于根节点 \(u\) 最后只可能等于一个子节点 \(v_i\) ,那么 \(u\) 只可能衔接在一个 \(dp[v_i][1]\) 后面。

    \(dp[v_i][0]\) 不能考虑进去。因为,当 \(v_i\) 为根的子树不是条链,一定存在子孙 \(w\) 使得 \(a[v_i]<a[w]\) ,那么 \(a[u]<a[w]\) 不可能衔接到 \(w\) 后面;当 \(v_i\) 为根的子树是链时,则 \(dp[v_i][1] = dp[v_i][0]+1>dp[v_i][0]\) ,没必要选。

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

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

代码

#include <bits/stdc++.h>

using namespace std;

vector<int> g[100007];
int f[100007][2];

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = 1;
    for (auto v : g[u]) {
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] = max(f[u][1], f[v][1] + 1);
    }
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 2;i <= n;i++) {
        int p;
        cin >> p;
        g[p].push_back(i);
    }
    dfs(1);
    cout << max(f[1][0], f[1][1]) << '\n';
    return 0;
}

标签:831,cout,int,复杂度,Codeforces,long,solve,Div,dp
From: https://www.cnblogs.com/BlankYang/p/16842270.html

相关文章

  • Codeforces Round #828 (Div. 3)
    题目链接CodeforcesRound#828(Div.3)DivisibleNumbers(hardversion)题目描述给出四个整数\(a,b,c,d\),请你构造一对整数\((x,y)\),满足:\(a<x\leqc......
  • Codeforces Round #831 (Div. 1 + Div. 2)
    CodeforcesRound#831(Div.1+Div.2)1.Problem-D-Codeforces首先是一个结论就是如果除了起点终点以外你发现只要是还多一个格子你是可以把所有牌都任意移动的。......
  • SET DECIMAL_V2=FALSE及UDF ERROR: Cannot divide decimal by zero及Incompatible ret
    概述最近在全职负责一款数据产品的升级改造。因旧版平台的代码写得太乱,简直惨不忍睹;别说增加功能,已有问题的定位与修复都无从下手。用户提交的,在旧版平台能执行的SQL语句,在......
  • Codeforces Round #831 (Div. 1 + Div. 2) E
    E.HangingHearts我们观察每一个节点它可以由其子节点的所有长链来构造还有就是直接可以由自己构成的一条长链所以对于每一个节点我们的答案就是max(加上自己的最长链......
  • Codeforces Round #831 (Div. 1 + Div. 2)
    A.FactoriseN+M题意:给出一个质数,求另一个质数,使得两个数之和不是质数。解:把那个质数再输出一遍就行了。B.JumboExtraCheese2题意:给出一些长方形,按照以下规则把长......
  • Codeforces Round #750 (Div. 2) F1
    F1.KorneyKorneevichandXOR(easyversion)我们观察题意发现我们需要找的是一个上升序列我们回忆上升序列的状态设计dp[i]表示第i个作为结尾最长的序列长度是多少......
  • Educational Codeforces Round 93 (Rated for Div. 2) D
    D.ColoredRectangles考虑数据范围显然可以n3dp我们发现dp转移时不是特别好枚举所以我们选择记忆化搜索打完你们可能会发现过不去第三个样例显然我们应该sort一遍......
  • Codeforces Round #827 (Div. 4) A-G
    比赛链接A题解知识点:模拟。时间复杂度\(O(1)\)空间复杂度\(O(1)\)代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;boolsolve(){......
  • Educational Codeforces Round 1
    EducationalCodeforcesRound1C.Nearestvectors题目大意给出n个向量,求出其中夹角最小的两个向量。分析求出所有向量与x轴的夹角,然后排序,两两比较夹角。AC_code#......
  • Codeforces Round #826 (Div. 3) A-E
    比赛链接A题解知识点:模拟。时间复杂度\(O(n)\)空间复杂度\(O(n)\)代码#include<bits/stdc++.h>#definelllonglongusingnamespacestd;boolsolve(){......