Codeforces Round #587 (Div. 3)

Codeforces 1216


Codeforces 1216
第一次把div3给做完了,虽然赛场上没做完。
ABCD签到

E

E1不难想,1e9可以用数组保存下来,两次二分。
E2赛后看别人写得。
1e18就不能使用数组了,我们同样也二分,这个关键在于计算个数,推一下就可以。感觉标程写的挺漂亮的。
我的代码


#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
const int M = 3e4 + 5;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
#define lowbit( x )  (x&(-x))
typedef pair < int, int > P;
int n, q;
ll k;

int Count(int x) {
    int cnt = 0;
    while (x) cnt++, x /= 10;
    return cnt;
}

ll cal(int x) {
    int num = Count(x);
    ll st = 0;
    for (int i = 1; i < num; i++) st = st * 10 + 9;
    ll res = 1LL * num * (x - st) * (x - st + 1) / 2;
    for (int d = num - 1; d > 0; d--) {
        ll cnt = 9;
        for (int i = 1; i < d; i++) cnt *= 10;
        res += 1LL * d * cnt * (cnt + 1) / 2;
        ll ct = 0;
        for (int i = 1; i <= d; i++) ct = ct * 10 + 9;
        res += 1LL * d * cnt * (x - ct);
    }
    return res;
}

int ac(ll x, int cnt) {
    int d[20], tot = 0;
    while (x) {
        d[++tot] = x % 10;
        x /= 10;
    }
    return d[tot - cnt + 1];
}

int main() {
    scanf("%d", &q);
    while (q--) {
        scanf("%lld", &k);
        int l = 1, r = 1e9;
        while (l < r) {
            int mid = (1LL * l + r) >> 1;
            if (cal(mid) >= k) r = mid;
            else l = mid + 1;
        }
        k -= cal(l - 1);
        for (int d = 1;; d++) {
            ll cnt = 9;
            for (int i = 1; i < d; i++) cnt *= 10;
            if (k > cnt * d) {
                k -= cnt * d;
            }
            else {
                cnt = 0;
                for (int i = 1; i < d; i++) cnt = cnt * 10 + 9;
                cnt = cnt + (k + d - 1) / d;
                k = (k - 1) % d + 1;
                printf("%d\n", ac(cnt, k));
                break;
            }

        }
    }
    return 0;
}

F

当时感觉是$dp$,也没搞出来

$dp[i][k]$表示前$i$个接在一起的最小花费,$k=0$代表不使用$i$点,$k=1$代表使用。
显然有这样的递推式
$$dp[i][0] = min(dp[j][1]),i-k<=j<=i-1,s[j]=1)$$
接下来考虑$dp[i][1]$

  • 如果$s[i]=1$,那么可以从$dp[j]$转移过来,其中$max(i-k+1,1)<=j<=i-1$(因为当前$s[i]$为$1$了,此时当前$i$已经盖住$k$个了。所以$i$前面的$k+1$个都可以转移),我们使用其中最小的。
  • 如果$s[i] != 1$,那么当前$dp[i][1]$起码可以从$dp[i-1]$转移过来,也可以从$dp[j][1]$转移过来,其中$max(i-k+1,1)<=j<=i-1,s[j]=1$(这里也是$i-k+1$,因为当前$i$已经使用了,自己就不需要被前面盖住了),因此我们也需要知道这些中的最小值

因此可以用线段树来优化,为了保证有些查询必须满足$s[j]=1$,因此再来一个线段树保存。

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int M = 3e4 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 1000000000000000000;
const int mod = 1e9 + 7;
#define lowbit( x )  (x&(-x))
#define ls rt<<1
#define rs rt<<1|1
typedef pair < int, int > P;
ll MN1[N << 2], MN2[N << 2];
int n, k;
char s[N];
ll f[N][2];
 
void build(ll MN[], int rt, int l, int r) {
    if (l == r) {
        MN[rt] = INF;
        return;
    }
    int mid = (l + r) >> 1;
    build(MN, ls, l, mid);
    build(MN, rs, mid + 1, r);
    MN[rt] = min(MN[ls], MN[rs]);
}
 
void update(ll MN[], int rt, int l, int r, int p, ll v) {
    if (l == r) {
        MN[rt] = v;
        return;
    }
    int mid = (l + r) >> 1;
    if (p <= mid) update(MN, ls, l, mid, p, v);
    else update(MN, rs, mid + 1, r, p, v);
    MN[rt] = min(MN[ls], MN[rs]);
}
 
ll query(ll MN[], int rt, int l, int r, int x, int y) {
    if (x <= l && r <= y) return MN[rt];
    int mid = (l + r) >> 1;
    ll ans = INF;
    if (x <= mid) ans = query(MN, ls, l, mid, x, y);
    if (y > mid) ans = min(ans, query(MN, rs, mid + 1, r, x, y));
    return ans;
}
 
int main()
{
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1);
    build(MN1, 1, 0, n);
    build(MN2, 1, 0, n);
    f[0][0] = 0;
    f[0][1] = 0;
    update(MN2, 1, 0, n, 0, 0);
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = query(MN1, 1, 0, n, max(i - k, 0), i - 1);
        if (s[i] == '1') f[i][1] = query(MN2, 1, 0, n, max(i - k - 1, 0), i - 1) + i;
        else {
            f[i][1] = query(MN1, 1, 0, n, max(i - k - 1, 0), i - 1) + i ;
            f[i][1] = min(f[i][1], min(f[i - 1][1], f[i - 1][0]) + i);
        }
        if (s[i] == '1') update(MN1,1, 0, n, i, f[i][1]);
        update(MN2, 1, 0, n, i, min(f[i][1], f[i][0]));
    }
    cout << min(f[n][0], f[n][1]) << endl;
    return 0;
}

网上好像有线性做法。

Last modification:September 22nd, 2019 at 10:35 pm
如果觉得我的文章对你有用,请随意赞赏

One comment

  1. 云中君 Google Chrome 61.0.3163.100 Windows 10

    OωO嗯嗯,说的有道理

Leave a Comment