Deep_Kevin的娱乐空间

前话      图是一种非常重要的数据结构，描述对象复杂的练习。这里开始接触图的基本概念。          掌握好了图，在比赛中就可以拿到大部分的分数。正题      第一题：信息传递      这道题比较容易，有两种做法，一个是并查集，一个是深搜。      个人认为并查集会快一些。。。      当然暴力搜索也不能忽视，本题可以转化为一个求最小环的过程，然后每个点进去搜一遍，如果已经遍历过一...

正题      题目链接点这      如果我们给一条边加1的流量，那么费用是不是多了，给一条边减1的流量，那么费用多了。      这两个都是挺明显的吧。      考虑怎么保证流量平衡。      设原边为。      那么建两条边，，现在改一个环就可以使得流量平衡。      为什么？      假设这个环先走了一段一类边，再走了一段二类边，然后再走了一段一类...

专题测试 今天早上的题都是搜索。 第一题：给出n个开关，一个开关对应一个灯，灯与灯之间有连边，当摁下一个开关时，对应的灯和相邻的灯都会改变状态，问至少摁下多少开关，才可以把所有灯打开。 这道题很容易就可以想到一个结论：一个开关只会被打开一次，打开两次没有影响。 就可以直接爆搜拿到60分。满分也很简单，我们折半搜索，把第一次搜索的结果存在一个m...

综合测试 考试的前一天老师说今天的题比NOI稍微简单一些。 第一题，给你n，要你求。定义为其所有约数的异或和。. 这题还是比较简单的，直接数论分块，讨论那些为奇数就行了。 求前缀和的时候考虑相邻两个数（偶奇）的异或和为1.然后讨论一下情况就可以了。#include<cmath>#include<cstdio>...

水法测试 第一题：小 M 培养了 n 个菌落。其中每个菌落有质量和颜色两种属性，颜色只可能为紫色或 红色。小 M 想把所有的菌落合并成一个菌落。 因为合并的过程非常费劲，小 M 每天只能进行一次合并，整个过程需要进行 n-1 天。 一次合并会将两个菌落变成一个菌落。如果原来两个菌落的颜色相同，两个菌落会进行融合， 新的菌落质量为原来两个菌落质量之和，颜色不变；如果原来两个菌落的颜色不...

正题 这题还是挺好玩的吧。 首先我们考虑插头Dp，如果当前位置有一个插头，那么这个位置只能取消这个插头，然后继续传递，如果没有插头，就可以选择在这个位置上放一个插头，或者如果下一个位置是没有插头的话，可以在下一个位置放一个插头。 我们发现状态数很少。只有那么多种。所以我们就可以直接枚举每一种状态，看一下它转移到下一层时，可以转移到那些状态，我们用一个矩阵记...

正题 今天讲的是一些杂题 一开始的是一些搜索。 1.长度为N的数列，已知N个前缀和以及N个后缀和共2N个数打乱后的结果，已知数列中每个数的范围是不超过500的整数，求原数列，存在多组时间求字典序最小的。1<=N <= 1000 我们考虑将整个序列从小到大排序，然后第一个元素一定是F[1]或者G[1]。就这样按顺序得向下选，就可以...

正题 搜索要明确状态，操作，性质，事先思考怎么搜合适，即怎么搜会更快，不要碰到题就开始搜，剪枝也最好在写题前写好想好，剪枝放在一起放在最前面。 搜索的本质：一棵树或图。 特征：1.树或图较大，无法存储。（存的下就可以Dp，递推，也就是记忆化搜索 2.限制条件比较充分。 在做题的时候考虑三个方面： 1.当前搜的状态，...

正题 “诶，今天讲最小生成树哎。不听了，我刷我自己的题。。”------来自某位神犇。 太难了。 求解最小生成树有两种方法Kruskal和Prim算法，图较为稀疏的情况下，我们一般选择前者。图较为稠密的情况下，我们一般选择后者。 只讲一些我原先不懂得例题。（即使我懂的也就那几道。。。 例题1：动态图连通性 给定一个...

正题      这一题挺水的？      直接随便求一条1到n的路径异或和，建出Dfs树，每一条返祖边与两点之间路径异或和组成环，扔进线性基，最后维护一遍即可。      首先证明为什么只用扔返祖环和为什么可以扔环？      先解决第二个问题，每一个环肯定可以从1走到其中的某个点上，遍历一遍这个环，在从开始遍历的那个点回去。      那么1到这个点就被遍历了两遍，异或和为0...

