比赛记录 【Codeforces Round #667 (Div. 3)】

He_Ren · 2020-09-05 10:29:06 · 个人记录

Codeforces Round #667 (Div. 3)

A. Yet Another Two Integers Problem

贪心地考虑，每次若 |a-b|\geq 10，就移动 10 步；若 |a-b| < 10，则可以在一步内走完。

于是答案为 \lceil\frac{|a-b|}{10}\rceil。

My Code

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

void solve(void)
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a > b) swap(a,b);
    printf("%d\n",(b-a + 10-1)/10);
}

int main(void)
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

B. Minimum Product

考虑最优的方案，一定是先将一个数减到无法再减为止，然后再尽可能地减小另一个数。于是分别先减 a 和先减 b 这两种方案的答案，取最小值即可。

My Code

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

ll gao(ll a,ll b,ll x,ll y,ll n)
{
    int tmp = min(n, a-x);
    a -= tmp; n -= tmp;

    tmp = min(n, b-y);
    b -= tmp; n -= tmp;

    return a * b;
}

void solve(void)
{
    ll a,b,x,y,n;
    scanf("%lld%lld%lld%lld%lld",&a,&b,&x,&y,&n);
    printf("%lld\n",min(gao(a,b,x,y,n), gao(b,a,y,x,n)));
}

int main(void)
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

C. Yet Another Array Restoration

注意到排序后的 a 序列是一个等差数列，所以可以枚举其公差 dif，要求 dif|(y-x)。

如果 (y-x)/dif + 1 > n，说明不能找到一个公差为 dif 的等差数列；否则贪心地取最多 x 之前的项，即可计算出首项。

所有答案取最小值即可。时间复杂度是 O(n+(y-x))，最快可以做到 O(n + \sqrt{y-x})。

实际上，枚举首项和公差，然后从序列中找到 x,y 也是一种可行的方法，其时间复杂度是 O(n^3)，可以通过本题，而且代码较为简单。

My Code

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf = 0x3f3f3f3f;

void solve(void)
{
    int n,x,y;
    scanf("%d%d%d",&n,&x,&y);

    int ans = inf, ansi = -1, ansd;

    for(int i=1; i<=y-x; ++i)
        if((y-x)%i == 0)
        {
            int dif = (y-x)/i;
            if(i+1 > n) continue;

            int len = min((x-1)/dif, n-(i+1));
            int fir = x - dif * len;

            int lst = fir + n * dif;
            if(lst < ans)
            {
                ans = lst;
                ansi = fir;
                ansd = dif;
            }
        }
    for(int i=1; i<=n; ++i)
        printf("%d ",ansi + (i-1) * ansd);
    putchar('\n');
}

int main(void)
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

D. Decrease the Sum of Digits

若 n 的数位和已经 \leq s，那么答案为 0。

考虑不断增加 n。注意到在将 n 的第一位加至进位前，n 的数位和都是不断增大的，只有在进位后，数位和才会减小。注意到其他所有位都同理。

于是可以枚举最后一个进位的位置，计算答案即可。

My Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 18 + 5;

inline int calc(char s[],int n)
{
    int res = 0;
    for(int i=1; i<=n; ++i)
        res += s[i] - '0';
    return res;
}

inline void add(char s[],int n,int i)
{
    while(i>=1 && s[i] == '9')
        s[i] = '0',
        --i;
    if(i>=1) ++s[i];
}

char s[MAXN];

void solve(void)
{
    int x;
    scanf("%s%d",s+1,&x);
    int n = strlen(s+1);

    if(calc(s,n) <= x){ printf("0\n"); return;}

    ll cost = 1, ans = 0;
    for(int i=n; i>=1; --i)
    {
        while(s[i] != '0')
            ans += cost,
            add(s,n,i);
        if(calc(s,n) <= x){ printf("%lld\n",ans); return;}
        cost *= 10;
    }
}

int main(void)
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

Code

tmwilliamlin168

使用递归求解让思路更加清晰。solve(n,s) 返回将数 n 的数位和 \leq s 的最小步数，有以下几种情况：

1. 数位和已经 \leq s 直接返回 0。

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

#define ll long long
#define ld long double
#define ar array

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

template<class T> bool umin(T& a, const T& b) {
    return b<a?a=b, 1:0;
}
template<class T> bool umax(T& a, const T& b) { 
    return a<b?a=b, 1:0;
} 

