题目链接：https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=117      简单DP，tag[i][j] 表示截止到 s1 的 i 位置和 s2 的 j 位置的最长公共子串长度。由于子串连续，最后找到最大值位置向前递推即可。代码如下：   class Solution { public:     /**      * longest common substri...

根据题意，我们可以使用 复杂度求出以 为右边界的左边界在哪，然后把所有的询问离线，按照右端点从小到大排序，维护一个棵线段树，结点代表以 为右边界的最小区间长度，对于每个询问，只要把所有的右端点前的值更新到线段树中，再查询一次最小值即可知道答案。 #pragma comment(linker, "/STACK:1024000000,1024000000") #include <cstdio> #include <string> #include <cstdlib> #include <cmath> #include <iostream>...

归并排序就是用的这样的思路，每次比较两个数组的第一个元素，并将较小的一个存入新数组，从原数组删除，然后继续比较两个数组的第一个元素，以此类推。   代码如下：   class Solution { public:     void merge(int A[], int m, int B[], int n) {         vector<int>&nbs...

首先,回合数越少越好。我们发现,让boss剩下最多(但是在一个回合内能够击杀)的血量时回合数最少 把boss的血量状态压缩，然后进行枚举，代码如下： #include <bits/stdc++.h> #define R register #define ll long long #define cmin(a, b) ((a < b) ? a : b) #define cmax(a, b) ((a < b) ? b : a) const int MaxN = 2e5 + 10; typedef std::pair<int, int> pa; ll h, n; ...

对于每次询问，我们建一棵“虚树”这棵虚树只包括询问点以及相应的lca这样在虚树上dp复杂度为总复杂度为 代码如下： #include <bits/stdc++.h> typedef long long ll; const int N = 250010; using namespace std; int n, q; struct edge { int e, w, nxt; } E[N << 1]; int cc, h[N]; void add(int u,int v,int w) { E[cc].e = v; E[cc].w = w; E[cc].nxt = h[u]; ...

每个节点记录四个量，从左到右最多匹配到第几个字符，以及初始的端点。从右到左最多匹配到第几个字符，以及初始的端点。 #include<bits/stdc++.h> using namespace std; const int N=5e5+7; int n,m; struct Edge{ int u,v,w,nxt; Edge(int u=0,int v=0,int w=0,int nxt=0):u(u),v(v),w(w),nxt(nxt){} }e[N*2]; int p[N],edn; void add(int u,int v,int w){ e[++edn]=Edge(u,v,...

对于每一棵树，我们要统计以每个点为根的树的最长深度。树形DP统计最长链和次长链+换根就可以。现在得到统计每棵树的概率p[i]和不能通过的概率q[i]=(1-p[i])。dp[i]:从第1棵树到第i棵树的期望时间。dp[i]=dp[i−1]+q[i]∗(1)+pi我们在第i-1棵树的时候。尝试一次。p[i]成功只用1秒。有q[i]失败，尝试时间1+重启时间+3+重新从1到i的时间。化简：dp[i]=(dp[i-1]+1+3*q[i])/(1-q[i]); 代码如下： #include <bits/stdc++.h> #define LL long long using namespa...

因为最大值和最小值求法对称，以求最小值为例。 要让尽量小的上来，可以贪心选择一条路前面都是min不够了后面就用max。因为如果min上面有max，max换到下面不会更差。 但是这条前面都是min的路选哪一条呢？显然是最后一个min节点的子节点里max取最小的。共k个min，所以取第k+1层所有节点的max函数的最小值。 但是，如果有的叶子深度小于k，是可以直接达到的，所以要取这些叶子的最小值更新答案。 但是，如果一个节点只有一个子节点，原来认为一条路前面都选min的贪心就不成立了 所以，我们换个思路，把每个单子节点深度设为父节点的深度，这样就可以计算出正确答案。 代码如下：（为什么运行了20秒...

我们设计状态 g[i][j]表示当前在i节点，处理到了第k棵子树时，还能向外扩展j层的最小花费。 f[i][j]表示当前在i节点，处理到了第k棵子树时，在i节点的子树中向下还有j层没有被覆盖时的最小花费。 那么状态转移(现在在点u,v为新子树)： g[u][j]=min(g[u][j]+f[v][j],g[v][j+1]+f[u][i+1]) 意思分别是： u点向上还要覆盖j层的话，也就是原来就可以向上覆盖j层，加上这棵新的子树的花费 u点向上还要覆盖j层的话，也就是这棵新子树可以向上覆盖j+1层，加上原来子树的花费 那么代码如下： #include<bits/stdc++.h> ...

首先我们考虑一个点连上它子树的不通电概率(这里转化为"不"是为了方便算,不转化也能做)有:f[u]=∏i(f[vi]+(1−f[vi])∗(1−wi))注意到v不通电和v通电但边不通电是互斥事件,故我们可以把概率直接加起来对于子树以外的部分,直接换根dp​就行,详见代码: #include <bits/stdc++.h> #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const int mxn=5e5+5; int n,cnt,hd[mxn]; dou...

思路：DP首先自己观察一波，发现如果有相邻两个格子都是红色的话，那么显然可以在任意位置都存在一个跳棋。可以让两个位置反复互相跳就好了。这样子第一问的答案显然就是0，否则的话第一问的答案就是偶数位置上0的个数。如果没有相邻的两个位置都是红格子，我们还可以得出第二问的答案就是偶数位置上红格子的数目。现在有两个红格子相邻，设f[i]表示在i这个位置要出现一个棋子的最小加入的跳棋数目，显然可以暴力dp。那么最终的答案就是所有偶数位置上的f的和。代码如下： #include<bits/stdc++.h> using namespace std; #define ll long long #d...

题目链接思路：BFS简单模拟两个函数，然后通过BFS不断将当前可能的两种操作放入队列，只要变成了B就说明是最小次数，代码如下： #include<bits/stdc++.h> using namespace std; #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int N=5005,mod=233; int vis[300]; const ll INF=999999999999999999; ll a,b; struct A{ ll now,num;...

题目链接：https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=117   思路：模拟   遍历链表并计数，每遍历 k 个元素就进行一次翻转，并接回结果链表，代码如下：    class Solution { public:     // 翻转一个长度为k的链表，返回新的头、尾指针     pair<ListNode*, ListNode*> revK(ListNo...

题目链接：https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=117&&tqId=35074&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking      思路：双指针/滑动窗口   分析：我们固定一段区间 (i, j)，记录该区间内所有数组元素的出现次数。每次 j++，并将其对应的数组元素对应次数加1，若该元素出现次数大于1，说明之前出现过，则左指针右移：i++，直到满足所有元素出现次...