absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋

[破碎的状态] 101630J

感谢@wavator 提供解题思路!

题意:

n个点m条边的图

求1到n的最短路

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

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

继续阅读

[破碎的状态] 101630G

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

迟到一天的题解

题意:

你正在修城墙

一开始,所有城墙等级为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小的价格

继续阅读

[破碎的状态] 101630K

题意:

给你n个数

保证:

a1<a2

a1+a2<a3

a1+a2+a3<a4

......

a1+...+an-1 < an

以及a1 + ... + an < q

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

bi = ai * r

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

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

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

现在选定q = 2^64

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

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

继续阅读

[破碎的状态] cf 101630A

题意:

给你n个操作

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

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

继续阅读

[破碎的状态] Codeforces Round #467 补题记录

一共补了5道题

继续阅读

[破碎的状态] cf 917C

迟到一天的题解QAQ

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

题意:x个青蛙

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

跳1~k格消耗c1~ck的体力

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

一个长度为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)

继续阅读

[破碎的状态] cf 914D

题意:

给你n个数,两个操作

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

2,修改一个数

n<=5e5 q<=4e5

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

继续阅读

[破碎的状态] Codeforces 893F

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

题意:

n个点的树,r为根

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

继续阅读

开学后第一场cf的碎碎念

阅读全文

[这个blog需要恢复] 432D

感谢@nonamenotitle 的指教

题意:

给你个字符串

求所有的前缀=后缀的长度,以及这个前缀(后缀)在整个字符串里面出现了多少次

继续阅读

[这个Blog需要恢复] 568B

阅读全文

[破碎的状态] [-3] 一天比赛

12:00 -- 17:00 多校 结局:rank 15

19:00 -- 20:35 tc 结局:rank 42 Rating+ 147416??

21:05 -- 23:20 cf 结局:rank 414 Rating-73 21532080

感觉自己滚粗太厉害..

多校:

1001 第一问是一个最小生成树的水题啊..

第二问..好像还是水题..

炸精度挂了一次

1002 SG函数的好题..当补习课外知识了..

如果NOI考到的话..说不准有用

1003 找规律?

不知道哪里WA了不太理解

1004~1011 不是我做的

*1005 装压dp,不过我没来得及拆掉就有人过了这题

*1011 好像可以模拟退火,不过有人数学方法A掉了

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

tc:

300:一个不难的构造题,好多人写错不太懂

500:以为是一个费用流题..

结果我的暴力算法我觉得烦没写= =暴力果然过了..我的费用流不能跑..

800:不知道怎么做

challenge:

300好多人写错..

各种奇怪错误..捞到3个challenge,+3;-1

+125分

rank 42

涨rating了

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

cf:

似乎有个定律..

最近每天最多A 5题的定律..

所以cf只出了A和B..

C死活出不来好难过...

[破碎的状态] [-8] 倒数第二场cf(Before NOI)

这一场比赛的经历也是比较有趣呢

继续阅读

[破碎的状态] [-9] 546E

网络流模版题

曾经在去年救过我省选的题,感谢周植

题意:有n个城市,第i个城市里一开始有ai个人

后来,有些人往某个相邻的城市走(只走一次),之后,第i个城市有bi个人

求是否有可能,如果可能,输出方案数,也就是说第i个城市有几个人往第j个城市走(i=j则表示没走的人)

继续阅读

[破碎的状态] [-11] 690 C3

题意:

给你个节点

每次向里面加一个点以及这个点连一条边到一个已知点

每次操作后求树的直径(即两点的距离的最大值)

继续阅读