absi2011's Blog & Daily Life.

感谢@wavator 提供解题思路!

题意:

n个点m条边的图

求1到n的最短路

PS:路径长度只计算路径上长度最大的k条边

n<=3000 m<=3000 k<=m

没错还是这一场比赛,我好像和它杠上了

迟到一天的题解

题意:

你正在修城墙

一开始,所有城墙等级为1级

你可以指定两个长度为r的区间,让这两个区间的城墙各升1级

之后,你需要支付以下价格:

对于第i块城墙,1级城墙的价格为ai,2级为bi,3级为ci

保证1<=ai<bi<ci<=1e6,保证n<=30000,1<=r<n

那么你一共有(n-r)*(n-r+1)/2

求第k小的价格

题意:

给你n个数

保证:

a₁<a₂

a₁+a₂<a₃

a₁+a₂+a₃<a₄

......

a₁+...+a_n-1 < a_n

以及a₁ + ... + a_n < q

现在我们选出了一个数字r,保证gcd(r,q)=1

b_i = a_i * r

那么当我们要发送一个长度为n的01信息给某人,我们可以发送一个b_i的对应位置的和(对q取模)过去

例如11 49 100 发送149表示011(但是b数组不保证a数组的性质)

如果q是120的话,发送29表示011

现在选定q = 2^64

现在给你b,给你发送的数字

知道r的人可以自己通过r^-1来求出相应的信息从而得出结论,但你没有r,你也要求出这个信息.

题意:

给你n个操作

1,放个靶子上去,保证靶子不重叠

2,丢个飞镖,如果扎中靶子,输出什么时候放的这个靶子;然后移除这个靶子

一共补了5道题

题意:

225

给你一个数字串,求有多少个子序列是3的倍数

n<=100,允许前导0的子串

(例如132有三个子序列:12 3 132是3的倍数;1 2 13 32则不是)

450

n*n的格子(0~n-1,0~n-1)

你每次跳的距离必须大于等于d

问最少要跳几次才能从(sx,sy)到(tx,ty)

n<=1000 d<=2000 0<=sx,sy,tx,ty<n

800

给你一个长度为n的序列

你可以对这个序列进行任意次操作

每次可以选个x让x(i+1) ^= x(i)

求变换后的最长公共子序列长度的最大值

n<=100 0<=x(i)<=1e18

迟到一天的题解QAQ

http://codeforces.com/contest/917/problem/C

题意:x个青蛙

每次让最左边的青蛙往前跳1~k步,不允许两只青蛙呆在同一个格子上

跳1~k格消耗c₁~c_k的体力

有q个特殊的点,第p个点每只青蛙跳上去会消耗额外的w_p点体力(如果是负数那么就是增加体力)

一个长度为x的一条路(一共x个格子的路)

一开始x个青蛙在1,2...x的位置

问到达n-x+1,n-x+2....n的位置

最少需要多少体力(可以为负)

1<=x<=k<=8 n<=1e8 0<=q<=25 (q<=n-k)

题意:

给你n个数,两个操作

1,询问区间内的gcd是否可以在修改最多一个数的情况下为x

2,修改一个数

n<=5e5 q<=4e5

=============

题意:

n个袋子,每个袋子里俩球

你要把一个染成红色,一个染成蓝色

每个球上面有个数字,求(蓝色球的极差)*(红色球的极差)的最小值

例如,蓝色为1,3,4,1,2,1,7 (极差:7-1=6)

红色为4,2,3,1,8,7,2 (极差:8-2=6)

则这一组分配方案为36

http://codeforces.com/problemset/problem/893/F

题意:

n个点的树,r为根

强制在线的询问,以x为根的子树里面,深度<=k(根深度为0)的点的权值最小为多少

来源:北京赛区

http://hihocoder.com/problemset/problem/1630

一个纯代码题....

下次争取少WA几次....

http://www.rqnoj.cn/problem/707

做法如下:

题意&链接:

http://agc010.contest.atcoder.jp/tasks/agc010_c

n个点的树,每个点上有一个权值

每次你可以选两个不同的叶子(必须是叶子!)然后把它们路径上的所有点权值-1

要求把所有点权值变为0

求是否可能

范围:2<=n<=100000 0<=权值<=1e9

link:http://arc063.contest.atcoder.jp/tasks/arc063_c

题意:

给你一颗树,有些点有初始权值

现在求一个方案(当然如果不存在方案输出No即可)(如果方案存在,输出Yes)

把所有点都赋一个权值,每条边的权值差恰好为1

(原来有权值就不能改了)

link:http://agc012.contest.atcoder.jp/tasks/agc012_d

题意:

给你n个球

每个球有一个颜色(c)和一个权值(w)

如果两个同色球的权值和<=X可以交换它们

如果两个异色球的权值和<=Y可以交换它们

问:你最多可以交换出多少种颜色排列?

例如:三个同色球,不管X,Y,w是多少答案都是1,

1<=c<=n

n<=200000