首页 程序设计 AtCoder

待补题，题目传送门

# A

大水题，四个数 1→41 \to 4，计算有多少个出现过两次的数字就行

python
1
2
3
4
5
6
7
8
9
10
11
12
13
cnt = [0 for _ in range(5)]

a = list(map(int, input().split()))

for i in a:
    cnt[i] += 1

res = 0

for i in range(1, 5):
    res += cnt[i] // 2;

print(res)

# B

# 题意

对于给定方程 (d + x) % q[t] == r[t] ，已知 d,qt,rtd,q_t,r_t，求 d+xd+x

# 题解

证明

方程等价于： d + x = k * q[t] + r[t]
x = k * q[t] + r[t] - d
因为 x≥0x \ge 0，所以可以得到

k⋅q[t]+r[t]−d≥0k · q[t] + r[t] - d \ge 0

等价于

k≥d−r[t]q[t]m,minn(k)=⌈d−r[t]q[t]⌉k \ge \frac{d - r[t]}{q[t]}m,minn(k) = \lceil{\frac{d - r[t]}{q[t]}}\rceil

可以写成

k=d−r[t]+q[t]−1q[t]k = \frac{d-r[t]+q[t]-1}{q[t]}

总结有 ⌈ab⌉\lceil{\frac{a}{b}}\rceil = a+b−1b\frac{a+b-1}b

python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
q = [0 for _ in range(110)]
r = [0 for _ in range(110)]

n = int(input())
for i in range(1, n + 1):
    (q[i], r[i]) = list(map(int, input().split()))

z = int(input())
for i in range(z):
    (t, d) = list(map(int, input().split()))

    k = (d - r[t] + q[t] - 1) // q[t]  # 等价于向上取整
    # 计算 x
    x = k * q[t] + r[t] - d

    print(d + x)

# C

水题，对于每一个 aia_i 找到其左边第一个满足 ak=aia_k = a_i 的 kk 的值，如果不存在这样的 kk，则输出 -1
你需要注意的是，aia_i 的范围最大是 10910^9，开数组会爆炸，用 dictdict，不然会爆炸

python
1
2
3
4
5
6
7
8
9
10
11
12
13
place = {}
a = [0 for _ in range(20010)]

n = int(input())
a = list(map(int, input().split()))

for i in range(n):
    if a[i] not in place:
        print(-1, end = ' ')
    else:
        print(place[a[i]], end = ' ')
    
    place[a[i]] = i + 1

# D

搜索题，没啥好说的搜就是了

python
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
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

s = ['' for _ in range(20)]
flag = [[0 for _ in range(11)] for _ in range(11)]
res = 0

(h, w, k) = map(int, input().split())

def dfs(x, y, t):
    global res
    if t == k:
        res += 1
        return
    
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]

        if (xx >= 0 and xx < h and yy >= 0 and yy < w and s[xx][yy] == '.' and flag[xx][yy] == 0):
            flag[xx][yy] = 1
            dfs(xx, yy, t + 1)
            flag[xx][yy] = 0

for i in range(h):
    s[i] = input()

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            flag[i][j] = 1
            dfs(i, j, 0)
            flag[i][j] = 0
    
print(res, end = '')

# E

# 题意

给你一个由 NN 个非负整数组成的序列 A=(A1,A2,...,AN)A = (A_1, A_2, ..., A_N) 和一个正整数 MM 。
求下列数值：

∑1≤l≤r≤N((∑l≤i≤rAi)modM)\sum_{1 \leq l \leq r \leq N} \left( \left(\sum_{l \leq i \leq r} A_i\right) \mathbin{\mathrm{mod}} M \right)

# 题解

设 sis_i 表示 (∑j=1iAj)modM(\sum\limits_{j=1}^{i}{A_j})~mod~M 的值，那么原式可以转化成： ∑1≤l≤r≤n(sr−sl−1)\sum\limits_{1 \le l \le r \le n} (s_r - s_{l-1})
展开有：∑1≤i≤n∑0≤j≤i−1(si−sj−1)\sum\limits_{1 \le i \le n}\sum\limits_{0 \le j \le i - 1} (s_i - s_{j-1})
整理可得：∑1≤i≤n(i∗si−∑0≤j≤i−1sj)\sum\limits_{1 \le i \le n}(i * s_i - \sum\limits_{0 \le j \le i - 1}s_j)
如果直接减，那么如果 sj>sis_j > s_i 的话便会减出负数来，这个时候要加上一个 mm
用树状数组维护对于每个 ii 有多少个 sj>sis_j > s_i，然后继续加上这么多 mm 就行

c++
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
int n, m, sum[N], ans, res, c[N];

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

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

int getSum(int x) {
    int ans = 0;
    while (x > 0)
        ans += c[x], x -= lowbit(x);
    return ans;
}

void solve () {
    cin >> n >> m;
    for (int i = 1, x; i <= n; i++) {
        cin >> x;
        sum[i] = (sum[i - 1] + x) % m;
    }

    for (int i = 1; i <= n; i++) {
        ans += i * sum[i] - res + (getSum(m) - getSum(sum[i] + 1)) * m;
        res += sum[i];
        add(sum[i] + 1, 1);
    }

    cout << ans << endl;
}

更新于 阅读次数 次

请我喝[茶]~(￣▽￣)~*

duoxichangan 微信支付

微信支付

duoxichangan 支付宝

支付宝