Codeforces Round #595 (Div. 3)

比赛链接:传送门


Codeforces1249A. Yet Another Dividing into Teams(水题)

代码:

#include <bits/stdc++.h>
#define N 105

using namespace std;

int a[N];
int main()
{
    int q;
    cin >> q;
    while (q--) {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        sort(a+1, a+1+n);
        int ans = 1;
        for (int i = 2; i <= n; i++) {
            if (a[i] == a[i-1] + 1) {
                ans++;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
View Code

Codeforces1249B2. Books Exchange (hard version)

一本书在一个周期内经过的路径中的每个人,拿到自己原来的书所需要的时间都等于这个周期的长度。

代码:O(n)

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 200005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define upperdiv(a,b) (a/b + (a%b>0))
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)

using namespace std;
typedef long long ll;
typedef double db;

/** fast read **/
template <typename T>
inline void read(T &x) {
    x = 0; T fg = 1; char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') fg = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
template <typename T>
inline void write(T x) {
    int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;
    do{++len; c[len] = x%10 + '0';} while (x /= 10);
    for (int i = len; i >= 1; i--) putchar(c[i]);
}
template <typename T, typename... Args>
inline void write(T x, Args ... args) { write(x), write(args...); }

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

int p[N], ans[N];
int solve(int x) {
    int len = 0;
    int tmp = x;
    do {
        tmp = p[tmp];
        len++;
    } while (tmp != x);
    do {
        ans[tmp] = len;
        tmp = p[tmp];
    } while (tmp != x);
    return len;
}
int main()
{
    int q;
    cin >> q;
    while (q--) {
        int n; read(n);
        for (int i = 1; i <= n; i++) {
            ans[i] = 0;
        }
        for (int i = 1; i <= n; i++)
            read(p[i]);
        for (int i = 1; i <= n; i++) {
            if (!ans[i]) {
                solve(i);
            }
        }
        for (int i = 1; i <= n; i++) {
            printf("%d%c", ans[i], " 
"[i==n]);
        }
    }
    return 0;
}
View Code

Codeforces1249C2. Good Numbers (hard version)(进制转换 贪心)

把n转化成三进制放在数组中,如果有2的话说明要找比n大的最小的满足条件的。

只要把权值最大的2加一变成3,然后进位。并把比这个2小的所有三进制数值置零就行了。

比如129用三进制表示是1121。操作过程中的值就是:1121->1200->2000->10000。结果就是35 = 243。

代码:O(logn)

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 200005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define upperdiv(a,b) (a/b + (a%b>0))
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)

using namespace std;
typedef long long ll;
typedef double db;

/** fast read **/
template <typename T>
inline void read(T &x) {
    x = 0; T fg = 1; char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') fg = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
template <typename T>
inline void write(T x) {
    int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;
    do{++len; c[len] = x%10 + '0';} while (x /= 10);
    for (int i = len; i >= 1; i--) putchar(c[i]);
}
template <typename T, typename... Args>
inline void write(T x, Args ... args) { write(x), write(args...); }

ll b[N], a[N];
int main()
{
    b[0] = 1;
    for (int i = 1; i <= 38; i++) {
        b[i] = b[i-1] * 3;
    }
    int q; read(q);
    while (q--) {
        ll n; read(n);
        for (int i = 38; i >= 0; i--) {
            a[i] = n/b[i];
            n %= b[i];
        }
        int st = 0;
        for (int i = 38; i >= 0; i--) {
            if (a[i] == 2) {
                st = i;
                break;
            }
        }
        for (int i = 0; i < st; i++) {
            a[i] = 0;
        }
        for (int i = st; i <= 38; i++) {
            if (a[i] >= 2) {
                a[i] = 0;
                a[i+1]++;
            }
        }
        ll ans = 0;
        for (int i = 0; i <= 38; i++) {
            if (a[i])
                ans += b[i];
        }
        cout << ans << endl;
    }
    return 0;
}
View Code

Codeforces1249D2. Too Many Segments (hard version)(扫描线+单调队列+multiset维护)

这题好像比E难的样子。

思路:

考虑从左到右枚举每一个小区间,看这个小区间被多少个线段覆盖。如果被超过k个线段覆盖,则把这些线段中右端点最大的一个remove掉。

实现:

先把所有线段按l、r从小到大排序,然后从左到右遍历。

对于每一条线段(l0,r0),考虑维护之前有多少个线段的r比l0大。具体的就是保存之前的所有的r,如果r < l0,则把这些r删去。(这里可以用单调队列或者set维护,但是考虑后面的操作,这里选择了set)

如果比l0大的r的数量超过了k,那么就贪心地删去里面最大的那个r(这里就体现了set的方便之处,可以直接erase(--set.end()))。考虑到会有重复元素,所以set要换成multiset。

代码:O(nlogk)

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 200005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define upperdiv(a,b) (a/b + (a%b>0))
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)

using namespace std;
typedef long long ll;
typedef double db;

/** fast read **/
template <typename T>
inline void read(T &x) {
    x = 0; T fg = 1; char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') fg = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
template <typename T>
inline void write(T x) {
    int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;
    do{++len; c[len] = x%10 + '0';} while (x /= 10);
    for (int i = len; i >= 1; i--) putchar(c[i]);
}
template <typename T, typename... Args>
inline void write(T x, Args ... args) { write(x), write(args...); }

struct Node{
    int l, r, id;
    bool operator < (const Node& x) const {
        if (l == x.l)
            return r < x.r;
        return l < x.l;
    }
}nodes[N];

struct SNode{
    int val, id;
    bool operator < (const SNode& x) const {
        return val < x.val;
    }
};

multiset <SNode> S;
vector <int> ans;
int main()
{
    int n, k; read(n, k);
    for (int i = 1; i <= n; i++) {
        read(nodes[i].l, nodes[i].r);
        nodes[i].id = i;
    }
    sort(nodes+1, nodes+1+n);
    for (int i = 1; i <= n; i++) {
        while (!S.empty() && (*S.begin()).val < nodes[i].l)
            S.erase(S.begin());
        S.insert(SNode{nodes[i].r, nodes[i].id});
        if (sz(S) > k) {
            ans.push_back((*--S.end()).id);
            S.erase(--S.end());
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int i = 0; i < sz(ans); i++) {
        printf("%d%c", ans[i], " 
"[i == sz(ans)-1]);
    }
    return 0;
}
View Code

Codeforces1249E. By Elevator or Stairs?(dp)

思路:

上楼肯定是要一层一层上的,所以每层楼只要考虑下面那层楼爬到这一层楼的情况。

设当前楼层为i,$f_{i,0/1}$表示到达第i层楼时,最后一层是走楼梯(0)或者电梯(1)所需要的最短时间。

显然有$f_{1,0} = 0$,特别地,令$f_{1,1}=c$。

1、如果我上第i层楼想走楼梯,那么:$f_{i,0} = min(f_{i-1,0}+a_{i-1}, f_{i-1, 1}+a_{i-1})$

2、如果我上第i-1层楼走的楼梯,并且第i层楼想走电梯的话,要花c的时间等电梯:$f_{i,1} = min(f_{i,1}, f_{i-1,0}+c+b_{i-1})$

3、如果我上第i-1层楼走的电梯,并且第i层楼想走电梯的话,不用再花时间等电梯了:$f_{i,1} = min(f_{i,1}, f_{i-1,1}+b_{i-1})$

显然到达第i层楼的最短时间是$min(f_{i,0}, f_{i,1})$

代码:O(n)

#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define N 200005
#define M 100005
#define INF 0x3f3f3f3f
#define mk(x) (1<<x) // be conscious if mask x exceeds int
#define sz(x) ((int)x.size())
#define upperdiv(a,b) (a/b + (a%b>0))
#define mp(a,b) make_pair(a, b)
#define endl '
'
#define lowbit(x) (x&-x)

using namespace std;
typedef long long ll;
typedef double db;

/** fast read **/
template <typename T>
inline void read(T &x) {
    x = 0; T fg = 1; char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') fg = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    x = fg * x;
}
template <typename T, typename... Args>
inline void read(T &x, Args &... args) { read(x), read(args...); }
template <typename T>
inline void write(T x) {
    int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;
    do{++len; c[len] = x%10 + '0';} while (x /= 10);
    for (int i = len; i >= 1; i--) putchar(c[i]);
}
template <typename T, typename... Args>
inline void write(T x, Args ... args) { write(x), write(args...); }

int a[N], b[N];
int f[N][2];// 0 stair 1 elevator
int main()
{
    int n, c; read(n, c);
    for (int i = 1; i < n; i++)
        read(a[i]);
    for (int i = 1; i < n; i++)
        read(b[i]);
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    f[1][1] = c;
    for (int i = 2; i <= n; i++) {
        f[i][0] = min(f[i][0], f[i-1][0] + a[i-1]);
        f[i][0] = min(f[i][0], f[i-1][1] + a[i-1]);
        f[i][1] = min(f[i][1], f[i-1][0] + c + b[i-1]);
        f[i][1] = min(f[i][1], f[i-1][1] + b[i-1]);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d%c", min(f[i][0], f[i][1]), " 
"[i==n]);
    }
    return 0;
}
View Code

 

原文地址:https://www.cnblogs.com/Lubixiaosi-Zhaocao/p/11725120.html