解题报告：哎。。。我蒟蒻啊，这都没看出来，我以为是线段树的题，结果是dp题，就是算出最长非降序子序列的长度len，然后n-len就行了。 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include<queue> #include<set> #define IL inline #define...

解题报告：初学三分，大致思想其实和二分差不多，只不过二分区间是有严格单调的性质的，但是三分的话只能求类似二次函数一样的最值，思路就是把整个区间分为三段，然后比较三分之一点和三分之二点的顶点函数值的大小，然后求最小值，就往小的地方逼近。 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include<queue&...

解题思路：题目大致意思是求在题目给出的点中离s最近的距离，其实我们可以创建一个虚拟源点让各个点到他的路径是0，spfa 0 就行了。 #include<bits/stdc++.h> using namespace std; const int N=1010,M = 50010; int e[M],h[N],idx,ne[M],w[M]; int dist[N]; bool st[N]; int n , m , s ; void add(int a,int b,int c) { w[idx] = c ,ne[idx]=h[a],e[idx]=b ,h[a]= ...

解题思路：题目大意是要到一个位置，但是图中会有对应的门，而且门的种类不同，需要不同种钥匙来打开，不同种的钥匙分别放在地图中的某个位置，问最多要多少步才能到。 这道题的解题思路也是非常的取巧，他并没有告诉你每个点之间的边，这个需要我们去构造，并且还有墙，墙是不可逾越的，那么我们需要用一个set来维护两条边之间是否存在墙或者门，我们初始的dist一维数组是肯定不够的，要开第二个状态[j],这里的状态应该用个二进制状态来存，如果开始搜的时候两点之间的w[i]如果大于0，那么二进制状态右移w[i]位&1如果等于0那么就不存在。在采用bfs的时候，如果脚下有钥匙我们肯定要捡起，然后双端队列的可以...

解题报告：这题可以用spfa判断正环的做法+二分来做，我们二分他的环的平均长度，看看能不能凑成环，如果暴力去把每个字符串变成一个点，总共会有1e5的点，可以优化一下，把整个字符串变成一条边，把前两个和后两个的单词字母映射成一个点，总共26*26个点，如果朴素去做会tle，那么要加个玄学优化，如果更新次数太多的话（十几倍左右）就暂且认为他是一个环，然后stl的queue太慢了，要用数组来模拟队列。 #include<bits/stdc++.h> using namespace std; const int N=100010,M=700; int h[M],e[N],ne[N],...

解题报告：二分他们的商值，把每条边变成t[i]-mid*w[i]，然后看是否存在正环。 #include<bits/stdc++.h> using namespace std; const int N= 1010 ,M=5010; int h[N],idx,e[M],ne[M]; double t[N],w[M]; int n,m; int q[N]; double dist[N]; int cnt[N]; bool st[N]; void add(int a,int b,int c) { e[idx]=b,ne[idx]=h[a],w[idx]=c...

`#include #include #include #include #include #include<map> #include #include #include #define IL inline #define x first #define y second typedef long long ll; using namespace std; char s[10010]; int main() { int n; cin>>n;</map> scanf("%s",s); bool flag=0; int ans=0;...

sqrt返回的是float形的所以不能用%lf输出（wa警告），仔细观察可以发现，该图可以转换为4个部分，其中第二个和第三个部分坐标变换是不变的，第一个是关于对角线对称，第四个是关于斜对角线对称，如果递归到了第0层就返回坐标{0,0}，我们假设坐标是从0开始的，编号也是，所以递归的时候a-1，b-1，当递归到下一层的时候，当前的编号可不是下一层的编号，要模上四分之一改成所有的编号数（1<<(2*n-2)）当我们求出坐标返回到上一层的时候要找到返回到哪一个部分，再做转换。。。太难了。 #include<iostream> #include<cstring> ...

只要满足从2开始到n的差分数组d为0就行了，总共有四种操作，其中第四种是无效的，第一种最有效，我们尽量去去选一正一负的来操作，这样可以消掉两个第二第三种做法只能消掉一个，那么我们算出正数差分总和，和负数差分的总和，两个的max就是操作的数量，然后最后有多少种结果呢，就是最大值-最小值+1，因为d1 可以从 0~max(p,q)-min(p,q)

第一次做交互题，这种题只需要写一个函数就行了，返回要返回的，我们可以假设前面也排好序了，因为是单调递增的，我们可以二分出来要插入数的位置，二分出比他小的数的位置，然后从后面往前面依次交换放到该位置后面就行了，特判一下如果没有比他小的数，那就把它放到最前面。 // Forward declaration of compare API. // bool compare(int a, int b); // return bool means whether a is less than b. class Solution { public: vector<int> s...

解题报告：二分平均值，由于他限定要不小于l长度的平均值，我们可以用个数组记录a[i]减去二分的平均值，如果最大的连续子序列长度大于等于0就l=mid ,由于是浮点数，eps设置为保留位数+2就行了，这题就是5.同时最后要乘以1000，l和r都是满足题意的，因为是最大值用r来*1000下取整就行了，接下来要找最大长度大于等于连续子序列的和，可以i从l开始循环，记录一下i-l前缀和和min，最后每次用前缀和i-min来更新ans就行了。 #include<iostream> #include<algorithm> #include<cstdio> #inclu...

我唯一想说的是：我卢本伟没有开挂 ，第二句话是个废话，让一个树连通，边的数量是定制n-1(n为点数）。 #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<vector> #include<queue> #include<set> #define IL inline #define x first #define ...

解题报告：应该把要选的都给选上，然后在从小到大选边。 #include<bits/stdc++.h> const int N=31000; using namespace std; struct node{ int p; int a; int b; int c; }q[N]; int p[N]; int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } bool cmp(node a,node b) { if(a....

网站 解题报告：这道题实质上是在问满足存在k个连通块的最小d是多少。然而并不用二分，因为在kruskal算法的过程中本身联通块的数目就是递减的，从一开始的n到k然后记录最小值就能ac这道题了。 #include<iostream> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=125010; struct edge{ int a; int b; double w; }q[N]; i...