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道题

迟到一天的题解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

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

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

题意:

n个点的树,r为根

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

感谢@nonamenotitle 的指教

题意:

给你个字符串

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

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

19:00 -- 20:35 tc 结局:rank 42 Rating+ 1474→16??

21:05 -- 23:20 cf 结局:rank 414 Rating-73 2153→2080

感觉自己滚粗太厉害..

多校:

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死活出不来好难过...

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

网络流模版题

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

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

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

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

题意:

给你个节点

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

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