首页 > 其他分享 >Codeforces Round 914 (Div

Codeforces Round 914 (Div

时间:2024-01-26 19:14:56浏览次数:32  
标签:std boy Lazy int Codeforces ++ 914 Div first

A Forked!

题目大意

给定王后和国王的位置, 马可以先朝一个方向走a步,再朝另一个方向走b
问:马有多少个位置可以同时走到皇后和国王

解题思路

就无脑遍历一下马能走到国王和皇后的位置
然后再判断下有没有相同的位置

代码

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
const int INF = 1e9 + 50;

int dx[4] = {-1, 1, -1, 1}, dy[4] = {-1, -1, 1, 1};

void solve() {
    int x1, x2, y1, y2, a, b;
    std::cin >> a >> b >> x1 >> y1 >> x2 >> y2;
    std::set<std::pair<int ,int>> s1, s2;
    for(int i = 0 ; i < 4 ; i++){
        s1.insert({x1+dx[i]*a, y1+dy[i]*b});
        s1.insert({x1+dx[i]*b, y1+dy[i]*a});
        s2.insert({x2+dx[i]*a, y2+dy[i]*b});
        s2.insert({x2+dx[i]*b, y2+dy[i]*a});
    }
    int cnt = 0;
    for(auto i : s1){
        if(s2.find (i) != s2.end())
            cnt ++;
    }
    std::cout << cnt << endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--)
        solve();
    return 0;
}

B Collecting Game

题目大意

给一个数组a,对于每一个元素,我们都会有一个初始值w = a[i] (0 <= i < n)只要w大于或等于数组中的某个元素,w = w + a[k]并且就会把这个数删除掉.

问: 对于每个元素,至多可以删除多少元素?

解题思路

由于需要最大化删除个数,我们可以先对数组升序排序,这样对于i(0 <= i < n) 就可以将0 ~ i-1的所有数删除掉,然后再考虑后面的.

就这样模拟下过程就完事儿了.

代码

(提交的一次TLE的代码)

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
typedef std::pair<int, int> pii;

void solve() {
    int n;
    std::cin >> n;
    pii a[n];
    for (int i = 0; i < n; i++)
        std::cin >> a[i].first, a[i].second = i;
    std::sort(a, a + n);
    std::vector<int> s(n, 0ll);
    for (int i = 0; i < n; i++) {
        if (i == 0)
            s[i] = a[i].first;
        else
            s[i] = s[i - 1] + a[i].first;
    }
    std::vector<int> ans(n, 0ll);
    for (int i = 0; i < n; i++) {
        int t = s[i], j = i + 1;
        while (j < n && t >= a[j].first)
            t += a[j++].first;
        ans[i] = j - 1;
    }
    for (int i = 0; i < n; i++)
        a[i].first = ans[i];
    std::sort(a, a + n, [&](pii aa, pii bb) {
        return aa.second < bb.second;
    });
    for(int i = 0 ; i < n ; i ++){
        std::cout << a[i].first << " ";
    }
    std::cout << endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--)
        solve();
    return 0;
}

(AC代码)

#include <bits/stdc++.h>

#define int long long
#define endl '\n'
[[maybe_unused]] const int INF = 1e9 + 50;

typedef std::pair<int, int> pii;

void solve() {
    int n;
    std::cin >> n;
    pii a[n + 1];
    for (int i = 0; i < n; i++) {
        std::cin >> a[i].first;
        a[i].second = i;
    }
    std::sort(a, a + n);
    std::vector<int> b(n, 0ll), c(n, 0ll), d(n, 0ll);
    for (int i = 0; i < n; i++) {
        b[i] = a[i].first;
        if (i == 0)
            c[i] = b[i];
        else
            c[i] = c[i + 1] + b[i];
    }
    for (int i = 0; i < n; i++) {
        int t = c[i];
        int k = t;
        while (true) {
            int w = std::upper_bound(b.begin(), b.end(), t) - b.begin();
            if (w == n) {
                d[a[i].second] = n - 1;
                break;
            } else {
                if (c[w - 1] == k) {
                    d[a[i].second] = w - 1;
                    break;
                } else {
                    k = c[w - 1];
                    t = c[w - 1];
                }
            }
        }
    }

    for (int i = 0; i < n; i++)
        std::cout << d[i] << " ";
    std::cout << endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--)
        solve();
    return 0;
}

C Array Game

题目大意

给一个数组a,有k次操作,每次操作选一个(i, j) (0 <= i < j < n) ,将|a[j] - a[i]|放在数组的足以后方.

问:k次操作后得到的数组最小的数为多少?

解题思路

