首页 > 其他分享 >第二周训练题单

第二周训练题单

时间：2023-07-25 19:24:13浏览次数：36  
标签：vector cout 训练 int nullptr cin long 第二周 题单

多项式输出

小细节比较多

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    for (int x , i = n ; i >= 0; i--) {
        cin >> x;
        if( x == 0 ) continue;
        if (x < 0) cout << "-", x = -x;
        else if( i != n )  cout << "+";
        if (x > 1 || i == 0 ) cout << x;
        if( i > 1 ) cout << "x^" << i;
        else if( i == 1 ) cout << "x";
    }
    return 0;
}

铺地毯

根本不需要维护整张图，读入所有地毯倒序枚举判断一下就好了。

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n+1) , b(n+1) , c(n+1) , d(n+1);
    for( int i = 1 ; i <= n ; i ++ )
        cin >> a[i] >> b[i] >> c[i] >> d[i] , c[i] +=a[i] , d[i] += b[i];
    int x , y;
    cin >> x >> y;
    for( int i = n ; i >= 1 ; i -- )
        if( a[i] <= x && x <= c[i] && b[i] <= y && y <= d[i] )
            cout << i , exit(0);
    cout << "-1\n";
    return 0;
}

第k小

因为 k 值不变，所以直接维护大小为 k 的堆就好了。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    priority_queue<int> q;
    for (int x; n; n--)
        cin >> x, q.emplace(x);
    while (q.size() > k) q.pop();
    for( int op , x ; m ; m -- ){
        cin >> op;
        if( op == 1 ){
            cin >> x , q.emplace(x);
            while (q.size() > k) q.pop();
        }else{
            if(q.size() < k ) cout << "-1\n";
            else cout << q.top() << "\n";
        }
    }
    return 0;
}

丢手绢

实际上，在总长度不超过半径时，问任意子区间的最大值，要注意的是，这里是环，所以要进行破环成链，这里我采用了循环坐标，当然也可使用存两遍。区间最大值用双指针就能很好的解决。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, C = 0;
    cin >> n;
    vector<int> a(n);
    for (auto &i: a)
        cin >> i, C += i;
    int res = 0;
    for (int l = 0, r = -1, cnt = 0; l < n ; l++) {
        while ( cnt * 2 <= C) {
            r = ( r + 1 ) % n , cnt += a[r];
            res = max(res, min(cnt, C - cnt));
        }
        cnt -= a[l];
    }
    cout << res << "\n";
    return 0;
}

中位数图

规定 x 是子区间内比 b 大的数的数量，y 是子区间内比 b 小的数的数量

首先我们统计 b 的一侧，每个位置上x-y的值。然后再遍历另一侧，对于当前的x,y，看另一侧有多少y-x

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;

#define mp make_pair

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m, P = -1, res = 0;
    cin >> n >> m;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    for (int i = 0; P == -1 && i < n; i++)
        if (a[i] == m) P = i;
    map<int, int> cnt;
    for (int i = P, x = 0, y = 0; i >= 0; i--) {
        if (a[i] > m) x++;
        if (a[i] < m) y++;
        cnt[x - y]++;
    }
    for (int i = P, x = 0, y = 0; i < n; i++) {
        if (a[i] > m) x++;
        if (a[i] < m) y++;
        res += cnt[y - x];
    }
    cout << res << "\n";
    return 0;
}

好串

括号匹配

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;

#define mp make_pair

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    string s;
    cin >> s;
    int cnt = 0;
    for (auto i: s) {
        if (i == 'a') cnt++;
        else cnt--;
        if (cnt < 0) {
            cout << "Bad\n";
            return 0;
        }
    }
    if (cnt == 0) cout << "Good\n";
    else cout << "Bad\n";
    return 0;
}

兔子的区间密码

在二进制下考虑，从高位开始枚举，遇到第一位l!=r的，一个数当前位置 1 其他位置 0，另一个数当前位置 0 其他位置 1。

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

void solve(){
    int l = read() , r = read();
    int i = 63;
    for( ; i >= 0 ; i -- )
        if( (l>>i) != (r>>i) ) break;
    printf("%lld\n" , (1ll << (i+1))-1 );
    return;
}

int32_t main() {
    for(int T = read(); T ; T--)
        solve();
    return 0;
}

道路建设

最小生成树

#include <bits/stdc++.h>

using namespace std;

struct dsu {
    vector<int> fa;

    dsu(int n = 0) : fa(n + 1, -1) {};

    int getfa(int x) {
        if (fa[x] < 0) return x;
        return fa[x] = getfa(fa[x]);
    }

