Codeforces Round #769 (Div. 2) ABCD题解

作者： 作者的头像   Time_Limit_Exceeded ,  2022-01-31 14:50:18 ,  所有人可见 ,  阅读 277

4


Codeforces Round #769 (Div. 2)

A. ABC

题意：给定长度为n的01串，可以对这个串重新任意排列，问是否存在一种排列，使得该串的任意一个长度大于1的子串都不为回文串。

解法：容易得到，如果有大于1个1或者大于1个0都是NO

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

inline void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int c1 = 0, c2 = 0;
    for (int i = 0; i < n; i ++ ) {
        if (s[i] == '0') c1 ++;
        else c2 ++;
    }
    if (c1 > 1 || c2 > 1) cout << "NO\n";
    else cout << "YES\n";
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

B. Roof Construction

题意：给定一个n，表示有一个长度为n的数组p，元素是 $0,1,2,…,n - 1$，要求对这个数组重新排列，使得 $max_{1 \le i \lt n} p_i \,xor\,p_{i + 1}$ 最小，输出排列后的数组。

解法：构造

首先我们可以打表找规律，得到 $max_{1 \le i \lt n} p_i \,xor\,p_{i + 1}$ 值为小于n的最大2的幂，然后我们可以这么构造

首先要得出答案，设为k，我们先提出0，k

然后把剩下的数分成两组，一组为 $[1, k - 1]$ 另外一组为 $[k + 1, n - 1]$。

第一组的任意排列，其相邻的xor值都不会大于k，第二组也是，因为最高位1被消掉了。

那么就是边界问题了，主要是第二组，一定会有一个数字是和别的数字接触的，那么我们用k去接触，把它的最高位消掉即可。

那么就可以排列出 $n - 1, n - 2, …, k, 0, 1, 2, …, k - 1$ 

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

inline void solve() {
    int n; cin >> n;
    int k = 1;
    while (k < n) k <<= 1;
    k >>= 1;
    for (int i = n - 1; i >= k; i -- ) cout << i << ' ';
    cout << 0 << ' ';
    for (int i = 1; i < k; i ++ ) cout << i << ' ';
    cout << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

C. Strange Test

题意：给两个数a,b，有以下三种操作，每个操作都可以做任意次，问最少几次操作可以使a和b相等

1、a = a + 1

2、b = b + 1

3、a = a | b

解法：暴力枚举

首先容易看出，最后使得a和b相等的操作，要不就是第一种，要不就是第三种

如果是第一种的话，答案就是b - a

如果是第三种的话，那么最后一步之前一定存在a | b = b

注意到 It is guaranteed that the sum of b over all test cases does not exceed $10^6$. 直接暴力枚举即可

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

inline void solve() {
    int a, b; cin >> a >> b;
    int res = b - a;
    for (int i = a; i <= b; i ++ ) {
        if ((i | b) == b) {
            res = min(res, i - a + 1);
            break;
        }
    }
    for (int i = b; i; i ++ ) {
        if ((i | a) == i) {
            res = min(res, i - b + 1);
            break;
        }
    }
    cout << res << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

D. New Year Concert

题意：给定一个长度为n的数组a，我们定义一个数组是bad，当且仅当存在这么一对 $[l, r]$ 使得 $gcd(a_l, a_{l + 1}, …, a_r) = r - l + 1$。

我们可以通过改变数组中的数来避免这一现象。

定义 $f(a)$ 为对于长度为k的数组中，至少要改变多少的数使得不存在bad数组。

对于一个长度为n的数组a，求出 $f(a_1), f(a_1, a_2), …, f(a_1, a_2, .. ,a_n)$

解法：线段树，二分

对于一段连续的数来说，gcd是单调递减的，数组长度是单调递增的。

所以最多只存在n个bad数组。

所以我们对于每个左边界 $l$，最多能找到一个 $r$ 满足bad数组的定义。

以上方法可以通过二分查找出。

那么查到以后，我们的想法是直接修改成一个大质数即可，由于原数组值域只有1e9，我们修改为1e9 + 7

由此可知，我们需要用到单点修改，区间gcd查询，二分，用线段树即可实现

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 2e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

struct node {
    int l, r;
    int val;
} tr[N << 2];
int a[N];

node operator + (node A, node B) {
    node res = {A.l, B.r, __gcd(A.val, B.val)};
    return res;
}

void push_up(int u) {tr[u] = tr[ls] + tr[rs];}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        tr[u].val = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    push_up(u);
}

void update(int p, int u, int val) {
    if (tr[u].l == tr[u].r) {
        tr[u].val = val;
        return ;
    }
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (p <= mid) update(p, ls, val);
    if (p > mid) update(p, rs, val);
    push_up(u);
}

int query(int st, int ed, int u) {
    if (st <= tr[u].l && tr[u].r <= ed) return tr[u].val;
    int mid = (tr[u].l + tr[u].r) >> 1;
    int res = 0;
    if (st <= mid) res = __gcd(res, query(st, ed, ls));
    if (ed > mid) res = __gcd(res, query(st, ed, rs));
    return res;
}

inline void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    build(1, 1, n);
    vector<int> f(n + 1);
    auto check = [&](int l, int r) {
        int len = r - l + 1;
        int val = query(l, r, 1);
        return val >= len;
    };

    for (int i = 1; i <= n; i ++ ) {
        int l = i, r = n;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(i, mid)) l = mid;
            else r = mid - 1;
        }
        int val = query(i, l, 1);
        if (val == r - i + 1) {
            f[l] ++;
            update(l, 1, MOD);
        }
    }
    for (int i = 1; i <= n; i ++ ) f[i] += f[i - 1];
    for (int i = 1; i <= n; i ++ ) cout << f[i] << ' ';
    cout << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
//    int T; cin >> T;
//    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

E. Distance Tree

待补

4 评论

用户头像
wudima6   2022-02-01 08:25         踩      回复

orz

用户头像
arthur15   2022-01-31 21:21         踩      回复

It is guaranteed that the sum of b over all test cases does not exceed 1e6. 大佬，问下这句话不是说初始的b不超过1e6，没说+1之后不超过1e6吧

用户头像
Time_Limit_Exceeded   2022-01-31 23:13         踩      回复

但是就算b再怎么加，也不会多出加到多出一位二进制的1，也就是不会大于2b的。

用户头像
arthur15   2022-02-01 07:32    回复了 Time_Limit_Exceeded 的评论         踩      回复

明白了。感谢