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

Codeforces Round 888 (Div. 3)

时间：2023-07-26 20:01:05浏览次数：42  
标签：int 888 Codeforces long cin ++ vector solve Div

A. Escalator Conversations

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve(){
    int n , m , k ,H;
    cin >> n >> m >> k >> H;
    vector<int> h(n);
    int res = 0;
    for( int h , i = 1 ; i <= n ; i ++ ){
        cin >> h;
        h = abs( h - H );
        if( h % k != 0 || h == 0 )continue;
        if( (h / k) < m ) res ++ ;
    }
    cout << 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;

}

B. Parity Sort

把奇偶分别排序在重新放回去

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b, c;
    for (int i = 0, x; i < n; i++) {
        cin >> x;
        a[i] = x & 1;
        if (a[i]) b.push_back(x);
        else c.push_back(x);
    }
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
    for( int i = 0 , j = 0 , k = 0 ; i < n ; i ++ ){
        if( a[i] ) a[i] = b[j] , j ++;
        else a[i] = c[k] , k ++;
    }
    for( int i = 1 ; i < n ; i ++ ){
        if( a[i] < a[i-1] ) {
            cout << "NO\n";
            return ;
        }
    }
    cout << "YES\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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &i: a) cin >> i;
    auto b = a;
    sort(b.begin(), b.end());
    for (int i = 0; i < n; i++)
        if ((a[i] - b[i]) & 1) {
            cout << "NO\n";
            return;
        }


    cout << "YES\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;
}

C. Tiles Comeback

贪心的选择前缀和c[1]相同的、后缀和c[n]相同的。

特判一下c[1]==c[n]的情况

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> c(n + 1);
    for (int i = 1; i <= n; i++) cin >> c[i];
    int l = -1, r = -1;
    for (int i = 1, cnt = 0; l == -1 && i <= n; i++) {
        if (c[i] == c[1]) cnt++;
        if (cnt == k) l = i;
    }
    for (int i = n, cnt = 0; r == -1 && i >= 1; i--) {
        if (c[i] == c[n]) cnt++;
        if (cnt == k) r = i;
    }

    if (l == -1 || r == -1)
        cout << "NO\n";
    else if (c[1] == c[n])
        cout << "YES\n";
    else if (l < r)
        cout << "YES\n";
    else
        cout << "NO\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;
}

D. Prefix Permutation Sums

先差分回去，统计缺少的数字数量。

  1. 缺大于 2 个 ，无解
  2. 缺2个，检查缺的数字之和和多的数字之和是否相同
  3. 缺 1 个，此时多的数字应该是0
  4. 不缺，不存在
#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), vis(n + 1);
    int x = 0, y = n * (n + 1) / 2, z = n;
    for (int i = 1; i < n; i++) cin >> a[i];
    for (int i = n - 1; i > 1; i--) a[i] = a[i] - a[i - 1];
    for (int i = 1; i < n; i++) {
        if (a[i] > n) x += a[i];
        else if (vis[a[i]] == 0) vis[a[i]] = 1, y -= a[i], z--;
        else x += a[i];
    }
    if (z > 2) cout << "NO\n";
    else if (x == y) cout << "YES\n";
    else if (z == 1 && x == 0) cout << "YES\n";
    else cout << "NO\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;
}

E. Nastya and Potions

把无限供应的药品的cost修改为 0，合成药品的关心其实可以看做有向图，建反向图，在反向图上跑拓扑序，根据拓扑序去计算每种药品获得的最小代价。

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> cost(n + 1), v(n + 1, -1);
    for (int i = 1; i <= n; i++)
        cin >> cost[i];
    for (int i = 1, x; i <= k; i++)
        cin >> x, cost[x] = 0;
    vector<vector<int>> e(n + 1), g(n + 1);
    vector<int> inner(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> inner[i];
        for (int j = 0, x; j < inner[i]; j++)
            cin >> x, e[i].push_back(x), g[x].push_back(i);
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (inner[i] == 0) q.push(i);

    while (!q.empty()) {
        int i = q.front();
        q.pop();
        if (!e[i].empty()) {
            int sum = 0;
            for (auto j: e[i])
                sum += cost[j];
            cost[i] = min(cost[i], sum);
        }

        for (auto j: g[i]) {
            inner[j]--;
            if (inner[j] == 0) q.push(j);
        }
    }
    for (int i = 1; i <= n; i++)
        cout << cost[i] << " ";
    cout << "\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;
}

