思路： 表示与可以构成以为结尾的的长度。当时，当时，，显然需要满足，因为是以为结尾的。最后枚举为结尾的的长度，找最大的。 MyCode: #include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; const int maxn=1e5+7,maxm=2e5+7,mod=1e9+7; typedef long long int ll; typedef unsigned long long ull; int a[3005]...

题目对案例3 2 1解释中，他没有把每个数隔开，注意点就好。 思路：满足条件的排列是往右往后都是递减的，求所有的排列数。就像上面图片画的那样，我们对学生的身高降序编号，最高的人编号为，最低的人编号为。那么就是一个简单的填数问题，从依次填入，那么任意时刻每一行中已经填了数一定是从左端开始的连续若干位置(保证往右递减)，并且填第行的第列的数时第行的第列必须填了数。那么线性dp的转移方程已经状态就不难了。当时滥用爆内存了，居然不是超时。 MyCode: #include <iostream> #include <cstdio> #include <cstring>...

思路：如果号点到号点是连通的，那么一定可以完成，反之一定不能完成，输出-1； 解法一：分层图最短路 图中的每个节点不仅限于“整数编号”，可以扩展到二维，用二元组代表一个节点，表示该点的编号以及第几层，显然在同层移动需要支出费用，向高层移动不需要支出费用。从到有长度为的边，表示端点为的电缆需要付费；从到有长度为的边，表示端点为的电缆是免费的。然后很容易想到用动态规划来解，表示从号基站到基站x，途中已经指定了条免费的电缆时的进过路径上最贵的花费最小是多少。就是二元组的值，然后沿着边对应的状态转移。显然这个状态转移是有后效性的。为了解决后效性，可以利用迭代思想、借助算法，直至所有状态有所收敛。 My...

