hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

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

[土]秘法地震

题意：求在一个nm的01矩阵中有多少个不全为0的kk矩阵; 思路：纯模拟代码： #include<bits/stdc++.h> #define ll long long #define inf 1000000007 using namespace std; char s[1005]...

模拟

2020-05-20

0 543

储物点的距离

题意：在一个数轴，有n个储物点，每一个储物点有b[i]个东西，同时第（i+1）个储物点距离第i个储物点a[i]的距离。进行m次查询，每次查询给与x,l,r三个整数，表示求将区间[l,r]个储物点的东西全部运到第x个储物点的代价？比如储物点i有b[i]个东西，要运到储物点j，代价为b[i] * dis...

前缀和

2020-05-20

0 725

maze

题意：在一个n x m个格子组成的迷宫，'#'表示的格子不能走，'.'表示可以走。起点用'S'表示，目的地用'T'表示。只能向上下左右相邻的格子移动，每移动一次花费1秒。有q个单向传送阵，每个传送阵各有一个入口和一个出口，在入口处，你可以选择是否传送，传送过程会花费3秒；注意：一个格子可能既有多个入...

bfs 优先队列

2020-05-20

0 577

加分二叉树

题意：给出一个n个节点的二叉树，中序遍历为1，2，3,......，n;每个节点都有一个分数（均为正整数），任一棵子树subtree的加分计算方法如下：subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数求二叉树的最大分数和前序遍历？思路：f[i][j]为从第i个...

dp

2020-05-18

0 563

模拟战役

题意：给出一个整数m,再给出8行字符串，前4行为司机基地情况，后四行为齐齐基地情况，求齐齐在摧毁司机全部大炮后最多剩多少门大炮？（无法全部摧毁司机大炮则输出-1）思路：dfs求出司机基地有多少个大炮连通块，再用dfs求出齐齐每一个大炮连通块的大炮个数并保存，由于保存最多的大炮，使用的大炮所在连通块...

dfs 贪心

2020-05-18

0 551

[火]皇家烈焰

题意：有n个格子排成一列对于一个格子，里面会有以下几种字符： 0：这个格子没有烈焰，且其左右两个格子均没有烈焰 1：这个格子没有烈焰，且其左右两个格子中只有一个烈焰 2：这个格子没有烈焰，且其左右两个格子中均有烈焰 *：这个格子有烈焰？：未告诉你本格情况求n个格子分布合理的情况数？思路：dp ...

dp

2020-05-07

0 608

滑雪与时间胶囊

题意：有一个n个节点和m条边的图，每个节点有一个高度，路只能从一个点到一个高度不大于它的另一个点，你可以从你所经过的任何一个点出发去下一个点，求经过的点最多为多少个，且此时经过的最短路为多少？思路：prim算法中优先队列第一关键词以所到达的节点的高度降序，第二关键词以路程升序代码： #inclu...

prim

2020-05-06

0 585

换个角度思考

题意：给定一个序列，有多次询问，每次查询区间里小于等于某个数的元素的个数思路：将所有询问按x升序排列，a序列也按升序排列，然后每次询问当前[l,r,x]之前把ai小于等于x的ai在树状数组中加入他对应的原下标（只需要对应原下标位置+1就行)，然后询问[l,r]区间有多少个数。代码： #inclu...

树状数组离散

2020-05-06

0 496

Symmetric Matrix

题意：求满足以下条件的n*n矩阵的个数：1.所有元素的值属于{0，1，2}；2.为对称矩阵；3.每一行的值的和为2；4对角线的值为0；结果对m取模。思路：我们知道无向图的邻接矩阵是对称的，所以将四个条件可以转化为找满足没有自环的n个节点且每个节点有且仅有二条边的无向图有多少个？我们可以知道这样的无...

数学 dp

2020-05-06

0 825

美味菜肴

题意：有n种食材，m种菜肴，每种菜肴给出所需食材和美味值和制作时间，因为每种食材以a[i]的速率变得不新鲜，求在t秒总美味值最大为多少？注意：最大总美味值可能为负。思路：贪心+01背包贪心：设二种相邻菜肴，第一种所需食材变的不新鲜的速率为w[i].a,美味值为w[i].b，制作时间为w[i].c...

贪心 dp

2020-05-04

0 917