首页 > 其他分享 >20240319天梯赛训练

20240319天梯赛训练

时间：2024-03-19 23:23:32浏览次数：26  
标签：const 训练 int vi 20240319 long cin 天梯 using

P2669 [NOIP2015 普及组] 金币

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int k , res = 0;
    cin >> k;
    for (int i = 1; k; i++) {
        for (int j = i; j and k; j-- , k --)
            res += i;
    }
    cout << res << "\n";
    return 0;
}

P5660 [CSP-J2019] 数字游戏

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string s;
    cin >> s;
    int res = 0;
    for( auto i : s )
        res += (i == '1');
    cout << res << "\n";
}

P5015 [NOIP2018 普及组] 标题统计

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string s;
    int res = 0;
    while (cin >> s)
        res += s.size();
    cout << res << "\n";
}

P5681 [CSP-J2019 江西] 面积

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int a , b , c;
    cin >> a >> b >> c;
    if( a * a > b * c ) cout << "Alice\n";
    else cout << "Bob\n";
}

P1190 [NOIP2010 普及组] 接水问题

优先队列模拟

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    priority_queue<int, vi, greater<int>> q;
    for (int i = 1; i <= m; i++) q.push(0);
    for (int i = 1, x; i <= n; i++)
        cin >> x, x += q.top(), q.pop(), q.push(x);
    for (int i = 1; i < m; i++) q.pop();
    cout << q.top() << "\n";
    return 0;
}

P7071 [CSP-J2020] 优秀的拆分

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ui64 = uint64_t;
using i128 = __int128;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

bool cmp(const array<int, 3> &x, const array<int, 3> &y) {
    if (x[0] != y[0]) return x[0] > y[0];
    return x[2] < y[2];
}


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    if( n & 1 ){
        cout << "-1";
        return 0;
    }
    vi res ;
    for( int i = 1 ; n ; n >>= 1 , i <<= 1)
        if( n & 1 ) res.push_back(i);
    reverse(res.begin(), res.end());
    for( auto i : res )
        cout << i << " ";
    return 0;
}

P2670 [NOIP2015 普及组] 扫雷游戏

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ui64 = uint64_t;
using i128 = __int128;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1, 1, 1, -1, -1}, dy = {1, -1, 0, 0, 1, -1, 1, -1};

bool cmp(const array<int, 3> &x, const array<int, 3> &y) {
    if (x[0] != y[0]) return x[0] > y[0];
    return x[2] < y[2];
}


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (auto &i: g) cin >> i;
    for (int i = 0, cnt; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '*') {
                cout << '*';
            } else {
                cnt = 0;
                for (int l = 0, fx, fy; l < 8; l++) {
                    fx = i + dx[l], fy = j + dy[l];
                    if (fx < 0 or fy < 0 or fx >= n or fy >= m) continue;
                    cnt += g[fx][fy] == '*';
                }
                cout << cnt;
            }
        }
        cout << "\n";
    }
    return 0;
}

P1098 [NOIP2007 提高组] 字符串的展开

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ui64 = uint64_t;
using i128 = __int128;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1, 1, 1, -1, -1}, dy = {1, -1, 0, 0, 1, -1, 1, -1};

bool cmp(const array<int, 3> &x, const array<int, 3> &y) {
    if (x[0] != y[0]) return x[0] > y[0];
    return x[2] < y[2];
}


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int a, b, c;
    cin >> a >> b >> c;
    string s, t;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] != '-') cout << s[i];
        else {
            auto l = s[i - 1], r = s[i + 1];
            if ('0' <= l and l <= '9' and '0' <= r and r <= '9') {
                if (l >= r) {
                    cout << '-';
                    continue;
                }
                t = "";
                for (l++; l < r; l++) {
                    for (int j = 0; j < b; j++) {
                        if (a <= 2) t += l;
                        else t += '*';
                    }
                }
                if (c == 2) reverse(t.begin(), t.end());
                cout << t;
            } else if ('a' <= l and l <= 'z' and 'a' <= r and r <= 'z') {
                if (l >= r) {
                    cout << '-';
                    continue;
                }
                t = "";
                for (l++; l < r; l++) {
                    for (int j = 0; j < b; j++) {
                        if (a == 1) t += l;
                        else if (a == 2) t += l + 'A' - 'a';
                        else t += '*';
                    }
                }
                if (c == 2) reverse(t.begin(), t.end());
                cout << t;
            } else {
                cout << "-";
            }

        }
    }
    return 0;
}

P5657 [CSP-S2019] 格雷码

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ui64 = uint64_t;
using i128 = __int128;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

i128 read() {
    i128 x = 0, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x;
}

string solve(i128 n, i128 k) {
    if (n == 1) {
        if (k == 1) return "1";
        else return "0";
    }
    if (k < ((i128) (1) << (n - 1))) return "0" + solve(n - 1, k);
    return "1" + solve(n - 1, ((i128) (1) << n) - 1 - k);
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    i128 n = read(), k = read();
    cout << solve(n, k) << "\n";
    return 0;
}

