Problem A

有 \(n\) 个字符串，\(t_1,t_2,…,t_n\)，这些字符串只由字符 s 和 h 组成。 定义这些字符串的连接为 \(t_1,t_2,…,t_n\) 首尾相接。

可以对这 \(n\) 个字符串进行任意次重排，希望重排后字符串的连接之中 sh 子序列出现次数最多，并求出这个最大值。

\(1≤n≤10^5\)，总长度不超过 \(10^5\)。

G. Omg Graph

https://codeforces.com/contest/2117/problem/G

给定无向带权连通图，定义一条路径的花费为：路径经过的边中，边权最大值 + 最小值。求从 \(1\) 到 \(n\) 路径中的最小花费（注意不一定是简单路径）。

\(2≤n≤2⋅10^5,n−1≤m≤\min(2⋅10^5,n(n−1)/2),1≤u,v≤n,1≤w≤10^9\)

给出链接、标签和一句话题解。

• https://codeforces.com/contest/2101/problem/B

  逆序对 奇数位只会被交换到奇数位，偶数位类似。奇偶分开考虑，如果奇数列和偶数列的逆序对个数相同（模 \(2\) 意义下），则两者交换需求都可以满足，两数列必定各自有序；否则，有一个数列并非有序（其中一个序列无法排好最后两个数）。

  阅读全文 »

Problem C

给长度为奇数 \(n\) 的数组 \(a\)。最多执行 \(k\) 次操作，每次任意选定一个元素，其值加一。最大化中位数。

\(1≤n≤2\times 10^5\)，\(n\) 为奇数，\(1≤k≤10^9,1≤a_i≤10^9\)。

Problem K

给 \(n\) 个节点的一棵树，上面有 \(m\) 个特殊边。有 \(k\) 个路径（从某点到某点），选出最少数量的路径包含所有的 \(m\) 条特殊边。无解输出 -1；有解还要求方案数。

\(2≤n≤2×10^5, 1\leq m\leq 22, 1\leq k\leq 2\times 10^5\)。

原创题目但是不知道怎么做。

选票统计

G 国共 \(n\) 个城市，\(m\) 个双向道路把它们连接起来，每个城市都可以通过某条路径到达其他任何一个城市。

G 国为了减少建设开支，希望将 \(n-1\) 条道路建设为主干道使用，使得每个城市都可以通过这 \(n-1\) 条道路到达其他任何一个城市。G 国已经给出了一个建设方案。

居民们有拜访其他城市居民的需求，自然需要尽量少走路。如果对于一个城市，到达其他任何一个城市的最短距离和只走主干道到达此城市的最短距离均相等，那么这个城市内的居民就会同意这个建设方案。否则，他们就不会同意这个方案。

你作为 G 国的大臣，你提议通过民主投票来决定这个方案是否通过。于是，你需要找出哪些城市里的居民同意方案，哪些不同意方案。

Problem A

正整数范围内，长度为 \(n\) 的漂亮序列 \(x\) 的定义：存在与之长度相等、元素互不相同的序列 \(y\)，使得 \(\forall\text{ }i,j\in[1,n],x_iy_i=x_jy_j\)。给一个长度为 \(n\) 的正整数序列 \(a\)，求最长的子序列 \(a'\)，使 \(a'\) 为漂亮序列。\(t\) 组数据。

\(1≤t≤500,1≤n≤100,1≤a_i≤n\)。

Problem A

给定一个包含 \(n\) 个正整数的数组 \(a_0,a_1,…,a_{n−1}\)，你可以选择任意下标 \(x\)（\(0≤x<n\)）作为起始位置，并进行若干次操作：\(a_x\gets a_x-1\)，之后 \(x\gets (x+1) \bmod n\)。如果操作之前数字为 \(0\)，终止操作。

请问如果选择合适的 \(x\)，最多可以进行多少次操作。

Problem F

把数组 \(\{a_n\}\) 分为三段，使得在三段内同时出现的数字数量最大。输出最大值以及左右指针（即分割方法）。

\(3\le n\le150000,1\le a_i\le10^6\)。

Dashboard - SDU 2024暑假排位 Round 2 - Codeforces

Problem A

一个圆形走廊由两个区域组成。内区域被均匀地分为 \(n\) 个扇区，外区域被均匀地分为 \(m\) 个扇区。每对相同区域（内或外）的扇区之间都有墙壁，但内区域和外区域之间没有墙壁。12 点钟位置总是有一堵墙。

内区域的扇区顺时针方向标记为 \((1,1),(1,2),⋯,(1,n)\)。外区域的扇区同样标记为 \((2,1),(2,2),⋯,(2,m)\)。

有 \(q\) 个询问，是否可以从一个扇区移动到另一个扇区。

\(1≤n,m≤10^{18},1≤q≤10^4\)。