题目地址 经典状态压缩题，思路挺巧妙的。（也可能是我太蒻了吧）、、、 题解 我们要从 \([0-m]\) 中间选一个数 \(x_0\) 使得最后的攻击力最大。 如果从二进制的角度来观察 \(x_0\) ，你就会发现一系列的 \(\text{xor}\)、 \(&\) 、 \(|\) 操作只不过是 \(x_0\) 二进制下的每一位在进行这一系列操作，使得最后的答案最大。 “换言之，对于任意的 k（0<=k<=30）,‘ans 的第 k 位是几’只与‘ \(x_0\) 的第 k 位是几’有关” 于是考虑二进制下填位的方法，从高位到低位依次填 \(1\) 或 \(0\) \(x_...

最短Hamilton路径 经典状压DP，以后还是要多练习练习。 题解 设 \(f[i][j]\) 表示 \(i\) 状态 ， 最后一个点落在 \(j\) 点的最短路径。 记住，i是一个状态，是二进制的状态压缩。 那么我们来推推公式，推出来后是这个样子： \[f[i][j]=\text{min }\{ f[i\text{ xor }(1<<j)][k]+dis[k][j] \}\] 我们设\(k\)是上一个节点，转移到\(j\)节点。 xor是异或 ，i xor (1<<j)表示 i 状态二进制下第 j 位取反。我们当做这个状态下还没有来过 j 节点，现在在k节点 理解了...

题目地址  方法一 （口胡一下就好了啊）  快速幂思想的灵活运用。 把 \(b\) 用二进制表示 , 设 \(b\) 在二进制下有 \(k\) 位 , \(c_i\) 表示 \(b\) 在二进制下的第 \(i\) 位 \[b=c_{k-1}*2^{k-1}+c_{k-2}*2^{k-2}+...+c_{0}*2^{0}\] 根据加法原理，\(a*b\) 相当于 \(b\) 个 \(a\) 相加，现在把 \(b\) 用二进制表示，那么就有： \[a*b=c_{k-1}*2^{k-1}*a+c_{k-2}*2^{k-2}*a...+c_0*2^0*a\] 根据模运算的规则，边运算边取模。 再打上类...

目标 && 前言 近期的目标就是刷《算法竞赛——进阶指南》这本书  先花两三天左右把 0x00 基本算法 刷完，好的题目我录下来。 用一两天快速地把 0x10 基本数据结构 刷完，因为比较简单。好的题目录下来。 0x20 搜索 先放在这边，因为我觉得搜索比较毒瘤，过了初赛再刷搜索，顺便提高代码能力。 0x30 数学知识 数学我不太擅长，先留着 0x40 数据结构进阶 马上就要开学了，这个看看一周到一周半的时间能不能刷完，好的题目我会录下来。 0x50 动态规划 刷完上面这个就要赶紧刷下面这个，两周到三周，重难点，好的题录下。 0x60 图论 两到三周 刷完这里水平应该就上来了，...

RT，求助

可达性统计 题目地址（牛客） 一道比较经典的拓扑排序题 题目描述 给定一张\(N\)个点\(M\)条边的有向无环图，分别统计从每个点出发能够到达的点的数量。\(N,M≤30000\)。 题解 设从点 u 出发能够到达的点构成的集合是 f(u)，从点 u 出发能够到达的点，是从 u 的各个后继节点 v 出发能够到达的点的并集，再加上点 u 自身。先按照拓扑排序算法求出拓扑序，然后按照拓扑序的倒叙进行计算------因为在拓扑序中，任意一条边 (u ,v)，u 都排在 v 之前。倒序处理即可。 Code #include<algorithm> #include<iostream&...

前言 又是卡在了T4 ， 总分 100 + 200 + 300 = 600pts rank 2449。以后还是要多积累比赛经验。   A 输出a+b，a-b，a*b中最大的数，还要多简单？不挂代码了 Ｂ 题目描述  数字线上有2000001块石头。这些石头的坐标是- 1000000，- 999999 ，- 999998 ，... ，999999 ，1000000。其中，一些ķ连续的石头涂成黑色，其他石头涂成白色。另外，我们知道坐标X处的石头黑色的。打印所有可能包含黑色石头的坐标，按升序排列。  数据范围  1 ≤ ķ ≤ 100 0 ≤ X ≤ 100 输入中的所有值都是整数。  看不懂？（我...

前言 今天突然想到开个学习录，督促并记录自己学习，制定计划，实施计划。 Day 1 今天上午只A两道，下午只A两道，晚上肝到23:28才补完一场牛客普及模拟，眼睛身体都有点不适。 明天不要熬夜了，提高效率。 早上早起，读点书。上午做个4.5道题，把题单补起来。下午学算法（二分图），刷题（图论）4.5道，晚上再补一场比赛，写题解。有时间还可以做点作业。  Day 2 这天白天在正常刷题。 晚上想补一场提高模拟，如下 边独立集 && 牛客OI周赛1-提高组 A 分组 类似。这两道题的思路有点像我都没有做出来 自闭了！自闭了！   烂大街？ 我看是我烂大街了，极度自闭 明天加快效率学...

比赛地址 A 小Q想撸串 题目分析 普及T1水题惯例。字符串中找子串。 Code #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); } ...

前言  开个题单补点题 题单 边独立集 && 牛客OI周赛1-提高组 A 分组 类似。这两道题的思路有点像我都没有做出来 自闭了！自闭了！   烂大街？ 我看是我烂大街了，极度自闭 CF1185D, CF1183H, CF1183F, CF1182E, CF1182D, CF1182C, CF1188C, CF1187D, CF1187F, CF1187E, CF1197D CF1185D 等差数列知识 + 思维。 排序后处理显然无错，把相邻两两数的差存起来，看是否有差值出现的次数>=n-3（n-1，n-2，n-3），可否用来作为公差。考虑一共有n-1个差值，删去一个数后...

前言 比赛地址 这是我第一次发比赛的完整题解，留个纪念吧QwQ。 这场比赛A,B,C都比较水，D题想了想，E,F有点难（这是本蒟蒻的感受，有些大佬轻松AK了） 最后得分 100 + 200 + 300 = 600 ，rank A 题意： 有两个瓶子，1号瓶有A升水，总共可以***升，2号瓶有C升水，尽可能多的把2号瓶的水移到1号瓶，求2号瓶最后有多少水。 签到题，小学数学题，还剩C-(B-A),如果<0,则输出0。 B 题意： 给你一个数\(n\)，让你求出所有 在\(1\)~\(n\)之间的位数为奇数个的数 的数量 题目分析 跟 <数字统计> 差不多，n的范围小， 暴力枚举...

前言 我就是看blog看懂的，直接上blog吧，如果哪天有空再放我自己的讲解。 blog推荐 基本图论-连通分量(tarjan强/弱联通 割点/边 边/点双) 刷题 提前声明 有一些题目我会写代码，并且挂上去。 有些不会（懒） 题目 P3387 模板 + topo排序 + 超级简单DP 。如果不会topo排序的赶紧去学一下吧 推荐blog传送门 P1262 点与点连边，如果有点到不了，则输出NO，从大到小找点输出；反之输出YES，如果图中无环，直接topo排序输出所有入度为0的节点，如果有环，则是在环上找一个最小的节点。故Tarjan缩点，再topo排序 P2542 看起来是道图论题，缩点什么...

前言 上个学期学了一下KMP，基本上都忘光了，因为没有完全理解透彻。 学算法还是要理解清楚的，所以这次我又通彻地学习了一下KMP算法。 这篇博客以推荐文章为主，我自己的见解比较少（因为我太懒了）。 Blog推荐 KMP ----从入门到理解到彻底理解 自己的总结 KMP其实也不难，就两个过程 （S[ ]是文本串，就是长的字符串，T[ ]是短的单词）  匹配 ：当匹配字符失效 ，即\(S[ i ] != T[ j ]\) , 那么 \(j\) 指针指向 \(next[ j ]\) , 即 \(j = next[ j ]\) 求next：\(next[ j ]\) 就是单词\(T[ 0 ~ j-1...

动态规划学习 前言 以前我也算是接触过一点DP，陆陆续续学了一些背包问题，线性动规和区间动规。现在我再次发现了动规的重要性，决定在暑假里专门刷一些动规题。这篇blog主要记录我刷过的一些DP题。 引用 _皎月半撒花 大佬的一段话  动态规划自古以来是\(dalao\)凌虐萌新的分水岭，但有些\(OIer\)认为并没有这么重要——会打暴力，大不了记忆化。但是其实，动态规划学得好不好，可以彰显出一个\(OIer\)的基本素养——能否富有逻辑地思考一些问题，以及更重要的——能否将数学、算筹学（决策学）、数据结构合并成一个整体并且将其合理运用\(qwq\)。  推荐 （大佬的blog）   <什...