正题      第六题：新汉诺塔      这题的问题：     1.怎么保证放好之后当前位置的点下面没有更小的点     2.怎么通过第三根柱子把自己运到目标柱子上。     解决方法：     1.从大往小做，先处理大的在处理小的。     2.把小于当前圆盘编号的圆盘先移动到第三根柱子，再把自己移动到目标柱子。代码&lt;挺短的&gt;，变量名帮助理解（where，现在在哪）（shuold，...

正题      第二题：封锁阳光大学      这道题看上去好像想到了网络流最小割？？      其实不用那么麻烦，用染色法，如果图中的肯定黑白相间，那么就有两种状态，选黑的点，选白的点，看一下哪一种点数比较少，就直接输出即可。      如果把每个点设置一个点权，那么就肯定要用最小割来做咯。。代码&lt;哇这个简洁&gt;// luogu-judger-enable-o2#include&lt...

正题      第三题：无序字母对      首先这题如何判No Solution相信大家都会，因为就是欧拉回路一笔画，有解当且仅当度为奇数的点有两个或没有。      大概就是这样吧，证明不怎么会。。。（我比较菜）。       否则就用矩阵记录一下有边的点，然后选出最小的点，遍历即可。代码&lt;邻接矩阵更简单哦~&gt;#include&lt;cstdio&gt;#include&lt;c...

正文      第四题：[USACO08DEC]Trick or Treat on the Farm      其实这道题已经规定了每个点的出度只有1，那么就很好做了。      每个点建立一个时间戳数组d[i]，初始化为0，当一个点从自己出发，回到了自己，那么就等于，回到的时间戳-1就是所在环的大小。      如果一个点不在环中，那么，他一定可以遍历到一个在环的点，用到这的时间戳+这个环的大小...

开头     开始提高组的试炼。这里已经去除了所有普及组难度的题目。哼哼，怕了吧。。正题      别怕我们一起来。。。      搜索是暴力之本，在茫茫大佬中，打得一手好搜索骗分可以不用惧怕大佬diss飞。正题      第一题：小木棍P1120.      这题不错，很暴力。      看题意，聪明的同学很快就想到二分枚举+贪心判正确性，那么十分遗憾地告诉你错了，因为贪心这种东西一定要满足“选...

正题      废话不多说因为这题有点简单。      第二题：油滴扩展       看到数据很开心&lt;n&lt;=6&gt;,废话不多说暴搜。FFF（Fast,Fast,Fast）      具体做法不用多说直接看一下当前的油滴距离方框四周的距离和其他已放置油滴的距离即可，扩展之后放下一个，注意精度。代码&lt;不喜勿喷&gt;#include&lt;cstdio&gt;#include&...

正题      第三题：引水入城      具体地说，从每一个点向周围bfs，找到能覆盖的最右端和最左端，记录下来。然后这段区间就是它所管辖的范围。剩下的事情就是区间DP。      enenen.      可能很多人想问，为什么找出左端点和右端点就可以保证全覆盖。因为题目如果有解，就不存在其中有一个点比其他的点都高。      具体还是看代码// luogu-judger-enable-o2...

慢慢悟。。正题      第四题：Mayan游戏      很无聊的一道题-_-（所以调了那么久？？）      我们可以优先考虑右移，如果左边为空我们才往左移。      交换两个颜色相同的块没有意义。      注意抵消之前，我们需要先找出来，要不就判不到那个十字的情况。代码&lt;注意函数名&gt;#include&lt;cstdio&gt;#include&lt;cstdlib&gt;...

正题      第五题：砝码称重      没错，dfs+判断，      可以不用加优化。取走k个点之后，用01背包算一下有多少种状态即可。#include&lt;cstdio&gt;#include&lt;cstdlib&gt;#include&lt;cstring&gt;int n,m;int a[25];int max=0;bool tf[2010];bool we[201...

正题 第一题：.字符串复制 定义一次变换：。 现在给出，问令的最小的是多少。 首先判断无解的方法就直接看一下下面出现字符的顺序是否可以对上S0中的一个子序列。 如果有的话，那么就可以构造一组解。考虑第一次变换之后是什么样子的：对于一个t中的连续子段必定对应一个S0中的位置x，那么我们将覆盖，我们没办法覆盖下一个x的位置，否则下一...