首页 > 其他分享 >Codeforces Round 811 (Div. 3)

Codeforces Round 811 (Div. 3)

时间：2023-10-01 18:34:58浏览次数：34  
标签：int res void Codeforces long solve using 811 Div

A. Everyone Loves to Sleep

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int n, h, m, t;
    cin >> n >> h >> m;
    t = h * 60 + m;
    vector<int> a;
    for (int i = 1, x, y; i <= n; i++)
        cin >> x >> y, a.push_back(x * 60 + y);
    sort( a.begin(), a.end() ) , a.push_back( a.front() + 24 * 60 );
    int p = *lower_bound( a.begin(), a.end() , t );
    p -= t;
    cout << p / 60 << " " << p % 60 << "\n";
    return;
}

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

B. Remove Prefix

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e18;

using vi = vector<int>;

const int N = 1e3;
vi val(N + 1, inf);

void solve() {
    int n;
    cin >> n;
    vi a(n);
    for( auto & i : a ) cin >> i;
    set<int> cnt;
    reverse(a.begin(), a.end());
    for( auto & i : a )
        if( cnt.insert(i).second == false ) break;
    cout << n - cnt.size() << "\n";
    return;
}

int32_t main() {
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C. Minimum Varied Number

贪心暴搜似乎过不去，但是可以打表

#include<bits/stdc++.h>

using namespace std;

//int res, n = 0;
//vector<int> q, vis(10);
//
//void dfs(int x) {
//    int cnt = 0;
//    auto p = q;
//    sort(p.begin(), p.end());
//    for (auto i: p) cnt = cnt * 10 + i;
//    if( cnt > res ) return ;
//    if (x == 0) {
//        res = min(res, cnt);
//        return;
//    }
//    for (int i = 1; i <= 9; i++) {
//        if (i > x) break;
//        if (vis[i]) continue;
//        vis[i] = 1, q.push_back(i);
//        dfs(x - i);
//        vis[i] = 0, q.pop_back();
//    }
//}

//void solve() {
//    ++ n, res = INT_MAX;
//    dfs(n);
//    cout << res << "\n";
//}

vector<string> res = {"1",
                      "2",
                      "3",
                      "4",
                      "5",
                      "6",
                      "7",
                      "8",
                      "9",
                      "19",
                      "29",
                      "39",
                      "49",
                      "59",
                      "69",
                      "79",
                      "89",
                      "189",
                      "289",
                      "389",
                      "489",
                      "589",
                      "689",
                      "789",
                      "1789",
                      "2789",
                      "3789",
                      "4789",
                      "5789",
                      "6789",
                      "16789",
                      "26789",
                      "36789",
                      "46789",
                      "56789",
                      "156789",
                      "256789",
                      "356789",
                      "456789",
                      "1456789",
                      "2456789",
                      "3456789",
                      "13456789",
                      "23456789",
                      "123456789"};

void solve(){
    int n;
    cin >> n;
    cout << res[n-1]<< "\n";
}

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

D. Color with Occurrences

当我们确定之前覆盖的部分后，可以直接贪心的选择可以之前覆盖区间能够相连且，覆盖距离最远的。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e18;

using db = long double;
using vi = vector<int>;
using pii = pair<int, int>;

void solve() {
    string t, s;
    int n;
    cin >> t >> n;
    int m = t.size();
    vector<array<int, 3>> e;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int l = 0, r = s.size()-1; r < m; l++, r++) {
            if (t.substr(l, s.size()) == s)
                e.push_back({l + 1, r + 1, i});
        }
    }
    vector<int> res;

    for (int pos = 0, left = 1, right = 0; left <= m; pos = 0) {
        for (int i = 0; i < e.size(); i++)
            if (e[i][0] <= left and e[i][1] > right)
                right = e[i][1], pos = i;
        res.push_back(pos);
        left = right + 1;
        if (res.size() > e.size() + 100) {
            cout << "-1\n";
            return;
        }
    }
    cout << res.size() << "\n";
    for (auto i: res)
        cout << e[i][2] << " " << e[i][0] << "\n";
}

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

E. Add Modulo 10

可以发现除了结尾是5和 0 的情况，其他的都会进入到2 4 8 6 的循环中，所以可以先把各位全部移动到循环上，然后判断差值是否都是20 的倍数

#include<bits/stdc++.h>

using namespace std;

#define int long long
using vi = vector<int>;