F. Lisa and the Martians

首先\((a_i\oplus x)\&(a_j\oplus x )= a_i\odot a_j =\overline{(a_i\oplus a_j)}= y\)，所以\(y\)实际上就是同或最大值或者异或的最小值。

同时可以知道\(x=(a_i \oplus y ) | (a_j \oplus y)\)

数组中任意两数异或的最小值一定是排序后的相邻数的异或

根据这个性质就很好求了。

求异或最小值

#include <bits/stdc++.h>

using namespace std;

#define int long long
typedef bitset<30> Num;
vector<int> Temp(31);

void solve() {
    int n, k;
    cin >> n >> k;
    int T = (1ll << k) - 1;
    vector<pair<int,int>> a;
    for( int i = 1 , x ; i <= n ; i ++ )
        cin >> x , a.emplace_back( x , i );
    sort( a.begin(), a.end() );
    int l , r , res = INT_MAX , val;
    for( int i = 1 ; i < n ; i ++ ){
        if( res > (a[i].first^a[i-1].first)){
            res = a[i].first ^ a[i-1].first;
            l = a[i].second , r = a[i-1].second;
            val = T ^ ( a[i].first | a[i-1].first );
        }
    }
    cout << l << " " << r << " " << val << "\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
typedef bitset<30> Num;
vector<int> Temp(31);

void solve() {
    int n, k;
    cin >> n >> k;
    int T = (1ll << k) - 1;
    vector<pair<int, int>> a;
    for (int i = 1, x; i <= n; i++)
        cin >> x, a.emplace_back(x, i);
    sort(a.begin(), a.end());
    int l, r, res = INT_MIN, val;
    for (int i = 1, t; i < n; i++) {
        t = (~(a[i].first ^ a[i - 1].first)) & T;
        if (t > res) {
            res = t;
            l = a[i].second, r = a[i - 1].second;
            val = (a[i].first ^ t) | (a[i - 1].first ^ t);
        }
    }
    cout << l << " " << r << " " << val << "\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;
}

G. Vlad and the Mountains

首先可以知道的是，从\(a\)出发可能到达的点\(i\)一定满足\(h[i]\le h[a] + e\)

对于每条边\(i\)，记\(w_i=\max( h[u_i],h[v_i])\)，这样的话从\(a\)出发可以走的边一定满足\(w_i\le h[a]+e\)

取所用复合条件的边，用并查集维护，最后检查 \(a,b\)是否联通即可。

为了优化，可以离线询问，按照\(h[a]+e\)从小到大的顺序回答即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

class dsu {
private:
    vector<int> fa;
public:
    dsu(int n = 1) {
        fa = vector<int>(n + 1, -1), fa[0] = 0;
    }

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

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

    bool same(int x, int y) {
        x = getfa(x), y = getfa(y);
        return (x == y);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> h(n + 1);
    for (int i = 1; i <= n; i++) cin >> h[i];
    vector<array<int, 3>> edge(m);
    for (auto &[w, x, y]: edge)
        cin >> x >> y, w = max(h[x], h[y]);
    sort(edge.begin(), edge.end());

    int q;
    cin >> q;
    vector<array<int, 4>> Q(q);
    for (int i = 0, a, b, e; i < q; i++)
        cin >> a >> b >> e, e += h[a], Q[i] = {e, a, b, i};
    sort( Q.begin(), Q.end() );

    dsu d(n);
    vector<bool> res(q);
    int t = 0;
    for( const auto & [ e , a , b , id ] : Q ){
        for ( ; t < edge.size() && edge[t][0] <= e ; t  ++ )
            d.merge( edge[t][1] , edge[t][2] );
        if( d.same( a , b ) ) res[id] = true;
    }

    for (auto i: res)
        if (i) cout << "YES\n";
        else cout << "NO\n";
    cout << "\n";
    return;
}

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

标签：int,888,Codeforces,long,cin,++,vector,solve,Div
From： https://www.cnblogs.com/PHarr/p/17583421.html

相关文章

  • Codeforces Round 888 (Div. 3)F(异或小技巧）
    题意：给你一个数组长度为n的a数组，要求a数组的值为非负整数，再给你一个k，a的值全小于2的k次方，找到一个小于a的k次方的值x，再从a中找到两个值，让他们(ai⊕x)&(aj⊕x)最小结论：n个数的最小异或对的答案就是排序后最小的相邻异或和思路：(ai⊕x)&(aj⊕x)的最高位为1，可以把它先转换成二进制......
  • 【题解】Educational Codeforces Round 150（CF1841）
    赛时过了A-E，然后就开摆了，为什么感觉C那么无厘头[发怒][发怒]排名：25thA.GamewithBoard题目描述：Alice和Bob玩游戏，他们有一块黑板。最初，有\(n\)个整数\(1\)。Alice和Bob轮流操作，Alice先手。轮到时，玩家必须在棋盘上选择几个（至少两个）相等的整数，擦除它们，然后写一个......
  • Codeforces 1852A Ntarsis' Set 题解
    题目传送门：Codeforces1852ANtarsis'Set题意给定一个集合，里面初始有\(1,2,3...10^{1000}\)，告诉你每天会拿掉其中的第\(a_1,a_2,a_3...a_n\)个，询问这样的\(k\)天之后剩下的最小的数是多少。分析思考如果\(x\)在这天没有被删掉，那么哪些被删掉的位置会对它产生什么......
  • Codeforces Round 886 (Div. 4) D - H
    D.BalancedRoundProblem-D-Codeforces双指针，贪心题意：​ 给出\(n\)个数，我们可以删去其中若干个数，使得删完后的数重新排列任意相邻的数之差绝对值不超过\(k\)，输出最小删去数的个数思路：​ 很明显可以先将给出的数组进行排序。对于排序后的数组，我们可以将其分为若干个相邻......
  • CodeForces 725F Family Photos
    洛谷传送门CF传送门不错的贪心题。我们考虑一对照片只有一张的情况。那么先后手会按照\(a+b\)降序取。因为若\(a_i+b_i\gea_j+b_j\)，变形得\(a_i-b_j\gea_j-b_i\)且\(b_i-a_j\geb_j-a_i\)，所以对于双方先取\(i\)一定是不劣的。回到原题，如果\(a_{i......
  • Codeforces Round 887 (Div. 2) A-D
    CodeforcesRound887(Div.2)A.Desorting题意：给出一个数组，可以进行任意次以下操作：选择一个i对于数组中的a[1],a[2],...,a[i]全部+1a[i+1]...a[n]全部-1,问最小使得数组变得无序的操作是多少次Solution直接找相邻的两个数的最小的差值即可voidsolve(){ intn;cin>>n......
  • Educational Codeforces Round 71 (Rated for Div. 2)
    EducationalCodeforcesRound71(RatedforDiv.2)A-ThereAreTwoTypesOfBurgers思路：价格高的优先取#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128typedefpair<int,int>PII;typedefpair<string,int&......
  • 题解 Codeforces Round 887 (Div 1+Div 2) / CF1853AB,CF1852ABCD
    下大分！悲！Div1只过了1A！！！但还是补完整场Div2吧。A.Desortinghttps://codeforces.com/problemset/problem/1853/Aproblem用操作：\([1,i]++,[i+1,n]--\)，使得数组不单调不降，求最小操作次数。\(n\leq10^5\)。solution操作等同于在差分数组上选出\(i\)，做\(c_1:=c_1+1,c_i:......
  • Codeforces Round #887 Div.2 A-E
    CodeforcesRound#887Div.2一定要手玩哦前言：一定要手玩，一定要手玩！我今早一手玩发现C很TM简单，如果赛时我能切C说不定直接上1800.。。。时隔多年，我的CodeforcesRating(1718)再次超越了@cqbzlhy(1674)！！！赛时错误：B题出得太慢了->劣于pzj半小时。%%%pzjC没有手玩，瞪眼半天......
  • UESTC 2023 Summer Training #13 Div.2
    Preface开始裸泳咯这个A题给我写的头皮发麻，后面发现我就是个智障儿童比赛的时候E题想了半天感觉天皇老子来了也是\(\frac{1}{n^2}\)，赛后发现我是小丑感觉中间做J的时候因为看错题目浪费了很长时间，不过再给一个小时思博题该不会还是不会A.PainttheMiddle比赛的时候一眼贪......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99