2018/3/27 省选模拟赛 140分

T1 树归 100

T2 写的快速幂卷积 40,超时了,正解是矩阵乘法之类的。

正解

 1 暴力(m<=5):将x的所有约数提出来矩阵乘法
 2
 3 定义乘法同构:
 4 A=p[1]^a[1] * p[2]^a[2] * ... * p[n]^a[n]
 5 B=q[1]^b[1] * q[2]^b[2] * ... * q[n]^b[n]
 6 其中p[i]与q[i]皆为质数
 7 将数组a与b降序排序后如果是完全相同的,那么称A与B是乘法同构的
 8 如 2*2*2*2*3*3*5 与 7*11*11*3*3*3*3 同构
 9
10 我们发现,10^5内在乘法同构下本质不同的数字只有165个
11 定义kind[x]:x在乘法同构下所属于的种类
12 对着165个本质不同的数构造出矩阵A
13 我们发现,f0[d]对fk[x](d是x的因子)的贡献为f0[d] * A^k[kind[1]][kind[x/d]]
14 所以我们只需要A^k[kind[1]][]这一行就够了
15 预处理A,A^2,A^4,A^8,...O(165^3*log(n))
16 对于每次询问因为最终只需要一行,可以优化到O(165^2*log(n))
17 总复杂度O(165^3*log(n) + m*165^2*log(n))

T2 交互题,不会写,正解是朝任意方向走一定步数(不回头)然后判断此时的深度与初始深度。

 1 假设初始点为s,首先暴力找出s的父亲x
 2 定义函数work(s,x)
 3 从x开始随机游走9步,要求:第一步不能走向s,不走回头路
 4 假设最终走到了y,询问y的深度
 5 我们知道了x与y的深度,也知道x与y之间的距离(9),那么我们可以轻易走到x与y的lca处,并称此点为z
 6 如果z=x,也就是说一开始就是向更深处走的,那么我们已经知道了x向深处走的两个方向(s方向与y方向),自然可以推出x的父亲f,递归work(x,f)
 7 如果z!=x且z!=y,那么我们知道了z向深处走的两个方向(x方向与y方向),自然可以推出z的父亲f,递归work(z,f)
 8 如果z=y,递归work(s,x),即什么都不做
 9 我们发现有2分之一可能深度减1;4分之一可能深度减2;8分之一可能深度减3...
10 于是愉快的在测距期望initialDeep/2次的情况下找到出口

我真鸡儿丢人

原文地址:https://www.cnblogs.com/137shoebills/p/8656735.html

时间: 03-26

2018/3/27 省选模拟赛 140分的相关文章

2018/3/9 省选模拟赛 0分

第二题模拟扫一遍就可以过,不能更划算了.q=1的30分写的比100分还麻烦,有趣哦. 破暴力40分也没什么可写了,日常辣鸡吃枣药丸. 原文地址:https://www.cnblogs.com/137shoebills/p/8533870.html

2018.3.10 省选模拟赛

从这里开始 概况 Problem A 三元组 Problem B 攻略 Problem C 迂回 概况 这是省选T1合集?还是欢乐AK赛? 全班一半以上的人三道题都会做qwq. Doggu还剩一小时时以为自己AK了,然后玩了一小时.虽然最终被卡了20分的常数. ZJC 1个半小时AK?Excuse me? 我这条大咸鱼到最后10分钟才敲完了T1,然后发现线段树要T掉. 发自内心鄙视垃圾出题人卡常数,本来的欢乐AK变成280. 教练给我们考4个小时的试,题面上也这么写的,看题解,woc,考试时间3

2018.2.12 省选模拟赛

