CF Div.2 1805 补题

· 2023-04-03 · # 补题 # 模拟 # 贪心 # Codeforces # 二分

A

看题，发现 $0 \le x < 2^8$ 而且 $1 \le n \le 10^3$ ，直接枚举 $x$ 判断是否满足条件即可。
时间复杂度： $\mathrm O(\omega \cdot n)$ 其中 $\omega = 511$
AC代码

#include <bits/stdc++.h>
using namespace std;

#define debug(args...) fprintf(stderr, ##args)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mk make_pair
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repll(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (b); i >= (a); --i)
#define perll(i, a, b) for (ll i = (b); i >= (a); --i)
#define maxv(a, b) (a = a > b ? a : b)
#define minv(a, b) (a = a < b ? a : b)

using ll = long long;
using db = double;

const int N = 1e3 + 7;

int t, n, a[N], b[N];

void solve() {
    scanf("%d", &n);
    rep (i, 1, n) scanf("%d", &a[i]);
    rep (i, 0, 511) {
        rep (j, 1, n) b[j] = a[j] ^ i;
        int sum = 0;
        rep (j, 1, n) sum ^= b[j];
        if (sum == 0) return printf("%d\n", i), void();
    }
    return puts("-1"), void();
}

int main() {
    scanf("%d", &t);
    rep (_, 1, t) solve();
    
    return 0;
}

B

容易发现移动字典序大于字符 $s_1$ 的 $s_i$ 无意义。
考虑对于 $s$ 中字典序最小的字符 $s_x$ 发现将其按照题目所述操作移至字符串开头即得答案。

证明
若移动 $s_x$ 得到 $s' = \{s_x, s_1, ..., s_{x - 1}, s_{x + 1}, ..., s_n\}$ 并非最优，则一定存在一个字符 $s_y$ 使其为最优 $s'' = \{s_y, s_1, ..., s_{y - 1}, s_{y + 1}, ..., s_n\}$ 。而按照定义 $s_x$ 为最小字符，则 $s''$ 的字典序小于 $s'$ ，即 $s'$ 更优。证毕。
AC代码

#include <bits/stdc++.h>
using namespace std;

#define debug(args...) fprintf(stderr, ##args)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mk make_pair
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repll(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (b); i >= (a); --i)
#define perll(i, a, b) for (ll i = (b); i >= (a); --i)
#define maxv(a, b) (a = a > b ? a : b)
#define minv(a, b) (a = a < b ? a : b)

using ll = long long;
using db = double;

const int N = 1e5 + 7;

string s;
int t, n, cnt[30];
void solve() {
    memset(cnt, 0, sizeof cnt);
    cin >> n;
    cin >> s;
    for (auto x : s) ++cnt[x - 'a'];
    char ch = s[0];
    per (i, 0, 25) 
        if (cnt[i]) ch = (char)(i + 'a');
    int pos = 0;
    rep (i, 0, n - 1) if (s[i] == ch) pos = i;
    putchar(s[pos]);
    rep (i, 0, n - 1) if (i == pos) continue; else putchar(s[i]);
    putchar('\n');
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    rep (_, 1, t) solve();
    
    return 0;
}

C

一眼二分，但是调不过。
看了官方题解，发现可以用 lower_bound（我：！@#￥%……&* 怎么就把这玩意忘了呢）
官方题解思路：由一元二次方程判别式 $\Delta = y^2 - 4xz$ （其中 $x, y, z$ 分别为一元二次方程的二次项，一次项，常数项系数）可知，当直线与二次函数无交点时，即为方程 $ax^2 + bx + c = kx$ 无实根。
化简得：

ax^x + (b - k)x + c = 0

因为无实根，所以 $\Delta = (b - k)^2 - 4ac < 0$ 即： $(b - k)^2 < 4ac$
进一步化简得：

b-\sqrt {4ac} < k < b + \sqrt {4ac}

所以，在直线系数中二分查找最大的小于 $b$ 的系数 $A$ 和最小的大于 $b$ 的系数 $B$ ，分别检查 $A、B$ 是否符合要求即可。（可我就是不会二分 o(╥﹏╥)o）
AC代码

#include <bits/stdc++.h>
using namespace std;

#define debug(args...) fprintf(stderr, ##args)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mk make_pair
#define pb push_back
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define repll(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (b); i >= (a); --i)
#define perll(i, a, b) for (ll i = (b); i >= (a); --i)
#define maxv(a, b) (a = a > b ? a : b)
#define minv(a, b) (a = a < b ? a : b)

using ll = long long;
using db = double;

const int N = 3e5 + 7;

int t, n, m, x;

void solve() {
    scanf("%d %d", &n, &m);
    set<ll> s;
    rep (i, 1, n) scanf("%d", &x), s.insert(x);
    rep (i, 1, m) {
        ll a, b, c;
        scanf("%lld %lld %lld", &a, &b, &c);
        ll x = 4 * a * c;
        auto it = s.lower_bound(b);
        ll k = *it;
        if (it == s.end()) {
            k = *--it;
            if ((b - k) * (b - k) < x) printf("YES\n%lld\n", k); else puts("NO");
            continue;
        }
        if ((b - k) * (b - k) < x) { printf("YES\n%lld\n", k); continue; }
        if (it == s.begin()) { puts("NO"); continue; }
        k = *--it;
        if ((b - k) * (b - k) < x) { printf("YES\n%lld\n", k); continue; }
        puts("NO");
    }
}

int main() {
    scanf("%d", &t);
    rep (_, 1, t) solve(), putchar('\n');
    
    return 0;
}

~~DEF以后再补~~（upd: 2023.7.30 不会再补了）