牛客532105025号

分类

题解(22)

/ 注册

全部文章（共25篇）

题解 | # 小红的字符串构造#

利用等差数列进行构造。 #include <bits/stdc++.h> using namespace std; int main() { int n,k; cin>>n>>k; vector<char> v(n + 1); ...

C++

2024-03-25

0 244

题解 | #求和#

一道简单的dfs序的问题。题目链接：求和 (nowcoder.com) 问题描述：n个节点，n - 1条边，根节点为k。现在又m个操作。 1 a x：将节点a的权值加上x 2 a：求a节点的子树上所有节点的和（包括a节点本身）思路，发现以a为根的子树权值和是一个非线性的，不能用树状数组或者线...

C++ 深度优先搜索

2023-10-31

0 264

题解 | #小红的基环树#

做这题时发现是800分的题，感觉好奇怪，基环树怎么会怎么简单，看题后发现是构造一个满足条件的基环树的最小直径是多少。那就推导一下： n = 3时，基环树如下：最小直径显然是1。 n = 4时，基环树如下：最小直径为2。 n = 5时，基环树如下：可以发现，最小直径为2：对于...

Python3 Python2

2023-09-13

0 574

题解 | #[NOIP2002]过河卒#

整体++，方便写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,...

2023-09-01

0 350

题解 | #牛牛的旅游纪念品#

牛牛的旅游纪念品 (nowcoder.com) 问题描述：一行有n个物品，要选m个，同时两个选的物品之间的间隔要大于等于k。求选m个的最大价值。思路：线性dp。状态表示为：在第j个选了i个的最大价值。转移方程： k \quad max(F(i,j-1), F(i-1,j-k) + a[j]) ...

2023-09-01

0 418

题解 | #[USACO 2007 Nov S]Best Cow Line#

数据范围2000，O(n*n)的算法可以过。类似于双指针，找最小的那个字母对于的指针，之后将其向前或向后进行移动。如果两个字母相同，则判断哪个位置取了可以让之后的字符串更小即可。代码： #include <iostream> #include <cstdio> using...

2023-08-31

0 421

题解 | #病菌感染#

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

2023-08-30

0 435

题解 | #签到题#

签到题 (nowcoder.com) 问题描述：添加、删除线段，并求总的线段并。思路：线段树。 pushup(int u)函数用来将以u为根的两个儿子的的最小区间并的长度合并到结点u，对儿子的区间并长度减去获得到的最小区间并长度。 void pushup(int u) { int mi =...

C++

2023-08-20

0 396

题解 | #二分#

二分 (nowcoder.com) 问题描述：根据对话，找可能的最多正确的对话。思路：如果是 val +，说明猜的数val比答案要大，此时，答案在区间(-inf, val)。如果是val -，说明猜的数val比答案要小，此时，答案在区间(val, inf)。如果是val .，说明...

C++

2023-08-16

1 383

题解 | #小A与小B#

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

C++

2023-08-16

0 346