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

Codeforces Round 690 (Div. 3)

时间:2023-08-06 17:47:29浏览次数:39  
标签:690 cout int ll Codeforces -- solve Div tt

Codeforces Round 690 (Div. 3)

https://codeforces.com/contest/1462

A. Favorite Sequence

按题意输出

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int a[N], n;

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    for (int i = 0; i < n / 2; i++) {
        cout << a[i + 1] << ' ';
        if (i + 1 != n - i) cout << a[n - i] << ' ';
    }
    if (n & 1)  cout << a[n / 2 + 1];
    cout << endl;
}

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

B. Last Year's Substring

形如:

...2020
2...020
20...20
202...0
2020...

分类讨论即可

#include <bits/stdc++.h>

using namespace std;

void solve () {
    int n;
    string s;
    cin >> n >> s;
    if (s[0] == '2' && s[n-3] == '0' && s[n-2] == '2' && s[n-1] == '0') cout << "YES\n";
    else if (s[0] == '2' && s[1] == '0' && s[n-2] == '2' && s[n-1] == '0') cout << "YES\n";
    else if (s[0] == '2' && s[1] == '0' && s[2] == '2' && s[n-1] == '0') cout << "YES\n";
    else if (s[n-4] == '2' && s[n-3] == '0' && s[n-2] == '2' && s[n-1] == '0') cout << "YES\n";
    else if (s[0] == '2' && s[1] == '0' && s[2] == '2' && s[3] == '0') cout << "YES\n";
    else    cout << "NO\n";
}

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

C. Unique Number

构造形如 123456789
易发现最达能构造出来的数字就是45,模拟即可,倒着从9开始填

#include <bits/stdc++.h>

using namespace std;

void solve () {
    int n;
    cin >> n;
    //cout << n << ": ";
    if (n < 10)     cout << n << endl;
    else if (n > 45)    cout << "-1\n";
    else {
        vector<int> v;
        for (int i = 9; i > 0; i--) {
            int t = min (i, n);
            //cout << t << ' ';
            if (v.size () && v.back () == t)    v.push_back (t - 1), v.push_back (1);
            else    v.push_back (t);
            n -= t;
            if (n == 0) break;
        }
        reverse (v.begin (), v.end ());
        
        for (auto i : v)    cout << i;
        cout << endl;
    }
}

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

D. Add to Neighbour and Remove

和固定,直接枚举最终局面,贪心计算和判断是否合法。

#include <bits/stdc++.h>

using namespace std;
const int N = 3005;
int a[N], n;

void solve () {
    int sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i], sum += a[i];
    for (int len = n; len >= 1; len--) {
        //剩下len个数
        if (sum % len)  continue;
        int tt = sum / len, cur = 0, cnt = 0;
        bool suc = true;
        for (int i = 1; i <= n; i++) {
            cur += a[i];
            if (cur == tt)  cnt++, cur = 0;
            else if (cur > tt) {
                suc = false;
                break;
            }
        }
        if (suc) {
            cout << n - len << endl;
            break;
        }
    }    
}

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

E1. Close Tuples (easy version)

见下表:

x  x+1  x+2
3  0    0
2  1    0
2  0    1
1  2    0
1  0    2
1  1    1

枚举然后计算次数即可

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 2e5 + 5;
ll n, x, a[N];

void solve () {
    ll ans = 0;
    cin >> n;
    for (int i = 1; i <= n + 3; i++)    a[i] = 0;
    for (int i = 1; i <= n; i++)    cin >> x, a[x]++;
    for (int i = 1; i <= n; i++) {
        ll t = a[i], tt = a[i + 1], ttt = a[i + 2];
        if (t >= 3)     ans += (t * (t - 1) * (t - 2)) / 6;
        if (tt > 0)     ans += (t * (t - 1) / 2) * tt;
        if (tt > 1)     ans += t * (tt * (tt - 1) / 2);
        if (ttt > 0)    ans += t * tt * ttt + (t * (t - 1) / 2) * ttt;
        if (ttt > 1)    ans += t * (ttt * (ttt - 1) / 2);
    }
    cout << ans << endl;
}

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

E2. Close Tuples (hard version)

相当于在 \([a_i, a_i+k]\) 范围的若干个数中选 \(m\) 个数的组合。

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7;
ll n, m, k, a[N];

ll fact[N], infact[N];

ll qmi(ll a, ll k, ll p){
    ll res = 1;
    while(k){
        if(k & 1)
            res = (ll)res * a % p;
        a = (ll)a * a % p;
        k >>= 1;
    }
    return res;
}

ll C (int a, int b) {
    if (a < b)  return 0;
    return fact[a] * infact[b] % mod * infact[a - b] % mod;
}

void init () {
    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i++){
        fact[i] = (ll)fact[i-1] * i % mod;
        infact[i] = (ll)infact[i-1] * qmi(i, mod - 2,mod) % mod;
    }
}

void solve () {
    ll ans = 0;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    sort (a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        int pos = upper_bound (a + 1, a + n + 1, a[i] + k) - a;
        if (pos - i >= m) { //[ai, ai+k] 的范围内共 pos-i-1 个数中选
            (ans += C (pos - i - 1, m - 1)) %= mod;
        }
    }
    cout << ans << endl;
}

int main () {
    init ();
    int t;
    cin >> t;
    while (t--)     solve ();
}

F. The Treasure of The Segments

计算每个区间的香蕉区间数,记录最大值。
具体计算:总区间数 - 相离区间数
相离:大于当前右端点的左端点数 + 大于当前左端点的右端点数
二分查找

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int n;

struct Node {
    int l, r;
    bool operator<(const Node &t) const {
        if (l != t.l)   return l < t.l;
        return r < t.r;
    }
}p[N];

