DDOSvoid's Blog

Luogu P1659 [国家集训队]拉拉队排练

发表于 2022-09-06 分类于 OI & ACM

本文字数： 1.6k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P1659

简要题意：给定一个长度为 $n$ 的字符串 $S$ 和一个正整数 $k$ ，求 $S$ 的长度前 $k$ 大的回文子串的长度的积

$n \leq 10^{6}, k \leq 10^{12}$

阅读全文 »

CF 1599F Mars

发表于 2022-09-04 分类于 OI & ACM

本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/problemset/problem/1599/F

简要题意：给定一个长度为 $n$ 的序列 $a_{i}$ ，现在有 $m$ 次询问，每次询问给定 $[l, r]$ 和 $d$ ，问 $[l, r]$ 内的数在模 $1 e 9 + 7$ 意义下是否可以构成一个差为 $d$ 的等差数列

$n, m \leq 2 \times 10^{5}$

阅读全文 »

CF 1548C The Three Little Pigs

发表于 2022-09-04 分类于 OI & ACM

本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/CF1548C

简要题意：给定 $n$ 和 $q$ ，现在有 $q$ 次询问，每次询问给定 $x$ 求 $\sum_{i = 1}^{n} (\binom{3 i}{x})$

$n \leq 10^{6}, q \leq 2 \times 10^{5}, x \leq 3 n$

阅读全文 »

CF 1016G Appropriate Team

发表于 2022-09-04 分类于 OI & ACM

本文字数： 3k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/CF1016G

简要题意：给定一个长度为 $n$ 的序列 $a_{i}$ 和两个整数 $X$ 和 $Y$ ，求有多少数对 $(i, j)$ 满足存在一个整数 $v$ ，使得 $(v, a_{i}) = X$ ，同时 $[v, a_{j}] = Y$

$n \leq 2 \times 10^{5}, a_{i}, X, Y \leq 10^{18}$

阅读全文 »

Luogu P5838 [USACO19DEC]Milk Visits G

发表于 2022-08-31 分类于 OI & ACM

本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P5838

简要题意：给定一棵 $n$ 个节点的无根树，每个节点有一个颜色 $c_{i}$ ，现在有 $m$ 次询问，每次询问给定 $x, y, z$ ，问从 $x$ 到 $y$ 的简单路径上是否有颜色 $z$

$n, m \leq 10^{5}$

阅读全文 »

The Hangzhou Normal U Qualification Trials for ZJPSC 2021 B Baom and Fibonacci

发表于 2022-08-31 分类于 OI & ACM

本文字数： 3.2k 阅读时长 ≈ 3 分钟

题目描述

https://codeforces.com/gym/103462/problem/B

简要题意：给定 $n$ ，求 $\sum_{i = 1}^{n} \sum_{j = 1}^{n} g c d (f i b (i), f i b (j))$

$n \leq 10^{10}$

阅读全文 »

Luogu P4707 重返现世

发表于 2022-08-31 分类于 OI & ACM

本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P4707

简要题意：现在有 $n$ 种物品，每个单位时间，有 $\frac{p_{i}}{m}$ 生成第 $i$ 中原料，求期望多少时间我们可以收集 $k$ 种不同的物品

$k \leq n \leq 1000, n - k \leq 10, \sum p_{i} = m, m \leq 10000$

阅读全文 »

CF 954I Yet Another String Matching Problem

发表于 2022-08-31 分类于 OI & ACM

本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/problemset/problem/954/I

简要题意：给定两个字符串 $S$ 和 $T$ ，定义两个长度相同的字符串的距离为需要多少次操作可以将两个字符串变得完全相同，每次操作可以选择两个字符 $c_{1}, c_{2}$ 将两个字符串中所有 $c_{1}$ 变成 $c_{2}$ ，求 $S$ 的所有长度为 $| T |$ 的字符串与 $T$ 的距离

$| S |, | T | \leq 125000, \sum = 6$

阅读全文 »

hdu 6756 Finding a MEX

发表于 2022-08-24 分类于 OI & ACM

本文字数： 2.5k 阅读时长 ≈ 2 分钟

题目描述

http://acm.hdu.edu.cn/showproblem.php?pid=6756

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，每个点有点权 $a_{i}$ ，现在有 $q$ 个操作，操作有两种，第一种操作给定 $x$ 和 $y$ ，修改 $a_{x} = y$ ；第二种操作给定 $x$ ，求与 $x$ 有连边的所有点 $a_{y}$ 所形成的的集合 $S$ 的 $m e x$ 是多少

$n, m, q \leq 10^{5}$

阅读全文 »

Luogu P5385 [Cnoi2019]须臾幻境

发表于 2022-08-24 分类于 OI & ACM

本文字数： 3.7k 阅读时长 ≈ 3 分钟

题目描述

https://www.luogu.com.cn/problem/P5385

简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，现在有 $q$ 次询问，每次询问给定一个区间 $[l, r]$ ，求只包含编号在 $[l, r]$ 内的边的连通块的数量，强制在线

$n, q \leq 10^{5}, m \leq 2 \times 10^{5}$

阅读全文 »