思路：是dp吧， 一开始没想到，瞄了一眼题解，线性dp， d p [ i ] [ 2 ] dp[i][2] dp[i][2] 代表考虑前1~i个不同的数获得的最大值，0表示当前第i位不选，1代表选了，转移就不用说了，我预处理了每个数出现的次数，然后排序，去重使得dp不具有后效性。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; #define int long long #define debug printf("---\n"); const int N=20001...

题目链接 题意：给定一个数组n ，对于任意k从1到n，问满足获得的数组是否一个排列，例如1 5 3 4 2当k=2时获得的数组是1332则不满足排列，对于任意len，一个排列指的是所有数从1～len都出现且出现一次。 思路： 看的官方题解。。反正我是想不到，%一下斌学长一做就是官方题解复杂度 O ( n ) O(n) O(n)，官方题意特判了一下k是1和n的情况，然后对于1<k<n，所有排列都是从1开始的，那么1只能出现的边界，然后开始迭代，维护l和r，最后判断l～r中间最小值是否满足i+1，如果ans[n-i+1]=1，然后可以发现是个类似递推。 #include<ios...

#include<bits/stdc++.h> using namespace std; int cnt; int root; int x,y,z; struct node{ int l; int r; int val; int key; int sz; }fhq[100010]; int newnode(int x) { ++cnt; fhq[cnt].sz=1; fhq[cnt].key=rand(); fhq[cnt].val=x; return cnt; } void updat...

#include<bits/stdc++.h> using namespace std; struct node{ int l; int r; int val; int key; int sz; int lz; }fhq[100010]; int root; int cnt; void update(int now) { fhq[now].sz = 1+fhq[fhq[now].l].sz+fhq[fhq[now].r].sz; } int newnode(int val) { fhq[++cnt].val=val; fhq[cnt].k...

题目链接 题意：构造一种方式 使得X和O不能出现横着或者竖着的三个情况，要求操作不超过k，k为O和X的总和. 思路： 把这个图变成三分图，可以发现横着或者竖着连续的，他们横纵坐标相加%3都不同。我们用个计数器来记录每个位置%3 X或者O出现的次数，我们只需要改变一个位置，就可以使得不出现连续的情况，但是如果O和X出现的最小值都是某个数的时候就可能出现改完X使得O出现连续，那么我们只需要取两个不同的模的最小值就行了，可以证明这样操作的数小于等于k/3。 #include<bits/stdc++.h> using namespace std; string str[310]; int...

复杂度 Q ∗ l o g ( N ) ∗ l o g ( M ) Q*log(N)*log(M) Q∗log(N)∗log(M) #include<bits/stdc++.h> using namespace std; typedef long long ll; #define debug printf("---\n"); const int N=2050,M=10010; #define int long long int t1[N][N],t2[N][N],t3[N][N],t4[N][N]; int n,m; int lowbit(int x) {...

#include<iostream> #include<cstring> #include<stdlib.h> #include<time.h> using namespace std; const int N=50010; int n,m; int cnt; struct node{ int l; int r; int val; int key; int sz; }fhq[N*40]; struct nd{ int l; int r; int root; }tr[N<<2]; int w[N]; ...

链接 题意：一开始有k个水量 ， 题目要求你在t天保持l～r的水量，每天固定消耗x水量，一天的刚开始你可以选择加y水量或者不加 ，问t天内是否一直能维持。 思路： 分类讨论， 这题突破点在于x，因为x的范围是最小的，在1e6。小trick，把k和r分别减去l，那么可以减去一边讨论，直接看是否小于0就行了，如果x=y，那么如果第一天能不小于0的话就可以一直苟，如果x>y，那么我们每一天必定加每天固定减少x-y，看看能撑到几天，如果x<y，那么我们直接快没的时候加，也就是在[0~x-1]的范围内加，然后用map记录一下每个位置，如果出现了则说明我只需要操作之前一样的操作就能维持这个数那...

有 N 个位置，M 个操作。每个位置可以同时存储多个数。 操作有两种，每次操作: 如果是 1 a b c 的形式，表示在第 a 个位置到第 b 个位置，每个位置加入一个数 c。 如果是 2 a b c 的形式，表示询问从第 a 个位置到第 b 个位置，第 c 大的数是多少。 输入格式 第一行包含两个整数 N,M。 接下来 M 行，每行包含一条指令，形如 1 a b c 或 2 a b c。 输出格式 输出每个询问的结果，每个结果占一行。 数据范围 1≤N,M≤50000, 1≤a≤b≤N, 1 操作中的 c 的绝对值不超过 N, 2 操作中 c 满足 1≤c≤231−1。 思路：...

题目链接 题意：题意很简单，就是两个人走随时都可以转弯，问最少的时间覆盖整个线段。 思路： 看了题解，分类讨论，一种是一个人把全部走完，另一种是两个人相对着走，最后一种是两个人分别把自己的一边处理完，假设x在左边，y在右边，那么可以二分判断x最右边的覆盖点与y最左边的覆盖点是否重合。 感想： 太难想了，我数学太烂了。。。 一开始没有想到中间回去这种case，光顾着直溜溜的走了，主要原因还是自己贪心不好。 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define debug printf(&...

题意把一个序列操作成字典序最小，每次操作可以把一段l～r区间变成平均数，n<=1000000.思路：一开始想的是o(N^2)的暴力做法，看到网上提供的类似单调栈+区间长度维护的思想，也就是从前往后遍历，遇到能更新前面区间的数就更新，把平均值放到栈中，然后不断把len更新代码： #include<iostream> #include<cstring> #include <iomanip> using namespace std; const int N=1000010; int a[N]; double s[N]; int len[N]; int to...

题意：每次可以选择相邻并且相等的数合并变成一个数，该数的值为该值+1，问怎样合并使得最后数组最少我区间dp太弱了，看不出来，状态转移就是单纯的另外额外开一个二维a数组 记录l～r之间是否能合并,并记录合并完的结果如果l~r之间能合并 那么直接合并把dp[l][r]变成1就行了。 #include<iostream> #include<cstring> using namespace std; int dp[510][510]; int a[510][510]; int main() { int n;...