AtCoder ABC194

这期比193稍微简单一点

C - Squared Error

手玩一下：
$N=3$时
展开得
$a^2+b^2?2ab+b^2?c^2?2bc+a^2+c^2?2ac$
每个数平方项都要计算$n?1$次
减的那一份可以按枚举一个数来算，发现剩下的项是前缀和

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @file     : atcoder.py
# @software : PyCharm

import bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100010)


def main():
    items = sys.version.split()
    fp = open("in.txt") if items[0] == "3.10.6" else sys.stdin
    n = int(fp.readline())
    a = list(map(int, fp.readline().split()))
    ans = 0
    for i in range(n):
        ans += a[i] * a[i] * (n - 1)
    s = 0
    for i in range(n):
        ans -= s * a[i] * 2
        s += a[i]
    print(ans)


if __name__ == "__main__":
    main()

D - Journey

纯正的数学题

三个性质：
1.取什么数是无关的，答案只与当前有几个数相关
2.类似马尔科夫随机过程，有自环
每个过程的期望独立，总期望=每个过程的期望之和
3.如图上，点i有$p=(n?1)/n$的概率用1步到下一个点i+1
期望步数=$1/p$
证明：设期望=$EX$
$EX=(1?p)(EX+1)+p(1)$
得证

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @file     : atcoder.py
# @software : PyCharm

import bisect
import copy
import sys
from itertools import permutations
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100010)


def main():
    items = sys.version.split()
    fp = open("in.txt") if items[0] == "3.10.6" else sys.stdin
    n = int(fp.readline())
    ans = 0
    for i in range(1, n):
        ans += n / i
    print(ans)


if __name__ == "__main__":
    main()

E - Mex Min

在一个10^6的范围内求是否有数，第一眼的感觉是BIT
但本题不是求是否有数，而是求第一个没有数的位置，可以二分计数count(x)=x
用BIT维护是否有数的数组
要注意一些trick的地方，比如出滑动窗口的数和入窗口的数是同一个数

#include <cstring>
#include <climits>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;


int n, m;
int a[1500005];
int c[1500005];
int cnt[1500005];

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

void add(int x, int val) {
    while (x <= n) {
        c[x] += val;
        x += lowbit(x);
    }
}

int get(int x) {
    int ret = 0;
    while(x > 0) {
        ret += c[x];
        x -= lowbit(x);
    }
    return ret;
}

bool check(int x) {
    return get(x) == x;
}


int main() {
    //freopen("in.txt", "r", stdin);
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++ i) {
        scanf("%d", &a[i]);
        a[i] ++;
    }
    for (int i = 0; i < m; ++ i) {
        cnt[a[i]] += 1;
    }
    for (int i = 1; i <= n; ++ i) {
        if(cnt[i]) add(i, 1);
    }
    int ans = n;
    for(int i = 0; i + m - 1 < n; ++ i) {
        int lo = 1, hi = n + 1;
        while(lo < hi) {
            int mi = (lo + hi) / 2;
            bool r = check(mi);
            if (r) lo = mi + 1;
            else hi = mi;
        }
        ans = min(ans, lo - 1);
        // printf("%d\n", ans);
        int j = i + m;
        if (i + m >= n) break;
        cnt[a[i]] --;
        cnt[a[j]] ++;
        if (a[i] != a[j]) {
            if (cnt[a[i]] == 0) add(a[i], -1);
            if (cnt[a[j]] == 1) add(a[j], 1);
        }
    }
    printf("%d\n", ans);
    return 0;
}

F - Digits Paradise in Hexadecimal

在1…N中寻找满足某种条件的数个数，是一个典型的数位dp题。

搜索的时候用bitmask表示搜索状态，但搜索到哪几个数字并不重要，只需要记录搜索到数字的个数即可，这是本题的技巧。

写了一个记忆化搜索，优化一下应该更快。
设dp[pos][c][cap][lead]
pos 当前要搜索的位置
c 当前状态（开始搜索前）不同数的个数
cap 当前搜索前是否抵达上界
lead 当前搜索前是否有非零数
答案为dp[0][0][1][0]

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#define LT(x) (x * 2)
#define RT(x) (x * 2 + 1)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;


char s[200020];
int a[200020];
int k, n;
ll mod = (ll)(1e9 + 7);
ll dp[200020][17][2][2];
int mem[1 << 17];

int pop_count(int x) {
    if (x == 0) return 0;
    if (mem[x]) return mem[x];
    int ret = 0;
    while (x) {
        x -= x & -x;
        ret++;
    }
    return mem[x] = ret;
}


ll get(int pos, int st, int cap, int lead) {
    int c = pop_count(st);
    if (c > k) return 0;
    if (pos == n) {
        return c == k && lead;
    }
    if (dp[pos][c][cap][lead] != -1) return dp[pos][c][cap][lead];
    int m = cap ? a[pos]: 15;
    ll ret = 0;
    for (int d = 0; d <= m; ++d) {
        int ncap = cap;
        if (d < m) ncap = 0;
        int nst = st;
        if (lead == 0 && d == 0)
            nst = st;
        else
            nst = st | (1 << d);
        int nlead = lead;
        if (d) nlead = 1;
        ret += get(pos + 1, nst, ncap, nlead);
        ret %= mod;
    }
    //printf("%d %d %d %d %lld\n", pos, c, cap, lead, ret);
    return dp[pos][c][cap][lead] = ret;
}


int main() {
    //freopen("in.txt", "r", stdin);
    scanf("%s", s);
    scanf("%d", &k);
    n = strlen(s);
    for (int i = 0; i < n; ++i) {
        if (s[i] >= '0' && s[i] <= '9') {
            a[i] = s[i] - '0';
        }
        else {
            a[i] = s[i] - 'A' + 10;
        }
    }
    memset(dp, 0xff, sizeof(dp));
    ll ans = get(0, 0, 1, 0);
    printf("%lld\n", ans);
    return 0;
}