Atcoder abc131

C
容斥原理 要注意同时能被CD整除的数应该是x%gcd(C,D) == 0
D
排序后贪心
这个题的难度比400分要低
E
容易想到将1点放在中心，其他点像星型连接1点，是K的上限
然后要观察到每连接两个点将当前的k值减一，就容易构造
F
xy坐标系拆开坐标建图，这个思路很有用
如果（x,y）坐标存在，在点x与点y之间连一条无向边
加一个点的操作就转换为：
如果存在x0,y0,x1,y1且(x0,y0)(y0,x1)(x1,y1)有边相连，(x0,y1)没有边相连，将x0与y1连起来
可以发现，只要在一个连通块里面的$x_i$点与$y_j$点不直接相连，总能在若干次原操作后对这两个点进行一次原操作
所以对于$x_i$点而言，可以增加的操作是连通块内y点的数量-原来与$x_i$点连接的y点的数量

# -*- 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(100010)


def main():
    items = sys.version.split()
    if items[0] == '3.10.6':
        fp = open("in.txt")
    else:
        fp = sys.stdin
    n = int(fp.readline())
    N = 100005

    fa = [i for i in range(N * 2 + 2)]

    def get_fa(x):
        if x == fa[x]:
            return x
        fa[x] = get_fa(fa[x])
        return fa[x]

    gx = [set() for _ in range(N + 1)]
    for i in range(n):
        x, y = map(int, fp.readline().split())
        gx[x].add(y + N)
        fx, fy = get_fa(x), get_fa(y + N)
        if fx != fy:
            fa[fx] = fy

    dsu = defaultdict(list)
    for i in range(1, N + 1):
        dsu[get_fa(i)].append(i)
    for i in range(1, N + 1):
        dsu[get_fa(i + N)].append(i + N)

    ans = 0
    for fi, t_list in dsu.items():
        x_list, y_list = [x for x in t_list if x <= N], [x for x in t_list if x > N]
        yn = len(y_list)
        for x in x_list:
            ans += yn - len(gx[x])
    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