这道dp题，我卡住了。主要是我陷入了一个思维误区。没有好好分析题目，获得所有的条件信息。我是这样想的。对于每一个时间i我有两种选择1.拿后面没拿的2.拿前面没拿的 但是，这种分析十分的困难，我还要判断是否此刻有料理为最佳出锅时间。真的是十分麻烦。 我漏了一个重要信息：其实，我们完全可以从头往后拿！！！！对于任意时刻，你拿前面或者你拿后面收益其实是相等的！！！！！！也就是，我们可以这样总结状态dp[i][j]在第i分钟，拿了前j个料理的最小不愉快度 那么，既然那前面和拿后面都一样的话，到底什么取决最小不愉快度呢？拿不拿的问题，即在一些时间我可能是不拿的。算上不拿的时间，其实我最多会耗到2*n的时...

考试周，好久没刷题了最近，kuangbin的题单暂时 松一松 。大概松半个月左右。cf上分要抓紧了。 这题我没看出来，我是有思路的。我们注意到，对于一个操作：- num1如果他的前面有- nun2若num2>num1则在num2后面，num1应该放置。num1是绝对不可以放在num2前面的。且- num1这个操作实行前一定要放置num1 根据这个信息我们想想到底应该怎么放置就近放置 优先队列存储pos遇到一个+就存上一个++pos遇到一个- 就在顶部的pos处放置 我们想想，我在最大 的pos处放置，能够最大限度地避免自己被放在前面比我大num前那问题来了，值会对后面的数无影响吗？如果正...

算是挺简单的。有一些坑点。我们通过分隔符将字符串们连接起来。注意分隔符不可以相等，否则在匹配时分隔符可能被算上。然后我们二分答案长度，进行height分组，判断是否可行。得到正确的长度后我们再去找子串，只要找到分组就好了，然后随便记录下分组中的一个坐标。之后将这些坐标按照ranks[i]序排序就好了。之后输出，每一个输出len长在二分判断时，我们要注意判断时n的奇偶。最方便的是乘2看是否大于n 代码如下： #include<iostream> #include<algorithm> #include<set> #include<vector> u...

这也是nim游戏，但是sg就不是一个数了，而是一个二元组。考虑到数据量，我们可以直接记忆化递归暴力求解sg值，然后再异或就可以了##代码如下： #include<iostream> #include<algorithm> #include<vector> #include<functional> using namespace std; int sg[1500][1500]; bool check(int x, int y) { return x >= 0 && y >= 0; } int SG(int x,int y...

很明显是nim游戏，考虑到数据量，我们无法老老实实的求解sg值。于是我选择打表找规律。老老实实地打到sg[100]我们就发现了规律。sg[i] i为偶数时sg[i]=i/2i为奇数时，如果sg[i-1]为偶数(此时i-1为偶数)那么sg[i]=sg[i-1]/2 如果sg[i-1]为奇数时，sg[i]=sg[i/2] (向下取整) ok初始条件为sg[1]==0(边界)那么我们就可以递归求解了。我们观察上述规律发现每次至少/2。而事实上很可能更快，所以复杂度应该小于O(nlogn)##代码如下： #include<iostream> #include<al...

nim 这算是一道变形的nim游戏的题目。这是从我学博弈论开始第一次独立做出来的 还算有点意思的博弈题目。 其实这里面的nim特征并不难发现。因为有符号'X'的存在将string划分成了几个小段。我们可以分别将这几个小段看成独立的nim游戏。最后再异或和，得到当前的sg值。从而判断这场游戏的胜负。 但是有几个坑点。我们先想想，sg[i]即长度为i的string其sg值毫无疑问，sg[0]==0又因为长度为1,2,3的string其子状态都长度为0的string所以sg[1]==sg[2]==sg[3]==1 为什么长度为1，2，3在选择一个点放置X后子状态都是长度为0的string呢？因为：对...

就是求桥而已，但是坑点很多。求出权值最小的桥，然后输出其权值。但是如果权值为零，我们仍要派一名士兵。另外如果图本身就不连通，我们优先输出0 代码如下： #include<iostream> #include<algorithm> using namespace std; const int max_m = 1e6 + 100; const int max_n = 1e3 + 100; struct edge { int to, rev, next, cost; }E[max_m << 1]; int head[max_n]; int cnt = 1;...

