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

  • 输出格式

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

YZOJ P2417 [FJWC2016][CF79-D]翻转硬币

YZOJ P2417 [FJWC2016][CF79-D]翻转硬币

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

难度: \(6.0\)

  • 题目描述

\(n\) 枚硬币正面朝上摆成一排,给定 \(a_1, a_2, \cdots, a_m\),每次操作可以任意选择一个 \(a_i\),并翻转连续 \(a_i\) 个硬币

要求经过最少次数的操作,使得第 \(x_1, x_2, \cdots, x_k\) 枚硬币反面朝上,输出最少次数。

  • 输入格式

第一行三个整数 \(n\)、\(k\)、\(m\) 。

第二行 \(k\) 个整数表示需要反面朝上的硬币位置,从 \(1\) 编号。

第三行 \(m\) 个整数表示 \(a_1, a_2, \cdots, a_m\) 。

  • 输出格式

一个整数表示答案,若无解,则输出 \(-1\) 。

  • 样例输入

  • 样例输出

  • 数据规模与约定

对于 \(30\%\) 的数据,\(n, m \leq 10\) 。 

对于 \(60\%\) 的数据,\(m \leq 20\) 。 

对于 \(100\%\) 的数据,\(1 \leq n \leq 10000\),\(1 \leq k \leq 10\),\(1 \leq m \leq 100\),\(1 \leq a_i \leq n\) 。

 

 

 

Source: CF79-D

YZOJ P3669 [USACO2008 Mar]土地购买

YZOJ P3669 [USACO2008 Mar]土地购买

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

难度:\(6.0\) (自评)

  • 题目描述

农夫 John 准备扩大他的农场,他正在考虑 \(N\) (\(1 \leq N \leq 1,000,000\)) 块长方形的土地。

每块土地的长宽满足 (\(1 \leq\) 宽 \(\leq 1,000,000\), \(1 \leq\) 长 \(\leq 1,000,000\))。每块土地的价格是它的面积,但 FJ 可以同时购买多块土地。

这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换。如果 FJ 买一块 \(3 \times 5\) 的地和一块 \(5 \times 3\) 的地,则他需要付 \(5 \times 5=25\)。

FJ 希望买下所有的土地,但是他发现分组来买这些土地可以节省经费。他需要你帮助他求出最小的经费。

  • 输入格式

输入文件的第 \(1\) 行一个数 \(N\), 表示土地块数。第 \(2\) 行至第 \(N+1\) 行,每行包含两个数,表示第 \(i\) 块土地的长和宽。

  • 输出格式

最小的可行费用。

  • 样例输入

  • 样例输出

 

 

 …

[CF868-F] Yet Another Minimization Problem

[CF868-F] Yet Another Minimization Problem

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

难度:\(6.0\)

  • 题目描述

有 \(n\) 个正整数构成序列 \(a\) ,定义一个区间 \([l, r]\) 的代价为 满足 \(l \leq i, j \leq r\) 并使得 \(a_i=a_j\) 的无序对 \([i, j]\) 的数量。

现要把 \(a\) 分成 \(k\) 个互不相交且不为空的连续的区间,求出在所有分法中,分出区间的最小代价和是多少。

  • 输入格式

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

第二行,序列 \(a\) ,共 \(n\) 个元素,用一个空格隔开。

  • 输出格式

一个整数,表示在所有分法中,分出区间的最小代价和。

  • 样例输入

  • 样例输出

  • 样例说明

一种可能的分法为 \([1], [1, 3], [3, 3, 2, 1]\) 。

第一个区间的代价为 \(0\) ,第二个区间的代价为 \(0\) ,第三个区间的代价为 \(1\) ,最小代价和为 \(1\) 。

(其他样例见原题

  • 数据范围

对于 \(10\%\) 的数据,\(2 \leq n \leq 20\) 。

对于 \(40\%\) 的数据,\(2 \leq n \leq 1000\) 。

对于 \(100\%\) 的数据,\(2 \leq n \leq 10^5\) ,\(2 \leq k \leq min\{20,n\}\) 。

保证 \(1 \leq a_i \leq n\) 。

 

 

 

\(Source\): CF868-F

YZOJ P3782 [校内训练20180619]组合数问题

YZOJ P3782 [校内训练20180619]组合数问题

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

难度:\(6.5\) 出题人:zzx

  • 题目描述

  • 输入格式

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

接下来 \(n\) 行,第 \(i\) 行两个正整数 \(a_i, b_i\),表示一个数对 \((a_i, b_i)\) 。

  • 输出格式

一行一个整数,表示所求式子的值。

  • 样例输入

  • 样例输出

  • 样例说明

  • 数据规模与约定

保证 \(2 \leq n \leq 200,000\) , \(1 \leq b_i \leq a_i \leq 2000\) 。

 

 

 …