yjjr's blog

还有点梦想的咸鱼OIer

洛谷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 题目 题目传送门 题目描述 某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的原材料中铁铝锡的比重不同。然后,将...

【noip2018模拟赛0】解题报告

清新不毒瘤的模拟赛

T1 yyy点餐 题意 给出长度为的序列,求有所有不同的组合的代价总和(每种组合的代价为该组合内所有数之和) 对于全部数据,有 题解 一眼就能秒掉的水题 求组合数的话,就用乘法逆元...

Bzoj4384 [poi2015]trzy wieże

结论题

标签:智商题 题目 题目传送门 Description 给定一个长度为n的仅包含’B’、’C’、’S’三种字符的字符串,请找到最长的一段连续子串,使得这一段要么只有一种字符,要么有多种字...

Bzoj3749 [poi2015]łasuchy

DP也很妙妙啊pxp

标签:DP 题目 题目传送门 Description 圆桌上摆放着n份食物,围成一圈,第i份食物所含热量为c[i]。 相邻两份食物之间坐着一个人,共有n个人。每个人有两种选择,吃自己左边或...


Page 1 / Total 21