神题。。。。。。 本蒟蒻又刷到一个难题。不会做 查了题解后发现这是poj1904的变种。我只想说这题太牛逼了。给出poj1904的题解：https://www.cnblogs.com/zxndgv/archive/2011/08/06/2129333.html其实还是增广路的思想。由此引发到了强连通分量。这让我想到了以前做过的一道题，记得是判断最小割中割边的唯一性。好像也是用到了强连通分量。真的是非常巧妙，要对增广路有十分清晰的认识。同时，还应该充分利用完美匹配的条件。真的是太强了。至于这道题，我们因为刚开始不是完美匹配所以需要构造完美匹配：见题解：https://blog.csdn.net/...

anti-nim游戏 他有一个结论：1.所有的石子堆石子数都是1且sg=02.至少有一堆石子数不为1且sg!=0满足上述条件中的一个先手就必胜！！！ 首先，我们尝试证明(我的证明比较玄学。。。。。。)首先对于第一个条件，是显而易见的。石子数均为1，sg==0意味着有偶数个石子堆。sg!=0意味着有奇数个石子堆那么答案自然就清楚了 那么对于第二个条件：如果只有一堆的石子数>1的话，我们可以通过对这堆的石子进行操作利用第一种条件获取胜利。而如果有两堆或两堆以上的石子数>1的话呢？根据sg定理，我们一定可以找到一个操作，使得在保持至少两堆石子数>1的情况下sg==0 因为后手接到的...

差分约束系统 这是我第一次接触到差分约束系统。还行 a b c代表d[b]<=d[a]+c是否？我们就见一条边a->b代表d[b]<=d[a]+c那么我们求解d[1]与d[n]的最大区分则假设1到n之间有这样的条路经：e1,e2,e3......那么d[n]<=d[1]+e1+e2+e3......这个不等式要对所有的路径都成立。那么，自然要对和最小的哪一个路径成立啦即，最终答案就是最短路径 代码如下： #include<iostream> #include<algorithm> #include<queue> #include&lt...

强连通分量 我们利用强连通分量进行缩点。然后找入度为0或者出度为0的点。他们其中一个一定是在我们最终的图中被孤立的点。 为什么要这样说呢？因为你仔细想想啊。假如我没有边，我让你用最多的边连出一个不是强连通分量的图你是不是孤立一个点，使他只有出度没有入度或者只有入度没有出度？那，这里不也是一样的吗？！其实，顺着感觉走就可以了。然后我们统计就可以了。我们想对于一个出度为零或者入度为零的点，孤立他得到的最大收益应该为：n(n-1)-m-cnt[i](n-cnt[i]) cnt[i]指该连通块中的点的数量。这里用的是割补法求的，刚开始我想直接求，麻烦得很。。。。。。。。我们注意到，这个式子里面只有一...

血淋淋的教训！！！！！！！ 这一题我觉得出的很好。后缀数组+单调栈。 我们很容易想到两个字符串通过间隔符相连height分组筛选出来一堆互相最长公共前缀大于等于K的后缀但是如何统计他们之间的贡献却成为了一个难事情。这里我们使用的技巧叫做 单调栈！！！ 其实好久之前我就遇到单调栈了，但是当时没有钻研。。。。。。 分组之后，我们统计每一个区间中属于s2的后缀与他前面属于s1的后缀所造成的贡献这样再扫一遍统计属于s1的后缀与他前面属于s2的后缀所造成的贡献。那就是答案了。 这两个问题是对称的，我们来看第一个问题。假设我们对于s2的后缀i要统计他前面的s1的后缀对他的贡献 这是一个怎样的过程？我们从...

题意是真恶心！！！！！！！！但还好，锻炼了编码的能力。 代码： #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<vector> #include<queue> using namespace std; const int max_n = 550; const int max_m = 3000 * 8; struct AC_Automation { int teir[max_n * 65][300];...

nim 我们可以很清楚地看出来，这应该是一个nim游戏。因为，我们可以把它分为每一行地小博弈所组成的一个矩形的大博弈。那么我们的关注点就要放在，每一行上的小博弈上了。乍一看，这个小博弈很复杂。还牵扯到每一列。但是，我们究其本质还会发现，取哪一列其实并没有什么关系。是否？关键是我取了多少石子，还剩多少石。简而言之，我们根本不需要更关心每一列。直接统计每一行的石子数，做nim博弈就好了 代码如下： #include<iostream> #include<algorithm> #include<cstdio> using namespace std; typede...