QOJ杂题合集
QOJ #151. Nice Lines
QOJ #838. Horrible Cycles
QOJ #894. Longest Loose Segment
QOJ #895. Color
给定一个有 \(n\) 个节点的无向完全图 \(G\)，每条边都被染成了 \(m\) 种颜色中的一种，颜色编号为 \(1\sim m\)。
我们称一个无向完全图合法，当且仅当对于 \(\forall x\in G\)，若存在 \((x,y),(x,z)\in E\)，满足 \(c(x,y)\neq c(x,z)\)，其中 \(c(u,v)\) 表示边 \((u,v)\) 的颜色。
可以证明合法的无向完全图的最大节点数量为 \(m+1\)。
请你求出是否可以在 \(G\) 的基础上扩展得到一个有 \(m+1\) 个节点的合法的无向完全图 \(G'\)。如果有，需要构造一组合法方案。
对于全部数据，满足 \(n,m\leq 200\)，\(n\leq m+1\)。
QOJ #957. Assignment Problem
QOJ #959. Multiple?
QOJ #962. Thanks to MikeMirzayanov
QOJ #970. Best Subsequence
QOJ #1085. Brave Seekers of Unicorns
QOJ #1088. Border Similarity Undertaking
QOJ #1173. Knowledge Is...
QOJ #1177. Bookface
今天是 YQH 的生日，她得到了一套益智玩具—— \(n\) 个电塔作为生日礼物。所有电塔位于同一条直线上。具体的，把电塔所在直线抽象为一条数轴的非负半轴，那么第 \(i\) 个电塔位于数轴上 \(x_i\) 的位置。
假如两个电塔之间的相对距离严格小于 \(d\)，那么它们就会放电。在游玩一段时间后，YQH 感到厌倦了，于是她准备把这些电塔收拾起来。为了不浪费电，她希望把电塔调到都不放电的状态。
具体的，YQH 每次可以把某个电塔沿数轴正方向移动一个单位或沿数轴负方向移动一个单位，但是必须保证电塔位于数轴的非负半轴。你可以认为其他电塔不会干扰电塔的移动。
移动电塔是一个很累的行为，所以 YQH 希望求出移动电塔的最小次数，使得所有电塔都不放电。
对于全部数据，保证 \(1\leq T\leq 10^5\)，\(1\leq n\leq 2\times 10^5\)，\(1\leq d\leq 10^6\)，\(0\leq x_i\leq 3×10^{11}\)，\(\sum n\leq 10^6\)。
QOJ #1197. Draw in Straight Lines
QOJ #1337. Parity Sort
QOJ #1346. The Spellbook
QOJ #1359. Setting Maps
QOJ #1395. Trzy drogi [A]
QOJ #1427. Flip
QOJ #1429. Hit
QOJ #1431. Joy
QOJ #1436. Split in Sets
QOJ #1462. Euclid's Algorithm
QOJ #1809. Find the MST for Grid
QOJ #1813. Joy with Permutations
QOJ #1825. The King's Guards
QOJ #1839. Joke
QOJ #1849. 2048 [TAG: Removed Problem]
QOJ #1869. Power Station of Art
QOJ #1875. Nein
QOJ #1878. No Rest for the Wicked
QOJ #1880. Nikanor Loves Games
QOJ #2065. Cyclic Distance
QOJ #2378. Tree Permutations
QOJ #2544. Flatland Currency
QOJ #2550. Lion and Zebra
QOJ #2559. Endless Road
QOJ #2562. Fake Plastic Trees 2
QOJ #2570. Maximal Subsequence
QOJ #2571. Aidana and Pita
QOJ #2606. Gachapon
QOJ #2609. Number Guessing
QOJ #2610. Build a City
QOJ #2620. Escaped from NEF
QOJ #2624. Implemented Incorrectly
QOJ #2709. Travelling Merchant
QOJ #2808. Gardening
QOJ #2812. Paths
QOJ #3039. Cleaning
QOJ #3301. Economic One-way Roads
QOJ #3575. Where is the legend?
QOJ #3798. Planning Railroad Discontinuation
QOJ #3801. Cancer DNA
QOJ #3835. Oracle
QOJ #3875. Fruits
QOJ #3998. The Profiteer
QOJ #4219. Insects
QOJ #4635. Graph Operation
QOJ #4758. Captivating process
QOJ #4794. Salaj
QOJ #4878. Easy Problem
QOJ #4882. String Strange Sum
QOJ #4887. Fast Bridges
QOJ #5071. Check Pattern is Good
QOJ #5241. Miny [A]
QOJ #5423. Perfect Matching
QOJ #5439. Meet in the Middle
QOJ #5475. Make a Loop
QOJ #6101. Ring Road
QOJ #6119. Frustration and Bracket Sequences
QOJ #6299. Binary String
QOJ #6308. Magic
QOJ #6322. Forestry
QOJ #6366. Message
QOJ #6380. LaLa and Divination Magic
QOJ #6540. Beautiful Sequence
给定一个长为 \(n\) 的序列 \(a\)，你需要将其重排成序列 \(b\) 使得其好元素最多，输出最多的好元素个数。
一个元素 \(i\) 是好的，当且仅当 \(a_i \geq \max(a_{i−1}, a_{i+1})\)（我们认为 \(a_0 = a_{n+1} = 0\)）。
有多组测试数据。
对于 \(100\%\) 的数据，\(1 \leq \sum n \leq 3 \times 10^5\)，\(1\leq a_i \leq n\)。
QOJ #6555. Sets May Be Good
QOJ #6638. Treelection
QOJ #6659. Ring Road 2
QOJ #6807. Travel Dream
QOJ #7106. Infinite Parenthesis Sequence
QOJ #7510. Independent Set
QOJ #7520. Monster Generator
QOJ #7605. Yet Another Mex Problem
有一个长度为 \(n\) 的序列 \(a\)。
设一个区间的价值为此区间的 \(\text{mex}\) 值乘上区间元素总和。其中 \(\text{mex}\) 值定义为该集合中不属于集合的最小非负整数，例如 \(\text{mex}(0,1,3,5)=2\)。
你需要将数组划分成若干非空区间，其中每个区间的长度不超过 \(k\)。一个划分方案的价值为每个区间的价值之和。
你需要找到满足题意的划分方案下的最大价值。
对于全部数据，满足 \(2\leq n\leq 2\times 10^5\)，\(1\leq k\leq n\)，\(0\leq a_i\leq n\)。