YZOJ P3385 [校内训练20171201]笔名分配问题

YZOJ P3385 [校内训练20171201]笔名分配问题

时间限制：1000MS      内存限制：262144KB

难度：\(5.5\)

  • 题目描述

班里有 \(n\) 个同学。老师为他们选了 \(n\) 个笔名。现在要把这些笔名分配给每一个同学， 每一个同学分配到一个笔名，每一个笔名必须分配给某个同学。现在定义笔名和真名之间的相关度是他们之间的最长公共前缀。设笔名为 \(a\)，真名为 \(b\)，则他们之间的相关度为 \(lcp(a,b)\)。那么我们就可以得到匹配的质量是每一个同学笔名和真名之间相关度的和。

对于两个字符串 \(a,b\)（从 \(1\) 开始标号），定义 \(a,b\) 的最长公共前缀 \(lcp(a,b)\) 为最大的非负整数 \(k\)，使得 \(k\le |a|, k\le |b|\)，且对所有 \(i=1,2,\ldots,k\)，\(a_i = b_i\) 。

给出一种分配笔名的方案，使得匹配质量最大。

  • 输入格式

第 \(1\) 行有 \(1\) 个整数 \(n\)，表示班级中同学的数目。接下来 \(n\) 行，表示每一个同学的真名。最后 \(n\) 行是老师已经安排好的笔名。每行的名称仅由小写字母组成。

  • 输出格式

将分配笔名的方案输出到文件中。第一行输出一个数，表示最大匹配质量。接下来 \(n\) 行，每行两个数 \(a,b\)，表示把编号为 \(b\) 的笔名分配给编号为 \(a\) 的同学。同学和笔名均按输入顺序从 \(1\) 至 \(n\) 编号。若方案不唯一，任意输出一种即可。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于所有测试点，\(n \leq 100000\)，输入串总长 \(\leq 800000\) 。

 

 

 …

YZOJ P3361 [校内训练20171117]数点问题

YZOJ P3361 [校内训练20171117]数点问题

时间限制：2000MS      内存限制：262144KB

出题人：zzx      难度：\(6.0\)

  • 题目描述

\(k\) 维空间内有两个点集 \(A=\{X_1,X_2,\ldots,X_m\}\)，\(B=\{Y_1,Y_2,\ldots,Y_n\}\)，每个点的坐标是一个 \(k\) 元组 \((x_1,x_2,\ldots,x_k)\)。我们称点 \(X(x_1,x_2,\ldots,x_k)\) 控制点 \(Y(y_1,y_2,\ldots,y_k)\) 当且仅当 \(\forall 1\le i\le k,x_i>y_i\)，记为 \(X>Y\)。数点问题是要求计算点 \(X_i\) 能控制 \(B\) 中的点数 \(c_i\)，即 \(c_i=\left| \{Y \in B\ |\ X_i > Y\} \right|\)。

  • 编程任务

对于给定的点集 \(A\) 和 \(B\)，求出对于所有 \(1\le i\le m\) 的 \(c_i\) 的值。

  • 输入格式

第一行有三个正整数\(m\)、\(n\) 和 \(k\)，分别表示集合 \(A\) 和 \(B\) 的基数及维数。接下来的 \(m+n\) 行依次给出点 \(X_1 , X_2 ,\ldots, X_m ,Y_1 ,Y_2 ,\ldots,Y_n\)，每个点的坐标用一行 \(k\) 个整数 \(x_1 , x_2 ,\ldots, x_k\) 描述，所有坐标在 \(int\) 范围内。

  • 输出格式

将计算出的 \(c_1 ,c_2 ,\ldots,c_m\) 依次输出到文件中，每个 \(c_i\) 输出 \(1\) 行。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于数据点 \(1\)，\(n,m\le 200,000\)，\(k=1\)…

YZOJ P3216 行商

YZOJ P3216 行商

时间限制：1000MS      内存限制：262144KB

难度：\(4.0\)

  • 题目描述

有 \(n\) 个货物，每个货物都有各自的重量 \(w_i\) 和价值 \(c_i\)，但是载重量仅为 \(m\) 。

挑选出一些货物，总重量不超过 \(m\)，使价值之和最大。

  • 输入格式

第一行，两个整数 \(n\)，\(m\)；

接下来 \(n\) 行，每行两个整数 \(w_i\)，\(c_i\) 。

  • 输出格式

