题目大意是每次给你两个数，你只能在其中选一个没有选过的数，可以不选。问你最多选多少个数 我们可以把两个数当成一条边，由于数字会很大，所以先离散化。然后就转化成了一个图的问题。 题目意思等价于在图中有若干条边，对于每条边，你可以选择它所连接的两个顶点中的一个，问你最多可以选择多少个不同的点。 我们知道整个输入数据转化成图后，肯定是由若干个联通的图组成的。我们就单独对一个联通图考虑。 我们设一个联通图有n个点，联通代表着它最少有n-1条边。n-1条边你能选多少个点嘞，显然是n-1个。为啥嘞，你可以把这个图想象成一个有根树，只要我们不选根，那么它剩下的节点我们都可以选，而且只有n-1条边代表着我们只...

题目大题：K—Bag：数组是由若干个长度为k的全排列组成的，然后在开头和结尾都可以删去位置连续的若干个元素。最后要你判断是否是K-Bag 我们定义一种边（u, v)； 若u=1 或v=n+1，则要求a[u],a[u+1],..,a[v-1]都是由不同的数字组成的 反之，我们要求 v-u == k, 并且要求a[u],a[u+1],..,a[v-1]恰好是一个全排列 至于为什么要这样定义。仔细想想就好了，每个边其实都代表下标[u,v)之间其实都是不悖于条件的，要么是完整的一个全排列，要么可能是被删去了一部分的全排列。 最后我们判断是否可以由1到达n+1, 若可以则输出YES，反之NO。 注意实现...

题目大意：有两种操作，1.整个数组执行若干次循环移位，2.前n-1个元素执行若干个循环移位。问，把一个全排列排成升序最少要执行多少次第二种操作。 我们再把两种操作组合一下，按照1 2 1来组合，我们发现可以等价于把任意一个数放在任意的地方。 直觉证明：1 2 3 4 5我们通过三个操作把5放在3前面通过1操作，把要移动的数放在最后一个，1 2 3 4 5。通过2操作，选择要移动到的位置4 1 2 3 5通过1操作，大概还原一下数组 1 2 3 5 4 所以问题等价于：把任意一个数放在任意的地方，将数组排成升序，求最少要移动多少次。 显然答案是数组长度减去最长上升子序列的长度。因为子序列中的数是...

#1024#

 #1024# 1 + 1 = 10

#1024#程序员节快乐！这次必中杯子！！！

#1024#程序员节快乐！， 想要一个杯子

#1024#一定来，一定来

搬家搬家

题目给你三种操作： 1：将第i个数加上j； 2：求一个区间内数的和 3：将一个范围内的数改成与它最接近的斐波那契数，若距离两个相邻的数字距离一样取小的那个。 数组内所有数初始值为0 经典的线段树维护区间修改单点修改，区间查询。只要维护一个原数组和改变后的数组即可。区间更新的时侯直接赋值就可以了 Accode： #include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; const double pi = acos(-1); namespace { ...

题目地址 转移剩余的空间，当前的剩余的容量为j，则dp[j] 由 dp[j+a[i].p] 转移过来。但是由于物品出现的位置不确定，所以要排个序。不理解要排序的可以用这两组样例试一下： 2 10 1 10 10 2 9 10 2 10 2 9 10 1 10 10 正解为20； ac代码： #include<bits/stdc++.h> using namespace std; typedef long long LL; const int INF = 0x3f3f3f3f; namespace { template <typename T> inline v...

求LIS的方法有很多，现在我知道的有三种，分别是dp， 贪心+二分，树状数组。这篇博客就重点写一点用树状数组解决LIS相关的题目。 预备知识：树状数组，离散化。 一个板子题：题目 我就简单的说一下用树状数组的思路：首先数据很大，很自然的想到离散化。然后树状数组维护什么呢？[1-i]（i为离散化后的相对大小）中以i结尾的LIS的长度，以为是1-i嘛，所以维护起来和普通的没什么两样。然后对于一个数a，离散化后它为i，那么我们就先求出 i-1 （想想为什么是i-1）结尾的LIS，再用这个结果+1去更新以 i 结尾的LIS的长度。如果还不理解就看看代码吧。 #include<bits/stdc...

题目 经典的anti-nim题目。 和普通的nim差不多，判断结局的方式不一样：游戏的SG函数不为0且游戏中某个单一游戏的SG函数值大于1，游戏的SG函数为0且没有某个单一游戏的SG函数大于1，先手必胜。 ac代码： #include<bits/stdc++.h> using namespace std; typedef long long LL; namespace { template <typename T> inline void read(T &x) { x = 0; T f = 1;char s = getchar(); for...