Ender's blog

「洛谷P1220」 关路灯 题解 问题 原题链接 洛谷P1220 题目描述 某一村庄在一条路线上安装了 nnn 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。 为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。 现在已知老张走的速度为 1m/s1m/s1m/s ，每个路灯的位置（是一个整数，即距路线起点的距离，单位： mmm ）、功率（ WWW ），老张关灯所用的时间很短而可以忽略不计。 请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。 输入格式 第一行是两个数字 nnn （表示路灯的总数）和 cc ...

「BZOJ2744」 HEOI2012 朋友圈 题解 问题 原题链接 BZOJ2744 Description 在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。 两个国家看成是AB两国，现在是两个国家的描述： A国：每个人都有一个友善值，当两个A国人的友善值a、b，如果 axorb≡1(mod2)a xor b \equiv 1 \pmod 2axorb≡1(mod2) ， 那么这两个人都是朋友，否则不是； B国：每个人都有一个友善值，当两个B国人的友善值a、b，如果 axorb≡0(mod2)a xor b \equiv 0 \pmod 2axorb≡0(mod2) 或者 (aorb)(a or b)(aorb) 化成二进制有奇数个 111 ，那么两个人是朋友，否则不是朋友； A、B两国之间的人也有可能是朋友，数据中将会给出A、B之间“朋友”的情况。 在AB两国，朋友圈的定义：一个朋友圈集合S，满足 S∈A∪BS \in A \ ...

「HDU5093」 Battle ships 题解 问题 原题链接 HDU5093 Problem Description Dear contestant, now you are an excellent navy commander, who is responsible of a tough mission currently. Your fleet unfortunately encountered an enemy fleet near the South Pole where the geographical conditions are negative for both sides. The floating ice and iceberg blocks battleships move which leads to this unexpected engagement highly dangerous, unpredictable and incontrollable. But, fortunately, as an experienced navy comma ...

「HDU2819」 Swap 题解 问题 原题链接 HDU2819 Problem Description Given an N*N matrix with each entry equal to 0 or 1. You can swap any two rows or any two columns. Can you find a way to make all the diagonal entries equal to 1? Input There are several test cases in the input. The first line of each test case is an integer N (1 <= N <= 100). Then N lines follow, each contains N numbers (0 or 1), separating by space, indicating the N*N matrix. Output For each test case, the first line contain the ...

Learn English With HDUOJ undirected [adj.] 无向的 weighted [adj.] 加权的 denote [v.] 表示 navy [n.] 海军 tough [adj.] 艰难的、坚固的 fleet [n.] 舰队 encounter [v.] 遭遇 embattle [vt.] 布阵 cannon [n.] 大炮 engagement [n.] 交战、约会 arbitrary [adj.] 武断的 iceberg [n.] 冰山 column [n.] 列、柱子 unpredictable [adj.] 不可预测的 represent [v.] 相当于 battlefield [n.] 战场 respectively [adv.] 各自地 iteratively [adv.] 反复地 symbolize [vt.] 象征

k条白边最小生成树问题 问题 给定一张图，每条边都有一个权值和颜色，仅为黑色或白色，求一条恰好包含 kkk 条白边的最小生成树。 求解 这个问题与分数规划问题非常类似 给每条白边的权值都增加 CCC ，二分 CCC ，求此时的最小生成树总权值 www ，并求出这个树包含几条白边。 假如包含的白边数 r>kr > kr>k ，则增大 CCC ，否则减小 CCC ，直到 r=kr = kr=k ，则最小生成树的总权值则为 w−k∗Cw - k * Cw−k∗C

分数规划模型学习笔记 问题 给定 nnn 个二元组 (ai,bi)(a_i, b_i)(ai​,bi​) ，从中选出 kkk 个二元组使得 ΣaiΣbi\frac{\Sigma a_i}{\Sigma b_i}Σbi​Σai​​ 尽可能大，求出最小值。 求解 假设 ΣaiΣbi≥x\frac{\Sigma a_i}{\Sigma b_i} \geq x Σbi​Σai​​≥x 则可以将式子变形为 Σai−x⋅Σbi≥0\Sigma a_i - x \cdot \Sigma b_i \geq 0 Σai​−x⋅Σbi​≥0 对 xxx 进行二分，将 ai−x⋅bia_i - x \cdot b_iai​−x⋅bi​ 从大到小排序，选出前 kkk 个 ，判断式子是否成立，如果成立则增加 xxx ，不成立则减小 xxx ，直至求出最优解。

树链剖分学习笔记

线段树优化建图笔记 问题 给定 nnn 个结点， mmm 组边，第 iii 组边从 $ P_i$ 向 LiL_iLi​ 到 RiR_iRi​ 这段点号区间中所有点连一条长度为 ViV_iVi​ 的边，求最短路。 线段树使用 首先线段树每一个区间节点都向这个节点的子区间节点连一条长度为零的边，叶子结点向这个长度为 111 的区间所表示的点连一条长度为零的边。 如果有一组边为从 333 号点向 [4,8][4, 8][4,8] 这段区间连长度为 vvv 的边，则从 333 号点向区间节点 [4,4][4, 4][4,4] 连一条长度为 vvv 的边，再从 333 这个点向区间节点 [5,8][5, 8][5,8] 连一条长度为 vvv 的边，就完成了连边以及建图。 代码模板 在写了在写了