离ACM还有一定距离

分类

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

/ 注册

全部文章（共51篇）

[每日一题]滑雪与时间胶囊

题意给定一个 n 个点 m 条边图，只能从点权高的点走到低的，且可以不计路程的瞬移至之前走过的某个点，求经过最多点的最短路径。 solution 求经过最多点显然直接bfs，建图的时候建高到低的单向边即可，（值得注意的是，若点权相同，则为相互可达的，需要建双向边）。然后根据bfs遍历可以走到的点，...

2020-04-30

0 640

【每日一题】换个角度思考

题意给定一个长度为的数组，次询问查询区间内的元素个数。 solution 考虑树状数组。我们在查询区间的个数时，为了更好计数，这个区间应该不包含的元素才行。因此我们不妨离线，将询问的从小到大排序，将数组也从小到大排序，这样从小到大处理询问，每次处理时只将的数挂到树的对...

2020-04-29

0 708

【每日一题】美味佳肴

题意件食材（每种食材的数量可以视为无限），小明连续工作时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第道菜肴有三个属性，，，是该菜肴的美味值，是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为：，完成这道菜需要 ...

2020-04-27

1 780

【每日一题】Removeal

题意给定一个长度为的数组，求长度为的不同子序列个数。（） Solution 表示长度为，删除个元素的子序列个数，不考虑重复的话，有（即已经删除了个和已经删除了个再删除这一个的情况）。考虑去重。如果是单纯求不限长度的不同子序列的去重，容易得到：（为上一次出现的...

2020-04-24

1 848

【每日一题】子序列

题意给定一个由n个元素组成的序列 { a1, a2, a3,..., an } ，她想知道其中有多少个子序列 { ap1, ap2, ..., apm } ，满足对于所有的 , apipj < apjpi成立。 Solution1 py + dp直接冲。 n, mod = int(inpu...

2020-04-23

0 555

【每日一题】K-th Number

题意给定一个长度为的数组 A ，把所有长度 >= 的区间中的第大值插入 B 数组中，求 B 数组的第大数。 Solution 这种显然二分答案题我们主要关心问题。如何计算第大数的区间个数？假设区间中刚好有个数，则区间全部满足第大数。因此考虑...

2020-04-21

1 478

【每日一题】华华给月月准备礼物

Solution:木棍合理范围即初始区间是[0,n项和/k]，n项和/k是理想情况不考虑木棍分段的最大长度，或者默认用一个比较大的数字开始分也可以。然后二分棍子的长度，根据截得的段数总和来判断是否满足要求。 #include<stdio.h> int main() { long ...

2020-04-20

0 600

【每日一题】糖糖别胡说

Solution:如果直接从前往后，则后面的又会影响到之前到，所有干脆从后往前考虑，这样就不会对之前计算到的造成影响。从后往前维护两个队伍各自的最大值和会被增加的战斗力，如果前面的战斗力小于另一个战队的当前最大值，则被消灭，保证了每个人只会被计算一次。 #include <bits/stdc+...

2020-04-20

0 647

【每日一题】逆序对

题意题意很简单，求长度为n的01串逆序对数量和。( n <= 1e18 ) solution 任意选两个位置，令，这样一定能产生逆序对，这样有种选法。剩下的位置随便放，有种选法，总方案数即为答案。( 注意 1 需要特判 ) #include <bits/stdc++.h>...

2020-04-20

0 500

【每日一题】Treepath

题意：给定一棵n个节点的树，求偶数长度路径的数量。 Solution1: 考虑树的深度对距离的影响，可以发现，深度奇偶性相同的点之间的距离总是偶数。证明：我们先将深度更大的点走到和另一个点深度相同，显然需要偶数步，然后两个点同时移动到最近公共节点，可知所用的步数是相同的，加起来也是偶数。 Cod...

2020-04-19

1 535