zqy1018_

分类

题解(31)

/ 注册

全部文章（共31篇）

NC14700 追债之旅

题目大意给定一张无向图，每条边有费用，每走条边会有额外费用，至多走条边。问从点到点的最小费用路。题解把每一个点拆成个点，相当于对点记录一下时间即可直接套用 Dijkstra 算法。 #include <bits/stdc++.h> #define REP(te...

2020-08-05

0 806

NC14526 购物

题目大意有天，每天可购买个糖，不同时间、不同的糖有不同价格。每天购买个糖有额外代价。须保证第天结束时累计购买数达到。问最小代价。题解写了一个朴素的二维 DP，预先对每一天的糖价格排序，然后设为第天结束时买了个糖的最小代价。则其中表示前天最小的个糖的...

2020-08-04

1 627

牛客编程巅峰赛S1第8场 - 王者简要题解

A 由题意，设 b 的前两个数为。那么公差最多有 9 种，即。因此暴力枚举并判断即可。 B 可以用树形 DP，更简单的做法是发现答案等于所有边权和的两倍减去树的直径。 C 考虑固定右端点，计算可行的区间左端点数目。发现区间最大值随着左端点左移单调不减，区间最小值随着左端点左移单调不增。这表明如...

2020-08-01

1 785

NC20860 兔子的区间密码

题目大意给定，求从中任取两个数（可以相同）异或的最大值。多组数据。题解首先如果就直接返回，下面均讨论的情况。然后看的最高二进制位是否相同，如果相同就表明中所有数这一位都是相同的，这一个二进制位不会对答案造成任何影响，因为异或后一定会消掉。从而可以把最高那位减掉，对新的...

2020-07-30

0 748

NC20857 Xor Path

题目大意定义为树上编号为两点路径上的点权异或和。求所有的异或和。题解由于都是异或和，因此只需要对每一个点考虑其在所有路径中出现的次数即可。将出现分成三个部分：点出现在其子树内点和外部点的路径上、点连接其子树内点的路径上、点出现在其子树内点之间的路径上。分别统计即可。时间复杂度为。...

2020-07-29

0 701

NC20663 Max Power

题目大意给一个层的三角形，第层有个元素。设第行第列的元素为。一开始只有第一层的元素可选择，其他层的元素可被选择当且仅当和均被选择。求共选择个元素的元素和最大值。题解 DP。设表示后列用完，选了个元素，且第列共选择了前行元素的最大和。那么有...

2020-07-28

0 904

牛客编程巅峰赛S1第2场 - 黄金&钻石 C 题解

C 我们先定义两种计算：前向，即给出，计算这个序列的和，其中序列长为。反向，即给出，计算这个序列的和，其中序列长为。然后我们可以把新牌堆分拆成上下两部分：下面张牌，上面张牌，分别计算这两个部分对答案的贡献。先分析下面张牌的成分。一开始做了次操作后，原牌堆自...

2020-07-16

2 683

NC20242 [SCOI2005]最大子矩阵

题意给定一个的矩阵，。求从矩阵中选出个不相交小矩形，使得它们的权值和最大。题解先研究的情况。显然这等价于经典的“最大子段和”问题。可以在线性时间内解决。再研究的情况。设为前行中选出了个矩形可以得到的最大权值和。那么转移方程为三个选项中取最大值。其中 ...

2020-06-14

0 714

NC23486 小A与小B

题意给定一个迷宫，迷宫中 A 可以向 8 个方向移动（八联通的 8 个方向），B 可以向 4 个方向移动（四联通的 4 个方向），但一单位时间可以移动两次。不能通过障碍物。问 A 和 B 是否能相遇、最早什么时候相遇。题解一开始理解错意思了，以为相遇必须是在某一时刻到达同一个格子。于是开始纠结...

2020-06-12

0 528

NC19916 [CQOI2010]扑克牌

题意给定种牌和每种的个数，给定个王牌。有两种方案构成一套牌：种牌各一张。种牌各一张加上一张王牌。问最多可以构成的套牌数目。题解一开始写了一个贪心，利用堆每次选择数目最少的种数，用王牌去补。然后超时了，因为可以很大。然后开了窍，写了一个二分。大概就是二分答案为。设...

2020-06-08

0 620