sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

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

【每日一题】10月19日对称二叉树

题目描述给你n个节点的二叉树，其中 n <= 1e6下面给出一行n个数据用空格分开，代表每个节点的权值大小。在下面n行，代表第 i 行的节点的左子树和右子树是谁，需要你判断最大的相等二叉树节点个数是几？ Solution 梦回数据结构，二叉树判断相等根据题目描述，可以使用递归定义判断，那么就...

2020-10-18

1 681

【每日一题】10月16日Quasi Binary，思维来自专栏

题目描述给你一个n，你需要只用0或者1两个数凑出一些十进制数累加等于n，并且需要十进制数的个数最小，并且输出最小个数k，以及那些数构成的？ Solution 只用0或者1构建很容易发现最少的个数就是n当中最大的十进制位的大小。其他位不需要那么大直接补0即可，比较显然这个条件。接下来只需要去模拟每一...

2020-10-16

2 613

【每日一题】10月15日[ZJOI2006]物流运输，最短路+dp 来自专栏

题目描述你需要走n天，这n天你都要从1走到m城市。并且给出城市之间的边关系以及长度（就是花费的时间）。但是有一个不同寻常的地方有些城市会在 [ a , b ] 的天数内无法进入。所以这些天中你不能走进这些城市之中去。并且当你选定路线之后，每做一次路线更换都要额外花费 k 的时间。现在询问你这n天从...

2020-10-16

2 675

【每日一题】10月14日Garland，树形dp 来自专栏

题目描述你有n个节点的一棵树，n的量级是1e6。后面存在n-1行，第i行代表第i个节点的父节点是谁，并且给出第i个节点的权值，父节点是0的节点就是根。现在需要你找出一种方案，把两条连接的边切断，把这棵树分成三颗树，并且三棵树的权值之和相等。是否存在这种切法。如果不存在的话，需要输出-1。 Solu...

树形dp

2020-10-15

2 681

【每日一题】10月13日筱玛爱线段树，两次差分

题目描述第一行输入数轴长度n，以及操作次数m，都是1e5的量级。后面存在m行，第一列是操作数，第二列是 l ，第三列是 r 。op==1,把数轴 [ l , r ] 中间的点全部+1op==2，把操作编号是 [ l , r ] 的操作重新执行一遍。 Solution 不看操作2，只看操作1，会发现...

2020-10-13

0 631

【每日一题】10月12日Angry Cows(Silver)，二分

题目描述在一根数轴上，你需要处理n个目标物，你只有k个炸弹，每个炸弹可以你随意放置在x的地方，它的爆炸范围是这个区间，你需要求解k个炸弹的情况下最小的r是多少？ Solution 滑动窗口，二分求解。目标物的下标不一定有序，我们直接对目标物的下标进行排序。紧接着二分这个答案r，使用一个类似与滑动窗...

2020-10-11

0 598

牛客IOI周赛19-普及组

A、小y的考试结构体变量统计长度以及下标，对长度排序，在一个个判断就行了，符合那个情况就输出下标字母，最后输出C #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);...

2020-10-11

1 625

牛客小白月赛28

A、牛牛和牛可乐的赌约正面不容易直接得到答案，那就 1 - 反面的答案。如果我们求得不是他输的概率而是赢的概率的话，那就十分好求答案就是，我们直接拿1减掉，再通过费马小定理，逆元运算求得MOD下的值即可。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt"...

2020-10-05

0 684

【每日一题】9月29日Stressful Training，最小堆，二分，贪心来自专栏

题目描述第一行输入共有N个同学，带了N个笔记本，N < 2e5 + 1，需要坚持 K 分钟。第二行给出N个整数，每个整数代表笔记本初始电量，a[i] < 1e12 + 1第三行给出N个整数，每个整数代表笔记本每分钟消好电量，b[i] < 1e7 + 1现在你可以买一个充电器，再每...

2020-10-01

0 832

【每日一题】9月28日[SCOI2009]最长距离，DFS 来自专栏

题目意思给你个01地图大小n * m，你只能走最大T个1的地方。问你能最远走多远？起点随便选终点距离最远即可。地图规模最大30 * 30 解题思路地图规模比较小，可以随便写复杂度，那么我们直接使用最暴力的算法，枚举每一个位置成为起点，对每一个位置算一次DFS，把去到每一个点的最短1的数量算出来，...

2020-09-30

1 658