利用等差数列进行构造。 #include <bits/stdc++.h> using namespace std; int main() { int n,k; cin>>n>>k; vector<char> v(n + 1); int pos = 1; for(char c = 'a'; pos <= n; c = (c - 'a' + 1) % 26 + 'a') { int now = 1; v[pos++] = c; while(k >= now)...

一道简单的dfs序的问题。 题目链接：求和 (nowcoder.com) 问题描述：n个节点，n - 1条边，根节点为k。现在又m个操作。 1 a x：将节点a的权值加上x 2 a：求a节点的子树上所有节点的和（包括a节点本身） 思路，发现以a为根的子树权值和是一个非线性的，不能用树状数组或者线段树来做。但是dfs序却有一个天然的顺序可以来处理。 如何求dfs序？可以用以下代码来找dfs序。 vector<vector<int>> g(n+1); for(int i = 1; i < n; ++i) { // u,v 建图 ...

做这题时发现是800分的题，感觉好奇怪，基环树怎么会怎么简单，看题后发现是构造一个满足条件的基环树的最小直径是多少。 那就推导一下： n = 3时，基环树如下： 最小直径显然是1。 n = 4时，基环树如下： 最小直径为2。 n = 5时，基环树如下： 可以发现，最小直径为2： 对于n > 3的基环树都可以进行这样的构造： 环中节点数为3，其余节点放到同一个节点上，这样构造到树的直径恒为2。 代码： _ = int(input()) print(1 + (_ > 3)) Graph Editor (csacademy.com)

整体++，方便写dp。不开LL60分。 const int N = 2e2 + 21; LL f[N][N]; int vis[N][N]; void inpfile(); void solve() { int n,m; cin>>n>>m; int tx,ty; cin>>tx>>ty; n++,m++,tx++,ty++; vector<int> fx({-1,-1,-2,-2,1,1,2,2}), fy({-2,2,1,-1,2,-2,1,-1}); vis[tx][ty] = 1; ...

牛牛的旅游纪念品 (nowcoder.com) 问题描述：一行有n个物品，要选m个，同时两个选的物品之间的间隔要大于等于k。求选m个的最大价值。 思路：线性dp。状态表示为：在第j个选了i个的最大价值。 转移方程： k \quad max(F(i,j-1), F(i-1,j-k) + a[j]) \end{cases}&preview=true"> 状态表示：F(i,j)表示在选了第j个物品后选了i个物品的最大价值。 如果i = 1，对于位置j来说有两个状态，要么选j的物品，要么不选就是前面的最大的物品。如果i > 1 && j > k，对于j也有两个状态...

数据范围2000，O(n*n)的算法可以过。 类似于双指针，找最小的那个字母对于的指针，之后将其向前或向后进行移动。如果两个字母相同，则判断哪个位置取了可以让之后的字符串更小即可。 代码： #include <iostream> #include <cstdio> using namespace std; const int N = 2e3 + 21; char s[N]; char ans[N]; int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; ++i) getch...

简单的多路广搜。 将最初病菌放入队列，之后依次出列，判断其向外蔓延的格子是否可以被病菌覆盖，可以被覆盖将其放入队列，否则不做操作。 代码： void solve() { int n,m; cin>>n>>m; // 按 从 0 到 n-1 进行建图 vector<vector<int>> ph(n, vector<int>(n)), vis(ph); queue<PII> q; // pair<int,int> ==> x,y rep(i,1,m) { ...

test

签到题 (nowcoder.com) 问题描述：添加、删除线段，并求总的线段并。 思路：线段树。 pushup(int u)函数用来将以u为根的两个儿子的的最小区间并的长度合并到结点u，对儿子的区间并长度减去获得到的最小区间并长度。 void pushup(int u) { int mi = min(tr[ls(u)].cover, tr[rs(u)].cover); tr[ls(u)].cover -= mi; tr[rs(u)].cover -= mi; tr[u].cover += mi; } pushdown(int u)函数进行lazy标记的向下覆盖。 vo...

二分 (nowcoder.com) 问题描述：根据对话，找可能的最多正确的对话。 思路： ​ 如果是 val +，说明猜的数val比答案要大，此时，答案在区间(-inf, val)。 ​ 如果是val -，说明猜的数val比答案要小，此时，答案在区间(val, inf)。 ​ 如果是val .，说明猜的数val等于答案，此时，答案在区间[val, val + 1)。 ​ 可以用差分求最大覆盖区间。数据离散，可以用map代替差分离散化。 代码： void solve() { LL inf = LONG_LONG_MAX - 123456789; int n; cin>&gt...

E-小A与小B_【2023陕西暑假集训】一场快乐的比赛 (nowcoder.com) 双向广搜，一个简单bfs，一个01bfs。 #include <iostream> #include <vector> #include <string> #include <cstring> #include <set> #include <map> #include <queue> #include <ctime> #include <random> #include <sstream>...

问题描述：略。 转移方程： F(k,i,j)=max(F(i−1,i,j),F(i−1,i−1,j),F(i−1,i,j−1),F(k−1,i−1,j−1))+g[i][j]F(k,i,j) = max({F(i-1,i,j), F(i-1,i-1,j), F(i-1,i,j-1), F(k-1,i-1,j-1)}) + g[i][j]F(k,i,j)=max(F(i−1,i,j),F(i−1,i−1,j),F(i−1,i,j−1),F(k−1,i−1,j−1))+g[i][j] 状态表示： ​ F(k,i,j)，k表示一共走了多少步，i和j表示两个传递坐标的横坐标。通过k - i + 1, ...

花店橱窗 (nowcoder.com) 问题描述：略。 转移方程： F(i,j)=maxi<k<j(F(i,j),F(i−1,k)+A[i][j])F(i,j) = max_{i < k < j}(F(i,j), F(i-1,k) + A[i][j])F(i,j)=maxi<k<j​(F(i,j),F(i−1,k)+A[i][j]) 状态表示： ​ F(i,j)表示第i个花放在第j个花瓶上时的最大值。 边界： F(i,j)=−infif1≤i,j≤NF(i,j) = -inf \quad if \quad 1 \leq i,j \leq NF(i,j)=−i...

拓扑序 神经网络 (nowcoder.com) 拓扑序，输入层找入度为0的，输出层找出度为0的即可。注意当 Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。中间层即使c小于等于0也是可以遍历的，而不是当入度为0时判断是否大于零再入队，优先级不一样。 #include <iostream> #include <vector> #include <string> #include <cstring> #include <set> #include <map> #include <queue> #includ...