A. Array and Peaks   思路：构造个峰需要个元素，所以如果那么无法构成，否则可以从第二个位置开始放最大的数，每隔一个位置再放一个差值为1的数，放满k个，然后从头往后依次将没有填数的位置填上，依次从剩余的中没有的取掉的数从小到大取。 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=2e5+7,maxm=1e7,mod=1e9+7; typedef long long int ll; typedef unsigned long long ull; int n,k; int a[1...

含义：σ(n)表示从1到n（包含）的所有n 的因数之和。积性：如果gcd(n, m) = 1，有σ(nm) = σ(n) * σ(m)求值公式：  #include <bits/stdc++.h> using namespace std; const int maxn=1e7+7,maxm=1e7,mod=1e9+7; typedef long long int ll; typedef unsigned long long ull; bool vis[maxn]; int d[maxn],pos[maxn]; vector<int>prime; inline void ...

思路：区间或、求区间最大连续字段和。求区间最大连续字段和就是一个板子，用经典做法线段树维护一个 分别表示从左开始的最大子段和，右边开始的，区间的和，区间的答案。因为一个数的二进制位只有30位，而或操作只有将至少一个0变成1才对某个值有影响，所以有效的操作最多只会影响30n次改变，每次区间修改用单点修改然后再剪枝就行了。 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=1e5+7,mod=1e9+7; typedef long long int ll; int a[maxn<<2];...

题意：给定长度为n的排列，一次操作你可以选择任意个下标数对：(x1,y1)，(x2,y2)，…(xn,yn)。要求每个下标最多只出现一次。问最少需要几次操作能够将排列恢复为原排列，同时输出每次操作选择的下标。 思路： 之间连一条边，如果不形成环，那么一次操作就行，如果环上只有两个点，那么也只需要一次。如果环中有个点,那么两次交换即可，只需要维护两个游标从首尾开始交换，把大环拆成若干个只有两个点的小环和若个排好序的点，然后再操作一次拆掉2个点的小环就行了。 MyCode: #include <bits/stdc++.h> using namespace std; const int ...

题意：把一段相同的形状变成其它任意一个形状，需要使用一次魔法，问最少使用多少魔法能使全是同一个形状。 思路：先把连续的缩成一个连续段，假设缩点后有m个段，如果每个互不相同，答案显然是m-1，不管怎样合都对答案没有影响。如果在合并两个区间时，两个区间的左、右端点的值相同，那么可以通过将中间的值赋值成该值，可以省去一步。假设表示合并区间的最小代价，表示与相同的点的下标。枚举有没有参与省去的过程，即。同时注意考虑一下左端点相同的情况： MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=1e6+7,ma...

题意：输入n、k，问对任意长度为n，值在上的序列，给你一个p，然后通过事先和队友讲好的方案将序列内的某个数+1然后对k取余，接着把修改后的序列给队友，让队友猜，猜不对就输。 思路：将k^n个状态映射到n个集合的权重组合就可解 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=1e6+7,maxm=2e5+7; typedef long long int ll; typedef unsigned long long ull; int main() { ios::sync_with_stdio(fa...

题意：2021年，n个人过生日，做蛋糕需要天，生日那天给第i个人有个好感度，也可以选择送礼物，需要花元，获得个好感度，每个礼物最多买一次。在生日当天做蛋糕，如果只要一天也能赶上。 思路：2021年不会出现2月29假设给i个人做蛋糕，j个人发礼物是最优的我们可以爆搜求出表示给j个人发礼物能得到的最大好感度然后用动态规划求出给i个人做蛋糕，j个人发礼物能得到的最大好感度，当然还要加上一个时间t表示提前多少天开始做蛋糕 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=1e6+7,maxm=2e5+7...

题意：每次询问给出L,R，问[L,R]中选择一个子集求和，无法凑出的最小正整数是多少； 思路：首先，如果没有1，那么;假设现在能组成，且内有，那么就能凑出，即凑出,然后继续凑;反之若内不存在，则无法凑出的最小正整数就是x的增长速度是指数级的，因此最多次就出来了。 询问两个区间总和之差，需要用区间权值线段树，即可持久化线段树复杂度: 记录的是第个版本的线段树，每次建个新的线段树需要重新开个点。 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=1e6+7,maxm=2e5+7,N=1e5+7; t...

题意：求任意两点的异或最短路 思路：假设点x到点y必须经过一条边，那么它可以通过走环来减少路径的异或和(如果和环的异或值 异或后更小)如图，特别的即   我们可以先以1为根，建一颗树，跑出1到所有点的异或值，此时往树中加边一定会形成一个环，所以在建树时没有跑过的边对应一个环，这个环的异或值为。按二进制存环的异或值，一般情况，环的异或值二进制最高位为第位则存在中；特别的，当存了一个或多个环时，，如果下一位为空则存入反之继续。假如两个环的异或值最高为都是第位，分别为，假设处理后，那么表示的是这两个环都走一遍，而可以通过得到。 接下来计算任意两个点的异或最短路,假设，我们要求的就是走那些环可以减少d...

A - Domino on Windowsill   思路：贪心只要还有位置，多米诺骨牌就能摆上去。 MyCode: #include <bits/stdc++.h> using namespace std; const int maxn=2e5+7,maxm=1e6+7,mod=1e9+7; typedef long long int ll; typedef unsigned long long ull; inline void solve() { int n,k1,k2,w,b; cin>>n>>k1>>k2>>w>>...

D、Epic Transformation 题意：选择数组中不同的两个数消去，求消去后数组最少有多少个数。 思路：出现次数最多的数，如果出现次数小于等于n，最优策略是先排出现次数少的数，然后按出现次数降序插入，最后不可能有两个及以上的数没有配对成功，那么顶多有个数找不到配对；如果出现次数大于n，那么最优的策略是把其它的数分别插到这些数中间，那么最多只有个数没有配对。 MyCode1： #include <bits/stdc++.h> using namespace std; const int maxn=2e5+7,maxm=1e6+7,mod=1e9+7; typedef lon...