首页 > 其他分享 >Codeforces Round #826 (Div. 3) A-E

Codeforces Round #826 (Div. 3) A-E

时间:2022-10-28 20:22:19浏览次数:84  
标签:cout int 复杂度 Codeforces long solve Div 826 dp

比赛链接

A

题解

知识点:模拟。

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

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

代码

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

using namespace std;

bool solve() {
    string a, b;
    cin >> a >> b;
    if (a.back() != b.back()) {
        if (a.back() > b.back()) cout << '<' << '\n';
        else if (a.back() == b.back()) cout << '=' << '\n';
        else cout << '>' << '\n';
    }
    else if (a.back() == 'S') {
        if (a.size() > b.size()) cout << '<' << '\n';
        else if (a.size() == b.size()) cout << '=' << '\n';
        else cout << '>' << '\n';
    }
    else if (a.back() == 'L') {
        if (a.size() > b.size()) cout << '>' << '\n';
        else if (a.size() == b.size()) cout << '=' << '\n';
        else cout << '<' << '\n';
    }
    else 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;
}

B

题解

知识点:构造。

除了 \(n = 3\) ,其余取末尾两个倒放在前面,然后从 \(1\) 按顺序即可。

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

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

代码

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

using namespace std;

bool solve() {
    int n;
    cin >> n;
    if (n == 3) return false;
    cout << n << ' ' << n - 1 << ' ';
    for (int i = 1;i <= n - 2;i++) cout << i << ' ';
    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

题解

知识点:枚举。

暴力枚举可能的第一段作为基准划分,找到合法划分的中段的最大值,取所有合法的最小值。

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

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

代码

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

using namespace std;

int a[2007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i], a[i] += a[i - 1];
    int mi = n;
    for (int i = 1;i <= n;i++) {
        int tag = a[i] - a[0];
        int l = i + 1, r = i + 1, tmx = i;
        while (l <= n) {
            while (r <= n) {
                if (a[r] - a[l - 1] > tag) break;
                r++;
            }
            if (a[r - 1] - a[l - 1] == tag) tmx = max(tmx, r - l);
            else break;
            l = r;
        }
        if (l > n) mi = min(mi, tmx);
    }
    cout << mi << '\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

题解

知识点:模拟,构造。

模拟这个过程,每次对数组元素分组,组大小从 \(2\) 开始倍增,因为大组交换不会改变组内两边元素相对位置,所以从最小的组开始排序。每组比较先把一组分为两半,因为这两半在上一轮的分组排序一定排序好了,然后把两边第一个元素作为代表元比较大小,每次只交换代表元即可,下一轮比较一定是其中较小的代表元比较。

注意到,无论如何交换,都不能改变原数组两两连续分组后的各个元素的相邻元素 (如 12|34|56|78 ,其中两两元素一定相邻)。因此,如果发现某次交换,一组中两半的代表元差值,不是组大小的一半,那一定无解。

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

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

代码

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

using namespace std;

int p[300007];
bool solve() {
    int m;
    cin >> m;
    for (int i = 1;i <= m;i++) cin >> p[i];
    int cnt = 0;
    for (int i = 1;(1 << i) <= m;i++) {
        for (int j = 1;j <= m;j += 1 << i) {
            if (abs(p[j] - p[j + (1 << i - 1)]) != (1 << i - 1)) return false;
            if (p[j] > p[j + (1 << i - 1)]) swap(p[j], p[j + (1 << i - 1)]), cnt++;
        }
    }
    cout << cnt << '\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

知识点:线性dp。

朴素dp,设 \(dp[i]\) 为 \([1,i]\) 是否合法。考虑 \(b[i]\) 时,可以把其放下一段左侧或者是右侧,因此有转移方程:

if (i - b[i] - 1 >= 0) dp[i] |= dp[i - b[i] - 1];
if (i + b[i] <= n) dp[i + b[i]] |= dp[i - 1];

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

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

题解

代码

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

using namespace std;

int b[200007];
bool dp[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> b[i], dp[i] = 0;
    dp[0] = 1;
    for (int i = 1;i <= n;i++) {
        if (i - b[i] - 1 >= 0) dp[i] |= dp[i - b[i] - 1];
        if (i + b[i] <= n) dp[i + b[i]] |= dp[i - 1];
    }
    if (dp[n]) 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;
}

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

相关文章

  • Codeforces Round #830 (Div. 2)(持续更新)
    PrefaceAB很水,C一般难度,D1很简单但D2确实巧妙没有现场打有点可惜,后面补的时候都是1A(结果每次比赛的时候都要莫名WA上好久)A.Bestie我刚开始没咋想,感觉操作步数不会很......
  • 用esp8266向外界发送网络信号
    #include<ESP8266WiFi.h>constchar*ssid="fengzhihean";constchar*password="12345678";voidsetup(){Serial.begin(115200);WiFi.softAP(ssid,password);......
  • Codeforces Round #739 (Div. 3) E
    E.PolycarpandStringTransformation显然我们可以通过看谁消失的最早知道删除序列然后有了删除序列以后我们能干什么呢显然对于每一个删除序列我们要是第一次就把......
  • ESP8266 WIFI 模块
    发送“AT”(AT指令集后要换行),AT+RST复位一下模块配置ESP8266的工作模式为sta,输入AT+CWMODE=1AT+CWLAP扫描附近的无线AT+CWJAP="CIMS-GUEST","a1b2c3d4e5f6"AT+CWQAP......
  • Codeforces Round #672 (Div. 2) D
    D.RescueNibel!转化题意就是叫我们求k条线段都有重合的方案数最开始想的是离散化+线段树手模拟一下样例这样会是有重复的我们要如何保证不重不漏!显然我们可以将线......
  • Codeforces Round #631 (Div. 1) - Thanks, Denis aramis Shitov! A
    A.DreamoonLikesColoring显然我们不看把整块涂满最优的构造就是1234....但是要考虑将整块板涂满我们就要往右挪显然我们每次挪后面的板子都会动我们一定要让......
  • 【PNR#2 Div1 D】找零(DP)(贪心)
    找零题目链接:PNR#2Div1D题目大意有500,100,50,10,5,1这些面额的纸币,你有X块钱,使用最少的纸币数表示的。然后有一些物品,每种只有一个,有费用。每次你可以选择一些......
  • Educational Codeforces Round 138 F Distance to the Path
    DistancetothePath思维+树链剖分首先与树链剖分无关,先考虑如果只更新一个点的情况因为更新一个点,它既能向根的方向更新,又能向子树方向更新,非常难维护,于是我们只......
  • D. Factorial Divisibility
    D.FactorialDivisibilityYouaregivenaninteger$x$andanarrayofintegers$a_1,a_2,\dots,a_n$.Youhavetodetermineifthenumber$a_1!+a_2!+\dots+a......
  • Codeforces Round #829 (Div. 2)-C1
    C1题目链接:https://codeforces.com/contest/1754/problem/C1emmm,不知道怎么说,做的时候考虑的问题是我通过什么方法来划分整个数组使得题意成立,后面又困在怎么判断是否存......