离ACM还有一定距离

题解

学习笔记(7) 牛客多校2020(1)

/ 注册

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

【每日一题】加分二叉树

题意有一颗二叉树，树的每一个节点都有一个值，设他的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数若某个子树为主，规定...

2020-05-16

0 1074

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

题意给定和两点的距离和点的货物数量，次询问将所有物品搬到点的总费用（区间内每个物品各自离点距离和）。（） soltuion 前缀和维护：表示每个储物点离原点0的距离，表示前个储物点共有多少货物，表示前个储物点的所有物品到原点0的和。，即所有物品到原点的...

2020-05-15

1 954

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

题意求矩形区域中长度为k的正方形中含有1的正方形个数。 solution 枚举正方形只需要确定对角两个点即可，然后用二维前缀和维护 [0,0]-[i,j]含有1的个数，枚举正方形区域时二维前缀和查询该区域1的个数是否da即可。 #include <bits/stdc++.h> usin...

2020-05-15

0 602

【每日一题】Moovie Mooving

题意有 N 部电影，每部电影有不同的放映时常，和若干个放映起始时间。Bessie 可以在一部电影播放过程中的任何时间进入或退出放映厅。每部电影她最多看1次且她不能在看一部电影的过程中，换到另一个正在播放相同电影的放映厅。 Bessie 能不能从0到L分钟连续不断地观看电影？如果能，计算她最少看几部...

2020-05-15

0 548

【每日一题】maze

题意走迷宫，走一步花费1s，走传送花费3s，求活着到达终点的最短时间。 solution bfs裸题，把起点扔入队列，然后往四个方向移动搜，或者进入传送，注意路径标记和清空。 #include <bits/stdc++.h> using namespace std; typedef l...

2020-05-13

0 887

[每日一题]模拟战役

题意给定一张地图，表示我方和敌方2个人的地形布局，大炮间互相攻击，并且会影响3*3的区域，并且可以连带，问如果要摧毁所有敌方的大炮后，最多可以保留多少自己的大炮。 solution 分别对我方和敌方进行dfs求联通块数量，如果我方联通块更少，肯定输，输出-1。否则我们就用大炮数量最少联通块的去打对...

2020-05-13

0 708

【每日一题】过河

题意：桥长度为，分布有个石子，青蛙每次可以跳的距离,问青蛙过桥至少要踩多少个石子。 solution 这是个很显然的dp题，难点在于他的达到了，所以我们需要压缩一下。当时，答案就是位置能被整除的石子个数。当时，我们可以发现：假设当前位置为，那么之后的所有...

2020-05-13

0 734

【每日一题】codeJan与旅行

题意给定n个城市坐标，每个城市可以多次到达，问一共到m次，最短花费。给出起始位置，并且起始位置不在城市上。 solution 不难猜到要么就是一条路走到黑要么就是在路上找的两个城市然后一直往返。因此我们从原来的位置，往左右两边一直走下去，顺便枚举路上每两座城市之间横跳的花费，维护最小花费，同时注意...

2020-05-12

0 518

【每日一题】「火」皇家烈焰

题意现在帕秋莉告诉你一部分烈焰的分布情况，请你告诉她可能的情况有多少种对于一个格子，里面会有以下几种字符： 0：这个格子没有烈焰，且其左右两个格子均没有烈焰 1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰 2：这个格子没有烈焰，且其左右两个格子中均有烈焰：这个格子有烈焰 ?：未告诉你本格...

2020-05-10

0 685

【每日一题】合并回文子串

题意给定两个字符串，各取出一个子串接在一起，求最长回文子串的长度。 solution 先考虑普通的求最长回文子串的dp做法: 表示子串是否为回文串。那么，容易得到： && 。由于是由转移过来的，所以我们需要倒着遍历： Code for (int i = s.siz...

2020-05-02

0 702