Ad-hoc练习计划 1

幽云蓝 · 2022-07-03 00:48:03 · 个人记录

这个计划，是对一些个人最近补/做的 adhoc 题，加以包装，汇总后呈现在大家面前的一个计划。该计划会对题目进行主观的难度评定，并在题解中向大家呈现。

该计划旨在鼓励大家挑战形形色色的 adhoc 题，并在挑战这类看似“毫无规律”的题的过程中总结经验，提升自己，为逐渐思维化的 CNOI 做足准备。当然，这个计划的好处也是你不需要编写复杂的代码，只需要享受思维的过程。

这是这个计划的第一道正式题，由于大家反应题目过难，所以这道题给出了一道（主观评定）较简单的题。为了鼓励大家挑战，之后的题目不会在给出题解前提供（主观评定）难度（当然，不是绝对的，如果大家觉得不好随时会改）。

给定一张带权无向图，图的每个点都有正点权 w_i。试着决定一个删边顺序，使得：

• 令你当前要删除的边的两端点为 u 和 v，将 w_u 与 w_v 中的所有正数减一。你需要保证这两个数中至少有一个正数。

如果无解，请报告它。

边数、点数和点权的值域均为 2\times10^5。

附：adhoc 释义

adhoc，直译为“特殊的解法”，被用以形容一类解法不同于同类题目的特殊题目，用通俗的说法就是“思维题”。其主要特点：

• 思维过程短，常常含有“猜测”或者“非理性的证明”；
• 题目形式新颖，做法“怪异”；
• 过题较随机，高水平选手更可能在 adhoc 题上出现失误。

可能不全，望大家补充。