P1309 [NOIP2011 普及组] 瑞士轮

每次把赢得人放在一个队列，输的人放在一个队列，就依旧可以保证两个序列有序，然后归并一下，复杂度\(O(RN)\)

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

bool cmp(const array<int, 3> &x, const array<int, 3> &y) {
    if (x[0] != y[0]) return x[0] > y[0];
    return x[2] < y[2];
}

i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, r, q;
    cin >> n >> r >> q, n *= 2, q--;

    vector<array<int, 3>> a(n), b(n / 2), c(n / 2);
    for (int i = 0; i < n; i++)
        cin >> a[i][0], a[i][2] = i + 1;
    for (int i = 0; i < n; i++)
        cin >> a[i][1];
    sort(a.begin(), a.end(), cmp);
    while (r-- > 0) {
        for (int i = 0; i < n; i += 2) {
            if (a[i][1] > a[i + 1][1])
                a[i][0]++, b[i / 2] = a[i], c[i / 2] = a[i + 1];
            else
                a[i + 1][0]++, b[i / 2] = a[i + 1], c[i / 2] = a[i];
        }
        merge(b.begin(), b.end(), c.begin(), c.end(), a.begin(), cmp);
    }
    cout << a[q][2] << "\n";
    return 0;
}

P2058 [NOIP2016 普及组] 海港

可以用双指针维护出长时间\(m\)的时间段，开个桶统计一下。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;
using i64 = long long;
using ldb = long double;

#define int long long

using vi = vector<int>;
using pii = pair<int, int>;

const int mod = 998244353;
const int inf = 1e18;

const vi dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

const int N = 1e5 + 5, T = 86400;
int cnt[N], res, t[N];
vi x[N];


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1, l = 1, k; i <= n; i++) {
        cin >> t[i] >> k;
        x[i].resize(k);
        for (auto &xi: x[i]) {
            cin >> xi, cnt[xi]++;
            if (cnt[xi] == 1) res++;
        }
        while (t[i] - t[l] >= T) {
            for (auto &xl: x[l]) {
                cnt[xl]--;
                if (cnt[xl] == 0) res--;
            }
            l++;
        }
        cout << res << "\n";
    }
    return 0;
}

P3952 [NOIP2017 提高组] 时间复杂度

这题其实是个比较简单的模拟题。

为了便于处理，在检查的过程中如果发现ERR就会直接结束运行，所以要先把一组全部的读入都读进来。

首先这个循环的嵌套，我们要用栈来模拟。

首先考虑怎样会ERR

  1. 变量名重复
  2. 多E或少E

对于1，我用了一个set<string>used表示当前栈中的变量，每次有一个新循环，就把变量插进去，如果插不进去就是ERR

对于2，只要判断过程中栈空和结束后栈不空即可。

下面考虑计算复杂度。

对于每种循环，我规定了三种状态，1对复杂度有贡献，0对复杂度无贡献，-1无法执行，且无法执行的循环子循环全部无法执行。

那么只要在过程中判断每一种循环的状态即可，遇到1入栈就给当前累计复杂度加一，出栈就减一。

考虑如何判断一个循环的父循环是否可以运行？我维护了变量ok表示父循环是否可以运行，只要ok==false强制为-1即可。

当然一种情况是，随着E使得循环出栈，父循环的状态变为可以运行，这个该如何判断？根据我上述定义的规则，如果栈中有-1，一定是在栈顶有若干个连续的-1。所以每次出栈后，判断栈顶不是-1，将ok更新为true即可。

对于复杂度的详细判断可以仔细阅读题目和代码注释。

#include <bits/stdc++.h>

using namespace std;

using i32 = int32_t;


void solve() {
    int n;
    string ans;
    cin >> n >> ans;
    vector<vector<string>> op(n);
    for (string OP, I, X, Y; auto &it: op) {
        cin >> OP;
        if (OP == "F") {
            cin >> I >> X >> Y;
            it = {OP, I, X, Y};
        } else it = {OP};
    }

    set<string> used;
    int cnt = 0, res = 0;
    stack<pair<string, int>> stk;

    for (bool ok = true; auto it: op) { // ok 父循环是否可以运行
        if (it.size() == 1) {
            if (stk.empty()) { // 多 E
                cout << "ERR\n";
                return;
            }
            used.erase(stk.top().first);
            if (stk.top().second == 1) cnt--;
            stk.pop();
            if (stk.empty() or stk.top().second != -1) ok = true; // 父循环可以运行了
        } else {
            auto I = it[1], X = it[2], Y = it[3];
            if (I == "n" or used.insert(I).second == false) {
                cout << "ERR\n";
                return;
            }
            if (X != "n" and Y == "n") { // x -> n 如果可以运行 复杂度++
                if (ok) { // 父循环可以运行
                    stk.emplace(I, 1), cnt++;
                } else { // 父循环不可以运行
                    stk.emplace(I, -1);
                }
            } else if (X == "n" and Y != "n") { // n -> x 子循环全部不能运行
                ok = false, stk.emplace(I, -1);
            } else if (X == "n" and Y == "n") { // n -> n 即使运行 复杂度不变
                stk.emplace(I, vector{-1, 0}[ok]);
            } else { // x -> y 即使运行 复杂度不变
                if (stoi(X) > stoi(Y)) { // x > y 子循环全部不能运行
                    ok = false, stk.emplace(I, -1);
                } else {
                    stk.emplace(I, vector{-1, 0}[ok]);
                }
            }
        }
        res = max(res, cnt);
    }
    if (not stk.empty()) { // 缺 E
        cout << "ERR\n";
        return;
    }
    if (res == 0 and ans == "O(1)")
        cout << "Yes\n";
    else if (res != 0 and ans == "O(n^" + to_string(res) + ")")
        cout << "Yes\n";
    else
        cout << "No\n";
    return;
}


