分类： 难度

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}\) 的值。

  • 输出格式

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

[FJWC2019 Day3] 签到题

[FJWC2019 Day3] 签到题

时间限制： 1000ms               内存限制：256MB

难度： \(4.5\)

  • 题目描述

作为一道签到题，自然只能包含最基本的算法。本题的任务很简单，给定一个长度为 \(n\) 的序列 \(a\)，你要将其排序。

由于出题人很菜，不会排序算法，他决定自己编一个。他想找到一个数 \(x\)，使得序列中的所有数字都异或上 \(x\) 后序列恰好按从小到大排列。

顺带，这个序列会被进行若干次修改，每次修改后你需要回答当前是否存在一个 \(x\) 满足序列中数字异或上 \(x\) 后按从小到大排列，如果有，请你给出最小的 \(x\) 。

  • 输入格式

第一行一个正整数 \(n\) 。

第二行 \(n\) 个非负整数，表示序列 \(a\) 。

第三行一个非负整数 \(q\) ，表示修改次数。

接下来 \(q\) 行，每行一个正整数 \(x\) 和一个非负整数 \(y\)，表示将序列中第 \(x\) 个元素修改为 \(y\) 。

  • 输出格式

输出 \(q+1\) 行，每行一个整数，第一行表示一开始最小的合法 \(x\) ，之后 \(q\) 行依次表示每次修改后最小的合法 \(x\)，如果不存在则这一行输出 \(-1\) 。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 \(20\%\) 的数据，\(n,m \le 500\)，所有数字不超过 \(2^9\) ​​。

对于 \(50\%\) 的数据，\(n,m \le 1000\) 。

对于 \(100\%\) 的数据，\(n,m \le {10}^6\)​​，所有数字不超过 \(2^{30}\) ​​。

 

 

YZOJ P4263…

[FJWC2019 Day2] 直径

[FJWC2019 Day2] 直径

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

难度： \(4.0\)

  • 题目描述

你需要构造一棵至少有两个顶点的树，树上的每条边有一个非负整数边权。树上两点 \(i,j\) 的距离 \(dis(i,j)\) 定义为树上连接 \(i\) 和 \(j\) 这两点的简单路径上的边权和。

我们定义这棵树的直径为，所有满足 \(1 \leq i < j \leq n\) 的 \((i,j)\) 中，\(dis(i,j)\) 最大的。如果有多个这样的 \((i,j)\)，那么均为直径。

作为一个构造题，你需要构造一个恰有 \(k\) 个直径的树。可以证明在给定的限制下一定有解。

  • 输入格式

一行一个正整数 \(k\)，表示你需要构造出一个恰有 \(k\) 个直径的树。

  • 输出格式

第一行一个正整数 \(n\)，表示你构造的树的点数。

接下来 \(n-1\) 行，每行三个整数 \(i,j,w\)，表示一条连接点 \(i\) 和 \(j\) （点的编号为 \(1,2, \cdots, n\)）的树边，边权为 \(w\) 。

  • 样例输入

  • 样例输出

  • 样例说明

这只是一种符合题意的输出，可能还有其他输出。在这个输出中，直径为 \((1,5),(3,5),(4,5)\) 。

  • 数据规模与约定

注意，你需要构造出的树必须满足 \(2 \leq n \leq 5000, 0 \leq w \leq 10^5\) ！

对于 \(30pts\) 的数据，\(1\leq k \leq 2000\) ；

对于 \(100pts\) 的数据，\(1\leq k \leq 5 \times 10^6\) 。

 

 

YZOJ P4260…

[FJWC2019 Day1] 全连

[FJWC2019 Day1] 全连

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

难度： \(4.5\)

  • 题目描述

给定两个长度为 \(n\) 的序列 \(a\) 和 \(t\)，可以在其中选择一些元素构成集合 \(S\) ，使得 \(\sum\limits_{i \in S}{a_i \times t_i}\) 最大。

同时，集合 \(S\) 还要满足 \(\forall i \in S, \forall j \in (i-t_i, i+t_i)\) ， \(j \notin S\) 。

  • 输入格式

第一行一个整数 \(n\) ；

第二行 \(n\) 个整数表示序列 \(t\) ；

第三行 \(n\) 个整数表示序列 \(a\) 。

  • 输出格式

一行一个整数，即答案。

  • 样例输入

  • 样例输出

  • 样例说明

\(S=\{1,3,5\}\)，答案 \(=2 \times 3 + 2 \times 2 + 2 \times 4 = 18\) 。

  • 数据规模与约定

保证 \(t_i \leq n\) ， \(a_i \leq 10^9\) ，\(1 \leq n \leq 10^6\) 。

 

 

YZOJ P4257, YZOJ P3993…

YZOJ P3840 [2018省队集训]序列

YZOJ P3840 [2018省队集训]序列

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

