2017年九月
« 十    
 12
3456789
10111213141516
17181920212223
24252627282930

最近所更新的↓

☆在这里搜索文章

Siroi edit by Tusik

歡迎

08/06/2014

 

由於 剛剛建立 維護者異常懶的緣故,文章比較少……

如果對此BLOG有何問題與建議,請聯繫我:

Email: wangzhpp@gmail.com

 

希望您能夠在這裡有所收穫,度過開心的時光!

分享我的一些实习经历

09/22/2017

AFA的日子已经接近一年了,在这一年之中许多难以入眠(修仙)的夜晚中,我一直在思考我从参加算法竞赛的生涯中所获得、失去的都有什么,以及我自身所欠缺的、不断致使我难以获得成功的属性究竟是什么。

尽管认为不会有人来看,但我还是想要写一些自己从那时以来的经历与思考。

 

 

因为的确没有人看,所以就写这么多了。

背離毒奶的路跡線

10/28/2015

TheLineZen

Line Zen,很不错的小游戏,可以锻炼精神集中的耐力,以及不是很可靠地测试自己的疲惫程度(?)

被Sw学长奶死了半个月,终于在他不(摸)在(鱼)的那天晚上超过300分了(。。

10.20題目龜速填坑

10/22/2015

题目链接:天下無敵金大爺的熱身題

私密比赛不给看(。题目会发上来的!

密碼是233333


 

POJ4028:GCD Guessing Game

似乎POJ的题面挂了,可以到CF的GYM上找到(。

将质因子分为乘积<=n的k组,贪心地使k最小,k即为答案。

证明大概就是,我们设ans(i)为n=i时的答案,不难证明 ans(n)<=ans(n/i)+pre[i];  i为质数i在其中的组数。


 

POJ1257:余数之和

题意:对于给定的nk,求\sum_{i=1}^{n}{k\ mod\ i}

 

考你做没做过数学题,根据(n/i)向下取整的性质,sqrt(n)分组出解。

\sum_{i=1}^{n}{k\ mod\ i}=\sum_{i=1}^{n}{k-i*\frac{k}{i}}

很显然,\frac{k}{i}只有\sqrt{k}个取值,因此我们便可以按照\frac{k}{i}来分组求和。


 

POJ2480:Longge's Problem

题意:求\sum_{i=1}^{n}gcd(i,n),(n<=2^{31})

 

首先显然原式可以化简为 \sum_{d|n}{d*\varphi(\frac{n}{d})}

我们就可以O(\sqrt{n})的复杂度枚举所有n的约数来计算惹。

还有一个小问题,就是对于很大的欧拉函数我们难以快速地计算出来。我的做法是小的phi筛出来,大的phi分解质因数来计算。(数据组数大概不是很多啦。。>_<就通过惹)。

一个比较标准的思路是,我们不难发现 \sum_{d|n}{d*\varphi(\frac{n}{d})}f(n)=ng(n)=\varphi(n)的狄利克雷卷积,而两个积性函数的狄利克雷卷积仍旧是积性函数。(关于狄利克雷卷积)

因此我们所求的\sum_{d|n}{d*\varphi(\frac{n}{d})}也就是一个积性函数,很容易每次以分解质因子的复杂度来计算它了。


SPOJ LAMSUM:

题意:求\sum_{i=1}^{n}LCM(i,n),(n<=10^{6}),共300000组询问。

 

先化简成我们比较熟悉的形式……\sum_{i=1}^{n}\frac{in}{gcd(i,n)}

交换求和次序得到    n*\sum_{d|n}\sum_{gcd(k,\frac{n}{d})=1}k

不难发现(\sum_{gcd(i,n)=1}i)=(\frac{n*\varphi(n)}{2})

因此原式可化简为   n*\sum_{d|n}\frac{d*\varphi(d)}{2}

窝们就又可以愉快地筛出答案惹!QQ图片20140806234821


SPOJ GCDEX:

题意:求\sum_{i=1}^{n}\sum_{j=i+1}^{n}gcd(i,j),(n<=10^{6}),共20000组询问。

 

我们先让这个式子在主观上变得好看一点 \sum_{i=1}^{n}\sum_{j=1}^{i-1}gcd(i,j)

那么实际上我们只需需要维护\sum_{i=1}^{n}gcd(i,n)的前缀和就好了。

显然我们发现……这个式子和我们刚刚做过的POJ2480是一样的,可以化简为\sum_{d|n}{d*\varphi(\frac{n}{d})}

只需要在筛法的时候顺便记录一下每个数最小的质因子出现过几次……即可O(n)的复杂度筛出来。

然后注意一下对于每个上限ngcd(n,n)是不应该被统计进去的,于是我们将每一个答案都减掉gcd(n,n),再统计一下前缀和,即可。


 

SPOJ PGCD:

题意:求对于所有质数p,\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=p]

 

方便起见,我们设n<=m.

一个显然的、先枚举质数(以下关于该题目的讨论中字母p均为质数)再做莫比乌斯反演的思路是将柿子(?)化简为\sum_{p}\sum_{d=1}^{\frac{n}{d}}\mu(d)\frac{n}{pd}\frac{m}{pd}

这样子。。我们每次询问的复杂度依赖于n以内质数的个数,在询问组数太多的时候会美酒药丸。

我们会很自然(大概)地想到要让讨厌的pd消失掉,不妨设s=pd

于是得到\sum_{s=1}^{n}\frac{n}{s}\frac{m}{s}\sum_{p|s}\mu(\frac{s}{p})

所以发现,我们算法的瓶颈就是对于每个S求f(s)=\sum_{p}\mu(\frac{s}{p})

略微撕烤一下\mu函数的性质,我们不难得到:
f(s*p') =\begin{cases}\mu(s), & \text{if $s\ mod\ p=0$} \\\mu(s)-f(s), & \text{others} \\\end{cases}

很容易线性晒出f(n),这道题目就解决啦w。


不过剩下的题稍微有些懒得更新~(

組隊訓練計劃試做Ver1.0

10/20/2015

10.20-10.24   解决作业,考试问题等……

 

10.25開始,每逢周日,每人挂10-15题(至少包含2道计算几何),在周六前完成,在下次挂题前给队友讲懂或基本讲懂。

 

偶爾大家都有空的時候組隊做套題(。。QQ图片20140904231750

 

目前分锅状态:

  • 局座:树巨结垢、图论、奇怪的搜索题。
  • Zhpp: 数论、DP、需要推倒式子的准备工作。
  • L+R: 构造题,背锅题(?)。

计算几何大家一起club_d53ed3b96d0a72bf4ccb182fbc9ed9ae

 

可能的改进方向:

  1. 分锅状态不完全或不合理
  2. 讲题时遇到困难或者别人不会的算法
  3. 组队三人一机训练次数不足。

To be continued...

2015 ACM/ICPC Asia Regional Shenyang Online题解占坑

09/21/2015

A:还没补(x1

B:广义斐波契数列找循环节。

C:树DP,对于每个节点寻找跨立过它的边。

D:对和(积)式做筛法。

E:交给局座了!(容斥维护矩形)

F:签到题!

G:数位DP。递推和记忆化搜索都可以。

H:没补(。。这个忘记x了。。

I:缩点后LCT维护桥的个数(联通性)

J:没补(x2

K:没补(x3

L:没补(哎呀我的妈呀。。

 

M:化简式子后发现,每一个人所占领的区域为它的质心对于其余所有质心连线的垂直平分线的半平面交。

一类五月病可行的治疗方案。(试行

04/04/2015

五月病(ごがつびょう)とは、新人社員や大学の新入生などに見られる、新しい環境に適応できないことに起因する精神的な症状の総称である。——Wikipedia.

五月病的成因与治疗方案一向是困扰RHMW研究者们的难题,目前唯一公认在临床试验中行之有效的早死早投胎的治疗方案由于其简单粗暴的性质而受到了多方压力被迫淡出公众视野,作者身为资深该病患者遭受多年荼毒,在逐渐恢复之余希望依靠自己的经验之谈为一种特定的五月病治疗引起新思路。

这里我们简单陈述一种“(破旧)”五月病的一种成因以及试行的治疗方案。

该种五月病的诱因既可能来自自己也可能来自于他人,时常发作于突然興奮する患者突然沈静化する患者之中。(如图1)

kanja

图1:部分患者发作时面部会出现巨大模糊化马赛克,疑似患者lu多的心境具象化表现。

发作前有较长潜伏期,具体时间段根据患者独处时间长度约在1~16天不等。

(注:本文的状态大多指精神状态而非生理状态。

然而潜伏期大多数患者并无异样,甚至在前几天会依然处于亢奋状态,因此许多人陷入了将其误解为突然发作的误区,为日后的治疗带来了诸多不便,同样,日之前也很不方便。

接下来,将以诱因作为依据,分别讨论此类五月病患者不同的治疗方案。

那么,

@接下来  。(……

 

Math(?) 如何在计算器按键失灵的情况下得到"2015"

02/22/2015

你有一个计算器你从来也不骑,有一天你发现它的键按不进去。

数字键和加减乘除全都用不了,还能打出二零一五真呀真神奇。


来源:QQ图片20150222153015Problem 4.

题意:一个屏幕显示"0"的计算器,它的所有数字键以及"+","-","*","/"按键全部失灵。

能用的按键只剩下  {x^2 , \sqrt{x} , x! , exp(e^x) , ln , sin , cos , tan , cot , sec , csc , arcsin , arccos , arctan}

如何操作才能使计算器屏幕显示出2015?

//提示和解答为防剧透都是白色的,而且目测解法不唯一>_<

提示:{\color{white}{cos(arctan(x))=\frac{1}{\sqrt{1+x^2}}}}
解答:

根据提示,我们不难发现,对于一个任意的数x,我们先执行:{\color{white}{\sqrt{x}}},随后执行cos(arctan()),现在我们得到了{\color{white}{\frac{1}{\sqrt{1+x}}}}.最后我们通过{\color{white}{ln,x^2,\sqrt{x},exp,x^2}}的操作得到1+x,由此操作2015次即可得到解。按照这个思路……我们可以通过三角函数不同组合构造出来的式子来做出许多种解法,如果有其余魔法思路的话希望留言讨论一下w。

UVA6284 Hyperdrome

12/16/2014

题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=568&page=show_problem&problem=4295

题目大意:给出长度为n(<=10^5)的字符串,问该字符串有多少个“通过交换该子串内字母位置可以形成回文字符串”的连续子串。。

因为很懒……一句话题解= =

“二进制压位+前缀和,每次XOR处理即可……”  考虑所求字符串的特性……嘛,就是这样啦(*/ω\*)

【奇怪的训练】Four Points

11/17/2014

题意描述:给定平面上四个点,求它的一个外接正方形。

 

解法:

稍有常识的人即可看出,

最上、最下的两个点做平行于X轴的线,

最左、最右的两个点做平行于Y轴的线,

这是一定可以构造出一个外接矩形的。

那么稍有常识的人便可看出,

假如我们构造出了一个w>h的矩形,

那么将四个点顺时针旋转90°(立起来),

就可以得到h>w的矩形。

那么问题来了,

在这个旋转过程中是否可以形成一个w=h的矩形,即我们需要的正方形呢?

答案是显而易见的。。

因此,我们在[0,π/2]区间内二分需要旋转的弧度,

然后判断形成的矩形是否是正方形即可。

 

 

-----------------------------反正也没人看我的博客,谁想做这道题加我qq来要链接好了= =

 

偏序集及Dilworth定理

08/26/2014

很炫酷的东西QQ图片20140826103745

首先我们要了解一下什么是偏序关系:

【注:“≤”在此中的意义为“偏序关系” 而非 “小于等于”,不过不难发现“小于等于”也是一种偏序关系。

设集合X为一个非空集,关系P(≤)为集合X上的一个二元关系,

若关系P满足:

①自反性:a≤a

②反对称性:若a≤b , b≤a , 则a=b。

③传递性 :若a≤b , b≤c , 则a≤c。

那么我们称P(≤)为在集合X上的 偏序关系   ,带有偏序关系的集合我们称为 偏序集  (如X)。

在偏序集中,若存在 a≤b 或者b≤a,那么我们称a与b是可比的。

在偏序集中的元素a,若对于所有与a可比的元素均有a≤b,则称a为偏序集中的极小元

 

举几个偏序关系的栗子:

①小于等于显然是偏序关系!

②整除关系显然也是偏序关系!

③集合间的子集关系是偏序关系!(`·ω·丿)

 

若偏序集X中的一个子集X1满足X1内所有元素都相互可比,那么我们称X1是X中的一条

反之,若子集X2中的所有元素都相互不可比,我们称X2是X的一条反链

 

定理①:对于偏序集(X,≤),若 r 为其最长链的长度,则集合X的最小反链划分为 r 。

其对偶定理即为 Dilworth定理

(定理②) 对于偏序集(X,≤),若 r 为其最长反链的长度,则集合X的最小链划分为 r 。

我们仅需证明定理①成立,对偶定理即成立。

定理①的证明:

 

首先证明r的必要性:

对于最长链中,任意的两个元素都是可比的,因此最长链的任意两个元素都不可以同时存在于一条反链中,因此r条反链是必要的。

其次证明r的充分性:

将集合X中所有的极小元组成集合A,每次剔除集合A,如此反复处理下去,必然每次剔除的集合与上次剔除的集合均有元素满足偏序关系。而当X被剔除至空集后,所有被剔除的集合即为最小链划分,我们设被剔除的集合的个数为k ,由于每个集合之间均有偏序关系的元素,而最长链的长度为r,因此k<=r。

至此,定理①证明完毕。

 

通过这些定理的转化,我们便可以解决或者证明一些奇♂怪的问题啦。

举个例子:

炒鸡经典的入门级DP 导弹拦截  的第二问:“集合X能最少划分为几组不上升子序列?”

按照朴素题意的算法,我们需要求最小路径覆盖。

但是不难看出,这是求一个偏序关系“x先于y出现,且x大于y”的最少链划分,

所以根据定理,我们可以发现这就是求“x先于y出现,且x大于y”的最长反链长度,

即为最长上升子序列的的长度。

因此我们可以以nlgn的复杂度求出答案。

 

更多例题:SPOJ 3196. Divisibility Relation

 

Older Posts