题目大意 (题目很简洁了,不需要大意) 其实显而易见地可以发现,当被卡一次后后面的路程都是固定了的. 可以用类似动态规划的思想来进行预处理.现在的问题就是怎么知道在某个位置刚等完红灯然后出发会在哪个路口再次被卡. 尝试画一画图: 其中横轴表示位置,纵轴表示时间,长方体表示红灯时段.有用的部分长度只有$r + g$,所以在模意义下弄一下就可以减少很多重复和无用状态: 但是这样仍然不好处理上面提到的问题,考虑让线段横着走,第一个撞着的长方形就是答案.为了实现这个目标,就每个长方形向下移动一段(移动的

2018.6.29 省选模拟赛

*注意:这套题目应版权方要求,不得公示题面. 从这里开始 Problem A 小D与电梯 Problem B 小D与田野 Problem C 小D与函数 Problem A 小D与电梯 题目大意 假设电梯在0层,容量无限大.给定$n$个人的到达时间和要去的楼层.电梯上下一层楼花费的时间为1,电梯开关门.乘客上下的耗时不计,电梯可以停留在某一层楼.问将所有人送达到目的地,并让电梯回到0层的最少耗时. 先按到达时间将所有人排序.显然,每次电梯运输的人是一段连续的区间中的人. 用$f[i]$表示将前$

2018.2.23 省选模拟赛

从这里开始 Problem A cycle Problem B meal Problem C naive Problem A cycle 判断是否有经过一个点的负环,我们可以跑最短路.判断这个点到自己的最短路是否是负数. 于是可以二分环大小跑dfs版spfa. 于是可以分层图做时间复杂度四方的dp. (YYR给的数据水得吓人,这两个做法居然都跑过了.然后都被我和jmr卡掉了) 注意到如果一个点走不超过$k$条边回到自己的最短路的长度是负数,那么走不超过$k + 1$条边也是. 因此我们可以二分答

2018/3/29 省选模拟赛 80

我真是太菜了... T1 10分纯暴力没写,20分容斥也没写(人就是懒死的).还有30分矩乘不会 正解 <IOI2018 中国国家集训队第一阶段作业题解部分 - 杭州第二中学 吴瑾昭.pdf>最后一题 T2  以为自己能拿到50分,但是其实那个暴力算法只能过10分的点,n=2000的20分数据用n^3带剪枝过不了,所以拿了30分. 正解 <计数与期望问题选讲 CLJ.pdf>最后一题 我记得我以前好像看到过这个文档但是没读过..今天读一下 T3 依然是分情况50分,30分树归20分

2018/3/1 省选模拟考试 50分

T1 30分模拟暴力,40分树的直径.拿了0分.(空间开小了爆了,因为缩点之后是又建了一次图,两个边的编号tot没分开,mdzz) 只写了后40分,而这40分中有20分不需要边双连通分量.写了一个类似于强连通分量(标记双向边)的缩点,应该实现哪里出了偏差,因为就算空间开大改正tot的bug也还是20分. T2 写了50分纯暴力 会bsgs可以得80分好像,但是我只会快速幂和暴力,所以50. T3 看了题目,没写,感觉是lca和一些神奇的操作.题解看上去是一个挺裸的lca,亏了. 原文地址:htt

@省选模拟赛03/16 - T3@ 超级树

目录 @description@ @solution@ @accepted code@ @details@ @description@ 一棵 k-超级树(k-SuperTree) 可按如下方法得到:取一棵深度为 k 的满二叉树,对每个节点向它的所有祖先连边(如果这条边不存在的话). 例如,下面是一个 4-超级树: 请统计一棵 k-超级树 中有多少条不同的简单有向路径,对 mod 取模. input 一行两整数 k, mod. output 一行一整数表示答案. example input1: 2

xjoi省选模拟赛_14

T1 发现 对于当前 投出 奇数次向上的概率为 p 那么 若加入一个 pi=0.5 的骰子 发现  p奇 +1=p奇 * 0.5+p偶 * 0.5 = p偶+1  也就是说 只要方案中存在一个 p=0.5 的骰子 这个方案必然合法  : 1 #include <bits/stdc++.h> 2 #define N 100 3 #define eps 1e-7 4 using namespace std; 5 typedef long double ldb; 6 int t,n; 7 ldb A