题目描述 “我要成为魔法少女！” “那么，以灵魂为代价，你希望得到什么？” “我要将有关魔法和奇迹的一切，封印于卡片之中„„” 在这个愿望被实现以后的世界里，人们享受着魔法卡片（\(SpellCard\)，又名符卡）带来的便捷。 现在，不需要立下契约也可以使用魔法了！你还不来试一试？ 比如，我们在魔法百科全书（\(Encyclopedia of Spells\)）里用“\(freeze\)”作为关键字来查询，会有很多有趣的结果。 例如，我们熟知的\(Cirno\)，她的冰冻魔法当然会有对应的 \(SpellCard\) 了。 当然，更加令人惊讶的是，居然有冻结时间的魔法，\(Cirno\) 的...

题目描述 \(Alice\)和\(Bob\)现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在\(n\)个城市设有业务，设这些城市分别标记为\(0\)到\(n−1\)，一共有\(m\)种航线，每种航线连接两个城市，并且航线有一定的价格。 \(Alice\)和\(Bob\)现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多\(k\)种航线上搭乘飞机。那么\(Alice\)和\(Bob\)这次出行最少花费多少？ 输入输出格式 输入格式： 数据的第一行有三个整数，\(n,m,k\)，分别表示城市数，航线数和免费乘坐次数。 ...

今日小结：今天做了几道分层最短路的题目和几道最小生成树的题目，然后给他们讲了两道题，晚上剩下的时候看了些\(tarjan\)，割点那块有点懵。 一. 今日完成的题目： 洛谷P3831，洛谷P4568，洛谷P4822，洛谷P2939，洛谷P1265，洛谷P1318，洛谷P1547，洛谷P4018 二. 1. 当天完成题目数：8道。 2. 未完成6个题目的原因： 3. 复习的知识点：分层最短路，tarjan，最小生成树。 三： 1. 洛谷P3831 回家的路 题目背景 SHOI2012 D2T1 题目描述 \(2046\) 年 \(OI\) 城的城市轨道交通建设终于全部竣工，由于前期规划周密，建成...

题目背景 SHOI2012 D2T1 题目描述 \(2046\) 年 \(OI\) 城的城市轨道交通建设终于全部竣工，由于前期规划周密，建成后的轨道交通网络由\(2n\)条地铁线路构成，组成了一个\(n\)纵\(n\)横的交通网。如下图所示，这\(2n\)条线路每条线路都包含\(n\)个车站，而每个车站都在一组纵横线路的交汇处。 出于建设成本的考虑，并非每个车站都能够进行站内换乘，能够进行站内换乘的地铁站共有\(m\)个，在下图中，标上方块标记的车站为换乘车站。已知地铁运行 \(1\) 站需要 \(2\) 分钟，而站内换乘需要步行 \(1\) 分钟。\(Serenade\) 想要知道，在不中途...

今日小结：昨天晚上看了一晚上二分，然后今天整理了二分博客，做了五六道二分题目，还做了一两道DP题目。 一. 今日完成的题目： 洛谷P1163，洛谷P1168，洛谷P1571，洛谷P1678，洛谷P1918，洛谷P4771，洛谷P1412，洛谷P3918。 二. 1. 当天完成题目数：8道。 2. 未完成6个题目的原因： 3. 复习的知识点：二分，DP。 4. 不会的题目：洛谷P2757。 整理的二分博客： 二分查找 三. 1. 洛谷P1163 银行贷款 题目描述 当一个人从银行贷款后，在一段时间内他(她)将不得不每月偿还固定的分期付款。这个问题要求计算出贷款者向银行支付的利率。假设利率按月累计...

一：二分查找定义： 二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 ——百度百科 二：二分查找基本操作： 1、找到该值在数组中的下标 inline int fin...

T1 偶数输出n/2 奇数输出(n-1)/2即可 T2 判断是不是回文 不是直接输出子串 是回文继续判断 如果他前(len+1)/2内没有相同 输出-1 其他的 交换不同字符，输出子串 T3 贪心+二分 因为要满足\(b_i=a_i+a_{n−i+1}\) 也就是两边向中间，还要保证单调递增 那如果要让满足的结果最优 一定是左边尽量小，右边尽量大 每次二分答案就可以 复杂度\(nlogn\) T4 每一个联通块分别二分图判断一下 染色判断就可以 ans就是每个块的乘积 每个块可以分成两部分 贡献就是是\(2^{一部分个数}+2^{另一部分}\)

线段树： #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #define lson rt<<1 #define rson rt<<1|1 #define ll long long using namespace std; inline ll read() { char c=getchar();ll num=0,f=1; for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isd...