998244353

题解

Atcoder(3) C/C++(21) Codeforces(6) study(2) 动态规划(2) 图论(1) 基础知识(30) 字符串(2) 思维(15) 技巧(1) 搜索(1) 搜索基础(1) 数论(5) 未归档(14) 简单题解(1) 线段树(8) 贪心(1)

/ 注册

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

排座椅

题意：行列小孩，给定个横向分界线和个纵向分界线，总共有对小孩会交头接耳，问将这些分界线放在什么地方会使得交头接耳的小孩尽可能少。数据范围：题解：乍一看数据范围还以为是，分析完后横向和纵向相互独立，没有影响。所以每个方向单独考虑即可。即统计交头接耳的小孩的数量然后从大到小排序即可。注意输出的时候先输...

2020-08-07

0 583

追债之旅

题意：小明现在要追讨一笔债务，已知有座城市，每个城市都有编号，城市与城市之间存在道路相连（每条道路都是双向的），经过任意一条道路需要支付费用。小明一开始位于编号为的城市，欠债人位于编号为的城市。小明每次从一个城市到达另一个城市需要耗时天，而欠债人每天都会挥霍一定的钱，等到第天后（即第天）他就会离开城...

2020-08-06

0 893

点权和

题意：给你一棵树，最开始点权为。次操作，每次将与一个点树上距离的所有点点权，之后询问这些点修改后的点权和。输出一个数，即这次操作的答案的值，如果是第次操作，这次操作结果为,则这个值加上输出值对取模的结果。数据范围：题解：本题由于时间卡的很死，故所有操作都需要进行。是指的儿子个数，表示的父亲。指...

2020-08-06

0 726

2020牛客多校第七场 B.Mask Allocation

题意：有个类医院，个类医院，共个口罩。要你对这些口罩进行分箱，使得将所有口罩分给类医院时可以均分，将所有口罩分给类医院时也可以均分。数据范围：题解：设，那么一个箱子最多个口罩，否则若有某个箱子口罩数多于，当分给类医院时，必然存在某些医院分到多于个口罩，某些医院分到少于个口罩。所以可以先分出来箱...

2020-08-05

0 537

蓝魔法师

题意：给定一棵个点的树，问有多少种删边方案使得删边后每个连通块大小不大于，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对取模数据范围：题解：表示以为根，连通块的大小为的方案数。考虑的一个儿子：和的边被断开，则的连通块大小对无影响，与的边未被断开，则 ...

2020-08-05

0 652

购物

题意：小需要储备天的面包，面包店每天生产个面包，第天生产的第块面包的价格为，同时，一天购买块面包需要额外花费，现在问储备至少块面包的最低价格是多少。数据范围：题解：分组背包问题。从低价到高价开始选择面包，本题关键是考虑额外的部分。考虑第天的第块面包，需要多加，对于第块面包，需要多加，所以对于第块...

2020-08-05

1 705

2020牛客多校第八场 I-Interesting Computer Game

题意：给定组数，每组两个数，和。在第组数时，有三种操作：可以不选，如果未被选过，可以选择，或者没被选过，可以选择，但是一次最多选一个数。现在问组数最多可以选择多少个。题解：考虑将和连条边。假设最后有个连通分量，考虑第个连通分量，如果该连通分量的边数不小于点数，则加上点数，否则加上点数减。可以这...

2020-08-04

0 559

2020牛客多校第八场 G-Game Set

题意：太长了，懒得解释了。题解：暴力模拟即可，官方题解给定的是有相关证明在内一定可以找到解，所以直接暴力冲。但是如果极端情况的话还是可能被卡的可能，毕竟组，所以感觉还是可能的。具体就是直接模拟前两个个模块的是否相同，出现了该模块的三个直接，如果前两个某个模块不是且相同，则第三个模块也必须和他们...

2020-08-04

0 452

2020牛客多校第八场 K-Kabaleo Lite

题意：有种菜，每种菜利润为，数量为，问在尽可能服务多的客人的情况下，可以获得的最大利润是多少（可以为负数）。注意：除了吃第一种菜，吃第种菜前必须先吃第种菜。总共有组数据。数据范围：题解：最多客人数即。第一种：整体考虑。由于第一种菜必选，故从第二种菜开始考虑每次贪心地选可以吃到的总利润最大的菜，...

2020-08-04

0 482

小A的最短路

题意：给定一棵个点的树，边权均为，以及多出的一条边权为的边，询问树上两点之间的路径的最小权值。题解： https://ac.nowcoder.com/acm/problem/19814 这道题的弱化版，只多出了一条边权为的边。预处理树上倍增关系，然后加入这条边权为边，每次取直接在树上走的最短路权...

2020-07-31

0 540