[ABC163F] path pass i


题目描述给定一棵 nnn 个点的树,给第 iii 个点染上颜色 cic_ici​,其中,cic_ici​ 为 [1,n][1,n][1,n] 的一个整数。现在,对于每一种颜色 kkk,你要求出有多少条简单路径满足路径上至少有一个点的颜色为 kkk。(1≤k≤n≤2×1051 \le k \le n

解题报告 $2022.10.18$


T1 不稳定的道路题目描述有 nnn 个城市和 mmm 条道路。城市编号 至 ,道路编号 111 到 nnn。道路 iii 双向连接城市 aia_iai​ 和城市 bib_ibi​。但是通过每一条道路,所需的时间却是不稳定的,跟出发的时刻有关,如果在时刻 ttt 通过道路 iii,那么需要的时间为:

[CERC2014]The Imp


题目传送门题目传送门思路Lemma. 按照 viv_ivi​ 升序购买一定最优。Proof. 设先后购买的为 (v1,c1),(v2,c2)(v_1,c_1),(v_2,c_2)(v1​,c1​),(v2​,c2​) 其中 v1≤v2v_1 \le v2v1​≤v2。此时的答案为 min⁡(v1−c

[POI2010]MOS-Bridges


题目描述洛谷传送门LOJ 传送门思路好恶心好恶心的网络瘤题,属于是知道结论就会做但是会写挂的题,佩服出题人脑洞。性质:对于一条欧拉回路,每个点的入度 = 出度首先可以考虑二分答案,二分最小权值 xxx,对于每个 xxx,我们可以建出一张图来,在这张图中,我们把所有不符合条件的边砍掉(变成有向边,记得

[HAOI2016]字符合并


在一场战争中,战场由 $n$ 个岛屿和 $n-1$ 个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为 $1$ 的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他 $k$ 个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。

[ARC069D] Flags


Snuke 将 $N$ 个标志放在一条线上。 第 $i$ 个标志可以放置在坐标 $x_i$ 或坐标 $y_i$ 上。 Snuke 认为当他们中的两个之间的最小距离 $d$ 更大时,标志看起来更好。找出 $d$ 的最大可能值。

[NEERC2013]Interactive Interception


平面上有一个点,初始位置 $x\in[0,p]$,速度 $q\in[0,v]$,其中 $p,v$ 是给定的。 你可以进行不超过 $100$ 次询问,形如 ``check L R``,满足 $0\le L\le R\le 10^9$,交互库会告诉你是否有 $x\in[L,R]$,每次询问之后,交互库会令 $x\gets x+q$。你需要在某个询问后确定此时的 $x$,并告诉交互库,格式形如 ``answer x``。

[NOI2012] 美食节


作为一个喜欢尝鲜的美食客,小 M 自然不愿意错过这场盛宴。他很快就尝遍了美食节所有的美食。然而,尝鲜的欲望是难以满足的。尽管所有的菜品都很可口,厨师做菜的速度也很快,小 M 仍然觉得自己桌上没有已经摆在别人餐桌上的美食是一件无法忍受的事情。于是小 M 开始研究起了做菜顺序的问题,即安排一个做菜的顺序使得同学们的等待时间最短。

[JSOI2016]飞机调度


JSOI 王国里有 $N$ 个机场,编号为 $1$ 到 $N$。从 $i$ 号机场到 $j$ 号机场需要飞行 $T_{i,j}$ 的时间。由于风向,地理位置和航空管制的因素,$T_{i,j}$ 和 $T_{j,i}$ 并不一定相同。 此外,由于飞机降落之后需要例行维修和加油。当一架飞机降落 $k$ 号机场时,需要花费 $P_k$​​ 的维护时间才能再次起飞。 JS Airways 一共运营 $M$ 条航线,其中第 $i$ 条直飞航线需要在 $D_i$ 时刻从 $X_i$ 机场起飞,不经停,飞往 $Y_i$ 机场。 为了简化问题,我们假设 JS Airway 可以在 $0$ 时刻在任意机场布置任意多架加油维护完毕的飞机;为了减少飞机的使用数,我们允许 JS Airways 增开任意多条临时航线以满足飞机的调度需求。 JYY 想知道,理论上 JS Airways 最少需要多少架飞机才能完成所有这 $M$ 个航班。

不定元任意范围的整数解个数


给出方程: $\sum_{i=1}^nx_i=s$ 其中 $f_i \le x_i \le g_i(1 \le i \le n)$。 求这个方程组的解的个数 $ans \% 1000000007$。