题目描述：在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。考虑一个约束满足问题的简化版本：假设 𝑥1, 𝑥2, 𝑥3, ⋯ 代表程序中出现的变量，给定 𝑛 个形如 𝑥𝑖 = 𝑥𝑗 或 𝑥𝑖 ≠ 𝑥𝑗 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为： 𝑥1 = 𝑥2, 𝑥2 = 𝑥3, 𝑥3 = 𝑥4, 𝑥1 ≠ 𝑥4 ，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。现在给出一些约束满足问题，请分别对它们进行判定。 题解：并查...

题解：动态规划我们设方程为dp[i][j]代表前i个元素相差j的时候最大的重量是多少。 dp[i][j]=max(dp[i-1][j],dp[i][j]); dp[i][j+a[i]]=max(dp[i][j+a[i]],dp[i-1][j]+a[i]); dp[i][j-a[i]]=max(dp[i][j-a[i]],dp[i-1][j]+a[i]);今天的要由昨天的递推过来。为什么会有一个j+a[i]和一个j-a[i]，分别代表着把第i个物品放在同侧和把第i个物品放在右侧。这里的代码没用abs，所以开了一倍长的空间记录放在右侧的情况特别注意一点就是起始点不能为0，也就是dp[0][100...

题解：很明显的并查集，但因为它们带有权值，所以我们先要把他排序，我们要尽可能让危害大的罪犯在两个监狱里（这里有一点贪心的味道）。1.首先我们把它门按照之间的影响值从大到小排序。2.假设a与b是敌人，那么我们吧a，b分开放置，并且记录a的敌人是b，b的敌人是a3.又假设a与c是敌人，这样的话我们记录一下c的敌人是a，这样的话，b和c就在一个监狱里，所以把他俩合并起来，怎么知道b与c在一个监狱呢，这是因为我们用rem数组记录了a的敌人，敌人的敌人是朋友，所以b，c合并4.又说b和c是敌人，但是他俩已经被分到一个监狱了，所以直接输出他俩之间的影响值。怎么证明他俩之间的影响值是最小的呢，因为我们之前已...

题解：这道题跟dfs有些许关系，我们可以先通过dfs把所有幸运数字给求出来，然后我再再通过sort将其排好序，这样之后就昨晚第一个处理了。因为我们要找出一个区间内的next[x]比如说:4-7之间next[4],next[5],next[6],next[7]都为7，所以我们没有必要取遍历这个区间来取值，我们可以直接求除这个幸运数字到区间开始的地方距离*这个幸运数字的大小，这样会加快很大的速度，之后再更新开始的区间，再重复以上操作即可。 #pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <...

题解：跟加边的无向图其实差不多，就是看看添加几条边让其图中的边都可以相互到达，因为用的是路径压缩的算法，所以我们只需要查看一下一空有几个集合，也就是说有几个f[x]==x（根节点）就可以了。 /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 1010; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long l...

第一次做三分法，昨天晚上被边界问题折么了好久，初学三分的话一定要好好想想这个边界问题。题解：三分法，一共有两种装备，并且这两种装备的权值是一样的，这里叫做装备A和装备B，把r设为最多能做多少件装备A。check函数为：已知装备A的件数，看看剩下的材料能做多少件装备B，返回能做件数的总数。 /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 1010; const int MaxN = 0x3f3f3f3f;...

题解：并查集路径压缩的方法就可以很简单得做出来这个题目，因为所有孩子都直接连向他的父节点，所以我们判断一共有多少个关系得时候可以直接统计一下共有几个父节点即可也就是，f[i]==i;代码： /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 1e5+10; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long ...

题解：这个题属于走迷宫类型问题的一个升级版吧，不同之处在于一秒钟小A走一步，小B可以走两步，这两种事件是同时发生的，所以我们每秒钟让A扩散一步，让B扩散两步。两个人走过的路径分别用visited[0][maxn][maxn]visited[1][maxn][maxn]来进行表示。小a走的时候1.检查自己的地图（防止重复走一个地方）2.检查小b的地图，看看小b是否走过这个地方（如果小b走过了，那就可以视为他们相遇了）同理可得：小b走的时候1.检查自己的地图（防止重复走一个地方）2.检查小a的地图，看看小a是否走过这个地方（如果小a走过了，那就可以视为他们相遇了） 对于广搜，因为是两个点开始扩散，...

想了好久觉得这就应该是个贪心题，没曾想到看到题解竟然是个二分。。。题解：正解是个二分，那么如何证明他具有单调性呢，如果他能组成x套牌，那么他一定可以组成x-1套牌，所以可以用二分来解这道题目。如何check mid是取大了还是取小了呢，假设当前组成mid件，如果a[i]<mid，那么mid-a[i]部分就需要用joker来填充了，所以当设ans是缺少的牌数的总量，所以要保证joker的数量大于ans，那么一个限制条件就是return ans<=k。想一下还有没有另外一个限制条件呢？当然，题目还要求了 一套牌里面最多使用一个joker，所以我们的ans也要小于mid。综上所述 re...

状压dp第一次写状压dp的题目，可能是因为这种类型的比较难吧，所以是第一次做到。题解：我们可以用二进制来描述方格，1表示有德玛西亚，0表示没有。样例1中第一行的三个方格都可以站人一共有五种情况分别是 第一行的五种情况 第一种 000 第二种 001 第三种 010 第四种 100 第五种 101再看第二行 第二行情况 第一种 000 第二种 010 第三种 001第二行的第一种情况是有5种方法的，第二种情况是有4种方法（与第一行第三种情况冲突），第三种情况是有3种方法（与第一行第2、5钟情况冲突） 第三行情况 第一种 000 第二种 ...

题解：非常经典的一道二分题目，二分答案去猜测满足条件的最大木棍长度。先看一下这个是否满足单调性，如果我们要求的木棍长度越长，那么我们可以切出来满足条件的木棍条数必然会越少或者不变，那么我门就对最大长度进行二分求解，那么判断条件是什么呢？check函数：遍历一遍数组求出满足条件的木棍数量，如果大约或者等于则返回true。 for(int i=0;i<n;i++) ans+=a[i]/x;代码： #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 1e5+10; co...

题解：并查集+dp十分基础的一个并查集的题目（只考了并查集的基本操作），我们找出与小d所连的所有序号，在这个集合里进行01背包操作即可。这里并查集用一下路径压缩的写法吧，不仅写法简单明了，而且还快速。注意的是：不要忘记每次清空数组。 #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 1e4+10; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00c; typedef long long ll; const ...

题解：非常简单的一道贪心题目，题目想让你把一串子序列切割成长度为1的字串，每次切割的代价是被切割序列的总和，这样的话我们肯定是让序列中越大的数约往后切割，因为越大的数会对每次切割产生代价会越大，所以你是尽可能的想让这个数造成更大的代价，所以我们按照从小到大的顺序排序，之后从前往后切割就可以了。 #pragma GCC optimize(3,"Ofast","inline") #include <bits/stdc++.h> const int maxn = 1e5+10; const int MaxN = 0x3f3f3f3f; const int MinN = 0xc0c0c00...

题解：这道题之前用贪心写，没写出来，一直留在现在，今天回看了一下01分数规划才知道原来那个想法是错误的，简单来想一下，大概是因为物体的两个值是不可以约分的，这样的话就会导致每个物品值得权重不一样就好比说原来是100/1，如果加上100000/99999，这样的话，之前一百所占得权重就微不足道了，还不如加上一个1/2.所以正解应该是需要用到01分数规划的。 #pragma GCC optimize(3,"Ofast","inline") #include <iostream> #include <cstdio> #include <cstring> #incl...