题意:注释解释很清晰(逃.....)题解:参考当时Wannafly挑战赛7的题解如果要达到最小的值,那么最佳情况就是走到某一个点,然后找这个点两边距离最近的点,然后两点之间左右横跳(手动滑稽.jpg)比如 对于这个,肯定是在20和21之间横跳所求值最小,然后就是枚举每一位对于p和m进行操作时间复杂度:  #include <bits/stdc++.h> using namespace std; int T,n,m,p,a[200001]; int main() { for(scanf("%d",&T);T;T--) { scanf("%d%d%d",&n,&...

链接:https://nanti.jisuanke.com/t/42397题意:求图中所要求的线段的数量题解:dfs+dp,第一次知道dp还能这样玩.....对于每一位置先判断是否为起点,如果上下左右进入数量为1即为起点下来因为要求要长度最少为4,所以开三维dp数组进行计数 表示对于第i行第j列的位置,以此为终点的长度为k的情况有多少个下来就是对于起点进行广搜,对于可以到达的每个点都进行dp数组更新,如果到那个位置他的入度变为0,加入数组,因为如果入度不为0直接加入会有后效性,影响结果 #pragma GCC optimize(2) #include<bits/stdc++.h> ...

题意:问可以构成多少种情况题解:都在代码里面主要在于分类讨论时间复杂度:  #include<bits/stdc++.h> using namespace std;//雷=皇家火焰 long long dp[10000000][2];//表示从头开始到第i位,?为雷和不为雷的情况数(0,不为雷/1,为雷) int mod = 1e9+7; int main() { string s; cin>>s; int n=s.length(); s=" "+s; dp[0][0]=1;//初始情况下,假设s中无'?',即结果为输入的那一种 for(int i=1; i<=n...

链接:https://nanti.jisuanke.com/t/42388题意:n个点,x条无向边,y条有向边(存在负边权),一个起点s,然后求s到剩余点的最短路题解:这题卡spfa......然后看题解,写的用连通块加上Dijkstra,Dijkstra还能写负边权(???)相同的连通块之内用Dijkstra,不同的Dijkstra用遍历........ #include <bits/stdc++.h> using namespace std; int n, x, y, s; const int MAXN = 2e5 + 50; typedef pair<int, int&...

链接:https://nanti.jisuanke.com/t/42386公式化简:  #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 998244353; int inv2, inv6; int ans; int b; ll n; int ksm(int a, int b) { int ret = 1; for(; b; b >>= 1, a = 1LL * a * a % mod) { if(b & 1) ret = 1LL * ret *...

链接:https://nanti.jisuanke.com/t/42391题意:求两个矩阵的最大重叠面积题解:单调栈(悬线法...(有些没看懂))对于第二个矩阵的每一个位置求 表示第 位置可以和第一个矩阵相同可以到达的最高高度.下来转换成对于每行的 求直方图的最大面积如下:  int LargestRectangleArea(vector<int>& height){ height.push_back(0);//为了统计，数组最后添加0，确保原数组的最后一位得到计算 stack<int> s; int LargestArea = 0; int temp,i=0;...

链接:https://nanti.jisuanke.com/t/42387题意:给定多个操作,MULTIPLY操作为:区间 全部乘于 ,MAX操作为:查询区间的分解质因数后单个质数的次数最高为多少题解:乘于x相当于,2,3,5,7加若干值,所以写4个线段树,然后依次更新,查询 #include <bits/stdc++.h> #define mid (left+right)/2 #define ls (2*rt) #define rs ((2*rt)+1) using namespace std; const int N= 1e5+10; //四个线段树分别维护2,3,5,7 st...

链接:https://nanti.jisuanke.com/t/42381题意:给定多个物品,每个物品有name,color,power值,然后选取五件名字不同的五件物品,使power总和最大,然后下面还有奖励机制,给定五个名字和一个颜色,如果选择的五个物品某个物品在奖励名字里,其power总和值增加10%,如果颜色值在增加20%题解:分组背包,把名字相同的分为一组,然后把五件物品当作第一变化量,每个的奖励百分比当作第二变化量 #include <cstdio> #include <cstring> #include <algorithm> #include...

(这dp,服了服了,...........额,没做出来,看题解会的)参考链接:https://www.luogu.com.cn/blog/GUO2002/solution-p4158题解:涂色,对于每一行,要不全部都不会被涂色,要不全部都会被涂上色,涂错也算涂色,所以就不用考虑未涂色也算错误的因为涂色的颜色只有两种,所以就变成对于涂色的每一行,涂蓝色还是红色,然后dp, ,表示涂色到第i行,第j个位置,涂色k次,l=0/1,涂色正确或者错误的个数然后涂色有三种情况:(1)换行,对于每次换行后涂色,那铁定第一个位置是涂色正确的,那么可以得到下来解释这个:涂错反过来看不就是涂对吗?所以每次得到上述...

题意:给定 个点高度,和 条边,以及 条边的权值然后问,从1号点能到多少个点,并且所有能到的点的权值求和最小是多少题解:第一问:明显的广搜直接解决,记得标记下点第二问:因为可以返回到上面的任意的点,所以我们每去一个点,可以直接到与他相连且最近的那个点过去,(越解释越乱......)其实就是最小生成树比如我们从1点的一条边出去,把能连的点全部连上之后,相当于是一个集合,然后再加入1点可以到的,还没有加入集合的点,因为可以回溯到原来的某一个时间点,所以直接找距离集合最近的点,先加入,...然后重复时间复杂度:搜索是: ,最小生成树是:  #include<stdio.h> #inclu...

题解:主席树模板,树状数组也行 #include<bits/stdc++.h> using namespace std; const int MAXN=1e5+5; int n,m,bit[MAXN],ans[MAXN]; struct Num{ int x,id; bool operator<(const Num& obj)const { return x<obj.x; } }a[MAXN]; struct Query{ int l,r,k,id; bool operator<(const Query& obj)const { return k&...

(小声bb)(这题不会,看了好多题解看明白的)参考博客链接: https://blog.csdn.net/qq_37632935/article/details/81122408 https://ac.nowcoder.com/discuss/87364?type=101&order=0&pos=2060&page=1题意:构建合法矩阵,然后能够构建多少个合法矩阵要求: (后面有点挡住了......)合法矩阵举例: 的有 , 的有, 其中 种为题解:  把矩阵转换为无向图,并且该无向连通图为环,该无向图可以是多个简单环 假设我们现在已知 个点可以构成 种情况,那么我们求...

题意:在给定的时间内,选择做几种菜肴,然后让美味度最大题解:第一眼01背包,然后再看,额,比01背包还多了个条件,就是,在不同的时间内做出来的菜,美味度会有变化,答案还可能负的(负的还能吃吗???,弥天大雾)所以就是先进行贪心,把给定的数列处理成可以01背包的数列既然是贪心,那么肯定 ,所以假设有 两种菜,那么选个菜就是 和两式相减,求贪心,化简得到 ,然后就可以进行贪心 了.下来01背包拉进去时间复杂度:  #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; struct Node { long...

题意:给定n个会有重复数字,删除m个问有多少种序列,然后取模题解:dp构建状态转移方程 在第i个位置,要删除j个数字,那么要不前i-1位已经删除j个数字,要不前i-1位已经删除j-1个数字,第i再删除当然如序列 此时我们要删除5个数字,会出现 和 的重复所以应该去重,即 , 表示与第i位相同的数字,上一次出现的位置,然后具体的解释,参照第一个式子的解释时间复杂度:  #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define mod 100000000...