小红的树切割 题目要求切割后对于任意一棵树，需要满足树中任意相邻的两个节点的颜色不同。 因此在切割前，对于任意一条树上的边，只要与的颜色相同，就需要进行切割，否则不需要进行切割。 所以我们需要遍历树上的每一条边，检验边的两个端点颜色是否相同。  def solve(testcase): n = II() s = I() res = 0 for _ in range(n - 1): u, v = GMI() res += s[u] == s[v] print(res) for testcase in range(1): solve(testcase)

小红的树构造 首先考虑两种特殊情况：   : 一棵个节点的树，能取得的最大直径是 (此时树是一条链), 因此当时，无解   , 考虑一棵个节点的树能取得的最小直径:   当时，最小直径为，此时若，无解。   当时，最小直径为，此时若，把这条边连起来就行了。   当时，最小直径为，除了根节点(假设根为编号为的节点)以外，所有节点都与根节点直接相连，此时若，无解。     其他都是有解的情况，构造方法如下：   先构造出直径：连接这些边，这样从到的距离为，可以作为树的直径。   添加其他节点：对于其他节点，为了不干扰直径的长度，可以直接把这些节点和这个节点相连，这样可以维持直径不变。    def...

小红的树 用一个数组来记录树上每个点的度 对于每一条边:     最后输出数组中出现的次数。 def solve(testcase): n, k = MI() deg = [0 for _ in range(n)] for _ in range(n - 1): u, v = GMI() deg[u] += 1 deg[v] += 1 print(deg.count(k)) for testcase in range(1): solve(testcase)

小红走象步 当象处于时，共有四种可能的走法  ，条件是仍然在棋盘内，且处没有兵阻挡 ，条件是仍然在棋盘内，且处没有兵阻挡 ，条件是仍然在棋盘内，且处没有兵阻挡 ，条件是仍然在棋盘内，且处没有兵阻挡  从给定的起点开始进行BFS, 一直到遍历到，或者队列为空为止。 d = ((1, 1, 2, 2), (1, -1, 2, -2), (-1, 1, -2, 2), (-1, -1, -2, -2)) def solve(testcase): n, m = MI() k = II() A = [[True for _ in range(m)] for _ in range(n)] for _ in...

[模板]01背包（方案输出）  代表考虑前种物品，物品总体积为的前提下能带走的最大物品价值。 通过动态规划得出最优解之后逆序去找每个物品是否应该被选取。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll NEG_INF = - (4000000000000000000LL); void solve(int testcase) { ll n, m; cin >> n >> m; vector<pair<ll, ll>> items(n...

[模板]01背包（计数）  代表占用体积能达到的最大价值  代表占用体积能达到最大价值时的方案数 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MOD = 1000000007; const ll NEG_INF = - (4000000000000000000LL); void solve(int testcase) { ll n, m; cin >> n >> m; vector<ll> A(m + 1, NEG_INF); A[0] ...

利用倍增数组，记录：  B[i][j]: 从下标开始，向后走步会走到哪个下标 C[i][j]: 从下标开始，向后走步经过的所有数之和对取模的结果  ''' Hala Madrid! https://github.com/USYDDonghaoLi/Programming_Competition ''' import sys import os from io import BytesIO, IOBase BUFSIZE = 8192 class FastIO(IOBase): newlines = 0 def __init__(self, file): self._fd = file.file...

利用分块维护每个区间的信息:  blocks: 每个块中的所有数 blocksinfo: 每个块中所有数排好序后的结果 blockslz: 如果某次更改将这个块内所有的数全都加上了一个固定的值，将这个值增加到blockslz数组中该块对应的下标上  每次更新 (l, r, x)：  通过计算得到这次更新涉及那些块 对于未被完整更新的块（块中有的数没有被更新），将该块中每个被影响的数加上x，之后把这个块新的排好序后的结果存到blocksinfo对应的下标中 对于被完整更新的块（块中所有数都被更新了），将x加到blockslz数组中该块对应的下标上，因为这个块所有的数都被增加了x，数组中所有数之间...

灵梦的字符串问题 对于每一个元素，只有它小于等于下一个元素，复制它才可能会使得字符串变小。 把字符串通过双指针分成若干个子串，每个子串内元素相同。这样对于每一个字串而言，如果该字串的字符小于下一个子串的字符，那么对这个子串上的任意字符进行赋值操作都会使得字符串变小。我们可以把当前子串对应的进行排序，从小到大依次操作。 def solve(testcase): n, m = MI() s = I() A = LII() B = [] l, r = 0, 0 while r < n: while r < n and s[r] == s[l]: r += 1 B.append((s[l]...

互不侵犯的国王 把每一行能不能放国王的信息用二进制编码。 预处理出：  如果当前在某些位置放国王，下一行有哪些位置不能放国王（每个国王可以影响到下一行这三个位置。 在上一行的限制下，当前行有多少种不同的合理放置国王的方式（上一行被影响到的位置不能放国王，同时当前行放置的国王不能相邻，否则他们会互相攻击）  利用记忆化搜索 来进行记忆化搜索。代表当前遍历到的行下标，代表上一行对当前行的影响，代表当前还有多少个国王需要放置。 边界条件是：  当时，所有行都被遍历过了，此时如果，说明所有的国王都被放好了，是一种合理的放置方法，对应的方案数为。否则，还有国王没有被放置，这种放置方法是不合理的，对应的放...

fmin = lambda x, y: x if x < y else y fmax = lambda x, y: x if x > y else y def solve(testcase): n = II() A = LII() B = [0 for _ in range(100010)] for a in A: B[a] += a dp = [0 for _ in range(100010)] for i in range(100010): dp[i] = dp[i - 1] if B[i - 1]: dp[i] = fmax(dp[i], dp[i - 2] + B[i - ...

fmin = lambda x, y: x if x < y else y fmax = lambda x, y: x if x > y else y mod = 10 ** 9 + 7 # @TIME def solve(testcase): n = II() if n == 1: print(1) return dpl = [0 for _ in range(n + 1)] dpr = [0 for _ in range(n + 1)] dpl[0] = 1 dpr[0] = 1 pslo = [0 for _ in range(n + 1)] psro = [0 for _ ...

def solve(testcase): n, q = MI() A = LII() B = [0, A[0]] for i in range(1, n): B.append(A[i] - A[i - 1]) B.append(0) for _ in range(q): l, r, x = MI() B[l] += x B[r + 1] -= x for i in range(1, n + 1): B[i] += B[i - 1] print(*B[1: -1]) for testcase in range(1): solve(testcase)

fmin = lambda x, y: x if x < y else y fmax = lambda x, y: x if x > y else y # @TIME def solve(testcase): n = II() A = LII() dp = [0 for _ in range(n + 1)] for i, v in enumerate(A, 1): dp[i] = dp[i - 1] if i >= 3: dp[i] = fmax(dp[i], dp[i - 3] + A[i - 2]) print(dp[n]) for testcase in range(1...