看题目后 不会呀数据结构 (巨佬队友说是主席树的板子题果断向他学习了一下 下面是我的学习理解主席树相当于线段树1-1,1-2,1-n的前缀和 于是这样就可以用来维护区间信息将 l-r变为 1-l 1-r的减法套上板子 这题维护的信息是区间的名次 #include <bits/stdc++.h> using namespace std; const int maxn=1e5+5; int n,m; int a[maxn]; vector<int>v[maxn<<2]; vector<int>::iterator it; void build...

看题不会 疯狂自闭看完雨巨和其他大佬的题解后 写出了这道题写些自己的理解1、将矩阵的构造转化成图的构造（图的邻接矩阵表示法） 边权值即表示点与点有几条边于是由条件可知 每个点有且只有两条边（后面的关键） 这个图由几个简单环组成 每个环至少2个点2、如何由dp[n-1]推出dp[n] 相当于n-1个的点的图变为n个点的图第一种： n-1个点 选出一个点与新加的点连成环 其他n-2个点自由连 (n-1)dp[n-2]第二种： n-1个点 选出一个点与新加的点连一条边 然后本身的n-1个点自由连 必有空的一条边来连新加的点 (n-1)dp[n-1] ...

这是一道带点变化的01背包题首先对要做的 x y 两道菜怎么确定他们的先后关系？先做x后做y的美味值和为：a[x]-(\sum +t[x])b[x] + a[y] - (\sum + t[x] + t[y]) * b[y]a[x]−(\sum+t[x])∗b[x]+a[y]−(\sum+t[x]+t[y])∗b[y]先做y后做x的美味值和为：a[y]-(\sum +t[y])b[y] + a[x] - (\sum + t[x] + t[y]) * b[x]a[y]−(\sum+t[y])∗b[y]+a[x]−(\sum+t[x]+t[y])∗b[x]（\sum是做前面所有菜的时间和）比较大小就...

这是一道二维dp题我们用 dp[i][j] 来表示 前i个元素中删除j个如果不考虑重复的话 dp[i][j]=dp[i-1][j-1]+dp[i-1][j] 分别是删不删除当前数考虑到重复 重复的诞生是这一序列的第i个元素与前面的x位置相同那么就是以 a[x] 结尾的序列都能通过删除[x,i-1]这一段元素重新获得于是有 dp[i][j]-=dp[x-1][j-(i-x)] #include <bits/stdc++.h> #define ll long long int const N=1e5+5; int const mod=1e9+7; using namespace st...

这是一道类似导弹拦截的dp题首先式子可化为 log(a[j])/j<log(a[i])/i然后用dp[i] 来表示以i位为结尾的子序列的个数 #include <bits/stdc++.h> #define ll long long int const N=110; int const mod=1e9+7; using namespace std; int n,a[N],dp[N],ans; int main() { cin>>n; for(int i=1;i<=n;++i)cin>>a[i]; for(int i=1;i<=...

这题没看题解前是不会的 在看完雨姐的题解后 知道了这题的几个关键1、我们直接来分析边的染色是比较复杂的 那么我们就把边的权值当做边的两点的异或值那么题目要求的条件 环的异或和为0就已经达到了（相当于把每个点异或了两次）2、如果题目不给边值 而是全部由我们来标的话点有2^n次标法 但装换成边值 有两种点的标法是一样的 （把一种标法的1全部换成0 0换1）于是总方案有2^n-1次（n个点的联通图）3、但是题目给了我们一些边的值 那么又要怎么处理？求出每个由已有边权的边组成的连通图的点数 这种连通图里能自由标的点的值只有一个 其他点的值就由边确定了 那么答案就要/2^k-1（此连...

这题注意两点就行了1、用后缀和处理发功的问题 然后在把能力值加上这发功的2、反方向跑一遍能力值 当前的糖糖不被消灭的要求是后面同组的最大值小于他详细看代码理解 #include <bits/stdc++.h> #define ll long long int const N=5e4+5; using namespace std; int n,t,m,cnt[N]; struct T{ int x,y; }a[N]; int main() { cin>>t; while(t--) { cin>>n>>m; ...

三维凸包即解决空间中n个点构成的最小空间几何体的相关问题 选择题目：洛谷P4724 我所学习的方法是增量法 （与最小覆盖圆类似）   首先选出四个不共面的点为基础凸包   不断加点 判断这个点是否在这个凸包内 不在就形成新的凸包   具体的看代码理解 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll MAXN=2050; const double eps=1e-8; struct Point3{ //三维的点 double x,y,z; P...

这场打的时候一点状态都没有 就签了个到就跑了 /吐血A、Jelly这就是一个三维bfs的签到题（不信邪的写dfs加剪枝 我还是没有过 最后只能改成bfs #include <bits/stdc++.h> #define ll long long using namespace std; ll const N=110; ll n,s[N][N][N],dd,v[N][N][N]; struct T { ll a,b,c,d; }; queue<T>q; string z; int main() { cin>>n; for(int i=1;i&l...

经典二分 （之前想错了 不过这两个地方应该可以加速） #include <bits/stdc++.h> #define ll long long using namespace std; ll const maxn=2e5+5; ll n,k,a[maxn],ans,maxl,l,r,mid; bool check(ll m) { ll ins=0; for(int i=1;i<=n;++i) ins+=(a[i]/m); return ins>=k; } int main() { scanf("%lld%lld",&n,&k...

一直没想到二分然后想正解 看了别人说才想到那么这题就简单了 二分答案然后验证check函数为 判断第K大的数大于等于x的区间数面向结果编程..... #include<bits/stdc++.h> #define ll long long using namespace std; ll const N=1e5+10; ll n,m,k,a[N],t; bool check(ll x) { ll num=0,s=0; for(int i=1,j=1;j<=n;j++) { if(a[j]>=x) num++;///值大于X...

这是一个前缀异或和的比较简单的题目（给的区间范围是不是有锅 我开1e4不行我们只要知道 区间[i,j]的异或和等于异或和[1,i-1]^[1,j]的异或于是这题就出来了（代码有详解 #include <bits/stdc++.h> #define ll long long ll const N=1e7+5; using namespace std; ll n,x,a[N],b[N],ans; int main() { scanf("%lld",&n); for(int i=1;i<=n;i++) { int ...

这是一个简单的dfs偶数=偶数+偶数或者奇数+奇数 所有我们只用统计深度为奇数或者偶数的个数答案为 奇数或者偶数任取两个 即(ans1(ans1-1)/2)+(ans2(ans2-1)/2) #include<bits/stdc++.h> #define ll long long using namespace std; const int N=1e5+10; int head[N],nex[N<<1],to[N<<1],tot; int n,h[N]; ll ans1,ans2; void add(int a,int b){ to[++tot...

这是一道比较简单的组合数学题首先我们这么想 在n个位置选出两个位置来按放 1 0 为 （nn-1）/2其他位置随便放 结果为 2^n-2最终结果为 （2^n-2）（（n*n-1）/2） 然后在计算中取模仔细想一想这样是将所有情况全部都计算了（想不明白建议手推一下 #include <bits/stdc++.h> #define ll long long using namespace std; ll const mod=1e9+7; ll quickpow(ll a, ll b) {///模板 if (b < 0) return 0; ll ret...