YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

YZOJ P4637 [CSP-S 2019 五校联训 Round 2]由比滨结衣(sqrt)

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

难度:\(6.5\)

  • 题目描述

给定一个长度为 \(n\) 的正整数序列 \(\{a_i\}\),有 \(m\) 次操作。格式如下:

1 l r x 将区间 \([l,r]\) 中的所有数变为 \(x\)。

2 l r x 查询区间 \([l,r]\) 中数字 \(x\) 的出现次数。

  • 输入格式

第一行两个正整数 \(n,m\),表示序列长度和操作次数。

第二行 \(n\) 个正整数,第 \(i\) 个数为 \(a_i\),表示序列初始值。

接下来 \(m\) 行每行四个正整数,表示操作,含义如题目所示。

  • 输出格式

对于每个询问,输出一行一个正整数表示答案。

  • 样例 1 输入

  • 样例 1 输出

  • 数据规模与约定

对于 \(20\%\) 的数据,\(1 \leq …

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

  • 输出格式

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

  • 样例输入


Read the rest