Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3)

Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3)

A. Math Problem

• 思路：水题

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 1e5 + 10;

int t, n, ans;
int l[N], r[N];

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t -- ){
        cin >> n;
        for (int i = 1; i <= n; i ++ )
            cin >> l[i] >> r[i];
        sort(l + 1, l + n + 1);
        sort(r + 1, r + n + 1);
        ans = l[n] - r[1];
        if (ans < 0)
            ans = 0;
        cout << ans << "
";
    }
    return 0;
}

B. Box

• 思路：模拟

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 1e5 + 10;

int t, n, pos;
int p[N], q[N];
bool flag;
bool vis[N];

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t -- ){
        memset(vis, false, sizeof(vis));
        flag = true;
        pos = 1;
        q[0] = 0;
        cin >> n;
        for (int i = 1; i <= n; i ++ )
            cin >> q[i];
        for (int i = 1; i <= n; i ++ ){
            if (q[i] < pos){
                flag = false;
                break;
            }
            if (q[i] == q[i - 1]){
                p[i] = pos;
                vis[pos] = true;
                while (vis[pos])
                    pos ++ ;
            }
            else if (q[i] > q[i - 1]){
                p[i] = q[i];
                vis[p[i]] = true;
                while (vis[pos])
                    pos ++ ;
            }
        }
        if (flag){
            for (int i = 1; i < n; i ++ )
                cout << p[i] << " ";
            cout << p[n] << "
";
        }
        else
            cout << "-1
";
    }
    return 0;
}

C. Messy

• 思路：贪心 先统一变成（（（）））这种形式 先把右边分出来一个看需要几个，左边就出来多大的位置，然后每次从左边再分出来一个

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

typedef pair <int, int> pii;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 2010;
const int M = 2e4 + 10;

int t, n, k, pos, tot, cnt;
bool flag;
char s[M];

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    cin >> t;
    while (t -- ){
        pos = 1, tot = 0;
        flag = false;
        vector<pii> ans;
        cin >> n >> k;
        scanf("%s", s + 1);
        for (int i = 1; i <= n; i ++ ){
            if (s[i] == '('){
                tot ++ ;
                if (!flag)
                    pos ++ ;
                else{
                    if (s[i + 1] == '(')
                        continue;
                    else{
                        ans.push_back(pii(pos, i));
                        flag = false;
                        pos = tot + 1;
                    }
                }
            }
            if (s[i] == ')'){
                flag = true;
                continue;
            }
        }
        if (k != 1){
            ans.push_back(pii(k, n / 2 + k - 1));
            tot = k - 2;
            cnt = 2;
            while (tot -- ){
                ans.push_back(pii(cnt, cnt + tot + 1));
                cnt += 2;
            }
        }
        cout << ans.size() << "
";
        for (auto x: ans)
            cout << x.first << " " << x.second << "
";
    }
    return 0;
}

D. Optimal Subsequences

• 思路：考场的时候D1差半分钟就做出来了（我是zz D2参考dalao的思路 首先按数组中的下标建一棵线段树 用一个新数组记录原数组 然后对新数组先按权值排序 再按下标排序 然后再用数组记录m次访问 按k从小到大排序 最后把m次询问按原来的顺序排回来 最后按顺序输出答案即可

• AC代码

---

#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mult_mod(ll x, ll y, ll mod){
    return (x * y - (ll)(x / (long double)mod * y + 1e-3) * mod + mod) % mod;
}

ll pow_mod(ll a, ll b, ll p){
    ll res = 1;
    while (b){
        if (b & 1)
            res = mult_mod(res, a, p);
        a = mult_mod(a, a, p);
        b >>= 1;
    }
    return res % p;
}

ll gcd(ll a, ll b){
    return b ? gcd(b, a % b) : a;
}

const int N = 2e5 + 10;

int n, m, now;
int sum[N << 2];

struct node{
    int x, pos;
}a[N], b[N];

struct Node{
    int k, pos, id, ans;
}q[N];

inline void update(int l, int r, int rt, int pos){
    if (pos == l && l == r){
        sum[rt] = 1;
        return ;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid)
        update(l, mid, rt << 1, pos);
    else
        update(mid + 1, r, rt << 1 | 1, pos);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

inline int query(int l, int r, int rt, int k){
    if (l == r)
        return a[l].x;
    int mid = (l + r) >> 1;
    if (sum[rt << 1] >= k)
        return query(l, mid, rt << 1, k);
    else
        return query(mid + 1, r, rt << 1 | 1, k - sum[rt << 1]);
}

inline bool cmp1(const node &a, const node &b){
    if (a.x != b.x)
        return a.x > b.x;
    return a.pos < b.pos;
}

inline bool cmp2(const Node &a, const Node &b){
    return a.k < b.k;
}

inline bool cmp3(const Node &a, const Node &b){
    return a.id < b.id;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("my_in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++ ){
        cin >> a[i].x;
        a[i].pos = i;
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1, cmp1);
    cin >> m;
    for (int i = 1; i <= m; i ++ ){
        cin >> q[i].k >> q[i].pos;
        q[i].id = i;
    }
    sort(q + 1, q + m + 1, cmp2);
    for (int i = 1; i <= m; i ++ ){
        while (now < q[i].k)
            update(1, n, 1, b[ ++ now ].pos);
        q[i].ans = query(1, n, 1, q[i].pos);
    }
    sort(q + 1, q + m + 1, cmp3);
    for (int i = 1; i <= m; i ++ )
        cout << q[i].ans << "
";
    return 0;
}