首先,可以考虑到k>=3时,我们可以先选两次相同的(i, j),然后再选新加入的这两个,这样就可以得到0了`

然后再是k == 1时, 我们想让答案最小化,我们只能先将数组排序,然后再找相邻的两个的的差值,再到最小值后,答案还不是最优值, 所以还要与原数组最小值比较.

最后, 再是 k == 2时, 题目中明确告诉n^2 < 4e6,这就是让我们暴力循环,我们可以先将k == 1时的最小值记录下来,然后再暴力n^2跑一遍数组,再与之前的比较一下,最后输出答案.

代码

#include <bits/stdc++.h>

#define int long long
#define endl '\n'

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a;
    for (int i = 0; i < n; i++) {
        int x;
        std::cin >> x;
        a.push_back(x);
    }
    if (k >= 3) {
        std::cout << 0 << endl;
        return;
    }
    std::sort(a.begin(), a.end());
    auto calc = [&]() {//相当于处理了一次
        std::sort(a.begin(), a.end());
        int ans = a[0];
        for (int i = 1; i < (int) a.size(); i++) {
            ans = std::min(ans, a[i] - a[i - 1]);
        }
        return ans;
    };

    int ans = calc();
    if (k == 2) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int w = a[j] - a[i];
                int p = std::lower_bound(a.begin(), a.end(), w) - a.begin();
                if (p != n - 1)
                    ans = std::min(ans, a[p] - w);
                if (p != 0)
                    ans = std::min(ans, w - a[p - 1]);
            }
        }
    }
    std::cout << ans << endl;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--)
        solve();
    return 0;
}

标签:std,boy,Lazy,int,Codeforces,++,914,Div,first
From: https://www.cnblogs.com/Lazyboyjdj/p/17990492

相关文章

  • Codeforces Round 916 (Div
    AProblemsolvingLog题目描述给一个整数n,字符串s,字符串中s[i]表示第i分钟解决第s[i]题.问题A需要1分钟解决,问题B需要2分钟解决,以此类推.问:可以解决多少题?解题思路遍历字符串,统计问题A--Z用了多少时间解决.最后在遍历数组,判断问题A--Z是否满足解决时间.代......
  • Educational Codeforces Round 159 (Rated for Div
    EducationalCodeforcesRound159(RatedforDiv.2)ABinaryImbalance题目大意给定一个长度为n的一个01字符串,我们执行以下操作:当s[i]!=s[i+1]在中间插入0问:是否可以实现0的个数大于1的个数解题思路由题意可以明显看出只要有0就可以实现。下面简单分析下:0的个数大......
  • Educational Codeforces Round 160 (Rated for Div
    ARatingIncreas题目大意给定一个数字,让我们拆分成两个数,这两个数满足以下条件:a<b.两个数没有前缀0.问:输出满足条件的数a,b.解题思路直接暴力循环这个数的位数次,若满足a<b,再判断两个数的位数和是否与拆分前相同.代码#include<bits/stdc++.h>#defin......
  • Educational Codeforces Round 161 (Rated for Div
    ATrickyTemplate题目描述给一个数字n和三个长度为n的字符串a,b,c。找一个模板使得字符串a,b匹配,而c不匹配,是否存在这样一个模板.匹配的定义是:当模板字母为小写时,两个字符串字符相同,为大写时,两个字符不同,这样的两个字符串则匹配解题思路我们可以直接得出当a字符串......
  • hey_left 17 Codeforces Round 817 (Div. 4)
    题目链接A.把标准字符串和输入字符串排序,看是否相等#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;voidsolve(){intn;cin>>n;stringt;cin>>t;strings="Timur";sort(s.begin(),s.end());......
  • hey_left 16 Codeforces Round 827 (Div. 4)
    题目链接A.判最大的数是不是另外两个数的和#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=1e5+10;voidsolve(){inta,b,c;cin>>a>>b>>c;cout<<(max({a,b,c})==a+b+c-max({a,b,c})?"YES":"......
  • Codeforces 1667E Centroid Probabilities
    这个连边方式就可以理解为\(1\)为根,点\(u\)的父亲\(fa_u\)满足\(fa_u<u\)。重心有不止一种表示法,考虑用“子树\(siz\ge\lceil\frac{n}{2}\rceil\)最深的点”来表示重心。令\(m=\lceil\frac{n}{2}\rceil\),\(f_i\)为节点\(i\)的\(siz\gem\)的方案数。考虑枚......
  • Codeforces Round 920 (Div. 3)
    赛时过了A~E,表现分1738。感觉D~G都挺有意义拿出来说的。[D]VeryDifferentArray首先一个贪心的猜想是:如果A和B长度相同,那一个顺序一个逆序应该是最优的情况。思考下如何证明这个猜想。假如A和B的长度均为2,易证\(A_1\)<\(A_2\),\(B_1\)>\(B_2\)时最优......
  • CodeForces 1667E Centroid Probabilities
    洛谷传送门CF传送门首先需要了解重心的三种定义:删掉一个点后剩下子树大小\(\le\frac{n}{2}\)的点\(\sum\limits_{i=1}^n\text{dis}(u,i)\)最小的点最深的\(sz_u\ge\left\lceil\frac{n}{2}\right\rceil\)的点这道题我们使用第三种定义,也就是要统计\(i\)为最......
  • Codeforces round 919 (div2)
    Problem-A-Codeforces暴力枚举就可以;#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;vector<int>a;intn;signedmain(){int_;cin>>_;while(_--){a.clear();cin>>n;......