Fly

概念

算数基本定理：任何一个≥2的自然数 N都可以唯一分解成有限个素数（质数）的幂的乘积。

算数基本定理包括两点最基本的内容：
（1）数n可以以某种方式分解为素数的乘积。
（2）只有唯一一种这样的因式分解。（除因数重排外）

概念

模算数或称同余运算（英语：Modular arithmetic）是一个整数的算术系统，其中数字超过一定值后（称为模或余数）后会“卷回”到较小的数值，模算数最早是出现在卡尔·弗里德里希·高斯在1801年出版的《算术研究》一书中。

八皇后问题

爆搜dfs

题面

题目描述 5 个砝码，用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。如果只有 5 个砝码，重量分别是 1，3，9，27，81。则它们可以组合称出 1 到 121 之间任意整数重量（砝码允许放在左右两个盘中）。本题目要求编程实现：对用户给定的重量，给出砝码组合方案。

题面

给定 x 轴上 n 个闭区间。去掉尽可能少的闭区间，使剩下的闭区间都不相交。 给定 n 个闭区间，计算去掉的最少闭区间数。
输入数据的第一行是正整数 n (n <= 100)，表示闭区间数。接下来的 n 行中，每行有 2 个整数，分别表示闭区间的 2 个数端点。

输入输出

1
2
3
4
5
6

3
10 20
10 15
20 15

2

题面

一共有 n 个小岛位于 x 轴之上， x 轴为海岸， x 轴上方为海洋。现需要在海岸上建立雷达。在海岸建立的最少的雷达数目，使得雷达可以覆盖所有的小岛。可以认为每个小岛都是一 个点。如图所示，三个小岛分别是 P_1, P_2, P_3, 雷达的半径 d=2, 在 x 轴上建立两个雷达 (-2,0) 和 (1,0) 就能覆盖三个小岛。
一共有 n 个小岛位于 x 轴之上， x 轴为海岸， x 轴上方为海洋。现需要在海岸上建立雷达。在海岸建立的最少的雷达数目，使得雷达可以覆盖所有的小岛。可以认为每个小岛都是一 个点。如图所示，三个小岛分别是 P_1, P_2, P_3, 雷达的半径 d=2, 在 x 轴上建立两个雷达 (-2,0) 和 (1,0) 就能覆盖三个小岛。

题面

小S新买了一个掌上游戏机，这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏，他买了很多 5 号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用 5 个小时，有的可能就只能使用 3 个小时。显然如果他只有两个电池一个能用 5 小时一个能用 3 小时，那么他只能玩 3 个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电池分别能用 3、3、5 小时，他可以先使用两节能用 3 个小时的电池，使用半个小时后再把其中一个换成能使用 5 个小时的电池，两个半小时后再把剩下的一节电池换成刚才换下的电池（那个电池还能用 2.5 个小时），这样总共就可以使用 5.5 个小时，没有一点浪费。 现在已知电池的数量和电池能够使用的时间，请你找一种方案使得使用时间尽可能的长。 

题面

试设计一个用回溯法搜索子集空间树的函数。该函数的参数包括结点可行性判定函数和上界函数等必要的函数，并将此函数用于解 0-1 背包问题。0-1 背包问题描述如下：给定 n 种物品和一个背包。物品 i 的重量是w_i，其价值为v_i，背包的容量为C 。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

第一行有2个正整数n和Cn是物品数C是背包的容量。接下来的 1 行中有 n 个正整数，表示物品的价值。第3行中
有 n 个正整数，表示物品的重量。 

将计算出的装入背包物品的最大价值和最优装入方案输出。第一行输出为：Optimal value is

111

题面

输入

1
2
3
4
5
6

4 4 10
....
....
....
S**P
0 0 0

输出

1

YES