DDOSvoid's Blog

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/contest/1623/problem/D‘

简要题意：现在有一个 $n\times m$ 的网格图，以及一个以 $(r_b,c_b)$ 为起点的机器人，机器人每一秒会走一步，其坐标的增量为 $(dr,dc)$，初始时 $dr=dc=1$，每当机器人撞到横向或者竖向的墙壁后，$dr$ 或者 $dc$ 会变成 $-1$，机器人在每个位置都有 $p$ 的概率探测与其在横坐标或者纵坐标相同的所有点，当机器人探测到目标点 $(r_d,c_d)$ 后结束，求期望时间

$n\times m\le 10^5$

阅读全文 »

发表于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

题目描述

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

简要题意：现在有 $n$ 个学生正在考试，试卷有 $m$ 到题目，现在已知每个学生每道题目正确与否，要求给每道题目赋一个 $[1,m]$ 的分值，同时要求 $m$ 道题目的分值为一个排列，同时每个学生心中有一个预期分数 $a_i$，我们令学生真正的分数为 $b_i$，现在要求最大化 $\sum_{i=1}^n|a_i-b_i|$

$n\le 10,m\le 10^4$

阅读全文 »

发表于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/contest/1620/problem/G

简要题意：首先定义 $f([s_1, s_2,\cdots, s_k])$ 为本质不同的子串个数，要求这些子串至少是 $s_1,s_2,\cdots,s_k$ 中某一个串的子序列，现在给 $n$ 个串 $s_i$，求对于 $s$ 的 $2^n$ 种选择，求它们的 $f$，对于一种选择 $s_{i_1},s_{i_2,},\cdots,s_{i_k}$，求出 $f([s_{i_1},s_{i_2,},\cdots,s_{i_k}]) \bmod 998244353$，将其乘上 $k\times (i_1+i_2+\cdots+i_k)$，然后将求出的 $2^n$ 个 $f$ 异或起来，另外对于给定的串 $s_i$，保证 $s_i$ 中的字母是按照字典序排列

$n\le 23$

阅读全文 »

发表于 分类于
本文字数： 6.3k 阅读时长 ≈ 6 分钟

题目描述

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

简要题意：现在有两个序列 $a$ 和 $b$，长度分别为 $n$ 和 $m$，现在随机从 $a$ 中选一个数 $x$，然后再随机从 $b$ 中选一个数
$y$，求对于 $k\in [1,t]$，$(x+y)^k$ 的期望是多少，答案对 $998244353$ 取模

$a,b,t\le 10^5$

阅读全文 »

发表于 分类于
本文字数： 5.5k 阅读时长 ≈ 5 分钟

题目描述

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

简要题意：假设现在有一个集合 $S$，$S$ 中只含若干个 $[1,n]$ 的正整数，我们令 $f(k)$ 为把 $k$ 表示成 $S$ 中的元素的和的方案数，每个数都能用无限次，每种方案都是无序的，现在给定 $f(1)$ 到 $f(n)$ 这 $n$ 个模 $p$ 的值，求构造一个字典序最小的集合 $S$，保证 $p$ 是素数，但不一定是 $998244353$

$n\le 2^{18}$

阅读全文 »

发表于 分类于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

https://ac.nowcoder.com/acm/contest/26134/A

简要题意：现在有一个长度为 $n$ 的字符串，我们现在要将它的所有前缀按照某种顺序排成一排，如果前缀 $i$ 排在第 $j$ 个位置，那么它的代价为 $j\times a_i$，求最小贡献和，如果 前缀 $i$ 是前缀 $j$ 的 $border$，那么前缀 $i$ 一定要排在前缀 $j$ 的前面

$n\le 10^5$

阅读全文 »