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\) 局游戏的交换结束后,魔术球所在的魔术帽编号。

  • 样例输入


Read the rest

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\) 行,输出每次训练时的行驶路径经过的最大车道数。

  • 样例输入

  • 样例输出

  • 数据范围

数据点 \(n\) \(m\) 约定
1 \(=5\) \(5\)
2 \(=20\) \(20\)
3

Read the rest