前言

每周会在这里放几道c++的题目，难度不等。
难度分级：入门 → 普及- → 普及/提高- → 普及+/提高 → 提高+/省选- → 省选/NOI− → NOI/NOI+/CTSC
推荐IDE:https://sourceforge.net/projects/orwelldevcpp/

题目来源:https://www.luogu.com.cn/

做完后可自行上洛谷提交

题目

P1084 [NOIP 2012 提高组] 疫情控制

难度:省选/NOI−

题目描述

H 国有 n 个城市，这 n 个城市用 n−1 条双向道路相互连通构成一棵树，1 号城市是首都，也是树中的根节点。

H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。

现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。

请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

输入格式

第一行一个整数 n，表示城市个数。

接下来的 n−1 行，每行 3 个整数，u,v,w，每两个整数之间用一个空格隔开，表示从城市 u 到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。

接下来一行一个整数 m，表示军队个数。

接下来一行 m 个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎的城市的编号。

输出格式

一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出 −1。

输入输出样例

输入 #1复制

4 
1 2 1 
1 3 2 
3 4 3 
2 
2 2

输出 #1复制

3

说明/提示

【输入输出样例说明】

第一支军队在 2 号点设立检查点，第二支军队从 2 号点移动到3 号点设立检查点，所需时间为 3 个小时。

【数据范围】

保证军队不会驻扎在首都。

• 对于 20% 的数据，2≤n≤10；

• 对于 40% 的数据，2≤n≤50，0<w<105；

• 对于 60% 的数据，2≤n≤1000，0<w<106；

• 对于 80% 的数据，2≤n≤104；

• 对于 100% 的数据，2≤m≤n≤5×104，0<w<109。

NOIP 2012 提高组 第二天 第三题

P2562 [AHOI2002] Kitty猫基因编码

难度：普及-

题目描述

小可可选修了基础生物基因学。教授告诉大家 Super Samuel 星球上 Kitty猫的基因的长度都是 2 的正整数次幂 )， 全是由两种不同的基因单元组成的。 这两种不同的基因单元分别记成 0 和 1，于是 Kitty 猫基因可以写成一个 01 串表达式 。

为了便于分析和降低数据存储量，教授发明了 ABC 编码规则。该编码规则是不断地按照

对 Kitty 猫基因 01 串表达式 进行改写， 直至最终被改写成只含有字符 “ A”、“ B”、“ C”的符号串。

请你编写程序帮助小可可求出 Kitty 猫基因的 ABC 编码以协助教授开展科研工作。

输入格式

文件中以一行的形式存放了一个 Kitty 猫基因的 01 串表达式。

输出格式

以一行的形式输出这个 Kitty 猫基因的 ABC 编码。

输入输出样例

输入 #1复制

00

输出 #1复制

A

输入 #2复制

01001011

输出 #2复制

CCCABACCBAB

说明/提示

给出的01字符串长度Len≤256

题解

需要题解到评论区说，人数最多的几篇发题解(也可以自己去洛谷上搜)

也可以在评论区分享一下自己的解题思路