一个整数 \(ans\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

 \(1 \leq n \leq 10^6\)，\(1 \leq m \leq 4^{31}\)，\(1 \leq w_i \leq 3\)，\(1 \leq c_i \leq 10^9\) 。

 

 

 …

YZOJ P3791 餐馆

YZOJ P3791 餐馆

时间限制：2000MS      内存限制：524288KB

难度：\(6.0\)

  • 题目描述

在一条东西向的街道上有 \(n\) 个餐馆，从西向东编号为 \(1\) 至 \(n\)，第 \(i\) 个餐馆和第 \(i+1\) 个餐馆的距离为 \(a_i\) 。

吃货小W喜欢到这条街道的餐馆里吃饭。现在，小W得到了 \(m\) 张餐票，每张餐票可以用于在街道上的任一餐馆里吃一餐。在第 \(i\) 个餐馆中，使用第 \(j\) 张餐票吃饭，可以获得的美味度为 \(b_{i,j}\) 。注意，每张餐票最多用一次，但在同一餐馆内可以使用任意多张餐票。

小W打算用完这 \(m\) 张餐票。他可以选择任一餐馆作为起点，每次吃饭时，可以选择一个餐馆，然后从当前位置（上次吃饭的地点，如果不存在则为起点）出发前往该餐馆并用任意一张未用过的餐票吃一餐，直到吃完 \(m\) 餐为止。小W希望最大化每次吃饭的美味度之和减去路上经过的总路程的值。

  • 输入格式

输入第一行包含两个正整数 \(n,m\) 。

第二行包含 \(n-1\) 个正整数 \(a_1,a_2,\cdots,a_{n-1}\) 。

接下来 \(n\) 行，每行包含 \(m\) 个正整数，其中第 \(i\) 行第 \(j\) 个数为 \(b_{i,j}\) 。

  • 输出格式

输出一行一个整数，表示所求的最大值。

  • 样例输入

  • 样例输出

  • 样例说明

最优方案如下：以餐馆 \(1\) 为起点，在餐馆 \(1\) 使用第 \(1\) 张餐票、第 \(3\) 张餐票，然后前往餐馆 \(2\) 使用第 \(2\) 张餐票、第 \(4\) 张餐票。

  • 数据规模与约定

对于所有数据，\(nm \leq 10^6\)，\(n \geq 2\)，\(a_i, b_{i, j} \leq 10^9\) 。

 

 

 

Source：ARC067 F – Yakiniku …

YZOJ P3371 简单计数问题

YZOJ P3371 简单计数问题

时间限制：3000MS      内存限制：262144KB

难度： \(6.0\)          出题人：zzx

  • 问题描述

给定正整数序列 \(a[1], a[2], \cdots , a[n]\)，你需要依次解决 \(m\) 个询问，每个询问用两个正整数 \(L, R\) 描述， 请求出有多少个数在 \(a[L],a[L+1],\cdots,a[R]\) 中出现正偶数次。

  • 编程任务

求出每个查询的结果。

  • 数据输入

输入第一行四个整数 \(n\)、\(c\)、\(m\) 以及 \(t\) 。

第二行 \(n\) 个整数 \(a[1],a[2],\cdots,a[n]\)，每个数在 \([1,c]\) 间。

接下来 \(m\) 行每行两个整数 \(l\) 和 \(r\)，设上一个询问的答案为 \(ans\) (第一个询问时 \(ans=0\) )，令 \(L=(l+t \times ans) \bmod n+1, R=(r+t \times ans) \bmod n+1\)，若 \(L>R\)，交换 \(L\) 和 \(R\)，则本次询问为 \([L,R]\) 。

  • 结果输出

对于每个询问， 输出一行对应的答案。

  • 样例输入

  • 样例输出

  • 数据范围

对于 \(50\%\) 的数据，有 \(t=0\) 。

对于另外 \(50\%\) 的数据，有 \(t=1\) …

YZOJ P3846 [2018省队集训]Yist

YZOJ P3846 [2018省队集训]Yist

时间限制：1000MS      内存限制：524288KB

难度： \(7.0\)

  • 题目描述

有一个 \(n\) 个点 \(m\) 条边的无向图，结点从 \(1\) 到 \(n\) 标号，点 \(u\) 的初始权值为 \(w_u\)。你可以对任意结点 \(u\) 进行操作，将你的得分（初始为 \(0\)）加上 \(\sum_\limits{(u,v) \in E}w_v\) ，并将 \(w_u\) 除以 \(2\) 。

给定一个长度为 \(k\) 的结点序列 \(s_1,s_2,\cdots,s_k\) （\(1 \leq s_i \leq n\)），在一轮操作中，你需要依次对 \(s_1,s_2,\cdots,s_k\) 进行操作。你想知道，在进行了无限轮操作后，你得分的极限是多少。

显然答案一定可以表示成 \(P/Q\) 的形式，你需要输出 \(P \times Q^{-1}\) 在模 \(998244353\) 意义下的值。特别的，如果得分并不收敛，输出 \(-1\) 。

  • 输入格式

本题有多组数据，请读入到文件结束。

对于每组数据，第一行三个整数 \(n,m,k\) ，含义如题所述。

第二行 \(n\) 个整数 \(w_1,w_2,\cdots,w_n\)，表示结点的初始权值。

第三行 \(k\) 个正整数 \(s_1,s_2,\cdots,s_k\) 。

接下来 \(m\) 行，每行两个整数 \(u,v\)，描述了一条无向边。

  • 输出格式

对于每组数据，输出一行一个整数，表示答案。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(20\%\) 的数据，\(n,m \leq 5\)，\(k \leq 10\)；

对于 \(40\%\) 的数据，\(n,m \leq 1000\)，\(k \leq 2000\)；

对于另外 \(20\%\) 的数据，数据为随机生成；

对于 \(100\%\) 的数据，\(1 \leq …

YZOJ P3367 魔术帽游戏

YZOJ P3367 魔术帽游戏

时间限制：1000MS                       内存限制：262144KB

难度：\(6.0\)           出题人：zzx

  • 题目描述

有 \(n\) 顶外形相同的魔术帽和一个魔术球，每次游戏开始前，魔术帽会被倒扣放置排成一排，这些魔术帽从左到右依次编号为 \(1, 2, \cdots , n\) 。

每一局游戏，魔术球会被放在其中一顶魔术帽底下，然后进行若干次交换，每次交换时可以选出两顶魔术帽，交换它们的位置。整个过程对于小朋友们而言都是可见的。交换结束后，小朋友们可以打开魔术帽，正确找到魔术球则游戏胜利。

为了进行多局游戏，现有一个长度为 \(m\) 的操作序列 \((a_1,b_1), (a_2,b_2), \cdots ,(a_m,b_m)\)，其中 \((a_i,b_i)\) 表示反转 \(a_i\) 号和 \(b_i\) 号魔术帽之间的魔术帽的顺序（如原来魔术帽从左到右为 \(a,b,c,d,e,f,g\)，则操作 \((3,6)\) 进行后顺序变为 \(a,b,f,e,d,c,g\) 。之后，小朋友们会玩 \(q\) 局游戏。其中，第 \(j\) 轮游戏，魔术球会被放在 \(x_j\) 号魔术帽下，然后进行操作序列中 \([l_j,r_j]\) 这个片段，即依次进行反转操作 \((a_{l_j},b_{l_j}),(a_{l_j+1},b_{l_j+1}), \cdots ,(a_{r_j},b_{r_j})\) 。请求出每次游戏反转操作结束时，魔术球位于在哪一顶魔术帽下。注意：这里的魔术帽编号始终是按照位置从左到右编号的，即每次交换魔术帽之后，所有魔术帽会按照从左到右的顺序重新编号为 \(1,2,\cdots,n\) 。

  • 输入格式

第一行有三个整数 \(n,m,q\)，其中 \(n\) 代表魔术帽的数量，\(m\) 代表操作序列的长度，\(q\) 代表游戏次数。

接下来 \(m\) 行，其中第 \(i\) 行两个整数 \(a_i,b_i\)，表示操作序列的第 \(i\) 项。接下来 \(q\) 行，其中第 \(j\) 行三个正整数 \(x_j,l_j,r_j\)，表示第 \(j\) 局游戏。保证 \(1 \leq a_i \leq b_i \leq n\)，\(1 \leq x_j \leq n\)，\(1 \leq l_j \leq r_j \leq m\) 。

  • 输出格式

输出 \(q\) 行，每行一个整数，第 \(j\) 行的整数表示第 \(j\) 局游戏的交换结束后，魔术球所在的魔术帽编号。…

YZOJ P3392 越野赛车问题

YZOJ P3392 越野赛车问题

时间限制：1000MS      内存限制：262144KB

难度： \(6.0\)

  • 问题描述

某山上一共有 \(n\) 个广场，编号依次为 \(1\) 到 \(n\)，这些广场之间通过 \(n-1\) 条双向车道直接或间接地连接在一起。对于每条车道 \(i\)，可以用四个正整数 \(u_i, v_i, l_i, r_i\) 描述，表示车道连接广场 \(u_i\) 和 \(v_i\)，其速度承受区间为 \([l_i, r_i]\)，即汽车必须以不小于 \(l_i\) 且不大于 \(r_i\) 的速度经过车道 \(i\) 。

现计划进行 \(m\) 次训练，每次选择某山上的一条简单路径，然后在这条路径上行驶，且每次训练时的车速都是固定的。现在有在 m 次训练中分别计划使用的车速，要求一条合法的路径（车速在所有车道的速度承受区间的交集内），使得路径上经过的车道数最大。

  • 数据输入

输入文件的第一行包含两个正整数 \(n, m\)，表示广场数和训练次数。接下来 \(n-1\) 行，每行四个正整数 \(u_i, v_i, l_i, r_i ( \leq n)\)，描述所有车道。最后 \(m\) 行，每行一个正整数 \(v (\leq n)\) ，表示每次训练是的车速。

  • 结果输出

输出 \(m\) 行，输出每次训练时的行驶路径经过的最大车道数。

  • 样例输入

  • 样例输出

…

YZOJ P3484 子树求和

YZOJ P3484 子树求和

时间限制：2000MS      内存限制：262144KB      出题人：lgj

难度： \(6.0\)

  • 题目描述

已知一棵树有 \(n\) 个节点，并且根节点是固定的。

每个节点上都有一个权值 \(w_i\) ，记 \(s_i\) 为 以 \(i\) 为根的子树中，所有节点的 \(w_i\) 的和。

由于询问 \(s_i\) 太简单了，不能将 AKIOI 的你的高智商体现出来，所以每次询问给定 \(l, r\) ，求 \(\sum\limits_{i=l}^{r}{s_i}\) 。

为了避免此题难度太低，不能将 AKIOI 的你的高智商体现出来，所以的询问的过程中还可能修改某个节点的 \(w_i\) 。

为了将 AKIOI 的你的高智商体现出来，你要写一个程序来实时给出询问的答案。

  • 输入格式

第一行为两个整数 \(n\) 和 \(q\)，分别表示节点数和操作的次数；

第二行 \(n\) 个正整数，表示序列 \(w\) ；

接下来 \(n\) 行，第 \(i\) 行两个正整数 \(u_i\) 和 \(v_i\)，描述一条树上的边。特别地，\(u_i=0\) 时，表示 \(v_i\) 为树的根节点；

接下来 \(q\) 行，每行三个正整数 \(op, l, r\) 。描述 \(q\) 组操作。 \(op=1\) 表示 \(w_l\) 修改为 \(r\)，\(op=2\) 表示询问 \(\sum\limits_{i=l}^{r}{s_i}\) 的值。

  • 输出格式

对于每组询问操作，你需要依据当前树的情况输出该组询问的标准答案，每次询问的答案独占一行。…

浅谈斜率优化——截距优化

浅谈斜率优化——截距优化

最近（两个月前）学习了斜率优化 —— 一种优化 1D1D 动态规划转移方程的高效方法，在较高难度的比赛中是一种十分常见的 DP 优化手段。鉴于我之前（一年前）也稍微接触过一点相关方面的知识，但是完全没有搞懂（太菜了），最近（两个月前）再配合 orzCJK学长 提出的截距优化的思想理念才对于斜率优化问题有了深刻的见解，故在这里对 orzCJK学长 的 斜率优化_截距优化！.pdf 进行详细的解释说明。

 

首先，1D1D 指的是状态数 \(O(n)\) 转移 \(O(n)\) 的动态规划方程。在满足一些条件的情况下，斜率优化可以将转移的 \(O(n)\) 优化至 \(O(logn)\) 甚至可以到 \(O(1)\) 。这样时间复杂度就由 \(O(n^2)\) 变为 \(O(nlogn)\) 甚至是 \(O(n)\) ，可见斜率优化的高效性。

如果有一个 DP 方程的某个状态为 \(f_i\) ，如果能推导出类似于 \(f_i=c_i + \min\limits_{j<i \land \cdots}{\{a_j + w_i \cdot b_j\}}\) ，那么这个转移方程就可以使用斜率优化进行优化。

然而普通的转移方程并没有什么特殊的地方，使用经典的方法（我也不会）略显繁琐，所以现在我们要赋予它以几何意义。（时刻注意，这个转移方程的意义是对于一个 \(i\) 在 \(j < i\) 范围内寻找 \(j\) 使 \(a_j + w_i \cdot b_j\)）最小。）

换一下变量名，设 \(y_j=a_j, k_i=-w_i, x_j=b_j\) ，那么这样需要最小化的式子就变为 \(\underbrace{a_j}_{y_j} – \underbrace{-w_i}_{k_i} \cdot \underbrace{b_j}_{x_j}\) 。这不就是截距 \(b = y – kx\) 吗？！！也就是说，要最小化的就是一条过 \(\left(x_j, y_j\right)\) 且斜率为 \(k_i\) 的直线的截距！

换句话说，把所有对于当前 \(i\) 可转移的 \(j\) 都表示为二维平面上的一个点 \(p_j=\left(x_j, y_j\right)\) ，我们需要做的就是在所有这样的点中，找到一个点，使经过它且斜率为 \(k_i\) 的直线的截距最小！这也是为什么斜率优化就是截距优化的原因，它其实优化的是截距！

现在想象一条斜率固定的直线从下往上平移，当它第一次经过某个点 \(p_j\) 时，这时的截距肯定取到最小值。那么这个点 \(p_j\) 在什么地方呢？显然，它会在所有 \(p\) 组成的下凸壳上。

那么现在只要维护这个下凸壳，每次在上面找点使得截距最小，拿来更新 …