DDOSvoid's Blog

题目描述

https://codeforces.com/gym/103049/problem/G

简要题意：现在有一个迷宫，迷宫是一个长度为 $n$ 的数轴，共有 $m$ 个 $boss$，第 $i$ 个 $boss$ 的位置为 $t_i$，秒杀成功的概率为 $p_i$，秒杀失败则需要花 $d_i$ 的时间，你的速度为 $1$，现在这个迷宫的通关记录为 $r$，求如果你想破纪录期望最少需要花费多少时间，你可以在任何时候重来

$n < r\le 5000,m\le 50$

题目描述

https://codeforces.com/gym/103640/problem/D

简要题意：给定一个长度为 $n$ 的序列 $a_i$，定义合法区间 $[l,r]$ 为区间 $[l,r]$ 的所有前缀和都大于等于 $0$，现在再给一个数 $x$，求选择恰好一个位置将其加上 $x$ 后序列 $a_i$ 的合法区间的数量的最大值

$n\le 5\times 10^5$

题目描述

简要题意：给定两个长度均为 $n$ 的序列 $a_i,b_i$，定义一个数对 $(a_i,b_j)$ 的价值为 $a_i\times b_j$，现在每个 $a_i$ 和 $b_i$ 都只能使用一次，求对于 $k\in[1,n]$，选出 $k$ 个数对的最大价值和以及最小价值和

$n\le 10^5,-10^4\le a_i,b_i\le 10^4$

题目描述

https://codeforces.com/gym/103743/problem/H

简要题意：给定一个长度为 $n$ 的 $01$ 序列 $a_i$，现在要执行 $k$ 次操作，每次操作将所有 $a_i$ 异或上 $a_{i-1}$ 得到 $a’_i$，求最终的序列

$n\le 3\times 10^6,k\le 10^9$

题目描述

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

简要题意：给定 $m$ 个区间 $[l_i,r_i]$，现在有 $n$ 个人，每个人都从 $0$ 出发，第 $i$ 个人每次只能走 $i$，即他经过的位置都是 $i$ 的倍数，求每个人经过的位置属于多少种区间

$n\le 3\times 10^5,m\le 10^5$

题目描述

简要题意：现在有 $n$ 次询问，每次询问给定 $[l,r]$，求 $[l,r]$ 异或和/与和/或和

$n\le 5\times 10^6, 0\le l\le r< 2^{64}$

题目描述

https://codeforces.com/gym/102801/problem/A

简要题意：给定一个长度为 $n$ 的序列 $a_i$，$a_i$ 互不相同，定义两个点 $(x,y)$ 的距离为 $popcount(a_x,a_y)$，求最小生成树

$n\le 2\times 10^5,a_i< 2^{18}$

题目描述

https://codeforces.com/contest/1670/problem/F

简要题意：给定 $n,l,r,z$，求有多少个长度为 $n$ 的序列 $a_i$，满足 $l\le\sum_{i=1}^na_i\le r$ 且 $\bigoplus_{i=1}^na_i=z$，其中 $\oplus$ 为异或

$n\le 1000,1\le l,r \le 10^{18},z\le 10^{18}$

题目描述

https://codeforces.com/gym/102801/problem/L

简要题意：给定一个 $n\times m\times k$ 的六连通三维空间，在这个三维空间的整点上有一些点是居民的住房，另有一些点是邮局，其他点都是空地，现在要求选一块空地改造成邮局，定义一个居民到邮局的距离为到离他最近的邮局的距离他，求如何选择空地改造成邮局可以使所有居民到邮局的距离的最大值最小

$n,m,k\le 100$

题目描述

https://codeforces.com/contest/1679/problem/E

简要题意：给定一个长度为 $n$ 的串 $S$，保证 $S$ 的字符集为 $\sum=\lbrace a,b,c,\cdots,p,q\rbrace$，$S$ 中有若干个位置的值已经确定，还有一些位置可以随便填，现在有 $m$ 次询问，每次询问给出 $\sum$ 的一个子集 $\sum’$，求将 $S$ 中未确定的位置用 $\sum’$ 中的字符来填充后有多少个子串为回文串，即求所有填法的回文子串的和

$n\le 1000,m\le 2\times 10^5$