Menci's Blog

幻梦终醒,不悔华年


  • 首页

  • 关于

  • 归档

  • 标签

  • 友链

  • 搜索

Goodbye, 2018

发表于 2019-01-01 | 分类于 Diary

不知从何时开始,对元旦这种重要节日的概念,开始变得越来越浅 —— 从童年时的日思夜想,到如今,已经不再有什么期待,而只是当做一个平常的周末了。除了多放一天假之外,也便没有多么特殊了。但这总归是一年的结束,新一年的开始,这一年的回忆,大多数都在前半年高三的生活中,那时候便想,自己的故事一定要写给大家看,而现在看来,那些回忆也不过只有寥寥数言,但终究还是要在淡忘之前将他们记录下来,作为人生的一个阶段留下的记号罢。于是,便有了这些文字。

阅读全文 »

「2018 南京网络预赛」Sum - 线性筛

发表于 2018-09-14 | 分类于 OI

定义 f(x) 为满足以下条件的有序二元组 (a,b) 的方案数(即 (a,b) 与 (b,a) 被认为是不同的方案):

  1. x=ab ;
  2. a 和 b 均为无平方因子数(即其因子中没有除 1 以外的完全平方数)。

求 \sum\limits_{i=1}^nf(i) , n\leq 2\times 10^7 。

阅读全文 »

「NOI2010」超级钢琴 - 可持久化线段树 + 堆

发表于 2018-08-18 | 分类于 OI

给一个长度为 n 的序列 \{a_i\} ,定义一个区间 [l,r] 的价值为这个区间中数的总和。求区间长度在 [L,R] 之间的所有区间中,价值最大 k 的个区间的价值总和。

阅读全文 »

「NOIP 模拟赛」Azuki loves chess - 数论

发表于 2018-07-18 | 分类于 OI

在一个无穷大的中国象棋棋盘上,马每次可以在一个方向上移动一个单位,在另一个方向上移动两个单位。现将规则改为,马每次可以在一个方向上移动 a 个单位,在另一个方向上移动 b 个单位。问放置在 (0,0) 的马能否移动到 (n,m) 。

阅读全文 »

「Codeforces 650D」Zip-line - 树状数组 + LIS

发表于 2018-07-06 | 分类于 OI

给一个序列,每次求原序列的第 i 个数修改为 x 时的最长严格上升子序列长度。

阅读全文 »

梦结束的地方

发表于 2017-08-30 | 分类于 Diary

“终于 …… 要离开了吗 ……”

徘徊在绍兴一中的校园里,不舍地望着这里的一切,仿佛这曾是我所拥有的全部。

这里,是梦成真的地方; 也是,梦结束的地方 ……

阅读全文 »

「Codeforces 808G」Anthem of Berland - KMP + DP

发表于 2017-05-27 | 分类于 OI

给一个含有字母以及 ? 的 s 串和一个含有字母的 t 串,其中 ? 可以匹配任何字符,求 s 串最多匹配 t 串多少次。

阅读全文 »

「APIO2013」TOLL - 搜索 + 最小生成树

发表于 2017-05-27 | 分类于 OI

幸福国度可以用 N 个城镇(用 1 到 N 编号)构成的集合来描述,这些城镇最开始由 M 条双向道路(用 1 到 M 编号)连接。城镇 1 是中央城镇。保证一个人从城镇 1 出发,经过这些道路,可以到达其他的任何一个城市。这些道路都是收费道路,道路 i 的使用者必须向道路的主人支付 c_i 分钱的费用。已知所有的这些 c_i 是互不相等的。最近有 K 条新道路建成,这些道路都属于亿万富豪 Mr. Greedy。

Mr. Greedy 可以决定每条新道路的费用(费用可以相同),并且他必须在明天宣布这些费用。

两周以后,幸福国度将举办一个盛况空前的嘉年华!大量的参与者将沿着这些道路游行并前往中央城镇。共计 p_j 个参与者将从城镇 j 出发前往中央城镇。这些人只会沿着一个选出的道路集合前行,并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗,这些道路将由幸福国度中最有钱的人选出,也就是 Mr. Greedy。同样根据这个习俗,Mr. Greedy 选出的这个道路集合必须使所有选出道路的费用之和最小,并且仍要保证任何人可以从城镇 j 前往城镇 1 (因此,这些选出的道路来自将费用作为相应边边权的“最小生成树”)。如果有多个这样的道路集合,Mr. Greedy 可以选其中的任何一个,只要满足费用和是最小的。

Mr. Greedy 很明确地知道,他从 K 条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲,如果 p 个人经过道路 i ,道路 i 产生的收入为乘积 c_i \cdot p 。注意 Mr. Greedy 只能从新道路收取费用,因为原来的道路都不属于他。

Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用(将在明天公布),并且选择嘉年华用的道路(将在嘉年华的前一天公布),使得他在 K 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。

你是一个记者,你想揭露他的计划。为了做成这件事,你必须先写一个程序来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。

阅读全文 »

「APIO2014」Split the sequence - 斜率优化 DP

发表于 2017-05-26 | 分类于 OI

你正在玩一个关于长度为 n 的非负整数序列的游戏。这个游戏中你需要把序列分成 k + 1 个非空的块。为了得到 k + 1 块,你需要重复下面的操作 k 次:

  1. 选择一个有超过一个元素的块(初始时你只有一块,即整个序列)
  2. 选择两个相邻元素把这个块从中间分开,得到两个非空的块。

每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。

阅读全文 »

「CTSC2012」Cheat - SAM + 二分 + 单调队列 DP

发表于 2017-04-06 | 分类于 OI

给出 m 个串组成的「标准作文库」。对于任意一个串,如果它的长度不少于 L 且在标准作文库中出现过,则它是「熟悉」的。对于任意一个串,如果能将它划分为若干个串,使「熟悉」的串的长度超过总长度的 90\% ,则称这个串是「熟悉的文章」,定义 L_0 为使这个串成为「熟悉的文章」的最大的 L 。给出若干个串,求每个串的 L 值。

阅读全文 »
12…36
Menci

Menci

354 日志
3 分类
223 标签
GitHub QQ RSS E-Mail
© 2015 — 2019 Menci
运行于 GigsGigsCloud 云平台 | 由 Upyun 提供 CDN 服务
由 Hexo 强力驱动
|
主题 — NexT.Pisces v5.1.2