Arietta问题描述 Arietta 的命运与她的妹妹不同,在她的妹妹已经走进学院的时候,她仍然留在山村中。 但是她从未停止过和恋人 Velding 的书信往来。一天,她准备去探访他。 对着窗外的阳光,临行前她再次弹起了琴。 她的琴的发声十分特殊。 让我们给一个形式化的定义吧。 所有的 $n$ 个音符形成一棵由音符 $C$ ( 1 号节点) 构成的有根树,每一个音符有一个音高$ H_i$ 。 ...

C. Gotta Go Fast You’re trying to set the record on your favorite video game. The game consists of N levels, which must be completed sequentially in order to beat the game. You usually complete each l ...

「雅礼集训 2017 Day1」字符串问题描述 令 $ s $ 与 $ w $ 为两字符串，定义： $ w[l, r] $ 表示字符串 $ w $ 在区间 $ [l, r] $ 中的子串； $ w $ 在 $ s $ 中出现的频率定义为$ w $ 在 $ s $ 中出现的次数； $ f(s, w, l, r) $ 表示 $ w[l, r] $ 在 $ s $ 中出现的频率。 比如 $ f(\ ...

「雅礼集训 2017 Day1」矩阵问题描述 有一个 $ n \times n $ 的矩阵，每个位置 $ (i, j) $ 如果是 . 表示为白色，如果是 # 表示为黑色。 初始时，每个位置可以是黑色或白色的，$ (i, j) $ 位置的值会作为 $ a_{i, j} $ 给你。 现在有一种操作，选择两个整数 $ i, j \in [1, n] $，记 $ (i, 1), (i, 2), \ld ...

「雅礼集训 2017 Day1」市场问题描述 从前有一个贸易市场，在一位执政官到来之前都是非常繁荣的，自从他来了之后，发布了一系列奇怪的政令，导致贸易市场的衰落。 有 $ n $ 个商贩，从 $ 0 \sim n - 1 $ 编号，每个商贩的商品有一个价格 $ a_i $，有两种政令： $ l, r, c $，对于 $ i \in [l, r], a_i \leftarrow a_i + c ...

[CERC2015]奶牛围栏问题描述 一个10^6行10^6列的网格图，上面有一些牛、花和一些矩形围栏，围栏在格子的边界上，牛和花在格子里，牛只能向下或向右走，牛也不能穿过围栏和地图边界，求每头牛它能到达的花的数量。注意栅栏不会相交 .png) 输入格式 第一行一个数f表示矩形围栏的数量。 接下来f行，每行四个数x1,y1,x2,y2，表示(x1,y1)在围栏内部矩形的左上角，(x2,y ...

【CERC2017】旅游指南问题描述 给定一张n个点，m条双向边的无向图。 你要从1号点走到n号点。当你位于x点时，你需要花1元钱，等概率随机地买到与x相邻的一个点的票，只有通过票才能走到其它点。 每当完成一次交易时，你可以选择直接使用那张票，也可以选择扔掉那张票然后再花1元钱随机买另一张票。注意你可以无限次扔票。 请使用最佳的策略，使得期望花的钱数最少。 输入格式 第一行包含两个正整数n, ...

【AMPPZ2014】加油问题描述 给定一个n个点、m条边的带权无向图，其中有s个点是加油站。 每辆车都有一个油量上限b，即每次行走距离不能超过b，但在加油站可以补满。 q次询问，每次给出x,y,b，表示出发点是x，终点是y，油量上限为b，且保证x点和y点都是加油站，请回答能否从x走到y。 输入格式 第一行包含三个正整数n,s,m(2<=s<=n<=200000,1< ...

【Neerc2016】养猫问题描述 ls是一个特别堕落的小朋友，对于n个连续的小时，他将要么睡觉要么打隔膜，一个小时内他不能既睡觉也打隔膜，因此一个小时内他只能选择睡觉或者打隔膜，当然他也必须选择睡觉或打隔膜，对于每一个小时，他选择睡觉或打隔膜的愉悦值是不同的，对于第i个小时，睡觉的愉悦值为$s_i$，打隔膜的愉悦值为$e_i$，同时又有一个奥妙重重的规定：对于任意一段连续的k小时，ls必须至少 ...

【AMPPZ2014】船长问题描述 给定平面上的n个点，定义(x1,y1)到(x2,y2)的费用为min(|x1-x2|,|y1-y2|)，求从1号点走到n号点的最小费用。 输入格式 第一行包含一个正整数n(2<=n<=200000)，表示点数。 接下来n行，每行包含两个整数x[i],yi，依次表示每个点的坐标。 输出格式 一个整数，即最小费用。 样例输入 5 2 2 1 ...