    bool merge(int x, int y) {
        x = getfa(x), y = getfa(y);
        if (x == y) return false;
        if (fa[x] > fa[y]) swap(x, y);
        fa[x] += fa[y], fa[y] = x;
        return true;
    }

    int size(int x) {
        x = getfa(x);
        return -fa[x];
    }
};


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int c, n, m;
    cin >> c >> m >> n;
    dsu d(n);
    vector<tuple<int, int, int>> e(m);
    for (auto &[w, x, y]: e)
        cin >> x >> y >> w;
    sort(e.begin(), e.end());
    for (const auto &[w, x, y]: e)
        if (d.merge(x, y)) c -= w;
    if (c >= 0 && d.size(1) == n ) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

逛公园

反向建图跑最短路，正向记忆化搜索。

f[i][j]表示从起点走到点i多花费了j的方案数。

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

int n, m, k, P, flag;
vector<int> dis;
vector<vector<pair<int, int>>> e, g;
vector<vector<int>> f;
vector<vector<bool>> cnt;

void dij() {
    dis = vector<int>(n + 1, INT_MAX);
    dis[n] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.emplace(0, n);
    vector<bool> vis(n + 1, false);

    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w]: g[u]) {
            if ( dis[v] <= d + w) continue;
            dis[v] = d + w, q.emplace(dis[v], v);
        }
    }
    return;
}

int calc(int u, int t) {
    if (cnt[u][t]) {
        flag = 0;
        return 0;
    }
    if (f[u][t] != -1) return f[u][t] % P;
    cnt[u][t] = true;
    f[u][t] = 0;
    for (const auto &[v, w]: e[u]) {
        int p = t - (dis[v] + w - dis[u]);
        if (p >= 0) f[u][t] = (f[u][t] + calc(v, p)) % P;
        if (flag == 0) return 0;
    }
    cnt[u][t] = false;
    if (u == n && t == 0) f[n][0] = 1;
    return f[u][t] % P;
}

void solve() {
    n = read(), m = read(), k = read(), P = read();
    e = vector<vector<pair<int, int>>>(n + 1), g = vector<vector<pair<int, int>>>(n + 1);
    for (int u, v, w; m; m--) {
        u = read(), v = read(), w = read();
        e[u].emplace_back(v, w), g[v].emplace_back(u, w);
    }
    dij();
    f = vector<vector<int>>(n + 1, vector<int>(k + 1, -1));
    flag = 1;
    cnt = vector<vector<bool>>(n + 1, vector<bool>(k + 1, false));
    int res = 0;
    for (int i = 0; flag && i <= k; i++)
        res = (res + calc(1, i)) % P;
    if (flag == 0) res = -1;
    printf("%lld\n", res);
    return;
}

int32_t main() {
    for (int T = read(); T; T--)
        solve();
    return 0;
}

求先序排列

二叉树还原

#include <bits/stdc++.h>

using namespace std;

#define int long long

string getPrefer(string middle, string suffer) {
    if (middle.size() <= 1 ) {
        return middle;
    }
    int p;
    for (p = 0; p < middle.size(); p++)
        if (middle[p] == suffer.back()) break;
    string lMiddle = middle.substr(0, p);
    string rMiddle = middle.substr(p + 1);
    string lSuffer = suffer.substr(0, p);
    string rSuffer = suffer.substr(p , rMiddle.size());
    return suffer.back() + getPrefer(lMiddle, lSuffer) + getPrefer(rMiddle, rSuffer);
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    string middle, suffer;
    cin >> middle >> suffer;
    cout << getPrefer(middle, suffer);
}

数字组合

改变枚举的顺序

#include <bits/stdc++.h>

using namespace std;

#define int long long

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a (n) , b(n) , c(n) , d(n);
    for( int i = 0 ; i < n ; i ++ )
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    map<int,int> cnt;
    for( auto i : a )
        for( auto j : b )
            cnt[ i + j ] ++;
    int res =0;
    for( auto i : c )
        for( auto j : d )
            res += cnt[ - i - j ];
    cout << res << "\n";
    return 0;
}

Protecting the Flowers

贪心

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>


using namespace std;

#define int long long
struct node{
    int t , d;
};
bool cmp( node a , node b ){
    return a.t * b.d < b.t * a.d;
}

signed main() {
    int n , res = 0 , cnt = 0;
    cin >> n;
    vector<node> a(n);
    for( int i = 0 ; i < n ; i ++ )
        cin >> a[i].t >> a[i].d;
    sort( a.begin() , a.end() , cmp );
    for( int i = 0 ; i < n ; i ++ ){
        res += cnt * a[i].d , cnt += 2ll * a[i].t;
    }
    cout << res;
    return 0;
}

