AtCoder ABC194

发布时间:2024年01月11日

这期比193稍微简单一点

C - Squared Error

手玩一下:
N = 3 N=3 N=3
展开得
a 2 + b 2 ? 2 a b + b 2 ? c 2 ? 2 b c + a 2 + c 2 ? 2 a c a^2+b^2-2ab+b^2-c^2-2bc+a^2+c^2-2ac a2+b2?2ab+b2?c2?2bc+a2+c2?2ac
每个数平方项都要计算 n ? 1 n-1 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 p=(n-1)/n p=(n?1)/n的概率用1步到下一个点i+1
期望步数= 1 / p 1/p 1/p
证明:设期望= E X EX EX
E X = ( 1 ? p ) ( E X + 1 ) + p ( 1 ) EX=(1-p)(EX+1)+p(1) 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;
}
文章来源:https://blog.csdn.net/acrux1985/article/details/135520633
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。