AtCoder ABC 138

C - Alchemist
排序贪心，小的应该先除，大的后除
D - Ki
搜索
pypy不出意外的挂了

// atcoder.cpp : 
//
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef vector<int> vi;

int N, P;
vector<int> g[200005];
LL add[200005];
LL a[200005];


void dfs(int u, int fa, LL cur_s) {
	a[u] = add[u] + cur_s;
	for (auto v : g[u]) {
		if (v == fa) continue;
		dfs(v, u, a[u]);
	}
}


int main()  
{
	//freopen("in.txt", "r", stdin);
	scanf("%d%d", &N, &P);
	for (int i = 0; i < N - 1; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 0; i < P; ++i) {
		int u, w;
		scanf("%d%d", &u, &w);
		u--;
		add[u] += w;
	}
	dfs(0, -1, 0);
	for (int i = 0; i < N; ++i) {
		if (i) printf(" ");
		printf("%lld", a[i]);
	}
	printf("\n");
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

E - Strings of Impurity
S中的每个字符都可以列出一个在S中的位置列表
二分搜索当前的位置，算出每次移动的step
由于当前的位置可能是在列表的后面，因此S重复一遍

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : yhdu@tongwoo.cn
# @desc     :
# @file     : atcoder.py
# @software : PyCharm
import bisect
import copy
import sys
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(50005)


def get_pos(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mi = lo + hi >> 1
        if target < arr[mi]:
            hi = mi
        else:
            lo = mi + 1
    return lo


def main():
    items = sys.version.split()
    if items[0] == '3.10.6':
        fp = open("in.txt")
    else:
        fp = sys.stdin
    S, T = fp.readline().strip(), fp.readline().strip()
    set_t = set([c for c in T])
    set_s = set([c for c in S])
    if set_t & set_s != set_t:
        print("-1")
        return
    S = S + S
    ns = len(S)
    n = ns // 2
    ch_dict = defaultdict(list)
    for i, c in enumerate(S):
        ch_dict[c].append(i)

    ans = 0
    cur = -1
    for c in T:
        arr = ch_dict[c]
        pos = get_pos(arr, cur)
        ans += arr[pos] - cur
        cur = arr[pos]
        if cur >= n:
            cur = cur - n
    print(ans)


if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

F - Coincidence
本题的思路：https://blog.csdn.net/Jason_lxy/article/details/102892386

那么转换为求$(x,y)$的对数，使得$y\oplus x=y-x$
本题和129E题一样，是一道数位DP，但是需要维护两个limit
由于$x,y$的取值只可能是$(0,1),(1,1),(0,0)$，即$x\le y$
那么设定之前的搜索是否达到上限的标记位r_lim，及之前搜索是否达到下限的l_lim，这两个limit是$x,y$都要满足的。
在搜索当前位时，如果之前的搜索达到下限，那么现在的取值（0,1）不能取比L当前位小的数，不然就突破下限了。上限也同理。

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : yhdu@tongwoo.cn
# @desc     :
# @file     : atcoder.py
# @software : PyCharm
import bisect
import copy
import sys
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(50005)


def main():
    items = sys.version.split()
    if items[0] == '3.10.6':
        fp = open("in.txt")
    else:
        fp = sys.stdin
    L, R = map(int, fp.readline().split())
    l, r = [0] * 60, [0] * 60
    len_l, len_r = 0, 0
    while L:
        l[len_l] = L & 1
        L >>= 1
        len_l += 1
    while R:
        r[len_r] = R & 1
        R >>= 1
        len_r += 1
    mod = 10 ** 9 + 7

    @lru_cache(None)
    def get(pos, l_lim, r_lim):
        # x <= y
        # 当前搜索到pos, l_lim代表x是否达到L的下限, r_lim代表y是否达到R的上限
        if pos == -1:
            return 1
        ret = 0
        t0 = l[pos] if l_lim else 0
        t1 = r[pos] if r_lim else 1
        for x, y in [(0, 1), (1, 1), (0, 0)]:
            if y <= t1 and t0 <= x:
                ret += get(pos - 1, l_lim and (x == t0), r_lim and (y == t1))
        ret %= mod
        # print(pos, l_lim, r_lim, ret)
        return ret

    ans = 0
    for i in range(len_l - 1, len_r):
        # 枚举最高位
        ans += get(i - 1, i == len_l - 1, i == len_r - 1)
        ans %= mod
    print(ans)


if __name__ == "__main__":
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63