ll FIRSTTRUE(function<bool(ll)> f, ll lb, ll rb) {
    while(lb<rb) {
        ll mb=(lb+rb)/2;
        f(mb)?rb=mb:lb=mb+1; 
    } 
    return lb;
}
ll LASTTRUE(function<bool(ll)> f, ll lb, ll rb) {
    while(lb<rb) {
        ll mb=(lb+rb+1)/2;
        f(mb)?lb=mb:rb=mb-1; 
    } 
    return lb;
}

template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
    cin >> x;
}
void read(double& d) {
    string t;
    read(t);
    d=stod(t);
}
void read(long double& d) {
    string t;
    read(t);
    d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template<class A> void read(vt<A>& x) {
    EACH(a, x)
        read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
    EACH(a, x)
        read(a);
}

string to_string(char c) {
    return string(1, c);
}
string to_string(bool b) {
    return b?"true":"false";
}
string to_string(const char* s) {
    return string(s);
}
string to_string(string s) {
    return s;
}
string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))
        res+=char('0'+v[i]);
    return res;
}

template<size_t S> string to_string(bitset<S> b) {
    string res;
    FOR(S)
        res+=char('0'+b[i]);
    return res;
}
template<class T> string to_string(T v) {
    bool f=1;
    string res;
    EACH(x, v) {
        if(!f)
            res+=' ';
        f=0;
        res+=to_string(x);
    }
    return res;
}

template<class A> void write(A x) {
    cout << to_string(x);
}
template<class H, class... T> void write(const H& h, const T&... t) { 
    write(h);
    write(t...);
}
void print() {
    write("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) { 
    write(h);
    if(sizeof...(t))
        write(' ');
    print(t...);
}

void DBG() {
    cerr << "]" << endl;
}
template<class H, class... T> void DBG(H h, T... t) {
    cerr << to_string(h);
    if(sizeof...(t))
        cerr << ", ";
    DBG(t...);
}
#ifdef _DEBUG
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif

template<class T> void offset(ll o, T& x) {
    x+=o;
}
template<class T> void offset(ll o, vt<T>& x) {
    EACH(a, x)
        offset(o, a);
}
template<class T, size_t S> void offset(ll o, ar<T, S>& x) {
    EACH(a, x)
        offset(o, a);
}

mt19937 mt_rng(chrono::steady_clock::now().time_since_epoch().count());
ll randint(ll a, ll b) {
    return uniform_int_distribution<ll>(a, b)(mt_rng);
}

template<class T, class U> void vti(vt<T> &v, U x, size_t n) {
    v=vt<T>(n, x);
}
template<class T, class U> void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v=vt<T>(n);
    EACH(a, v)
        vti(a, x, m);
}

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

ll sd(ll n) {
    ll x=0;
    for(; n; n/=10)
        x+=n%10;
    return x;
}

ll solve(ll n, ll s) {
    if(sd(n)<=s)
        return 0;
    if(n%10==0)
        return solve(n/10, s)*10;
    return solve(n+10-n%10, s)+10-n%10;
}

void solve() {
    ll n, s;
    read(n, s);
    print(solve(n, s));
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t=1;
    read(t);
    FOR(t) {
        //write("Case #", i+1, ": ");
        solve();
    }
}

SSRS_

使用了数位 dp。

最小化步数即为最小化最后得到的数字。不妨设 a_i 为 n 的从高到低的第 i 位。dp[i][j][k] 表示，考虑从高到低的前 i 位，前 i 位的数位和为 j，而 k=0,1 表示第 i+1 位能不能填入 <a_{i+1} 的数字。

• 对于 k=0，转移的时候第 i+1 位只能填入 \geq a_{i+1} 的数字。填入一个 =a_{i+1} 的数字会转移到 k=0，而填入一个 >a_{i+1} 的数字将转移到 k=1。

• 对于 k=1，转移的时候第 i+1 位可以填入所有 0 到 9 的数字。

#include <bits/stdc++.h>
using namespace std;
const unsigned long long INF = 10000000000000000000;
int main(){
  int t;
  cin >> t;
  for (int i = 0; i < t; i++){
    long long n;
    int s;
    cin >> n >> s;
    string S = to_string(n);
    S = '0' + S;
    int L = S.size();
    vector<vector<vector<unsigned long long>>> dp(L + 1, vector<vector<unsigned long long>>(s + 2, vector<unsigned long long>(2, INF)));
    dp[0][0][0] = 0;
    for (int j = 0; j < L; j++){
      for (int k = 0; k <= s + 1; k++){
        if (dp[j][k][0] != INF){
          for (int d = S[j] - '0'; d <= 9; d++){
            int d2 = min(k + d, s + 1);
            if (d == S[j] - '0'){
              dp[j + 1][d2][0] = min(dp[j + 1][d2][0], dp[j][k][0] * 10 + d);
            } else {
              dp[j + 1][d2][1] = min(dp[j + 1][d2][1], dp[j][k][0] * 10 + d);
            }
          }
        }
        if (dp[j][k][1] != INF){
          for (int d = 0; d <= 9; d++){
            int d2 = min(k + d, s + 1);
            dp[j + 1][d2][1] = min(dp[j + 1][d2][1], dp[j][k][1] * 10 + d);
          }
        }
      }
    }
    unsigned long long ans = INF;
    for (int j = 0; j <= s; j++){
      ans = min(ans, dp[L][j][0]);
      ans = min(ans, dp[L][j][1]);
    }
    cout << ans - n << endl;
  }
}