小咪买东西

\[\frac{\sum v}{\sum c } = \max\\ \sum v - \max\sum c = \sum( v - \max c) = 0 \]

这样的话我们可以二分\(\max\)，如果枚举的值是\(x\)，先计算出\(y_i=v_i-xc_i\)然后选择前 k 大，判断和和零的大小即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long
const double eps = 1e-6;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<double> c(n), v(n);
    for (int i = 0; i < n; i++)
        cin >> c[i] >> v[i];
    auto f = [n, k, c, v](double x) {
        vector<double> y;
        for (int i = 0; i < n; i++)
            y.push_back(v[i] - x * c[i]);
        sort(y.begin(), y.end(), greater<int>());
        double cnt = 0;
        for (int i = 0; i < k; i++)
            cnt += y[i];
        return cnt < 0 ;
    };

    double l = 0, r = 1e9, mid, res = -1;
    while ( r-l > eps ) {
        mid = (l + r) / 2.0;
        if (f(mid)) res = mid, r = mid - eps;
        else l = mid + eps;
    }
    cout << (int)res << "\n";
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

星球大战

模拟

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod = 998244353;

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    map<int, multiset<int>> cntX, cntY;
    for (int x, y; n; n--) {
        cin >> x >> y;
        cntX[x].emplace(y);
        cntY[y].emplace(x);
    }
    for (int c, d; m; m--) {
        cin >> c >> d;
        if (c == 0) {
            cout << cntX[d].size() << "\n";
            for (auto y: cntX[d])
                cntY[y].erase(cntY[y].lower_bound(d));
            cntX[d].clear();
        } else {
            cout << cntY[d].size() << "\n";
            for (auto x: cntY[d])
                cntX[x].erase(cntX[x].lower_bound(d));
            cntY[d].clear();
        }
    }
    return 0;
}

叠积木

用并查集维护合并的过程，同时额外维护当前点到祖先节点的距离，注意在路径压缩的时候更新距离

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct dsu {
    vector<int> fa, dis;

    dsu(int n = 0) : fa(n + 1, -1), dis(n + 1, 0) {};

    int getFa(int x) {
        if (fa[x] < 0) return x;
        int t = fa[x], p = getFa(fa[x]);
        dis[x] += dis[t], fa[x] = p;
        return fa[x];
    }

    void merge(int x, int y) {
        x = getFa(x), y = getFa(y);
        dis[x] = -fa[y];
        fa[y] += fa[x], fa[x] = y;
    }

    int d(int x) {
        getFa(x);
        return dis[x];
    }
};


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int q;
    cin >> q;
    dsu d(30000);
    while (q--) {
        string op;
        cin >> op;
        if (op == "M") {
            int x, y;
            cin >> x >> y;
            d.merge(x, y);
        } else {
            int x;
            cin >> x;
            cout << d.d(x) << "\n";
        }
    }
    return 0;
}

传送带

考虑到精度要求不高，直接暴力的把线段分成5000个点，然后暴力枚举

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double
typedef pair<double, double> vec;

vec operator-(vec a, vec b) {
    a.first -= b.first, a.second -= b.second;
    return a;
}

vec operator+(vec a, vec b) {
    a.first += b.first, a.second += b.second;
    return a;
}

vec operator/(vec a, double x) {
    a.first /= x, a.second /= x;
    return a;
}

double dis(vec a, vec b) {
    return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    vec A, B, C, D;
    double p, q, r;
    cin >> A.first >> A.second >> B.first >> B.second >> C.first >> C.second >> D.first >> D.second >> p >> q >> r;
    auto d = (B - A) / 5000;
    vector<vec> t;
    int ct = 5000;
    for (auto i = A; ct; ct--, i = i + d)
        t.push_back(i);
    t.push_back(B);
    d = (D - C) / 5000;
    vector<vec> s;
    ct = 5000;
    for (auto i = C; ct; ct--, i = i + d)
        s.push_back(i);
    s.push_back(D);
    double res = LDBL_MAX;
    for (auto i: t)
        for (auto j: s) {
            double cnt = dis(A, i) / p + dis(i, j) / r + dis(j, D) / q;
            res = min(res, cnt);
        }
    cout << fixed << setprecision(2) << res << "\n";
    return 0;
}

Look Up