i32 main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--) solve();
    return 0;
}

标签：const,训练,int,vi,20240319,long,cin,天梯,using
From： https://www.cnblogs.com/PHarr/p/18084196

相关文章

  • 代码随想录算法训练营day28 | leetcode 93. 复原 IP 地址、78. 子集、90. 子集 II
    目录题目链接：93.复原IP地址-中等题目链接：78.子集-中等题目链接：90.子集II-中等题目链接：93.复原IP地址-中等题目描述：有效IP地址正好由四个整数（每个整数位于0到255之间组成，且不能含有前导0），整数之间用'.'分隔。例如："0.1.2.201"和"192.168.1.1"是有效IP......
  • 20240319每日一题题解
    20240319每日一题题解Problem判断一个数的结构是否为某个数重复两遍得到。例如，\(123123\)是重复两遍的数，而\(333\)，\(809680\)​则不是保证输入的数字不超过longlong型范围。若是，则输出yes；否则输出no。Solution从数字的角度要想解决这个问题也不是不可以，但是不如将给定的数......
  • Java基础 --- 面向对象综合训练
    面向对象综合训练案例一：文字版格斗游戏格斗游戏，每个游戏角色的姓名，血量，都不相同，在选定人物的时候（new对象的时候），这些信息就应该被确定下来。补充：publicclassTest{publicstaticvoidmain(String[]args){//两部分参数//第一部分参数：要输出的内容%......
  • 代码随想录算法训练营第五十一天| ● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股
    最佳买卖股票时机含冷冻期  题目链接：309.买卖股票的最佳时机含冷冻期-力扣（LeetCode）思路：本题难点在于如何将冷冻期加入到状态转移方程中，不妨画个图：按理来说，如何我们正处于买入状态，将股票卖出后，应该是冷冻状态，但是这里多加了一个今日卖出状态，就是将今日卖出和卖出状态分开......
  • 算法训练营第10天|栈与队列基础知识总结 LeetCode 232.用栈实现队列 225.用队列实现栈
    栈与队列基础知识总结 首先要明白栈和队列不同的地方在于，栈是先入后出的结构，队列是先入先出的结构。栈的基本操作栈的定义： stack<int>s;入栈元素：intx;s.push(x);出栈元素：s.pop();返回栈顶元素：s.top();判断栈是否为空：s.empty();队列的基本操作：队列和栈的基本......
  • 代码随想录算法训练营第五十一天 | 714.买卖股票的最佳时机含手续费，309.最佳买卖股票
     股票总结https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-%E8%82%A1%E7%A5%A8%E9%97%AE%E9%A2%98%E6%80%BB%E7%BB%93%E7%AF%87.html 714.买卖股票的最佳时机含手续费 已解答中等 相关标签相关企业 提示 给定一个......
  • 不平衡数据集cifar100训练模型，提取特征保存为mat文件
    主要分两步走，先训练好模型，保存模型，然后再读取模型，保存特征①训练模型，保存模型importtorchimporttorch.nnasnnimporttorch.optimasoptimimporttorchvisionimporttorchvision.transformsastransformsfromtorch.utils.data.samplerimportWeightedRandomSampler......
  • 算法模板 v1.10.1.20240319
    算法模板v1.1.1.20240115：之前历史版本已不可寻，创建第一份算法模板。v1.2.1.20240116：删除“编译”-“手动开栈”；删除“编译”-“手动开O优化”；修改“编译”-“CF模板”；删除“读写”；删除“图论”-“欧拉图”-“混合图”；删除“图论”-“可达性统计”；删除“数据类型”-“高精类”。......
  • 【GPT概念01】生成式预训练转换器
    一、说明        本文对GPT有所描述，主要解释了GPT的重要环节：only解码器。以及这个过程中，原始数据的维度演进、变化过程。对于想知道GPT内结构的朋友能有一定帮助。二、唯一解码器模型入门—因果语言建模     ......
  • [GPT概念-02] — 预训练、微调和不同的用例应用
    GPT: GenerativePretrainedTransformer一、说明        在之前的博客中，我们研究了生成式预训练转换器的整个概述。现在让我们看看关于预训练、微调和不同用例应用的超级重要主题。二、预......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99