「牛客挑战赛31 E | Nowcoder 880E」密涅瓦的谜题

好久没更了 = =

现在看到什么题都感觉一脸不可做,水平太低了

题意

给出仅包含小写字母的长度为 $n$ 的字符串 $s$

每次取出 $s$ 的一个子串 $t_i$(可以为空),执行 $m$ 次,顺次拼接成一个大字符串 $t=t_1 t_2\dots t_m$,求可以得到多少种本质不同的 $t$

$q$ 次询问,每次给出一个 $m$

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

Read more

「UOJ 345」「清华集训2017」榕树之心

UOJ #345. 【清华集训2017】榕树之心

题目背景

深秋。冷风吹散了最后一丝夏日的暑气,也吹落了榕树脚下灌木丛的叶子。相识数年的 Evan 和 Lyra 再次回到了小时候见面的茂盛榕树之下。小溪依旧,石桥依旧,榕树虽是历经荣枯更迭,依旧亭亭如盖,只是 Evan 和 Lyra 再也不是七八年前不经世事的少年了。

……

Read more

「LOJ 2983」「WC2019」数树

LOJ #2983. 「WC2019」数树

题意

本题包含三个问题:

  • 问题 0:已知两棵 $n$ 个节点的树的形态。要给予每个节点一个 $[1, y]$ 中的整数,使得对于任意两个节点 $p, q$,如果存在边 $(p, q)$ 同时属于这两棵树,则 $p, q$ 必须被给予相同的数。求给予数的方案数。

  • 问题 1:已知第一棵树,对于第二棵树的所有 $n^{n−2}$ 种选择方案,求问题 0 的答案之和。

  • 问题 2:对于第一棵树的所有 $n^{n−2}$ 种选择方案,求问题 1 的答案之和。

对 $998244353$ 取模

Read more

「Codeforces 1034C」Region Separation

没有思维能力了

Codeforces 1034C

题意

给你一棵 $n$ 个点的树,有点权$a_1,..,a_n$,整棵树是一个1级区域

  • 除非 $i$ 是最后一个等级,否则每一个i级区域都要被分成至少两个i+1级区域

  • 每个点必须恰好属于一个每种等级的区域

  • 一个区域必须是连通的

  • 每个相同等级的区域必须拥有相同的点权和

求有多少种不同的划分方案,模 $10^9+7$

$n\le 10^6,a_i\le 10^9$

Read more

「LOJ 2340」「WC2018」州区划分

LOJ #2340

题意

有 $n$ 座城市,第 $i$ 座城市的人口是 $w_i$,有一些无向边。

现在城市被划分为了若干个州,每个州至少包含一个城市,每个城市恰好在一个州内。

设 $V_i$ 是第 $i$ 个州的城市集合。

定义一条道路是一个州的内部道路,当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同,不经过任何不属于这个州的城市,且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径(路径长度可以为 $0$),则称这个州是不合法的。

定义第 $i$ 个州的满意度为:第 $i$ 个州的人口在前 $i$ 个州的人口中所占比例的 $p$ 次幂,即:

$$\left(\frac{\sum_{x\in V_i}w_x}{\sum_{j=1}^i\sum_{x\in V_j}w_x}\right)^p$$

定义一个划分的满意度为所有州的满意度的乘积。

求所有合法的划分方案的满意度之和。

答案对 $998244353$ 取模。

$n\le 21,0\le p\le 2$

时限 $10s$

Read more

「LOJ 2145」「SHOI2017」分手是祝愿

LOJ #2145


Zeit und Raum trennen dich und mich.

时空将你我分开。

题意

你有一排$n$个灯泡,有初始状态$0/1$,从$1$开始编号

一次操作可以选定一个整数$x\in[1,n]$,把$x$的所有约数号(含$1$和$x$)灯泡状态取反。

你要把所有灯泡变成$0$,给出$0\le k\le n$

  1. 若剩余最小操作次数$\le k$,你会直接按照最小操作次数操作,并结束

  2. 否则每次你会在$[1,n]$中等概率地选择一个整数进行操作,直到满足1的条件

求期望操作次数乘$n!$对$100003$取模的结果

$1\le n\le 10^5$

Read more

「Codeforces 1063F」String Journey

第一篇算法相关

第一次自己想sam

Codeforces 1063F

题意

给出一个长度为$n$的字符串$s$。

如果一个字符串序列$t_1,\dotsc,t_k$,$\forall1<i\le k$,$t_i$是$t_{i-1}$的一个子串,且长度严格小,那么称这个字符串序列是一个journey

一个journey的长度是其中字符串的数量

求最长的journey,满足存在字符串序列$u_1,\dotsc,u_{k+1}$(可以为空),使$s=u_1t_1u_2t_2\cdots u_kt_ku_{k+1}$。

Read more