单调栈？

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    stack<int> s;
    vector<int> res(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        while (!s.empty() && a[s.top()] < a[i])
            res[s.top()] = i, s.pop();
        s.push(i);
    }
    for (int i = 1; i <= n; i++)
        cout << res[i] << "\n";

    return 0;
}

标签：vector,cout,训练,int,nullptr,cin,long,第二周,题单
From： https://www.cnblogs.com/PHarr/p/17580750.html

相关文章

  • pytorch 选定多GPU训练
    PyTorch多GPU训练实现在本文中，我将向你介绍如何使用PyTorch进行多GPU训练。作为一名经验丰富的开发者，我将以表格的形式展示整个实现流程，并在每一步中提供需要使用的代码和对其意义的注释。实现流程步骤代码说明1importtorch导入PyTorch库2importtorch.nnasn......
  • sam训练数据制作过程
    1.辅助人工标注阶段这个阶段以人工标注为主，但是为了提高标注效率，用了SAM的模型来进行辅助，刚开始的SAM是采用公开的分割数据训练，标注时人工采用点击前景点、背景点作为SAM的prompt输入，对分割的结果进行标注和修正，随着标注数据的增多，会采用新标注的数据来重训SAM模型，这个阶段模型反......
  • CSSYZ 思维训练 R4
    ProblemA题目大意给出一张只有0和1的矩阵，可以将$k$个点反转，求是否可以使这个矩阵中心对称，多测。算法分析这题是一个非常经典的贪心策略问题，我们发现，如果一个矩阵中心对称，那么$a_{i,j}$一定要和$a_{n-i+1,m-j+1}$所以，我们只要求出有几组应该对称的点并没有......
  • CSP-J 济南刷题训练营
    Day1：基础算法枚举从可能得集合中一一尝试统计贡献。模拟模拟题目中要求的操作NOIP2014生活大爆炸版石头剪刀布洛谷链接：P1328[NOIP2014提高组]生活大爆炸版石头剪刀布注意到赢了是得\(1\)分，平局和输都是\(0\)分，所以我们直接根据题意打表。intVs[5][5]={{0,0,1,1,......
  • 基础模型自监督预训练的数据之谜：大量数据究竟是福还是祸？
    前言 在自监督预训练中，是否数据越多越好？数据增广是否始终有效？本文转载自PaperWeekly作者|诺亚方舟实验室仅用于学术分享，若侵权请联系删除欢迎关注公众号CV技术指南，专注于计算机视觉的技术总结、最新技术跟踪、经典论文解读、CV招聘信息。CV各大方向专栏与各个部署框架最全......
  • 暑假生活第二周
    本周我把学习时间主要集中在了晚上和周末，平均每天花费了3个小时的时间进行学习。这其中有一部分时间用于理解概念和原理，另一部分时间则用于实际编写代码和练习。具体来说，本周我做了以下几件事情：学习了SQLServer的基本概念和术语，包括数据库、表、列、行、主键、外键等。理解了......
  • 代码随想录算法训练营第三十六天| 198.打家劫舍 213.打家劫舍II 337.打家劫舍III
     198.打家劫舍 要求：给定一个nums，要求取得最大值，但是不可以选择两个相邻的数dp定义：dp[n]，取到第N个数字的时候，最大值递推公式：取：nums[i]+dp[j-2]不取：nums[i-1];代码：1//在两个数字不相邻的情况下，得到的最大金额2//思路：3//dp[n]第N个数字时的最大金额数4......
  • 大二假期第二周博客
    这一周因为虽然已经安装好了大部分环境，但是在实际的使用中发现了一些问题首先是在使用过程中原有的工程文件无法打开的问题最开始我下载的是jdk8和jdk20，但是我的文件适配的是jdk11，这点好说，因为idea可以在使用过程中临时下载所需要的适配版本jdk，主要的问题是我接下来遇到的，tomcat......
  • 第二周
    1.实现并总结容器跨主机的通信过程1.1修改docker默认子网实现跨主机通信首先，需要准备2台机器，以下环境系统为Ubuntu20.04.6LTS初始化安装，安装的docker为最新24.0.2规划默认IP地址范围如下主机名主机IPdocker的IP地址范围harbor110.0.0.23110.10.0.1/24harbor......
  • 2023牛客暑期多校训练营2 补题
    D.TheGameofEating题意：有n个人和m道菜，每个人对每个菜的都有一个喜好度a[i][j]，所有人都知道其他人的喜好度，现在需要上k道菜，从1，2...，n，1，2.....的顺序来选，如果每个人都只考虑自己的喜好，问最后哪些菜会被端上来Solution我们考虑到所有人都知道其他人的喜好度，也就是说，假设当前要选......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99