hnust_yangyanjun

分类

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

/ 注册

TA的专栏 30篇文章 0人订阅

每日一题题解

30篇文章 895人学习

全部文章（共125篇）

[CQOI2009]中位数图

题意：给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。思路：如果我们把比大于k的值变成1，比k小的值变成-1，那么计算从左边到k区间的值，并记录个数，加上为0的个数，再计算从右边到k区间的值，加上相反数的标记个数，如果值...

2020-05-22

0 562

图的遍历

题意：有一个n个点节点m条边的无向图，从点1开始遍历，按照每次“走两步”遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以最少加几条边，可以完整的遍历整个图？思路：如果一个连通块中有奇数环，则该连通块可以全部遍历到，加一条边可以使二个连通块合在一起，最后在一个大于等于3的连通块中...

图

2020-05-21

0 581

简单瞎搞题

题意：一共有n个数，第i个数是xi, xi可以取 [li , ri] 中任意的一个值。设 S = ,求S种类数? 思路：bitset,01背包bit[i]为前i个数中能得到的值的那一位为1，否则为0；当加上x[i+1]的平方时相当于bit[i]向左平移了x[i+1]的平方个位置所以bit[i...

bitset

2020-05-21

0 533

比赛

题意：一场比赛总共有12个题，对于第i个题，有a[i]的几率解决它，如果不能解决，则你有b[i]的概率从左边那个队那里听会这个题的做法，有c[i]的概率从右边那个队那里听会这个题的做法，请问最终你们队伍解出0-12题的概率分别是多少？思路：每一题单独的解决概率的d[i]=a[i]+(1-a[i])...

dp

2020-05-21

0 466

[土]秘法地震

题意：求在一个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