wxyww

题解

未归档(12) 精品(28)

/ 注册

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

【每日一题】Three States

problem 有一个的方格，每个格子上有3种情况： 1.障碍，不能通过2.国家，有3种国家（标号为1,2,3）可以直接通过。3.平地，可以花费1的代价建造一条道路。然后就可以直接通过了。问最少需要在多少个平地上建立道路，使得3种国家之间两两连通。无法满足条件则输出-1 solution 三种国家...

最短路

2020-06-19

1 702

【每日一题】扫雷MINE

problem 一个的扫雷棋盘，第二列没有雷，每个位置写着附近雷的个数。然后在第一个棋盘上摆放一些雷，使其满足第二列的要求，问方案数。 solution 当第一列的第一个位置确定了之后，那么后面的位置也确定了。所以就枚举一下第一个位置是0还是1，然后看一下是不是能构造出可行方案，可以的话就会让答案加...

构造

2020-06-18

1 893

【每日一题】小仙女过生日啦

solution 如果给出的是一个凸多边形，那么问题其实就是三角剖分，用不相交的对角线将多边形划分为多个三角形，要求最大的三角形面积最小。求这个面积。用表示从第个点到第个点进行三角剖分的答案。转移就枚举一个满足，表示以这三个点为顶点的三角形的面积，这个可以直接用叉积计算。如果给出的不是凸多...

动态规划

2020-06-17

1 825

【每日一题】颓红警

problem 给出一棵个节点的有根树。第个节点有一个生命值，每次可以选择一个节点进行攻击，如果对号节点发起攻击，那么的子树(包括)中与距离为的点会受到的伤害(为给定参数)。如果一个节点的生命值已经小于0了，那么这个节点就已被消灭，同时以后也不能再对这个节点发起攻击了。问最少攻击多少次才能消灭所有节...

贪心

2020-06-17

5 850

【每日一题】字符串

problem 给出一个长度为的字符串，求出他的一个最短子串，要求这个子串里面包含了全部个小写英文字母。 solution 统计出每个位置到后面每种字符的最近距离。其中的最大值就是以当前位置为起点的答案。用当前最靠前的字符所在的位置，然后从前往后扫，对于每个位置都统计一下答案即可。 code #i...

字符串暴力

2020-06-15

1 520

【每日一题】背包

solution 按m为奇数和m为偶数分类来做。如果m为奇数，那么我们就先对所有物品按价值从小到大排序，然后枚举一下中位数，看枚举的中位数左边最小的个大小和右边最小的个大小之和是不是比要小。如果是，那么就对答案有贡献，否则就没有贡献。然后问题就在于如何找到一个位置左边最小的个大小和和右边最小的个大...

优先队列

2020-06-10

1 576

【每日一题】失衡天平

problem 将个物品分成两堆，使得两堆重量之差不超过m。问两堆重量之和最多是多少。 solution 用表示前i个物品，左边一堆的重量减去右边一堆的重量为j，最大的重量之和。对于一个物品有放在左边，放在右边，不放三种决策。对于重量为x的物品如果放在左边，就有如果放在右边，就有如果不放，就有$...

背包

2020-06-10

1 688

【每日一题】最大子矩阵

solution 注意到。考虑时如何做。令表示前i个位置选出了j段的最大价值。转移就是同样的方法我们可以类比出时的做法。令表示第1列选到了第i个数，第二列选到了第j个数，总共选了k个矩阵的最大价值。转移就枚举一下最后放的一个矩阵，如果最后一个矩阵放在了第1列，那就从转移过来。如果最后一个矩...

动态规划

2020-06-05

3 780

【每日一题】扑克牌

solution 这数据范围是故意误导人的叭。。。显然答案具有单调性，如果可以组成n副，那么一定能组成n-1副啊（这也太废话了叭）。然后很容易想到要二分答案。假设现在二分了一个答案x。考虑如何去判断是否可行。如果不考虑每副牌最多只有一个joker的话，那只要看一下是不是满足就行了。然后考虑每...

二分答案

2020-06-03

2 696

【每日一题】德玛西亚万岁

solution 状压dp。用数字来表示一行方案，对于一个状态x，如果x的第i位（二进制下）为1，表示这一行的第i个位置安排士兵。否则表示不安排士兵。先把每一行可能的状态都搜出来，也就是在满足相邻两个二进制位不都为1的条件下，搜出所有的方案。可以发现一行的方案数最多不超过400。然后将两个可以...

状态压缩

2020-06-02

2 651