ZeRoLJ42

题解

/ 注册

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

【每日一题】【5月22日】[CQOI2009]中位数图

题意：给出的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是。题解：先考虑一段区间中位数为有什么性质：这一段区间内大于的数和小于的数一样多，并且包含。然后做一个简单的转化，大于的数记为，小于的数即为。那么中位数为的区间就有：区间包含所在...

每日一题

2020-05-21

0 625

【每日一题】【5月21日】图的遍历

题意：给定无权双向图，顶点数为，边数为。从顶点开始遍历，每次“走两步”。问最少需要添加多少条边，可以走遍整个图。解法：先考虑连通块内的情况：对顶点进行黑白染色，那么和顶点颜色相同的点，都可以直接通过原图中的边走到。然后再考虑从某个点如何“走两步”走到另一个颜色不同的点：若某个顶...

每日一题

2020-05-20

0 623

【牛客算法竞赛入门课第二节习题】Laptop

题意：给定个整数对，问存在多少个满足：，其中。题解：先对数对按排序，那么对于，会有。因此，对于，我们只需要考虑是否存在。这样我们逆序遍历，维护一个后缀最大的值，即可判断是否满足条件。 Code： #include <bits/stdc++.h> us...

牛客算法竞赛入门课第二节习题

2020-05-19

0 784

【每日一题】【5月20日】简单瞎搞题

题意：一共有个数，第个数是。可以取中任意的一个值。设，求种类数。解法：比较典型的分组背包问题：第个数取中的任一个值。表示前个数的平方和为是否可行。初始化：转移方程：复杂度为。由于这一行的值仅与有关。故可以优化空间，第一维大小为，即仅保存上...

每日一题

2020-05-19

0 579

【每日一题】【5月19日】比赛

题意：比赛中有道题。对于第道题，你有的概率自己解出来，有的概率从左边队伍听到题解，有的概率从右边的队伍听到题解。问解出道题的概率各是多少？解法：枚举对于第道题，最终能解出来的概率为。然后二进制枚举每道题是/否解出来，计算对应情况的概率，加到对应题数复杂度为 dp...

每日一题

2020-05-18

0 601

【每日一题】【5月12日】模拟战役

题意：齐齐和司机各有一个的矩阵表示各自的方格地图。格子内可能会有 '*' 表示大炮。齐齐先手攻击，选择一个大炮攻击司机的大炮。被击中的大炮会产生的波及区域。被波及的大炮会接着产生波及区域。齐齐选择的的大炮在攻击后会暴露视野，意味着接下来会被司机攻击（如果司机还存在大炮的话）。问齐齐在消灭了...

每日一题

2020-05-16

0 566

【每日一题】【5月18日】「土」秘法地震

题意：给定一个的二维矩阵，每个位置为 0 或者 1。询问所有的子矩阵中存在的矩阵个数。解法：二维前缀和。先从一维说起，个元素的一维数组为，下标从到。那么对应的前缀和数组的定义为：求前缀和的递推式为：代码实现： s[0] = 0; for(int i = ...

每日一题

2020-05-15

0 593

【每日一题】【5月15日】储物点的距离

题意：给定一维数轴上个点之间的距离，每个点储存一些货物。每次询问将一段区间的货物全部移动到点的代价和。储物点有个货物，全部移动到点的代价为。解法：前缀和。先根据和，之间的关系分情况讨论。先写下第一种情况的计算式：令，则令，则：。 ...

每日一题

2020-05-14

0 705

【每日一题】【5月14日】maze

题意：个格子组成的迷宫，迷宫中有陷阱 '#'，和可通行的点 '.'，起点为 'S'，终点为 'T'。每次移动代价为 1。另有传送阵若干，可以从传送阵的入口传送至出口，代价为 3。问从起点移动到终点的最小代价。解法：不考虑传送阵，最裸的 BFS。考虑传送阵，也算是比较经典的模型。有两种解法，但本...

每日一题

2020-05-13

0 692

【每日一题】【5月13日】加分二叉树

题意：给定一棵含个节点的二叉树，其节点编号为到。二叉树的中序遍历为。每个节点有一个分数。任一棵子树subtree（也包含tree本身）的加分计算方法为：subtree的左子树的加分 subtree的右子树的加分＋subtree 的根的分数。若左右子树中某一子树为空，规定其分数为...

每日一题

2020-05-12

1 827