清华集训Day4=。=

于是今天是清华集训的最后一Day,雪舞喵获得成就<狗牌滚粗>

结果今天雪舞喵只有最后5min打了个t2暴力得了40分=。=

因为实在太蒻了今天也没有代码=。=

具体情况接下来研究

T1 组合数问题

时间限制: 1.0 秒 内存限制: 512 MB

【问题描述】

组合数 \(C^m_n\) 表示的是从 n 个物品中选出 m 个物品的方案数。举个例子,从 (1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义,我们可以给出计算组合数 \(C^m_n\) 的一般公式:

\[C^m_n=\frac{n!}{m!(n-m)!}\]

其中 n!=1×2×⋯×n。(额外的,当 n=0 时, n!=1)

小葱想知道如果给定 n,m 和 k,对于所有的 0≤i≤n,0≤j≤min(i,m) 有多少对 (i,j) 满足 \(C^j_i\) 是 k 的倍数。

【输入格式】

从标准输入读入数据。

第一行有两个整数 t,k,其中 t 代表该测试点总共有多少组测试数据,k 的意义见【问题描述】。

接下来 tt 行每行两个整数 n,m,其中 n,m 的意义见【问题描述】。

【输出格式】

输出到标准输出。

t 行,每行一个整数代表所有的 0≤i≤n,0≤j≤min(i,m) 中有多少对 (i,j) 满足 \(C^j_i\) 是 k 的倍数,答案对 \(10^9+7\) 取模。

【样例1】

输入

1 2

3 3

输出

1

说明

在所有可能的情况中,只有 \(C^1_2=2\)  是 2的倍数。

【样例2】

输入

2 5

4 5

6 7

输出

0

7

【样例3】

输入

3 23

23333333 23333333

233333333 233333333

2333333333 2333333333

输出

851883128

959557926

680723120

【子任务】

  • 对于 20% 的测试点,1≤n,m≤100;
  • 对于另外 15% 的测试点,n≤m;
  • 对于另外 15% 的测试点, k=2;
  • 对于另外 15% 的测试点, m≤10;
  • 对于 100% 的测试点, \(1\le n,m \le 10^{18},1 \le t,k \le 100\) ,且 k 是一个质数。

据说这道题是原来要出到noip的题,然后被拒绝了,然后noip就把数据范围削到20%出成t1了,这道题就拿来清华集训了=。=

反正雪舞喵推了大概半个小时推出一个数位dp,这题和组合数啥的其实没啥关系, \(C^j_i \bmod p = 0\) 其实等价于j和i拆成k进制表示下i中至少有一位小于j。

然后敲了半小时敲出来了,调了3小时,没过。

……看来雪舞喵真的需要代码能力了

复杂度大概是 \(O(t \log n)\)

汽水

时间限制: 5.0 秒 内存限制: 512 MB

【问题描述】

牛牛来到了一个盛产汽水的国度旅行。

这个国度的地图上有n个城市,这些城市之间用n−1条道路连接,任意两个城市之间,都存在一条路径连接。这些城市生产的汽水有许多不同的风味,在经过道路 ii 时,牛牛会喝掉wi的汽水。牛牛非常喜欢喝汽水,但过量地饮用汽水是有害健康的,因此,他希望在他旅行的这段时间内,平均每天喝到的汽水的量尽可能地接近给定的一个正整数k。

同时,牛牛希望他的旅行计划尽可能地有趣,牛牛会先选择一个城市作为起点,然后每天通过一条道路,前往一个没有去过的城市,最终选择在某一个城市结束旅行。

牛牛还要忙着去喝可乐,他希望你帮他设计出一个旅行计划,满足每天|平均每天喝到的汽水−k|的值尽量小(其中天数至少为1),请你告诉他这个最小值。

\(n\le 5 \times 10^4,0\le wi \le 10^{13},0\le k\le 10^{13}\)

【输入格式】

从标准输入读入数据。

第一行两个正整数n,k。

接下来n−1行,每行三个正整数ui,vi,wi,表示城市ui和城市vi之间有一条长度为wi的道路连接。

同一行相邻的两个整数均用一个空格隔开。

【输出格式】

输出到标准输出。

一行一个整数,表示|平均每天喝到的汽水−k|的最小值的整数部分,即你只要将这个最小值向下取整然后输出即可。

【样例1】

输入

5 21

1 2 9

1 3 27

1 4 3

1 5 12

输出

1

说明

在图中,路径5->1->3是一条最合适的路线,总计喝到的汽水的量是27+12=39 , 平均每天喝到的汽水量是39÷2=19.5 , |19.5−21|=1.5 , 向下取整后得到1,因此答案是1。

【样例2】

下载目录下的 ex_soda2.in 与 ex_soda2.ans

【子任务】

对于20%的数据,n≤1000。

对于另外20%的数据,保证编号为i(1≤i≤n−1)的节点和编号为i+1的节点之间连接了一条边。

对于另外20%的数据,保证数据是以1为根的完全二叉树(在完全二叉树中,节点 i(2≤i≤n) 和节点 ⌊i÷2⌋ 之间有一条道路)。

对于另外20%的数据,保证除节点1以外,其他节点和节点1之间都有一条道路


这题是个点分治,标算雪舞喵听懂了,然而考试的时候根本没机会看,就搞了个前20分和菊花图20分的暴力=。=

前20分直接n个点各dfs一遍就行了,菊花图搞个set胡乱维护一下。

标算的话,首先把所有边权都减去k,然后只要求权值平均值大于0的最小值就可以了(然后把边权*-1再来一遍)

假设有个Δk,使得平均值大于Δk的路径等于平均值大于0的路径,那么这个答案一定大于Δk。

然后二分这个Δk,问题就变成了求权值平均值大于Δk的路径有多少。

点分一下=。=

复杂度3个log,可能还需要卡卡常

好像有个更优秀的算法可以在点分里面二分,能变成两个log

定向越野

时间限制: 2.0 秒 内存限制: 1024 MB

【问题描述】

定向越野是一项集智力与体力为一体的体育运动,在这项活动中,选手需要从起点出发,在尽可能短的时间内到达指定的地点。

牛牛非常喜爱这项运动,但是他不知道怎么样才能更快到达终点。他听说来参加集训的你智力过人,于是他把定向越野的地图交给了你,希望你帮他解决一些问题。

牛牛给你的地图描述的是一块平地,地图上不仅清楚地标出了起点和终点的坐标,还标有若干个互不相交圆形区域,每个区域表示一个圆形的水域。对于不会游泳的牛牛来说,进入水域是根本不可能的。因此,牛牛的行动路线不能从水域中穿过。牛牛想知道这样的路线长度最小可以是多少。

特别地,我们认为如果两个圆形水域相切,牛牛能够从中间经过。

【输入格式】

从标准输入读入数据。

第一行包含四个实数Sx,Sy,Tx,Ty,分别表示起点的x,y坐标和终点的x,y坐标。

第二行包含一个正整数n,表示水域的个数。

接下来n行,每行3个整数xi,yi,ri表示一片水域的圆心的x,y坐标和半径。

n≤500,−1000≤xi,yi,ri,Sx,Sy,Tx,Ty≤1000 。

保证起点和终点都不在水域的内部或边界上,起点和终点不重合。

【输出格式】

输出到标准输出。

输出一行,包含一个实数,四舍五入精确到小数点后恰好1,表示答案。你的输出必须和标准输出完全一样才算正确。

测试数据保证四舍五入后的答案和准确答案的差的绝对值不大于 \(4 \times 10^{-2}\)

(如果你不知道什么是浮点误差,这段话可以理解为:对于大多数的算法,你可以正常地使用浮点数类型而不用对它进行特殊的处理)

【样例1】

输入

2 1 20 11

2

5 5 4

16 9 4

输出

23.0

说明

这个地图如下图,其中画出的路径即是所求的最短路径。

[图片]

【样例2】

下载目录下的 ex_circle2.in 与 ex_circle2.ans

【子任务】

测试点 n 半径相同 网格
1 ≤0 × ×
2 ≤1
3
4 ≤2
5 ×
6 ≤3
7 ≤4
8 ≤5 × ×
9 ≤8
10 ≤16
11 ≤20 × ×
12 ≤50
13 ≤100
14 ≤200 × ×
15 ≤400
16
17 ≤500 × ×
18
19
20

半径相同:指任意两个圆半径相同。

网格:指所有圆分布在一个 \(\sqrt n \times \sqrt n\) 的正方形网格内部,每个圆都与所在格子的四条边界相切。(若圆的半径是r,那么整个正方形网格的边长应当是 \(2 \times r\times \sqrt n\)


这题起点终点直接连线可以得20分!20分!

雪舞喵当然写了,然而忘记提交了……

好了不说这些伤心事了,好像讲题的时候一直在讲一些高超的卡常技巧 \(O(n^3)\) 卡过,于是就忘了 \(O(n^2\log n)\) 的做法是啥了……

然后n3就是枚举两个圆,然后连接4条公切线,判断一下线是否被阻挡,如果没有就建边,然后圆上的点之间建边,起点终点到所有圆的切线建边,然后跑dij。

奇妙的优化技巧好像是判断线是否被阻挡的时候把其他的圆按圆心距离排序,还有判断一下起点终点连线是否没被阻挡(好像两个卡这个算法的点都能从起点直接到终点……)


那么到这雪舞喵的清华集训生活到此结束,照应一下开头,狗牌滚粗了,又得滚回去上学了=。=

非常的不开心=。=

12.07.2016

Yukimai

(^=。=^)

发表评论