2017/9/22~2017/9/23考试总结

2017-9-22
T1
排序贪心裸题。。考试时心慌。。没有认真写代码,数组开小了一半。RE了一半的点。。
T2
解方程。
选树上的每一条边,根据边两边的点,列方程,求出相对大小。再根据根节点的值解方程。解出所有的a值。
T3
卡特兰数或者打表找规律
当时没想到要找公式
写了四个DP水了45分
组合数学找规律这方面还需要加强


2017-9-23
T1
矩阵快速幂,考试的时候想到了,但觉得要T就没有写。
结果是1维矩阵快速幂,O(mod^2*m)的复杂度,可以跑过。
题目也很迷,讲了一大堆原根的内容,结果这道题跟原根有什么关系?
T2
先推一下式子,再通过带权并查集优化。
当时只推了一下式子,没有写并查集,而且题目所说的非负整数没有看到,一直以为样例是错的。。。
当然,出题人坑,本题数据是错的,标程也是错的。。
T3
水题,模拟一下就好。
读入了两次x1,光荣报零。。。

BZOJ3944 杜教筛

(被owenowl要求加上的内容)flx 教我杜教筛,虽然他没做这道题。

传送门,戳这里

Problem

Description

题目

Input

一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个 非负整数N,代表一组询问

Output

一共T行,每行两个用空格分隔的数ans1,ans2

Sample

Input

Output

Solution

杜教筛裸题。

下面是我学杜教筛的一点经验,和大家分享一下。
如果您已经精通杜教筛,请跳过下面的内容,直接看注意事项。

如果您还不会莫比乌斯反演,请先学习反演再看本文。否则,可能一头雾水。

一般求Phi函数和mu函数都用线性筛,可以在O(n)的时间内求出1~n的所有phi值和mu值。下面是线性筛的代码,主要思想就是筛质数,然后根据phi和mu的积性函数性质筛后面的数。

Markdown炸了。。没法打数学公式。。

但是对于n很大求前缀和的情况(比如本题),O(n)的复杂度就不够了。这个时候就需要一种新的方法————杜教筛。

设h = f ⊗ g,设f的前缀和为S,而h的前缀和易求,那么可以用杜教筛。经过推导,可以得到:
杜教筛公式

首先考虑对μ函数的前缀和(欧拉函数同理):
构造一个g(i)=1!那么,有:

M(x)为mu[x]的前缀和:

求phi函数的时候,如何构造g(x)留给读者自行思考。

杜教筛关键在于构造g函数与f函数进行卷积,再通过杜教筛的公式递归求值。(可以是另一个杜教筛)
有几个注意事项:

1、首先,在用杜教筛之前,先用线性筛把开始较小的一些数(1~n^(2/3))的phi和mu给筛出来,再调用杜教筛,这样可以优化一下复杂度。

2、在用杜教筛枚举i求phi(x/i)时,分段枚举,对于一段x/i相同的i的区间只枚举一次,再乘以这一段的大小即可。否则可能会T掉

3、对于线性筛筛出来的值,要用数组存,不要用map,否则会多一个log,很可能T掉;

Code bzoj 3944

附上AC代码,前几十行写了读入优化,可以跳过。
本题AC需要靠运气,或者您去学洲阁筛吧。

IObuff fread读入优化模板

话不多说,直接上代码吧(自带O3优化)

调用的时候gi(x)就是读入x;可以读long long

2017/9/17 总结

奇袭

©党星宇

Problem

Description:

由于各种原因,桐人现在被困在Under World(以下简称UW)中,而UW马上
要迎来最终的压力测试——魔界入侵。 唯一一个神一般存在的Administrator被消灭了,靠原本的整合骑士的力量
是远远不够的。所以爱丽丝动员了UW全体人民,与整合骑士一起抗击魔族。 在UW的驻地可以隐约看见魔族军队的大本营。整合骑士们打算在魔族入侵前
发动一次奇袭,袭击魔族大本营! 为了降低风险,爱丽丝找到了你,一名优秀斥候,希望你能在奇袭前对魔族
大本营进行侦查,并计算出袭击的难度。 经过侦查,你绘制出了魔族大本营的地图,然后发现,魔族大本营是一个N
×N的网格图,一共有N支军队驻扎在一些网格中(不会有两只军队驻扎在一起)。 在大本营中,每有一个k×k(1≤k≤N)的子网格图包含恰好k支军队,我们袭
击的难度就会增加1点。 现在请你根据绘制出的地图,告诉爱丽丝这次的袭击行动难度有多大。

Input

第一行,一个正整数N,表示网格图的大小以及军队数量。
接下来N行,每行两个整数,Xi,Yi,表示第i支军队的坐标。 保证每一行和每一列都恰有一只军队,即每一个Xi和每一个Yi都是不一样
的。

Output

一行,一个整数表示袭击的难度。

Solution

显然,题目可化简为:给定N个数的一个排列,问这个序列中有多少个子区间的数恰好是连续的。
进一步可以化为:有多少种情况使得,相邻的k个数中最大值和最小值的差小于等于k-1。
大致有两种解法,一种是分治,一种是线段树。
这里主要讲一下分治的解法。
考虑分治,对于当前分治区间[L,R],记区间中点为mid。当前区间的答案就是Ans[L..mid]+Ans[mid+1..R]+跨过中点的合法区间数,然后就分为两种情况了:
1.最小值和最大值在同侧。
2.最小值和最大值在异侧。
下面只考虑最值同在左,和最小值在左,最大值在右的情况。其余两种是对称的。
对于最值同在左侧的情况,我们枚举左边界在哪,然后可以计算出右边界的位置,在判断是否合法,统计答案。时间复杂度:O(N).
对于最小值在左侧,最大值在右侧的情况,如果一个区间满足我们所要求的关系的话,就一定有:
移项可得
然后可以用单调栈+桶来完成这个任务。时间复杂度:O(N).
如果加一些黑科技可以大大减少代码量,但是复杂度会多一个log
总的时间复杂度:O(NlogN)/O(NlogN^2)
简单提一下,线段树解法的思路大致也是维护一个单调栈,然后进行区间修改和查询,统计答案。
时间复杂度:O(NlogN).

Code