DDOSvoid's Blog

CF 316G3 Good Substrings

发表于 2022-11-29 分类于 OI & ACM

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

题目描述

https://codeforces.com/problemset/problem/316/G3

简要题意：给定一个字符串 $S$，同时给出 $m$ 个限制，每个限制给定一个字符串 $T_i$ 和一个区间 $[l,r]$，表示合法的字符串在 $T_i$ 中出现的次数在 $[l,r]$ 之间，求 $S$ 的本质不同合法子串的数量

$|S|,|T_i|\le 5\times {10}^4,m\le 10$

阅读全文 »

Luogu P5605 小A与两位神仙

发表于 2022-11-29 分类于 OI & ACM

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

题目描述

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

简要题意：给定一个整数 $n$，保证 $n$ 是奇质数 $p$ 的正整数次方，现在有 $m$ 次询问，每次询问给定两个正整数 $x,y$，保证 $(x,n)=1,(y,n)=1$，问是否存在非负整数 $a$，使得 $x^a\equiv y(modn)$

$x,y<n\le {10}^{18},m\le 2\times {10}^4$

阅读全文 »

CF 1603C Extreme Extension

发表于 2022-11-29 分类于 OI & ACM

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

题目描述

https://codeforces.com/problemset/problem/1603/C

简要题意：给定一个长度为 $n$ 的序列 $a_i$，每次操作可以选择序列中的一个数 $x$，将其变成 $a$ 和 $b$，注意 $a,b$ 插入到原序列 $x$ 的位置，且满足 $a+b=x$，我们定义 $f(l,r)$ 为最少需要多少次操作可以使得序列 $a_l,a_{l+1},\cdots ,a_r$ 单调不降，求 $\sum _{i=1}^n\sum _{j=i}^{n}f(i,j)$

$n,a_i\le {10}^5$

阅读全文 »

P5304 [GXOI/GZOI2019]旅行者

发表于 2022-11-19 分类于 OI & ACM

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

题目描述

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

简要题意：给定一个 $n$ 个点 $m$ 条边的有向图，同时给定 $k$ 个点，求这 $k$ 个点两两最短距离的最小值

$n\le {10}^5,m\le 5\times {10}^5$

阅读全文 »

CF 986E Prince's Problem

发表于 2022-11-19 分类于 OI & ACM

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

题目描述

https://codeforces.com/problemset/problem/986/E?f0a28=1

简要题意：给定一棵 $n$ 个点的无根树，每个点有一个点权 $a_i$，现在有 $m$ 次询问，每次询问给定一条树上的路径 $(u,v)$ 和权值 $w$，求 $\prod _{t\in (u,v)}gcd(a_t,w)$

$n\le {10}^5,a_i,w\le {10}^7$

阅读全文 »

CF 1009F Dominant Indices

发表于 2022-11-16 分类于 OI & ACM

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

题目描述

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

简要题解：给定一棵 $n$ 个节点的有根树，我们定义 $f_{u,k}$ 为 $u$ 的子树内距离 $u$ 为 $k$ 的点的个数，对于每个节点 $u$ 求 $f_{u,k}$ 最大的 $k$

$n\le {10}^6$

阅读全文 »

Luogu P6326 Shopping

发表于 2022-11-16 分类于 OI & ACM

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

题目描述

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

简要题意：给定一棵 $n$ 个点的无根树，每个点有一个物品，物品有重量 $w$，价值 $c$ 和数量 $d$ 这三个属性，现在要在树上做多重背包，给定重量 $m$，你现在可以选择的物品必须满足在一个连通块内，即如果你选了 $u$ 和 $v$ 中至少一个物品，那么 $u$ 和 $v$ 路径上的每个点你都必须至少选一次

$n\le 500,m\le 4000,w\le m,d\le 100$

阅读全文 »

Luogu P4211 [LNOI2014]LCA

发表于 2022-11-16 分类于 OI & ACM

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

题目描述

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

简要题意：给定一个 $n$ 个节点的有根树，现在有 $m$ 次询问，每次询问给定 $[l,r]$ 和 $u$，求 $\sum _{i=l}^{r}de{p}_{lcai,u}$

$n,m\le 5\times {10}^4$

阅读全文 »

2022-2023 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals) I IQ Game

发表于 2022-11-11 分类于 OI & ACM

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

题目描述

https://codeforces.com/gym/104012/problem/I

简要题意：现在有 $n$ 个人围成一圈进行游戏，游戏规则为每一轮在 $n$ 个人中随机抽取一个人使其出局，如果抽到的人已经出局，则顺延到下一个人，现在游戏已经进行了 $n-k$ 轮，还剩下 $k$ 个人，告诉你 $k$ 个人的编号，现在游戏继续进行，如果 $s$ 出局则结束，问游戏期望进行多少轮

$n\le {10}^9,k\le 200$

阅读全文 »

Luogu P6617 查找 Search

发表于 2022-11-10 分类于 OI & ACM

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

题目描述

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

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和一个整数 $k$，现在有 $m$ 次操作，操作有两种，第一种操作给定 $x,y$，将 $a_x$ 修改为 $y$；第二种操作给定一个区间 $[l,r]$，询问区间内是否存在两个数 $a_x+a_y=k$

$n,m,k\le 5\times {10}^5$，强制在线

阅读全文 »