horz

题解

/ 注册

全部文章 / 题解（共38篇）

追债之旅

分析简简单单最短路。只是要记录一下走了几天罢了，定义为从 1 到 i 走了 j 天的行程花费和欠债人挥霍的钱的最小总和。。 #include <bits/stdc++.h> using namespace std; #define mem(a,b) memset(a,b,sizeo...

2020-08-07

1 707

蓝魔法师

题意给出一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模。分析我们定义表示为i的子树的所有联通块大小不超过k，并且i所在联通块大小为j的方案数。对于每条边，假设为 u —...

2020-08-07

0 837

牛客算法周周练18

A 小K的疑惑显然我们选的三个点必须是两两之间的距离之差是偶数，我们选定一个参考点（也就是根），求出其他点到这个点的距离，然后距离为偶数的为一组，奇数的为一组，答案就是偶数的个数的三次方加上奇数的个数的三次方（可以重复选） #include <bits/stdc++.h> usi...

2020-08-04

0 722

小A的最短路

首先假设我们不考虑 u 和 v 两点的缆车，那么 x 和 y 之间的路程就是 x 和 y 的深度减去他们的 lca 的深度。接下来我们考虑使用缆车，无非也就两种情况： x -> u -> v -> y x -> v -> u -> y 我们对上面三种情况取一...

2020-08-04

0 530

购物

做完今天的N1，然后发现这不是一样的题目吗？？？题意我们每天可以最多购买m个糖果，连续买 k 个需要额外支付。保证每天吃一个糖，求买n个糖果的最少代价。分析我们定义dp[i][j]，表示前i天买了j颗糖的代价。我们对 m 颗糖可以贪心一下，一定是买更便宜的糖。然后枚举今天买几颗即可。...

2020-08-04

1 732

Alliances

这题太变态了吧。分析我们预处理出每个帮派的lca节点，当帮派合并的时候，我们就可以求各个帮派的lca的节点。假设首都节点是u,各个帮派的lca是pos，分两种情况当lca(u,pos) ！= pos的时候，说明u不在pos的子树下，答案就是dis(u,pos)。当lca(u,pos) ...

2020-07-11

0 715

牛客算法周周练14

A题不会 Circle 显然按排列是最大的，答案就是。 Tree 换根。一个节点的联通点集的数量可以通过子树和非子树求出来。被逆元虐了，是没有逆元的，因为除以是不合法的。 PUBG 求两个值的，注意爆「水」悠悠碧波联想到的，以结尾的子串可以匹配到的最长前缀的长度。我们直接求就行了，并且要小...

2020-07-09

1 519

矩阵取数游戏

题意一个的矩阵，每次每行取一个数，取次。每行取数的得分被取走的元素值。求得分的最大值。分析显然每行怎么取值都是相互独立的，不会影响其他行，所以我们只需要考虑如何取值才可以让一行的得分最大化。很明显，我们最先只可以取第一个或者最后一个数，第二次取剩下的第一个或者最后一个数。我们可以...

2020-07-09

0 696

最短路

题意给一个连通图，每次询问两点间最短路。分析首先我们取联通的条边，利用，处理出询问的答案。然后我们最多还剩下条边，我们对这些边的点跑，处理出所有点到该点的距离，然后遍历所有的询问，更新答案。时间有点紧 #include <bits/stdc++.h> using namespa...

2020-07-06

3 875

平衡二叉树

题意给定和，要求一个二叉树，使得任意节点左右子树深度之差不超过，求左右子树节点差值的最大值。分析我们可以使左子树节点个数最多，右子树节点个数最少。左子树显然是一颗满二叉树。考虑如何求右子树：首先深度尽量小，为。我们定义表示深度为的子树最少总节点个数。则转移方程，可以理解为左边放了一颗...

2020-07-03

2 691