“玲珑杯”ACM比赛 Round #18做题记录

这场比赛感觉题目较为简单,但是体验较差。主要是评测机崩掉了,然后莫名延时莫名突然结束,算了,按照qwertier大爷的口头禅:“这都无所谓了,反正你那么垃圾早过一个题又能怎样?”

A — 计算几何你瞎暴力

题意:略。

因为坐标范围较小,最多也就一千多个,所以暴力枚举然后统计一个关于距离的前缀和就好了。但是因为我一开始的脑子进水了,居然调了很久。

B — 数论你还会快速幂

题意:给出\(n\),\(p\),\(k\),范围都是\(10^{18}\),并且保证\(0 \leq n-p \leq 100\)。求\(\sum_{i=1}^{n}i^{k} \mod p\)

我是打表找规律,首先大于p的幂和不会超过100项所以选择直接暴力。那么转化成我们要求这么一个东西\(\sum_{i=1}^{p}i^{k} \mod p\)。那么当k为奇数的时候这部分一定是0.但是偶数的部分我不知道,所以选择打表,发现也是0。。。。当然,当k时p-1倍数的话,这一坨是p-1,根据费马小定理。。。所以说我们直接从p算到n求个快速幂就可以了,为什么要从p呢?因为会有k=0的情况,这时候\(p^{k} \mod p=1\)。机房几位大爷比我先发现这个规律,但是貌似就是因为这个坑,没我A的早。。。但是A了以后还是把我踩爆。。。

至于正解貌似是从原根角度证明的。。。我连原根是啥都不知道,贴个链接好了:链接

C — 图论你先敲完模板

题意:略。

和开火车的一道煞笔题一样的思想,就是随着距离增大增长是指数级的,这也就意味着当两个点距离过大的时候肯定分段比不分段优秀。。。所以\(n^2\)的dp就可以优化到\(nlogn\)

D — 最后你还是AK了

题意:略。

一开始以为是求一种分配方案让最长路径上的值最大,不会做。。。最后还剩半个小时才听闻原来是求sum最大。然后写完突然又告诉我比赛结束了。。。

那么每条边被经历的次数一定是他两个端点\(u\),\(v\)的子树大小中的最小值。所以我们可以先求出来每条边被经历了多少次,再考虑如何让路径和最大。那么自然是给经历次数最多的边次多的边依次加最大的变化,次大的变化这样的。。。。

所以就是dfs完成后,排序贪心。

E — 数据结构你干瞪眼啊

题意:给出一个\(n*m\)的矩阵,\(n*m<=100000\),每个值在\([0,255]\)的范围内。有\(q\)次操作。

(1)询问某个格子的值

(2) 询问某一行一段区间有多少种不同的值。

(3)某一行区间加一个数并且模256

(4)某一行区间翻转

比赛的时候看到了\(n*m<=100000\)的条件,但是因为下意识的想的是二维数据结构,或者什么东西套个分块之类的。。。觉得自己的码力根本没法写。。。。简直傻逼透顶。。。

其实直接当成区间操作就好了,然后splay随便做,维护一个256位的bitset的标记记录一下子树都有哪些值即可。如果没有区间翻转直接线段树就可以了。

 

“玲珑杯”ACM比赛 Round #18做题记录》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注