欢迎来到 Pomelorin 和 Cool-breeze 的博客！希望我们能相互交流，共同进步～

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

查询排序后的最大公约数

https://leetcode.cn/problems/sorted-gcd-pair-queries/description/

给你一个长度为 \(n(n\le10^5)\) 的整数数组 nums​，值域 \(5·10^4\) 。

两两组合出 \(n^2/2\) 个数对，对每个数对求出 gcd(nums[i], nums[j]) ，并放在一起升序排列成一个数组。

\(q(q\le10^5)\) 个查询，每次询问数组里下标为 \(q_i\) 的数是几。

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\)。