void solve () {
    int ans = 1;
    cin >> n;
    vector<int> vl, vr;
    for (int i = 1; i <= n; i++) {
        cin >> p[i].l >> p[i].r;
        vl.push_back (p[i].l);
        vr.push_back (p[i].r);
    }
    sort (p + 1, p + n + 1);
    sort (vl.begin (), vl.end ()), sort (vr.begin (), vr.end ());
    for (int i = 1; i <= n; i++) {
        int cnt = 1, l = p[i].l, r = p[i].r;
        //找不相交的有多少个
        int rr = upper_bound (vl.begin (), vl.end (), r) - vl.begin (); //在右侧不相交
        rr = n - rr;
        int ll = lower_bound (vr.begin (), vr.end (), l) - vr.begin (); //再左侧不相交
        cnt = n - ll - rr;
        ans = max (ans, cnt);
    }
    cout << n - ans << endl;
}

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

标签:690,cout,int,ll,Codeforces,--,solve,Div,tt
From: https://www.cnblogs.com/CTing/p/17609615.html

相关文章

  • Codeforces Round 890 (Div. 2) supported by Constructor Institute ————C - T
    关于这场div2,只能说一言难尽C题可以二分的,赛时看到n<=1000,直接往\(O(n^2)\)考虑,想了一会贪心的话能写出来,但是,细节太多没调出来,G掉打分。\(O(n^2)\)做法:思路:每次让i为起点,往前贪心枚举,并且当前位置如果满足,也要枚举当前区间,细节就是要注意上下限,赛时,漏了一种上界小于下届的情......
  • Codeforces Round 890 (Div. 2) supported by Constructor Institute 题解
    A.TalesofaSort关键就是找逆序对记一组逆序对下标为\(l,r\),则求出最大的\(a_l\)即可B.GoodArrays记要构造的GoodArray为\(b\)前置:\(\forall1\lei\len,b_i=1\)然后\(O(n)\)扫一遍看一下有没有重复,有重复就\(b_i\leftarrowb_i+1\)扫完之后,记\(sum=\sum_......
  • Codeforces Round 882 (Div. 2) 题解
    A.TheManwhobecameaGod求出相邻两个元素的差值,去掉前\(m\)个大的差值以后的差值和即为答案B.HamonOdyssey由按位与的性质可以知道,前缀与和的值只会越来越小,只要和为\(0\)的时候我们就清空按位与前缀和,增加一下次数,如果最终次数不为\(0\),特判一下,次数加一即可C.......
  • CodeForces 1856E1 PermuTree (easy version)
    洛谷传送门CF传送门考虑局部贪心,假设我们现在在\(u\),我们希望\(u\)不同子树中的\((v,w),a_v<a_u<a_w\)的对数尽量多。我们实际上只关心子树内\(a_u\)的相对大小关系,不关心它们具体是什么。如果\(u\)只有两个儿子\(v,w\),我们可以让\(v\)子树内的\(a\)全部......
  • CodeForces 1856E2 PermuTree (hard version)
    洛谷传送门CF传送门考虑局部贪心,假设我们现在在\(u\),我们希望\(u\)不同子树中的\((v,w),a_v<a_u<a_w\)的对数尽量多。我们实际上只关心子树内\(a_u\)的相对大小关系,不关心它们具体是什么。如果\(u\)只有两个儿子\(v,w\),我们可以让\(v\)子树内的\(a\)全部......
  • 【反思】洛谷8月月赛 Div.2 & RiOI Round 2 赛后反思
    RiOIR2赛后反思赛时开了一个T1,但是\(0pts\),然后就跑去跟人对线然后复盘(主要是我的锅,我忘记对线怎么开始的了)到了吃饭(雾不过本来我也不会做,不能怪人家赛后是shenshen教我T1+看的若归老师的反思捏推歌:歌爱ユキ&稲葉曇《キミに回帰缐》(希望没打错是我的错吗铅笔......
  • CodeForces 1856D More Wrong
    洛谷传送门CF传送门直接求最大值不好求。我们可以采用一个交互常见的套路,维护可能的答案集合\(S\),每次剔除掉一些。考虑初始把\(a_{i-1}<a_i>a_{i+1}\)的\(i\)加入\(S\),每次取出\(S\)中差最小的一对元素\(i,j\),那么若\(a_i>a_j\),\(a_i\)就大于\([i+1......
  • Codeforces Round 882 (Div. 2)
    CodeforcesRound882(Div.2)ATheManwhobecameaGod给定一个数组\(\{x_1,x_2,\cdots,x_n\}\)和一个整数\(k\),记\(f(l,r)=\sum_{i=0}^{i\ler-l}|x_{l+i}-x_{l+i+1}|\),求将数组划分为\(k\)个部分的划分方案,使得对每个部分的\(f(l,r)\)之和最小.​ 将两数相......
  • Codeforces Round 885 (Div. 2) C. Vika and Price Tags
    C.VikaandPriceTagsC-VikaandPriceTags题意:​ 初始两串数列\(a,b\),对于第\(i\)个数,令\(c_i=|a_i-b_i|\),然后将数列\(a=b,b=c\)。重复这样的操作,问是否可能让\(a\)串全部变成0。思路:这题实际上之前已经发过,但最近打牛客对这题有了新的理解,所以来记录一下。​ ......
  • Codeforces 1843D:Apple Tree
    1843D.AppleTreeDescription:一棵树(\(Tree\)无环无重边)\(n\)个节点,根节点为1(节点编号\(1\)~\(n\)),树上只有2个苹果,每次摇动苹果树时,每个苹果会有如下变化:当前苹果位于节点\(u\):1.若节点\(u\)有子节点,则该苹果移动到此节点(若有多个子节点,则可以到任意一个)。2.......