void solve() {
    int n, f1 = 1, f2 = 1;
    cin >> n;
    vi a(n);
    for (auto &i: a) {
        cin >> i;
        if (i % 10 == 0 or i % 10 == 5) {
            f1 = 0;
            if (i % 10 == 5) i += 5;
        } else f2 = 0;
    }
    if (f1 + f2 == 0) {
        cout << "No\n";
        return;
    } else if (f2) {
        for (auto i: a)
            if (i != a.front()) {
                cout << "No\n";
                return;
            }
        cout << "Yes\n";
        return;
    }
    for (auto &i: a)
        while (i % 10 != 2) i += i % 10;
    int top = *max_element(a.begin(), a.end());
    for( auto i : a )
        if( (top - i) % 20 != 0 ){
            cout << "No\n";
            return ;
        }
    cout << "Yes\n";
    return ;
}

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

F. Build a Tree and That Is It

除去不合法的情况，答案只有两种情况，一种是三个点在一条链上，此时选择中间的点作为根就好了。还有一种情况是一个 y 形的树，计算出三个点到分叉点的距离，分叉点做根就好了

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

void solve() {
    int n, d1, d2, d3;
    cin >> n >> d1 >> d2 >> d3;
    if (max({d1, d2, d3}) * 2 > d1 + d2 + d3) {
        cout << "NO\n";
        return;
    }
    if ((d1 + d2 + d3) & 1) {
        cout << "NO\n";
        return;
    }
    if ((d1 + d2 + d3) / 2 + 1 > n) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";

    vi p(n + 1);
    auto solver = [&](int root, int p1, int p2, int dep1, int dep2) {
        set<int> s;
        for (int i = 4; i <= n; i++) s.insert(i);
        int fa, dep, t;
        for (fa = root, dep = 1, t; dep < dep1; dep++) {
            t = *s.begin(), s.erase(s.begin());
            p[t] = fa, fa = t;
        }
        p[p1] = fa;
        for (fa = root, dep = 1, t; dep < dep2; dep++) {
            t = *s.begin(), s.erase(s.begin());
            p[t] = fa, fa = t;
        }
        p[p2] = fa;
        while (!s.empty())
            p[*s.begin()] = root, s.erase(s.begin());
        for (int i = 1; i <= n; i++)
            if (i != root) cout << i << " " << p[i] << "\n";
    };
    if (d1 + d2 == d3)
        solver(2, 1, 3, d1, d2);
    else if (d1 + d3 == d2)
        solver(1, 2, 3, d1, d3);
    else if (d2 + d3 == d1)
        solver(3, 1, 2, d3, d2);
    else {
        set<int> s;
        for (int i = 5; i <= n; i++) s.insert(i);
        int dep1 = (d1 + d3 - d2) / 2;
        int dep2 = (d1 + d2 - d3) / 2;
        int dep3 = (d2 + d3 - d1) / 2;
        int root = 4, fa, dep, t;
        for (fa = root, dep = 1, t; dep < dep1; dep++) {
            t = *s.begin(), s.erase(s.begin());
            p[t] = fa, fa = t;
        }
        p[1] = fa;
        for (fa = root, dep = 1, t; dep < dep2; dep++) {
            t = *s.begin(), s.erase(s.begin());
            p[t] = fa, fa = t;
        }
        p[2] = fa;
        for (fa = root, dep = 1, t; dep < dep3; dep++) {
            t = *s.begin(), s.erase(s.begin());
            p[t] = fa, fa = t;
        }
        p[3] = fa;
        while (!s.empty())
            p[*s.begin()] = root, s.erase(s.begin());
        for (int i = 1; i <= n; i++)
            if (i != root) cout << i << " " << p[i] << "\n";
    }
    return;
}

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

G. Path Prefixes

dfs 的过程记录一下到根的路径，在路径上二分一下就好

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e18;

using db = long double;
using vi = vector<int>;
using pii = pair<int, int>;

