Codeforces Round 870 (A-D)

huaiii / 2023-05-06 / 原文

A

\(n^2\)暴力推，遍历可能撒谎的人数(0-n)，然后\(O(n)\)check就行了。
仔细看逻辑其实\(O(1)\)就能check，草率了，后面再修正

点击查看代码

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define per(i, r, l) for(int i = r; i >= l; i--)
#define debug(tar, l, r) rep(ii, l, r) cout << tar[ii] << " \n"[ii==r]

using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+5;
const int mod = 1e9+7;

int n, a[N];

bool chk(int x){
    rep(i, 1, n-x){
        if(a[i] > x) return false;
    }
    rep(i, n-x+1, n){
        if(a[i] <= x) return false;
    }
    return true;
}

void solve(){
    cin >> n;
    rep(i, 1, n) cin >> a[i];
    sort(a+1, a+1+n);
    rep(i, 0, n){
        if(chk(i)){
            cout << i << "\n";
            return ;
        }
    }
    cout << "-1\n";
}
int main(){
    std::ios::sync_with_stdio(false);
    int tt; cin >> tt; while(tt--)
        solve();
    return 0^0;
}

B

回文对应的两个数的差值一定是\(x\)的倍数，把所有情况取个gcd即可

点击查看代码

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define per(i, r, l) for(int i = r; i >= l; i--)
#define debug(tar, l, r) rep(ii, l, r) cout << tar[ii] << " \n"[ii==r]

using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+5;
const int mod = 1e9+7;

int n, b[N];

void solve(){
    cin>> n;
    rep(i, 1, n) cin >> b[i];
    int ans = 0;
    rep(i, 1, n/2){
        int dif = abs(b[i]-b[n-i+1]);   
        ans = __gcd(ans, dif);
    }
    cout << ans << "\n";
}   
int main(){
    std::ios::sync_with_stdio(false);
    int tt; cin >> tt; while(tt--)
        solve();
    return 0^0;
}

C

n除1外的最小的因子小于等于m即可

点击查看代码

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define per(i, r, l) for(int i = r; i >= l; i--)
#define debug(tar, l, r) rep(ii, l, r) cout << tar[ii] << " \n"[ii==r]

using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e6+5;
const int mod = 1e9+7;

int n, m;
bool no[N];
vector <int> p;
void init(){
    rep(i, 2, 1000000){
        if(!no[i]) p.push_back(i);
        for(auto& pp:p){
            if(pp*i > 1000000) break;
            no[pp*i] = 1;
        }
    }
}

void solve(){
    cin >> n >> m;
    if(n > 1 && n <= m){
        cout << "NO\n";
        return ;
    }
    for(auto& pp:p){
        if(pp*pp > n) break;
        if(n%pp == 0){
            if(pp <= m){
                cout << "NO\n";
                return ;
            }
        }
    }
    cout << "YES\n";
}
int main(){
    std::ios::sync_with_stdio(false);
    init();
    int tt; cin >> tt; while(tt--)
        solve();
    return 0^0;
}

D

做法是尺取，不知道会不会假了
将\(b_{i1}+b_{i2}+b_{i3}-(r-l)\)转换成\((b_l+l)+(b_r-r)+b_i\)，其中\(l < i < r\)
对\(b_i+i\)求前缀最值，对\(b_i-i\)求后缀最值，中间\(b_i\)用st表，然后尺取

点击查看代码

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define per(i, r, l) for(int i = r; i >= l; i--)
#define debug(tar, l, r) rep(ii, l, r) cout << tar[ii] << " \n"[ii==r]

using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int N = 1e5+5;
const int mod = 1e9+7;

int n, b[N], p[N], s[N], f[N][30];
void pre(){
    rep(i, 1, n) f[i][0] = b[i];
    for (int k = 1; (1 << k) <= n; ++k)
        for (int i = 1; i + (1 << k) - 1 <= n; ++i)
            f[i][k] = max(f[i][k - 1], f[i + (1 << (k - 1))][k - 1]);
}
int ask(int l, int r){
    int k = log2(r - l + 1);
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}


void solve(){
    cin >> n;
    rep(i, 1, n) cin >> b[i];
    pre();
    p[0] = s[n+1] = -1e9;
    rep(i, 1, n) p[i] = max(p[i-1], b[i]+i);
    per(i, n, 1) s[i] = max(s[i+1], b[i]-i);
    int l = 1;
    int ans = 0;
    for(int i = 3; i <= n; i++){
        while(l+1 <= i-2 && p[l+1]+ask(l+2, i-1) >= p[l]+ask(l+1, i-1)) l++;
        ans = max(ans, p[l]+ask(l+1, i-1)+s[i]);
    }
    cout << ans << "\n";
}
int main(){
    std::ios::sync_with_stdio(false);
    int tt; cin >> tt; while(tt--)
        solve();
    return 0^0;
}