Vanilla_chan

Problem

There are \(2\cdot n\) cards arranged in a row, with each card numbered from \(1\) to \(n\) having exactly 2 copies.

Each time, Red can choose a subarray of consecutive cards (at least \(2\) cards) to remove from the deck. The chosen subarray must satisfy that the first and last cards have the same number. The score for this operation is: the number of cards multiplied by the number on the first card. Now Red wants to know what is the maximum value of the final score?

给你一个长度为 \(2n\) 的数组，\(1\) 到 $ n$ 每个数字恰好出现两次。你可以进行这样的操作：选择两个相同的数字 \(x\) （必须都还存在于数组中），将这两个数以及其间的所有数字（共计 \(cnt\) 个）全部拿走，并获得 \(x\cdot cnt\) 得分。求最终最多能够获得多少分？

\(1\le n\le 3\times 10^3\)

Problem

给一棵根为 1 的有根树，点 \(i\) 具有一个权值 \(A_i\) 。

定义一个点对的值 \(f(u, v)=\max \left(A_u, A_v\right) \times\left|A_u-A_v\right|\) 。

你需要对于每个节点 \(i\) ，计算 \(a n s_i=\sum_{u \in \operatorname{subtree}(i), v \in \operatorname{subtree}(i)} f(u, v)\) ，其中 \(\operatorname{subtree}(i)\) 表示 \(i\) 的子树。

请你输出 \(\oplus\left(a n s_i \bmod 2^{64}\right)\) ，其中 \(\oplus\) 表示 XOR。

\(n \leq 5 \times 10^5, 1 \leq A_i \leq 10^6\)

Problem

Sajin最近深入研究了最小生成树，现在他已经掌握了MST的算法。他渴望通过一系列查询来评估您对最小生成树概念的掌握程度。

您将面临一个加权无向图，该图包含没有任何自环的 \(n\) 个顶点和 \(m\) 条边。

Sajin提出 \(q\) 询问。对于每个顶点集，都给出了一个顶点集 \(S\) 。您的目标是确定 \(S\) 的诱导子图（induced subgraph）并找到其最小生成树的权重。如果 \(S\) 的诱导子图断开，则输出-1。

图的诱导子图是另一个图，由图的顶点子集和原始图中的所有边组成，连接该子集中的顶点对。即，对于图 \(G=(V,E)\) ，给定 \(V^\prime\) ，则有 \(E^\prime=\{(u,v) \mid u,v\in V^\prime,(u,v)\in E\}\)，诱导子图为 \(G^\prime=(V^\prime,E^\prime)\)。

\(2\le n\le 10^5,1\le m,q\le10^5\)

\(1 \le |S_i|\le n,\sum S_i\le 10^5\)

CF1988D The Omnipotent Monster Killer

Problem

怪物们在一棵有 \(n\) 个顶点的树上，编号为 \(i(1\le i\le n)\) 的怪物位于编号为 \(i\) 的顶点上，攻击力为 \(a_i\) 。你需要与怪物战斗 \(10^{100}\) 个回合。在每个回合中，会依次发生以下两步：

1. 所有活着的怪物攻击你。你的生命值会按照所有活体怪物攻击点的总和减少。
2. 您选择一些（可以选全部，也可以不选）怪物并杀死它们。被杀死的怪物将不会再进行攻击。

限制条件：在一个回合内不能杀死相邻的两只怪物。

如果您以最佳选择方式攻击的怪物，那么在所有回合后，您的健康值减少的最小值是多少？

\(1\le t\le 10^4,1\le n\le 3\cdot 10^5,1\le a_i \le 10^{12},\sum n\le 3\cdot 10^5\)

CF1992E Novice's Mistake

Problem

Noobish_Monk 有 \(n\in [1,100]\) 个朋友。每个朋友都给了他 \(a\in [1,10000]\) 个苹果作为生日礼物。Noobish_Monk收到礼物后非常高兴，他把 \(b\in[1,\min\{10000,a\cdot n\}]\) 个苹果还给了朋友们。Noobish_Monk 还剩下多少个苹果？"

K1o0n 写了一个解法，但不小心把 \(n\) 的值看成了字符串，所以 \(n \cdot a - b\) 的值的计算方法不同。具体来说

• 当用字符串 \(n\) 乘以整数 \(a\) 时，他将得到字符串 \(s=\underbrace{n + n + \dots + n + n}_{a\ \text{times}}\)。
• 从字符串 \(s\) 中减去整数 \(b\) 时，将删除最后的 \(b\) 个字符。如果 \(b\) 大于或等于字符串 \(s\) 的长度，则字符串将变为空。

现在 ErnKor 想知道在给定的 \(n\) 中，有多少对 \((a, b)\) 满足问题的约束条件且 K1o0n 的解法给出了正确答案。

“解法给出了正确答案”意味着得到了一个非空字符串，且这个字符串转换成整数后等于正确答案，即 \(n \cdot a - b\) 的值。

\(1\le t\le 100,1\le n \le 100\)

要求对被评价对象进行的客观公正合理的全面评价。一般，需要对很多个同类对象进行评价，被评价的对象往往涉及多个属性或指标。需要根据系统的属性判断确定这些这些系统状况或者未来发展孰优孰劣，即按照优劣对被评价对象进行排序或者分类。这类问题又称为多属性（多指标）综合评价问题。

Problem - E - Codeforces

爱丽丝和鲍勃玩摸球游戏。有 \(n\) 个球，其中 \(k\) 个是特殊球。每个球都有其价值。

他们轮流且不放回地摸球，每回合随机摸一个球并获得该球的价值。特别地，如果摸到了特殊球（且至少还有一个球）则这名玩家继续摸球。如果摸到的是普通球，则换人摸球。这样轮流摸球直到没有剩余球，游戏结束。Alice先手。

求游戏结束时双方的期望得分，对取模 \(10^9+7\) 。

\(t\le2\times10^5,1\le k\le n\le 4\times 10^5,1 \le v_i \le 10^7,\sum n\le 5\times 10^5\)

在许多实际问题当中，衡量一个方案的好坏标准可能不只一个。比如生产某个东西的时候想要“物美价廉”——既要质量好，又要成本低。这一类问题统称为多目标最优化问题或者多目标规划问题。

标准形式

多目标规划问题一般可以写成如下形式： \[ \begin{aligned} \min & f_1(x) \\ \min & f_2(x) \\ & \vdots \\ \min & f_p(x) \\ \text { s.t. } & g_i(x) \leq 0, i=1,2, \ldots, m \end{aligned} \]

其中, \(x=\left(x_1, x_2, \ldots, x_m\right)^T \in R^m, p \geq 2\)

这个学期比上个学期有意思得多了。但是为什么我只写了6月小结，没有写3月4月5月小结呢？因为那时候还没有想到用博客写这种小结形式的随笔啦……

横向对比，这四个月都挺有意思的。但是由于我太容易忘记事情了……我的记忆是有限的，先把6月发生的趣事赶紧记录下来比较好。

昨天更新了一下个人CV、估算了一下本学期的绩点，还是对这个学期比较满意的……但是这里是6月的月度小结，不能拓展太多写成学期小结了！2023-2024-2学期小结传送门。下面正式开始——