void solve() {
    int n;
    cin >> n;
    vi a(n + 1), b(n + 1), q, f(n + 1);
    vector<vi> e(n + 1);
    for (int i = 2, p; i <= n; i++)
        cin >> p >> a[i] >> b[i], e[p].push_back(i);

    auto dfs = [e, a, b, &f, &q](auto &&self, int x, int cntA, int cntB, int dep) -> void {
        q.push_back(cntB);
        int res = -1;
        for (int l = 0, r = dep, mid; l <= r;) {
            mid = (l + r) / 2;
            if (q[mid] <= cntA) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        f[x] = res;
        for (auto y: e[x])
            self(self, y, cntA + a[y], cntB + b[y], dep + 1);
        q.pop_back();
    };

    dfs(dfs, 1, 0, 0, 0);
    for( int i = 2 ; i <= n ; i ++ )
        cout << f[i] << " ";
    cout << "\n";
    return ;
}

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

标签：int,res,void,Codeforces,long,solve,using,811,Div
From： https://www.cnblogs.com/PHarr/p/17739094.html

相关文章

  • Codeforces 1702G2 题解
    题目大意给出一个大小为\(n\)的树，\(q\)次询问，每次给出一个大小为\(m\)的点集，判断是否有一条链覆盖这些点（这条链可以经过其他点）。\(n,\summ\leqslant2\cdot10^5\),\(q\leqslant10^5\)。提示提示1思考将$m$个点按深度排序。题解题解考虑将\(m\)个点按树......
  • CodeForces 1874B Jellyfish and Math
    洛谷传送门CF传送门看到这种操作乱七八糟不能直接算的题，可以考虑最短路。对于\(a,b,c,d,m\)按位考虑，发现相同的\((a,b,m)\)无论如何操作必然还是相同的。于是考虑对于每个可能的\((0/1,0/1,0/1)\)，所有终态有\((c=0/1,d=0/1)\)或者不确定。这样我们对于一......
  • 「题解」Codeforces Round 895 (Div. 3)
    A.TwoVesselsProblem题目Sol&Code签到题#include<bits/stdc++.h>typedeflonglongll;intmin(inta,intb){returna<b?a:b;}intmax(inta,intb){returna>b?a:b;}intT,a,b,c;intmain(){scanf("%d"......
  • AT_abc254_h [ABC254Ex] Multiply or Divide by 2 题解
    打篇题解巩固一下。题意给你两个集合\(A\)和\(B\)，对于任意\(A\)集合中的元素，我们可以进行\(2\)种操作：\(a_i\gets\left\lfloor\frac{a_i}{2}\right\rfloor\)或\(a_i\gets2\timesa_i\)。问最少要多少次才能使\(A\)和\(B\)中的元素相等。分析首先我们可以令\(a......
  • Codeforces Round 901 (Div. 2)
    CodeforcesRound901(Div.2)A-JellyfishandUndertale解题思路:卡在最后秒放。若\(x_i>(a-1)\):那么该\(x_i\)的贡献为\(a-1\)。否则，该\(x_i\)的贡献为\(x_i\)。代码:#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;typedefpair<int,in......
  • 901DIV2 (A~D)
    901DIV2A~DA:大于等于\(a-1\)的贡献都是a-1.voidsolve(){intans=0;inta,b,n;cin>>a>>b>>n;ans+=b;for(inti=1;i<=n;i++){intx;cin>>x;if(x>=a)x=a-1;ans+=x;}cout<<......
  • Educational Codeforces Round 155 (Rated for Div
    B.ChipsontheBoard题解：贪心显然我们可以把题意转化为：对于任意一个\((i,j)\)，我们可以花费\(a_{i,j}\)的代价占据第\(i\)行和第\(j\)列，求占据所有格子的最小代价考虑两种情况：在每一行选一个格子在每一列选一个格子贪心选即可intn,a[N],b[N];voidsolve......
  • Codeforces Round 898 (Div. 4)
    由于题目补完才来写总结，导致前面的有的题目都需要重新再看一遍，只好当作复习了。但考虑到趁热打铁，先看H.H题：从小白视角来看乍一看是博弈论，仔细思考以后发现是图论。本题给的是基环树，意识到这一点很重要，这个条件是让本题不是很复杂的关键。n个点n条边且没有重边保证这个联通图中......
  • Codeforces Round 900 (Div. 3)
    目录写在前面ABCDEFG写在最后写在前面比赛地址：https://codeforces.com/contest/1878。前天晚上他妈睡不着觉又不想看漫画打游戏于是到阳台上开把div3放松心情。40min过了5题把剩下两题都口了感觉没意思了于是睡觉。太菜了还是，现在是div3随便AK但是div2过不了E的......
  • Educational Codeforces Round 122 (Rated for Div. 2)
    A.Div.7#include<bits/stdc++.h>usingnamespacestd;voidsolve(){intn,a,b,c;cin>>n;c=n%10,n/=10;b=n%10,n/=10;a=n%10,n/=10;intres,val=100;for(inti=0;i<=9......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99