魔法学院 题目描述： 亚可喜欢上了收集不包括空格的可见字符(ASCII码为33~126)，在她眼中，一个字符的价值为其ASCII码大小，比如’a’的价值为97。 目前她已经收集了n个不包括空格的可见字符，第i个字符为Si。可是她想要把自己收集的n个字符的价值和最大化，因此去请求了戴安娜的帮助。 戴安娜有m种魔法，第i种魔法可以将[li,ri]区间的一个字符替换为ci。因为戴安娜出色的魔力，所以每种魔法都可以使用无限次。 请问戴安娜使用完若干次魔法后，亚可收集的n个字符的最大价值和可以是多少？ 思路1: 差分 + 贪心 对于每个字符，我们更新他能影响的所有的点的答案，最后计算所以点的答案和...

牛客小白月赛44 深渊水妖 题目描述： 找到所有极长的不严格上升段，并找出它们当中右端点权值 - 左端点权值最大的那些个段，输出端点坐标 思路： 模拟就行，千万要注意是权值的差的最大值，而不是r - l + 1的最大值 #include <bits/stdc++.h> using namespace std; #define endl '\n' #define inf 0x3f3f3f3f #define mod 998244353 #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d %d",&n...

数字游戏 题目描述： 一个x ，当x不为零时进行如下操作 如果二进制x中有奇数个1，则x二进制形式下最低位取反 如果二进制xxx中有偶数个1，则x二进制形式下非前导零最高位取反 询问对于一个x，操作几次后变为零 思路1： 对于奇数的情况，其实就对x异或了1 对于偶数的情况，其实就是把第一个的1去掉了，这里可以使用lowbit，一个数减去p次lowbit后等于0，就说明他有p个1，且可以获得第一个1对应的值，这样就可以实现判断与去掉第一个1 #include<map> #include<set> #include<stack> #include&l...

梦想赛道 题目描述： 给出一颗树，你需要构造一个图使得这个树在这个图中是一个严格的次小生成树，问图的权值最小可以是多少 思路： 只需要在原树的基础上加一条边即可，因为是要最小权值，所以我们就加1，（加0的话就不是严格的次小生成树了，况且题目中给的最小权值就是1） 有个特殊的情况就是如果这个树的权值全是1，那就无法构造了，因为如果加1，就不是严格次下生成树，如果加大于1的值，就变成最小生成树了，所以这里判一下就可以 /* Work by: Chelsea Problem: 不知名屑题 Knowledge: 垃圾算法 Time: O(能过) */ #include<map> #...

憧憬 题目描述： 给出n个向量，以及一个目标向量，问能否通过n个向量中两个向量相加来构造出一个与目标向量平行的向量 思路： 签到题 枚举+判断 n个向量两两组合得到所有的向量，然后挨个与目标向量进行判断即可 判断向量(a, b) // (c, d)的条件是：a * d = b * c 坑点： 一个向量不可以同时使用 /* Work by: Chelsea Problem: 不知名屑题 Knowledge: 垃圾算法 Time: O(能过) */ #include<map> #include<set> #include<stack> #includ...

嗅探器 题目描述： 红蓝军队打演习，蓝军有两个信息中心，红军计划在某个中间服务器上安装一个嗅探器，来获得蓝军情报，而蓝军网络相当庞大，数据包从一个信息中心传到另一个信息中心不止一条路，你需要将嗅探器安装到哪个中间服务器才能保证所有数据包都能被捕获 思路： 转换一下其实是找割点，但不仅仅是割点，是能将两个信息中心隔开的割点，只有割点才能将这两个信息中心隔断，不能进行信息交流，但如果判断这个割点能否将这两个信息中心隔断呢？ 我们以其中一个数据中心a为起点使用tarjan，如果遇到了割点，就说明这个割点的dfn值一定大于等于a，此时判断一下这个割点是不是a或b，如果不是，且dfn[b] &gt...

Cow Ski Area 题目描述： 滑冰，给你一个地图，值代表高度，你只能从高到低滑，相同高度的点可以随便滑，除了根据势能来滑动，你还可以建造传送门，可以无视传送机起点到终点的高度随便走，即双向的，众所周知，传送门很贵，你现在想知道最少造几个传送门使得任意一个点都可以滑到全图所有点 思路： 和Network of Schools差不多，这次只需要求出max(入度为0，出度为0)即可，仔细想一下，这个题真的需要建图吗？建图的意义是什么？在上一个题，建图的意义是使用tarjan缩点，但是这里给出了地图，相同高度的点可以随便到，就相当于一个点，这不就和缩点一样了嘛，那我们干嘛还建图跑tarj...

