AtCoder abc 136

AtCoder abc 136"/>

AtCoder abc 136

C
从后向前贪心
D
寻找规律
推一下可以发现连续的RR…RLL…L可以作为一个独立的循环节
最后这个循环节内的数字集中在RL的交界处
再处理一下奇偶性就好

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : yhdu@tongwoo
# @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.stdins = fp.readline().strip()n = len(s)rl, ll = [], []i = 0while i < n:bi = iwhile i < n and s[i] == 'R':i += 1rl.append(i - bi)bi = iwhile i < n and s[i] == 'L':i += 1ll.append(i - bi)m = len(rl)ans = []for i in range(m):s = ll[i] + rl[i]temp = [0] * sif s & 1 == 0:temp[rl[i]] = temp[rl[i] - 1] = s // 2else:if rl[i] > ll[i]:temp[rl[i] - 1] = s // 2 + 1temp[rl[i]] = s // 2else:temp[rl[i] - 1] = s // 2temp[rl[i]] = s // 2 + 1times = max(ll[i], rl[i]) - 1if times & 1:temp[rl[i] - 1], temp[rl[i]] = temp[rl[i]], temp[rl[i] - 1]ans += tempprint(*ans)if __name__ == "__main__":main()

E
这种一个加一一个减一的操作，应该马上想到其和是不变的
然后遍历可以被总和整除的自然数
对于每个因数，先进行模运算，然后排序，将左边的减1，右边的加1，找到一个分界点。

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : yhdu@tongwoo
# @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 check(arr, k, p):t = [x % p for x in arr]t.sort()n = len(arr)pre = 0st = sum(t)for i in range(n):pre += t[i]if pre > k:return Falseif pre == (n - 1 - i) * p - (st - pre):return Truereturn Falsedef main():items = sys.version.split()if items[0] == '3.10.6':fp = open("in.txt")else:fp = sys.stdinn, k = map(int, fp.readline().split())a = list(map(int, fp.readline().split()))sa = sum(a)p = 1ans = 0while p * p <= sa:if sa % p == 0:p0, p1 = p, sa // pif check(a, k, p0):ans = p0if check(a, k, p1):ans = p1breakp += 1print(ans)if __name__ == "__main__":main()