AQT

同上一份代码一样，也是使用能得到的最小数减去 n 得到答案。这份代码没有使用 dp。其思路是，如果当前位及其更高位没有触碰到下边界，就直接在所有更低位填 0；反之，设 n 中这一位为 a_i，那么分最后填的数为 a_i+1 和 a_i 两种情况进行讨论即可。

很类似 dp 的思路，但是没有使用 dp 进行转移，而使用了贪心来优化复杂度。

// Problem : D. Decrease the Sum of Digits
// Contest : Codeforces - Codeforces Round #667 (Div. 3)
// URL : https://codeforces.ml/contest/1409/problem/D
// Memory Limit : 256 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>

using namespace std;

long long pows[20];

long long rec(long long lim, long long s, long long crnt, int n, bool border){
    if(n == -1){
        if(s >= 0){
            return crnt - lim;
        }
        else{
            return LLONG_MAX/2;
        }
    }
    if(border){
        int d = lim/pows[n]%10;
        long long ret = LLONG_MAX/2;
        if(s > d && d != 9){
            ret = min(ret, rec(lim, s-d-1, crnt + pows[n] * (d+1), n-1, 0));
        }
        ret = min(ret, rec(lim, s-d, crnt + pows[n] * d, n-1, 1));
        return ret;
    }
    else{
        /*
        if(s >= 9){
            return rec(lim, s-9, crnt + pows[n] * 9, n-1, 0);
        }
        else{
            return rec(lim, 0, crnt + pows[n] * s, n-1, 0);
        }
        */
        return rec(lim, s, crnt, n-1, 0);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    pows[0] = 1;
    for(int i = 1; i<=18; i++){
        pows[i] = pows[i-1] * 10;
    }
    while(T--){
        long long N, S;
        cin >> N >> S;
        if(N == 1000000000000000000LL){
            cout << 0 << "\n";
            continue;
        }
        cout << rec(N, S, 0, 18, 1) << "\n";
    }
}

E. Two Platforms

注意到减小板子的纵坐标，答案不会变得更劣。将板子放在 y=-\infty 的地方可以接住所有它横坐标范围内的点。于是点的纵坐标是不重要的，下面只考虑每个点的横坐标 x_i。

将所有点按 x_i 从小到大排序。可以使用二分计算出，如果以第 i 个点为板子的右端点，这块板子能接住的点数 rig_i，和，如果以第 i 个点为板子的左端点，这块板子能接住的点数 lef_i。并且设 rig_0 = lef_{n+1} = 0。

那么答案为 \max_{i=1}^{n+1}(lef_i + \min_{j=0}^{i-1}(rig_j))。

注意到 \min_{j=0}^{i-1}(rig_j) 是可以预处理的。

所以时间复杂度为 O(n\log n)。

My Code

实际上动态维护了 rig 的前缀最大值。

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e5 + 5;

int a[MAXN];

void solve(void)
{
    int n,d;
    scanf("%d%d",&n,&d);
    for(int i=1; i<=n; ++i) scanf("%d",&a[i]);
    for(int i=1,y; i<=n; ++i) scanf("%d",&y);

    sort(a+1,a+n+1);

    int ans = 0;

    int mx = 0;
    for(int i=1; i<=n; ++i)
    {
        int pos = upper_bound(a+i,a+n+1, a[i]+d) - a;
        ans = max(ans, mx + pos-i);

        pos = lower_bound(a+1,a+i, a[i]-d) - a;
        mx = max(mx, i - pos + 1);
    }
    printf("%d\n",ans);
}

int main(void)
{
    int T;
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}

F. Subsequences of Length Two

对于 t_1 = t_2 的情况，直接贪心地最大化 s 中 t_1 的数量，设这个数量为 cnt，那么答案为 \binom{cnt}{2}。

下面只考虑 t_1 \neq t_2 的情况。

考虑 dp。