分类 - 公开的学术内容

solution 组合数学    2017-03-25 19:56:41    324    0    0

题目描述

给定 nm,求出所有顶点坐标满足 0x<n,0y<m 的格点三角形的面积和的两倍。答案模 1004535809 输出。

输入格式

一行两个整数 nm

输出格式

一行一个整数表示答案。

样例

样例输入 1

2 3

样例输出 1

24

样例输入 2

10 100

样例输出 2

218427047

样例输入 3

100 1000

样例输出 3

938425419

数据范围与提示

n3000,m109

题解

懒得做了,留坑,等有人催了再说

solution 数论    2017-03-25 19:47:20    509    0    0

题目描述

定义复数 a+bi 为整数 k 的约数,当且仅当 ab 为整数且存在整数 cd 满足 (a+bi)(c+di)=k,给定 n,求出 1n 的所有满足 a>0 的约数 a+bia 的和。答案模

solution 几何    2017-03-25 12:04:38    624    0    0

题目描述

有一天,小A的母亲对他家里的卫生状况非常不满意,他的房间里有非常多的苍蝇。在母亲的威逼利诱下,小A拿起了苍蝇拍去消灭家里的苍蝇。然而,小A以前从来没有亲手消灭过任何一只苍蝇,以至于在他拿起苍蝇拍的那一刻,他对苍蝇起了怜悯之心——他不想伤害任何一只苍蝇。现在,小 A 面前的窗户上有N只苍蝇,他想知道有多少种方式可以在他拿起苍蝇拍拍窗户的时候,不伤害任何一只苍蝇。

窗户可以看作是一个左下角位于坐标系原点的矩形,苍蝇拍可以看作是一个多边形。在小 A 向窗户挥苍蝇拍时,对应多边形的顶点必须位于坐标系的整点上,并且苍蝇拍所在位置不能超过窗户所在范围。一只苍蝇会被伤害当且仅当小 A 用苍蝇拍拍向窗户时,苍蝇位于苍蝇拍内部、边上或顶点上。

输入格式

第一行三个正整数Xp,YpN,分别表示窗户右上角的坐标和窗户上苍蝇的数量。
接下来 N行每行两个整数 XY,表示苍蝇在窗户上的位置。
接下来一行一个正整数 K,表示苍蝇拍的顶点数。
最后 K K 行每行两个正整数 Xi,Yi,表示苍蝇拍上的第 i个顶点。按顶点给出的顺序

solution DP    2017-03-23 21:28:28    696    0    0

题目描述

小 A 有 N 个正整数,紧接着,他打算依次在黑板上写下这 N 个数。对于每一个数,他可以决定将这个数写在当前数列的最左边或最右边。现在他想知道,他写下的数列的可能的最长严格上升子序列(可由不连续的元素组成)的长度是多少,同时他还想知道有多少种不同的最长的严格上升子序列。

两个子序列被认为是不同的,当且仅当:两个子序列属于两个不同的写序列的方案(两个写序列中有至少一步是不一样的)或两个子序列位于同一写序列方案的不同位置。

由于结果可能很大,所以小 A只需要知道最长严格上升子序列的方案数对 109+7 取模的结果。

输入格式

第一行一个整数 N
第二行 N 个正整数,表示小 A 写下的初始序列。

输出格式

输出一行两个整数,最长严格上升子序列的长度以及方案数模 109+7 后的结果。

样例

样例输入 1

2
1 1

样例输出 1

1 4

样例输入 2

4
2 1 3 4

样例输出 2

4 1

数据范围与提示

对于 30% 的数据, N20

solution 贪心    2017-03-23 19:51:38    325    0    0

题目描述

Mirko 是侏儒国的国王,Slavko 是精灵国的国王。最近,侏儒国和精灵国进行了一场战争。Slavko 率领着 N 个最强壮的精灵(编号从 1N)进攻侏儒国,而侏儒国的城堡也由 N 个侏儒(按顺时针方向从 1N 编号并形成环形)进行防守。

Mirko 为每一个精灵分配了一个侏儒对手 Ai,表示编号为 i的精灵要与编号为Ai的侏儒进行对决。然而,不久后他就发现,这个方案不能保证每一个侏儒都与唯一一个精灵进行对决。

经过协商,Mirko 和 Slavko 最终定下了如下规则:

Slavko 会按他安排的顺序依次派遣他的精灵进入城堡。一个精灵进入城堡时,上一个进入的精灵必须已经找到了就座的位置并坐下。
编号为 k 的精灵进入城堡时,会首先靠近编号为Ak

solution 分块    2017-03-23 15:09:02    527    0    1

题目描述

给你一个 n 个点的有根树, 1 为根,带边权,有 m 次操作。

  • x 的子树中第 k 小的深度的值,如果子树中没有k 个点则输出 1
  • xx 父亲的边权加上 k

保证每次操作 2 的 k 以及原树的边权小于等于一个数 len