[ZJOI2007]最大半连通子图 题目描述： 给你一个图G，让你求最大半连通子图拥有的节点数K，以及不同的最大半联通子图的数量C，C要对X取模 思路： 这是一个比较复杂的题？ 主要思路是：tarjan缩点+拓扑排序+dp 首先使用tarjan缩点，得到一个有向无环图，缩点的时候需要记录每个点集有的点数， u和v都是缩点后的点，且有u指向v的边，val指的是点集中的点数，f[i] 数组表示从起点出发到 i 的最大半连通子图的数量， 使用拓扑排序，从入度为0的点开始，使用dp，有两种情况： ​，此时dp[v]的值就可以修改了，dp[v] = dp[u] + val[v], f[v] = ...

[HAOI2006]受欢迎的牛 题目描述： 众所周知，喜欢是可以传递的（bushi，给你N头牛，给你M对喜欢关系，如果A喜欢B，B喜欢C，则我们认为A也喜欢C，现在需要求有多少头牛被所有牛喜欢 思路： 还是先进行tarjan缩点，当且仅当存在一个出度为0的点集，则输出该点集的数量，否则输出0 为什么呢？缩点以后得到的个有向无环图，如果一个点出度不为0，则他必然是一条路径的中间位置，也就是他指向下一个点，而因为是无环，则下一个点是不会指向他的，所以他已经不符合所有人都喜欢他的条件了，再说为什么必须只有一个，因为如果存在多个，这些点的出度都为0，那这些点都没法到达别的点，这样就不会存在一个点...

可达性 题目描述： 给出一个 0 ≤ N ≤ 105 点数、0 ≤ M ≤ 105 边数的有向图， 输出一个尽可能小的点集，使得从这些点出发能够到达任意一点，如果有多个这样的集合，输出这些集合升序排序后字典序最小的。 u1s1，这个题目描述讲的很难懂，你说是阅读理解都不为过，特别是最后一句，什么叫这些集合生序排序后字典序最小的？我一开始理解的是“输出这些集合升序排序后字典序最小的那个集合的元素”，但听雨巨的意思是，“将每个集合升序排序后，输出每个集合的第一个元素”，艹？ 思路： 说简单点就是缩点，计算缩点后每个点集的入度，输出每个入度为0的点集中最小的点的序号 那为什么要看入度为0的呢？...

Antenna Placement 题目描述： N * M的棋盘中，'o'代表障碍物，'*'代表空位，你可以使用1 * 2的多米诺骨牌放进空格，米牌可以重叠，也可以放在障碍物上，问最少使用多少牌使得放满所有空位 思路： 和上次那个棋盘问题很相似了，不过这次可以重叠了，那我们只需要计算出最大匹配值，然后就可以得出单放的空位是多少，最后需要放的牌的数量为：，num是空位的多少，pi是最大匹配数 #include<map> #include<set> #include<stack> #include<queue> #include<cma...

棋盘覆盖 题目描述： N * N的棋盘，已知某些位置不能放东西，求最多能往棋盘上放多少块1 * 2的多米诺骨牌，可以横着放，也可以竖着放，且任意两张多米诺骨牌都不重叠 思路： 都不重叠，就有点像二分图左右两集合内没有边相连的那意思了 有点绕其实，因为多米诺骨牌是1 * 2的，我们就将其看成一个左集合元素，一个右集合元素，也就是将原来的棋盘变成类似一个黑白相间的国际象棋的棋盘，黑色是左集合，白色是右集合 连边的时候，我们只需要对所有的左集的点去连接四条边。同样的是因为多米诺骨牌是1 * 2，所以连边的时候是连这个点与上下左右四个点中非禁止的点。 这里处理图、连边的时候不是很好处理，看代码应...

[ZJOI2007]矩阵游戏 题目描述： 给你一个N*N的矩阵，0代表白色，1代表黑色，你可以任意交换矩阵的两行或两列，问交换若干次能否使得方针的主对角线的颜色均为黑色 思路： 首先思考一下交换行和交换列的目的 交换行，假设该行最终交换到了第 i 行，也就是代表该行的第 i 个元素必须是黑色，当然这行不一定只有第 i 个是黑色，也就是说他可以换到任意一个黑色对应的行，举个例子：假如该行 3 5 7的位置是黑色，那最后代表他可以换到3 5 7行去 这样其实就不用交换列了，因为换行已经解决了 这时候左集合是行，右集合是列，算最大匹配数是不是n即可 #include<map> #...

Asteroids 题目描述： 给你一个n*n的地图，地图上有些点有外星生物，你有太空武器，一次可以杀死一行或一列的外星生物，问你最少需要几次攻击能杀死全部的外星生物？ 思路： 感觉这个题见了很多次，但好像又没有写过？ 贪心是肯定不行的，举个例子： 如果挑最多的一行或一列去贪心的选的话就会选四次，但其实选三次就可以了，所以贪心不可取 这里其实是用二分图匹配来做 左集合放1～n行，右集合放1～n列，然后按输入给的连边，那我们现在要做的就是选出最少的点使其能覆盖所有的边，相当于找最小点覆盖数，而最小点覆盖数就等于二分图最大匹配数，那问题就很简单了，跑一遍匈牙利即可 #include&l...