Codeforces Round #823 (Div. 2) A-D

比赛链接

A

题解

知识点:贪心。

对于一个轨道,要么一次性清理,要么一个一个清理。显然,如果行星个数大于直接清理的花费,那么选择直接清理,否则一个一个清理。即 (sum min (c,cnt[i])),其中 (cnt[i]) 表示轨道 (i) 的行星个数。

时间复杂度 (O(n))

空间复杂度 (O(1))

代码

#include 
#define ll long long

using namespace std;

int cnt[107];

bool solve() {
    int n, c;
    cin >> n >> c;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1;i > x;
        cnt[x]++;
    }
    int ans = 0;
    for (int i = 1;i > t;
    while (t--) {
        if (!solve()) cout 

B

题解

方法一

知识点:三分。

按位置从小到大排列,显然约会花费是一个关于 (x_0) 的单谷函数,因此可以三分位置。

由于位置最大有 (10^8) ,但点的个数只有 (10^5) ,考虑先用 map 存储有序对 ((x,t)) ,其中 (t) 是位置 (x) 的人最大打扮时间,因为比这个时间少的一定不影响结果。遍历结束以后把 map 内容移到 vector 中用 pair 存储用以三分,check 函数则只要遍历一遍 vector 即可。

时间复杂度 (O(n log max(eps)))

空间复杂度 (O(n))

方法二

知识点:贪心。

(t) 等效进位置,如果 (x_i)(x_0) 左侧,则等效位置是 (xi - t) ;如果 (x_i)(x_0) 右侧,则等效位置是 (x_i + t)

所有点的左侧等效位置最左的位置,就是等效区间左端点;所有点的右侧等效位置最右的位置就是等效区间的右端点。

如果等效区间的左右端点来自于不同两点的等效点,那么等效区间的中点一定在这两点之间,否则原来的点必有一个能覆盖另一个点,等效区间的左右端点就属于同一个点的等效点。

时间复杂度 (O(n))

空间复杂度 (O(n))

代码

方法一

#include 
#define ll long long

using namespace std;

int x[100007];
map mp;
vector> v;

double check(double mid) {
    double mx = 0;
    for (auto [i, j] : v) {
        mx = max(mx, abs(i - mid) + j);
    }
    return mx;
}

bool solve() {
    mp.clear();
    v.clear();
    int n;
    cin >> n;
    for (int i = 1;i > x[i];
        mp[x[i]] = 0;
    }
    for (int i = 1;i > T;
        mp[x[i]] = max(mp[x[i]], T);
    }
    for (auto [i, j] : mp) {
        v.push_back({ i,j });
    }

    double l = 0, r = v.back().first;
    while (abs(r - l) >= 1e-7) {
        double mid1 = l + (r - l) / 3;
        double mid2 = r - (r - l) / 3;
        if (check(mid1) > t;
    while (t--) {
        if (!solve()) cout 

方法二

#include 
#define ll long long

using namespace std;

int x[100007], T[100007];

bool solve() {
    int n;
    cin >> n;
    int l = 1e9, r = 0;
    for (int i = 1;i > x[i];
    for (int i = 1;i > T[i];
    for (int i = 1;i > t;
    while (t--) {
        if (!solve()) cout 

C

题解

知识点:贪心。

因为要字典序最小,那么一个数字他后面没有更小的数字则可以保留,其他都应该删除,所以从右往左找一个合法的保留序列,其他的数字加一,并且都是位置随意的,于是可以插入到保留下来的序列,并使插入后的序列是从小到大字典序最小的排列。因此直接把保留序列外的数字加一以后,对整个序列排序即可。

也可以直接桶排序。

时间复杂度 (O(n log n))

空间复杂度 (O(n))

代码

#include 
#define ll long long

using namespace std;

bool solve() {
    string s;
    cin >> s;
    int mi = 10;
    for (int i = s.size() - 1;i >= 0;i--) {
        if (s[i] - '0' > t;
    while (t--) {
        if (!solve()) cout 

D

题解

知识点:构造。

注意到操作不会改变无序对 ((a_i, b_{ n - i + 1 })) 数量以及种类。

引理:(a = b) ,当且仅当无序对是回文的

充分性:

(a = b) 时,如果 (i) 处存在一组无序对 ((x, y)) ,则必然会在 (n-i+1) 产生相同一组无序对 ((y, x)) ,除非当 (n) 为奇数时,可以在中间产生一个元素相同的无序对 ((x,x)) ,因此 (a = b) 时,无序对必然成回文状。

必要性:

当无序对是回文的,则第 (i) 组无序对 ((x,y)) 可以对应第 (n-i+1) 组无序对 ((y,x)) ,即 (a_i = b_i) ,所以 (a = b)

充要条件:YES 当且仅当无序对 ((a_i, b_{ n - i + 1 })) 中元素不同的无序对有偶数个,元素相同的无序对仅在 (n) 为奇数时至多 (1) 种有奇数个。

充分性:

根据引理,显然满足右边条件。

必要性:

显然没有任何限制时,给出的无序对条件能排列成回文的,现在尝试证明其必然可构造无序对回文。

注意到操作 (k = i) 可以使得 (a[1 cdots k])(b[kcdots n]) 交换位置,即 ((a[k], b[n - k + 1])) 这一组无序对被置换到了 (1) 号位置,同时 ((a[1],b[n])) 这一组无序对被置换到了 (i) 号位置,但这不会改变 (a[k+1 cdots n])(b[1cdots k-1]) 的顺序,即第 (k+1)(n) 组无序对及其实际元素顺序没有改变。因此,如果我们想要将无序对通过操作变成一个我们想要的顺序,可以从右往左构造。

假设 (i+1)(n) 的无序对都安排好了,现在 (i) 号位置想要 (j (jleq i)) 号位置的无序对时,可以先 (k=j) ,将 (j) 号替换到 (1) 号,然后 (k=i) ,将 (1) 号替换 (i) 号,过程中 (i+1 cdots n) 的无序对不会改变,包括实际元素顺序。

上述操作最后结果是无序对 (j) 替换到 (i) ,且 (j) 号无序对元素的实际顺序不会改变。但如果我们希望实际元素的顺序也发生改变,我们可以加一个步骤 (k = 1) 在中间,即通过 (k = j, k = 1, k = i) 替换 (i) 号后的 (j) 号元素实际顺序与原来是相反的,这也是为什么我们只需要知道无序对顺序即可,因为元素实际顺序是可以随时改变的。

通过上述操作我们可以实现无序对的任意排列,以及无序对实际元素的顺序。因此无序对满足回文条件时,必然可以构造出无序对回文。于是根据引理,得到 (a = b)

时间复杂度 (O(n))

空间复杂度 (O(n))

代码

#include 
#define ll long long

using namespace std;

string a, b;
int cnt[26][26];

bool solve() {
    memset(cnt, 0, sizeof(cnt));
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    for (int i = 0;i  y) swap(x, y);
        cnt[x][y]++;
    }

    bool ok = true;
    int esum = 0;
    for (int i = 0;i > t;
    while (t--) {
        if (!solve()) cout 

文章来源于互联网:Codeforces Round #823 (Div. 2) A-D

THE END
分享
二维码