如果操作 2 中 x1,那么视为将 x 的基础深度加上了 k

输入格式

第一行三个数 nmlen 。之后 n1 行每行两个数表示 2n 每个点的父亲编号,以及他们到父亲的边权。
之后 m 行每行三个数 opt

solution 网络流    2017-03-22 21:11:15    341    0    0

题目描述

人类智慧之神 zhangzj 最近有点胖,所以要减肥,他买了 N 种减肥药,发现每种减肥药使用了若干种药材,总共正好有 N 种不同的药材。

经过他的人脑实验,他发现如果他吃下去了 K0KN)种减肥药,而这 K 种减肥药使用的药材并集大小也为 K ,这 K 种才会有效果,否则无效。
i 种减肥药在产生效果的时候会使 zhangzj 的体重增加 Pi斤,显然 Pi 可以小于 0

他想知道,一次吃药最好情况下体重变化量是多少,当然可以一种药也不吃,此时体重不变。 由于某些奥妙重重的情况,我们可以让这 N种减肥药每一种对应一个其使用的药材,且

solution matrix-tree    2017-03-22 19:34:22    525    0    1

题目描述

俗话说,跳蚤国王下江南,火车司机出秦川,共价大爷游长沙。
但是这道题可能跟上面几句话没什么关系。 共价爷想构造一棵 N 个点的有根树,其中 1 号点是根。
显然的,对于一棵有根树,我们可以定义每个点的深度为,这个点到根的路径上点的个数(包括端点),也就是说, 1 号点深度为 1
共价爷希望,深度为奇数的点的个数,刚好为 K 个。
他想知道有多少棵不同的满足条件的有根树,你只需要输出答案对 P 取模的结果。

我们认为两棵树不同,当且仅当存在一对点 (i,j) ,满足 ij 在一棵树中有边相连,而在另一棵树中没有边相连。

输入格式

一行三个整数,依次为 NK

数据结构    2017-03-20 07:24:47    183    0    0

%%%whx

我们称LCT上是轻边而且正常树剖结果中也是轻边的边为轻轻边
LCT上是轻边而且正常树剖中是重边的边为轻重边

单次Access的重轻切换次数等于该路径上轻轻边轻重边的和。
轻轻边的复杂度是有保证的,不超过logn条。

我们采用势能分析轻重边的总量变。

每次一条轻重边会变成重重边,然而重重边只有在Access到相邻这个点上的时候才能被变成轻重边。所以我们每次把轻轻边重轻边的时候支付多余的一次时间费用。由于轻轻边是有保证的,所以重轻边也是有保证的。

于是总共的切换次数不超过nlogn

有点绕,不过还能看。。。。(别打我

继续去问武爷如何把logn卡满,然后武爷给了一个特别妙的主意——

建一颗满二叉树,每次插入时从根往下沿着虚边走,然后就可以了。

训练计划    2017-03-19 21:10:42    195    0    0

知耻而后勇,既然挂了就重新制定训练计划让自己更强。

Problems

  1. 代码能力太弱一定要改,考场吃亏太大了。确实近一个月没怎么写代码,手速和准确率都严重下降。
  2. 加强体育锻炼,5个小时脑子确实发热严重,最后一小时扛不住。
  3. 熟练Linux,开始环境不适应很亏。

Solutions:

  1. cf必须日常打,还需要代码量大的比赛。开始定时做16年各省省选。
  2. 三月前完成TC665-700 midiumhard,限时,超时弃疗。
  3. 更换系统为Linux,熟练使用vim
  4. 适当锻炼(或许可以找个妹子陪跑步)

训练计划2.11-2.28

SRM666-700 已完成 11/35

  • SDOI 2016 day1
  • SDOI 2016 day2
  • SDOI 2016 day3
  • SDOI 2016 day4
  • HNOI 2016 day1
  • HNOI 2016 day2
  • HAOI 2016 day1
  • HAOI 2016 day2

3.2

(看来是我玩手机玩多了)

SRM666-700 已完成 11/35

  • SDOI 2016 day1
  • SDOI 2016 day2
  • SDOI 2016 day3
  • SDOI 2016 day4
  • HNOI 2016 day1
  • HNOI 2016 day2
  • HAOI 2016 day1
  • HAOI 2016 day2

2017.03.04

SRM666-700 已完成 17/35

2017.03.13

SRM666-700 已完成 35/35


所以接下来开什么坑呢?

2017.03.15

  • TJOI 2016 day1
  • TJOI 2016 day2
  • SCOI 2016 day1
  • SCOI 2016 day2
  • CQOI 2016 day1
  • CQOI 2016 day2
  • ZJOI 2016 day1
  • ZJOI 2016 day2
  • JLOI 2016 day1
  • JLOI 2016 day2
  • JSOI 2016

update 3.17

  • TJOI 2016 day1
  • TJOI 2016 day2
  • SCOI 2016 day1
  • SC