wzf2000's blog

Codeforces536D

Codeforces536D 题解题意: 给你一张$n$个点$m$条边的无向图,每个点有一个点权$p_i$(存在负数) 有两个人在进行游戏,他们分别在$s$、$t$号点。 两个人轮流操作,每次操作选出一个非负整数$x$,表示将到他们所在点最短距离小于等于$x$的点的点权拿走。(拿走后点权消失,且每次拿走的有点权的点的个数至少为1) 询问最后胜负情况(谁的总点权和较大)。 $n \leq 2000,n-1 \leq m \leq 100000$     阅读全文
wzf2000's avatar
wzf2000 12月 25, 2017

Codeforces776G

Codeforces776G 题解题意: 设$x$的16进制表示为$x_{n-1} \cdots x_1x_0$,那么设$h(x)=2^{x_{n-1}}|2^{x_{n-2}}| \cdots 2^{x_1}|2^{x_0}$,求区间$[l,r]$中满足$x xor h(x)< x$的数的个数。     阅读全文
wzf2000's avatar
wzf2000 12月 25, 2017

Codeforces559E

Codeforces559E 题解题意: 一条路上有$n$盏不同的灯,每盏灯所在位置为$p_i$,向左或者向右可以照射的距离为$l_i$,求最大总照射长度。 $n \leq 100,l_i,p_i \leq 10^8$。     阅读全文
wzf2000's avatar
wzf2000 12月 23, 2017

Codeforces436D

Codeforces436D 题解题意: 开始有无限长的一段格子,有$n$个格子种有布丁怪兽,一开始连续的布丁怪兽算一个布丁怪兽。 每回合你可以将一个布丁怪兽向左或右移动,他会在碰到第一个布丁怪兽时停下,并与其合并。 如果最左边的怪兽向左,你可以认为是将其移动到了无穷远处。 有$m$个特殊格子,询问最终你最多可以让几个特殊的格子上被布丁覆盖。 $n \leq 10000,m \leq 2000$。     阅读全文
wzf2000's avatar
wzf2000 12月 23, 2017

Codeforces418D

Codeforces418D 题解题意: 给出一颗$n$个点的树,$m$次询问离给定两个点距离较小值的最大值。 $n \leq 10^5,m \leq 10^5$     阅读全文
wzf2000's avatar
wzf2000 12月 23, 2017

Codeforces232E

Codeforces232E 题解题意: 给你一张$n \times m$的网格图,每次可以向下或者向右,$q$次询问两点从一点是否可到另一点。 $n,m \leq 500,q \leq 6 \times 10^5$     阅读全文
wzf2000's avatar
wzf2000 12月 23, 2017

Codeforces238E

Codeforces238E 题解题意: 有一张$n$个点,$m$条边的有向图,有$k$种巴士,每种巴士有一个起点$s_i$和终点$t_i$,每一个时刻,巴士都会等概率选择一条两点间的最短路径。 询问一次从$a$到$b$最坏情况下最少需要乘坐几种巴士。 $n \leq 100,m \leq n \times (n-1),k \leq 100$     阅读全文
wzf2000's avatar
wzf2000 12月 23, 2017

Codeforces332E

Codeforces332E 题解题意: 给出两个字符串$p$和$s$和一个正整数$k$,要求构造长度为$k$的$01$串,满足以下要求: 将其不断复制到长度大于等于$|p|$。 对应$p$跑这个串,如果当前位置为$1$,则将$p$当前对应的字符加入一个串$q$的结尾。(开始为空串) 最后得到的串$q$与$s$相等。 输出满足要求的字典序最小的$01$串。 $|p| \leq 10^6,|s| \leq 200,k \leq 2000$     阅读全文
wzf2000's avatar
wzf2000 12月 23, 2017

Codeforces183D

Codeforces183D 题解题意: 有$n$个人和$m$种T-shirt,每个人都有一种喜欢的T-shirt,然而你只知道他们每个人喜欢某种的概率。 你需要在开始时选定$n$件T-shirt的种类,人们会按照编号从$1$~$n$挑选T-shirt,如果剩下还有他喜欢的,则会选走,否则不变。 请输出最大的期望送出的T-shirt件数。 $n \leq 3000,m \leq 300$     阅读全文
wzf2000's avatar
wzf2000 12月 23, 2017

Codeforces301E

Codeforces301E 题解题意: 给出$n,m,k$,询问有多少个长度为$n$的数组$b$满足以下要求: $b[i] \leq b[i+1],1 \leq i < n$ $1 \leq b[1] \leq b[n] \leq m$ 将$b$数组排列后有大于等于一种小于等于$k$种排列$a$满足以下要求: $|a[i]-a[i+1]|=1(1 \leq i<n)$ $|a[n]-a[1]|=1$ $a[1]=min_{i=1}^{n}a[i]$ $n,m,k \leq 100$     阅读全文
wzf2000's avatar
wzf2000 12月 23, 2017