- 2024-05-09P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
链接:https://www.luogu.com.cn/problem/P2341题目:思路:tarjan缩点:把所有强连通分量缩成一个点,然后统计出度为0的缩点,如果只有一个,那么能成为明星的数量就是该缩点扩充后的个数;如果不止一个,那就是0.代码:额,就是不知道为什么debug了两节课.......#include<iostream>#include<v
- 2024-01-13解题报告P2501 [HAOI2006] 数字序列
P2501[HAOI2006]数字序列题目描述现在我们有一个长度为\(n\)的整数序列\(a\)。但是它太不好看了,于是我们希望把它变成一个单调严格上升的序列。但是不希望改变过多的数,也不希望改变的幅度太大。输入格式第一行是一个整数,表示序列长度\(n\)。第二行有\(n\)个整数,第\(
- 2023-09-17P2501 [HAOI2006] 数字序列
先来看第一问。发现直接做要考虑两数中间的数能否变得合法,所以按套路将\(a_i\)减去\(i\),这样就只要变成单调不降,只要两数合法中间的数就一定能变得合法。考虑不改变的那些数,它们一定单调不降,所以答案就是序列总长度减去最长不下降子序列的长度。接下来看第二问,尝试观察一些性
- 2023-09-15P2501 [HAOI2006] 数字序列
原题是思路非常值得学习的一道题第一问:首先我们感性上觉得这题应该和LIS有一点关系,但里面有一点问题:1750505018如果我们求LIS的话,我们会认为只需要改掉505050即可,但其实我们只改掉这些数,我们是无法做到让数单增的我们发现这个限制写成数学语言即为:\(a_i-a_j\geq
- 2022-11-25P2341 [HAOI2006] 受欢迎的牛 G
每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的问有多少头奶牛可以当明星 缩点
- 2022-11-21洛谷 P2501 [HAOI2006]数字序列
洛谷P2501[HAOI2006]数字序列第一问实质是最大化不修改的数。假设\(i,j\)不修改(\(j<i\)),那么必须满足\(a_i-a_j\geqi-j\)。移项:\(a_i-i\geqa_j-j\)。设\(b_i=a
- 2022-08-241037 [HAOI2006]聪明的猴子 看有多少能到达所有点 最小生成树
链接:https://ac.nowcoder.com/acm/contest/26077/1037来源:牛客网题目描述在一个热带雨林中生存着一群猴子,它们以树上的果子为生。昨天下了