ARC075

在省选前一天听说正式选手线画到省二，有了别的女选手，慌的一批，然后刷了一个ARC来稍微找回一点代码感觉

最后还是挂分了，不开心

果然水平退化老年加重啊

原题链接

C - Bugged

直接做一个dp，找最大值时不找整十的位置即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9') {

        res = res * 10 +c - '0';

        c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

        out(x / 10);

    }

    putchar('0' + x % 10);

}

int N;

int s[105];

int dp[100005];

void Solve() {

    read(N);

    dp[0] = 1;

    for(int i = 1 ; i <= N ; ++i) {

        read(s[i]);

        for(int j = 100000 ; j >= 1 ; --j) {

            if(j >= s[i]) dp[j] = dp[j] | dp[j - s[i]];

        }

    }

    for(int j = 100000 ; j >= 0 ; --j) {

        if(j && j % 10 == 0) continue;

        if(dp[j]) {out(j);enter;return;}

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

D - Widespread

二分操作次数，相当于每个数集体减去\(mid * B\)，然后分配\(mid\)个\(A - B\)给还未减到0的数

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9') {

        res = res * 10 +c - '0';

        c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

        out(x / 10);

    }

    putchar('0' + x % 10);

}

int N;

int64 B,A;

int64 h[MAXN];

void Solve() {

    read(N);read(A);read(B);

    for(int i = 1 ; i <= N ; ++i) {

        read(h[i]);

    }

    sort(h + 1,h + N + 1);

    int64 L = 0,R = 1000000000;

    while(L < R) {

        int64 mid = (L + R) >> 1;

        int64 rem = 0;

        for(int i = 1 ; i <= N ; ++i) {

            if(h[i] - mid * B > 0) rem += (h[i] - mid * B - 1) / (A - B) + 1;

        }

        if(rem <= mid) R = mid;

        else L = mid + 1;

    }

    out(L);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

E - Meaningful Mean

每个数都减去K，合法区间即为和大于0的区间

记成前缀和转化成二维偏序的问题

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 200005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9') {

        res = res * 10 +c - '0';

        c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

        out(x / 10);

    }

    putchar('0' + x % 10);

}

int N,K,tr[MAXN];

int64 a[MAXN],sum[MAXN],val[MAXN];

int lowbit(int x) {return x & (-x);}

void Insert(int x,int v) {

    while(x <= N + 1) {

        tr[x] += v;

        x += lowbit(x);

    }

}

int Query(int x) {

    int res = 0;

    while(x > 0) {

        res += tr[x];

        x -= lowbit(x);

    }

    return res;

}

void Solve() {

    read(N);read(K);

    for(int i = 1 ; i <= N ; ++i) {

        read(a[i]);

        sum[i] = sum[i - 1] + a[i] - K;

        val[i] = sum[i];

    }

    val[N + 1] = 0;

    sort(val + 1,val + N + 2);

    int t = lower_bound(val + 1,val + N + 2,sum[0]) - val;

    Insert(t,1);

    int64 res = 0;

    for(int i = 1 ; i <= N ; ++i) {

        t = lower_bound(val + 1,val + N + 2,sum[i]) - val;

        res += Query(t);

        Insert(t,1);

    }

    out(res);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}

F - Mirrored

如果长度固定为L，每个数位上的数是\(b_{i}\)那么相当于

\(rev(N) - N = \sum_{i = 0}^{L - 1} (10^{L - i - 1} - 10^{i})b_{i}\)

然后对称的位置可以合并一下

\(rev(N) - N = \sum_{i = 0}^{L / 2}(10^{L - i - 1} - 10^{i})(b_{i} - b_{L - i - 1})\)

然后我们就相当于对于\(0-\lfloor \frac{L}{2}\rfloor\)中的每一个\(10^{L - i - 1} - 10^{i}\)乘上一个\(-9\)到\(9\)，组合出来的值是D，然后乘上这种方案的搭配数

然后发现对于一个

\(10^{L - i - 1} - 10^{i} > \sum_{j = i + 1}^{L / 2} (10^{L - j - 1} - 10^{j}) * 9\)

就是当前第i位决定完了，但和D差了大于\(10^{L - i - 1} - 10^{i}\)的时候，我们是无论如何也恢复不了的

所以当D确定时，合法的填法最多只有两个

对于固定的长度\(L\),最大是\(2L_{D}\)也就是D的十进制长度的二倍，最小是\(L_{D}\)

是二倍的原因是D是正数，我们如果要操作D必然要有在D大小以内的数加减，然后超过\(2L_{D}\)能加减的最小的数也超过了D，我们无法得到一个D

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 200005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

        if(c == '-') f = -1;

        c = getchar();

    }

    while(c >= '0' && c <= '9') {

        res = res * 10 +c - '0';

        c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

        out(x / 10);

    }

    putchar('0' + x % 10);

}

int64 D;

int Len(int64 D) {

    int res = 0;

    while(D) {

        res++;

        D /= 10;

    }

    return res;

}

int64 pw[20];

int64 v[20],d[20];

int up;

int64 dfs(int64 rem,int dep) {

    if(dep == up) return !rem;

    int64 t = rem / v[dep];

    int64 res = 0;

    if(abs(t - 1) <= 9 && abs(rem - (t - 1) * v[dep]) < v[dep]) {

        int c = 0;

        if(t - 1 >= 0 && !dep) c = 1;

        res += (d[t - 1 + 9] - c) * dfs(rem - (t - 1) * v[dep],dep + 1);

    }

    if(abs(t) <= 9 && abs(rem - t * v[dep]) < v[dep]) {

        int c = 0;

        if(t >= 0 && !dep) c = 1;

        res += (d[t + 9] - c) * dfs(rem - t * v[dep],dep + 1);

    }

    if(abs(t + 1) <= 9 && abs(rem - (t + 1) * v[dep]) < v[dep]) {

        int c = 0;

        if(t + 1 >= 0 && !dep) c = 1;

        res += (d[t + 1 + 9] - c) * dfs(rem - (t + 1) * v[dep],dep + 1);

    }

    return res;

}

void Solve() {

    read(D);

    int Ld = Len(D);

    int64 ans = 0;

    pw[0] = 1;

    for(int i = 1 ; i <= 18 ; ++i) pw[i] = pw[i - 1] * 10;

    for(int i = 0 ; i <= 9 ; ++i) {

        for(int j = 0 ; j <= 9 ; ++j) {

            d[i - j + 9]++;

        }

    }

    for(int i = Ld ; i <= 2 * Ld ; ++i) {

        for(int j = 0 ; j <= i / 2 ; ++j) v[j] = pw[i - j - 1] - pw[j];

        up = i / 2;

        int64 tmp = dfs(D,0);

        if(i & 1) tmp *= d[0 + 9];

        ans += tmp;

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

    return 0;

}