yjjr's blog

还有点梦想的咸鱼OIer

Bzoj4377 [poi2015]kurs szybkiego czytania

区间求交集的转化

标签:数学 题目 题目传送门 Description 给定,其中互质。定义一个长度为的串,其中当且仅当。 给定一个长为的小串,求出小串在大串中出现了几次。 Input 第一行包含整。...

Bzoj3750 [poi2015]pieczęć

模拟不水题

标签:模拟 题目 题目传送门 Description 一张的方格纸,有些格子需要印成黑色,剩下的格子需要保留白色。你有一个的印章,有些格子是凸起(会沾上墨水)的。你需要判断能否用这个印章...

Bzoj1103 [poi2007]大都市meg

树的dfs序转化

标签:dfs,树状数组 题目 题目传送门 Description   在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员Blue Mary也开始骑着摩托车传递邮件了。不过,她经常回...

洛谷4996 咕咕咕

fstqwq骗人去写状压DP,摔)

标签:组合数 题目 题目传送门 题目描述 小 F 是一个能鸽善鹉的同学,他经常把事情拖到最后一天才去做,导致他的某些日子总是非常匆忙。 比如,时间回溯到了 2018 年 11 月 3 ...

洛谷4995 跳跳!

青蛙作为题目背景,正解大多是贪心2333

标签:贪心 题目 题目传送门 题目描述 你是一只小跳蛙,你特别擅长在各种地方跳来跳去。 这一天,你和朋友小 F 一起出去玩耍的时候,遇到了一堆高矮不同的石头,其中第 块的石头高度为 ...

洛谷4994 终于结束的起点

夏花般绚烂/繁星般璀璨

标签:斐波那契数列 题目 题目传送门 题目背景 终于结束的起点 终于写下句点 终于我们告别 终于我们又回到原点 …… 一个个 OIer 的竞赛生涯总是从一场 NOIp 开始,大...

洛谷3521 [poi2011]rot Tree rotations

启发式合并总是很神仙

标签:线段树,启发式合并 题目 题目传送门 给一棵n(1≤n≤200000个叶子的二叉树,可以交换每个点的左右子树,要求前序遍历叶子的逆序对最少。 分析 树的逆序对个数=左子树的逆序对...

洛谷2480 [sdoi2010]古代猪文

有毒的数论题

标签:数论,Lucas定理,CRT,快速幂 题目 题目传送门 计算 的数据中, 分析 根据费马小定理,指数可以变成 然后可以使用Lucas定理快速求组合数,之后用快速幂求出答案...

洛谷2220 [haoi2012]容易题

容易题果然很easy

标签:快速幂 题目 题目传送门 题目描述 为了使得大家高兴,小Q特意出个自认为的简单题(easy)来满足大家,这道简单题是描述如下: 有一个数列A已知对于所有的A[i]都是1~n的自然数...

洛谷3469 [poi2008]blo Blockade

tarjan求割点

标签:Tarjan求割点 题目 题目传送门 Description Byteotia城市有n个 towns m条双向roads. 每条 road 连接 两个不同的 towns ,没有重复的...

洛谷2515 [haoi2010]软件安装

tarjan重构图后树形DP

标签:Tarjan重构图,树形DP 题目 题目传送门 题目描述 现在我们的手头有个软件,对于一个软件i,它要占用的磁盘空间,它的价值为。我们希望从中选择一些软件安装到一台磁盘容量为计算机...

洛谷2321 [hnoi2006]潘多拉的宝盒

tarjan缩点求最长链

标签:Tarjan缩点,bfs 题目 题目传送门 给定一些自动机,如果某个自动机A能产生的所有串都能在自动机B中产生,则称B是A的一个升级,求最长链 分析 两两连边,tarjan缩...

洛谷4180 【模板】严格次小生成树[bjwc2010]

严格次小生成树模板题

标签:Kruscal,次小生成树 题目 题目传送门 题目描述 小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。...

洛谷3244 [hnoi2015]落忆枫音

DAG加入一条边后会发生...

标签:DP,拓扑排序 题目 题目传送门 题目描述 「恒逸,你相信灵魂的存在吗?」 郭恒逸和姚枫茜漫步在枫音乡的街道上。望着漫天飞舞的红枫,枫茜突然问出这样一个问题。 「相信吧。不然我们...

洛谷3199 [hnoi2009]最小圈

分数规划+SPFA判负环

标签:分数规划,二分,SPFA 题目 题目传送门 题目描述 考虑带权的有向图以及,每条边的权值定义为,令。是中的一个圈当且仅当和都在中,这时称为圈的长度同时令,并定义圈的平均值为,即上所有...

Bzoj3390 [usaco2004 dec]bad cowtractors牛的报复

最大生成树模板题

标签:最大生成树 题目 题目传送门 Description 奶牛贝茜被雇去建设个牛棚间的互联网.她已经勘探出条可建的线路,每条线路连接两个牛棚,而且会苞费.农夫约翰吝啬得很,他希望建设费...

洛谷1963 [noi2009]变换序列

匈牙利算法的本质

标签:匈牙利算法 题目 题目传送门 题目描述 对于个整数,一个变换序列可以将变成,其中 且 。 ,,定义x和y之间的距离 。给定每个和之间的距离,你需要求出一个满足要求的变换序列T。如...

【noip模拟赛】divisors

数论水题

标签:数论 题目 给定 m 个不同的正整数 a1, a2, …, am,请对 0 到 m 每一个 k 计算,在区间 [1, n] 里有多少正整数是 a 中恰好 k 个数的约数。 对于 的...

洛谷2047 [noi2007]社交网络

floyd统计最短路径数量

标签:floyd 题目 题目传送门 题目描述 在社交网络(social network)的研究中,我们常常使用图论概念去解释一些社会现象。不妨看这样的一个问题。在一个社交圈子里有n个人,...

洛谷4049 [jsoi2007]合金

建图后利用floyd原理求最小代价

标签:计算几何,floyd 题目 题目传送门 题目描述 某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的原材料中铁铝锡的比重不同。然后,将...


Page 1 / Total 22