难度： \(8.0\)

  • 题目描述

给定一个长度为 \(n\) 的序列 \(x\) 。

你需要从序列中选出一些位置。对于第 \(i\) 个位置，如果它被选中，你会获得 \(x_i\) 的收益；否则找到最小的 \(j\) 使得第 \(j\) 个位置到第 \(i\) 个位置都没有被选中，你需要付出 \(i-j+1\) 的代价。

此外，你选出的位置必须满足 \(x_i\) 是单调不下降的。

最大化收益减去代价的结果。

  • 输入格式

第一行一个正整数 \(n\)，第二行 \(n\) 个整数 \(x_1\) ~ \(x_n\) 。

  • 输出格式

输出一行一个整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 样例 1 说明

选择第 \(1, 3, 5, 7\) 个位置，获得收益 \(1+2+3+4=10\) ，第 \(2, 4, 6\) 个位置的代价分别为 \(1, 1, 1\) ，收益减去代价为 \(10-3=7\) 。

  • 样例 2 输入

  • 样例 2 输出

  • 数据规模与约定

对于 \(5\%\) 的数据， \(1 \leq n \leq 5\) 。…

[CEOI2017]Building Bridges

[CEOI2017]Building Bridges

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

难度： \(7.2\)

  • 题目描述

有 \(n\) 根柱子依次排列，每根柱子都有一个高度。第 \(i\) 根柱子的高度为 \(h_i\) 。

现在想要建造若干座桥，如果一座桥架在第 \(i\) 根柱子和第 \(j\) 根柱子之间，那么需要 \((h_i-h_j)^2\) 的代价。
在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 \(i\) 根柱子被拆除的代价为 \(w_i\)​，注意 \(w_i\) 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 \(1\) 根柱子和第 \(n\) 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

  • 输入格式

第一行一个正整数 \(n\) 。

第二行 \(n\) 个空格隔开的整数，依次表示 \(h_1, h_2, \cdots, h_n\) 。

第三行 \(n\) 个空格隔开的整数，依次表示 \(w_1, w_2, \cdots, w_n\) 。

  • 输出格式

输出一行一个整数表示最小代价，注意最小代价不一定是正数。

  • 样例输入

  • 样例输出

  • 数据范围与提示

对于 \(30\%\) 的数据，有 \(1 \leq n \leq 1000\) ；

对于另外 \(40\%\) 的数据，有 \(\left| w_i \right| \leq 20\) ，保证存在一种最优方案，除了头尾两根柱子外，最多只保留两根柱子；

对于 \(100\%\) 的数据，有 \(2 \leq n \leq 10^5\)，\(0 \leq h_i,\left| w_i\right| \leq 10^6\) 。

数据来源 LOJ 2483 。

 

 

已搬至 YZOJ P4254 。…

[SDOI2012]任务安排

[SDOI2012]任务安排

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

难度： \(7.1\)

  • 题目描述

按顺序给定 \(N\) 个子任务，每个任务用时 \(t_i\) ，费用系数 \(f_i\)。

可以把连续的若干个（或一个）子任务合成为一个大任务，大任务的用时和费用系数分别为其中每个子任务的用时之和与费用系数之和。开始一个大任务之前需要准备时间 \(S\)，一个大任务的费用为他的 完成时刻 \(\times\) 费用系数 ，问按顺序执行完所有的大任务后，最小的费用和为多少。

形式化的，将 \(N\) 个任务划分成若干个块，每一组任务 \(M_i\) 花费代价 \((T+\sum{t_j}+S) \times \sum{f_j}\)，\(j \in M_i\)，\(T\) 为执行到这个任务之前花费的时间，求执行完所有任务的最小代价和。

  • 输入格式

第一行一个整数 \(N\) ；

而后 \(N\) 行中，第 \(i\) 行包含一个可能为负的整数 \(t_i\) 和一个非负整数 \(f_i\) 。

  • 输出格式

一个整数，表示最小的代价和。

  • 样例输入

  • 样例输出

  • 样例说明

如果分组方案是 \(\{1,2\}\)、\(\{3\}\)、\(\{4,5\}\)，则完成时间分别为 \(\{5,5,10,14,14\}\)，费用 \(C=\{15,10,30,42,56\}\)，总费用就是 \(153\) 。

  • 数据规模与约定

对于 \(20\%\) 的数据，\(1 \leq N \leq 1000\) ；

对于另外 \(40\%\) 的数据， \(1 \leq N \leq 300000\) ；

对于前 \(60\%\) 的数据，\(0 \leq t_i \leq 2^8\) ；

对于后 \(40\%\) 的数据，\(1 \leq N \leq 100000\)，\(-2^8 \leq t_i \leq 2^8\) ；

对于 \(100\%\) 的数据， \(0 \leq S, f_i …