2018年八月
« 三    
 1234
567891011
12131415161718
19202122232425
262728293031  

☆在这里搜索文章

Siroi edit by Tusik

分享我的一些实习经历

09/22/2017

AFA的日子已经接近一年了,在这一年之中许多难以入眠(修仙)的夜晚中,我一直在思考我从参加算法竞赛的生涯中所获得、失去的都有什么,以及我自身所欠缺的、不断致使我难以获得成功的一些属性究竟是什么。在Google Beijing实习的三个月里,我的host在和我的1:1meeting中,除了update project的进度之外,也时常地和我聊一些利用身边的资源提升自己的途径。丰富的人生经验解疑了我之前的许多困惑,再回忆起我先前一年在京东实习的经历,我想很有必要写一篇文章整理一下我这一年以来的经历与收获

(最近好忙啊,先咕咕咕了。。)

背離毒奶的路跡線

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道计算几何),在周六前完成,在下次挂题前给队友讲懂或基本讲懂。

 

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

 

目前分锅状态:

  • 局座:树巨结垢、图论、奇怪的搜索题。
  • 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:化简式子后发现,每一个人所占领的区域为它的质心对于其余所有质心连线的垂直平分线的半平面交。

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

02/22/2015

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

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


来源:QQ图片20150222153015似乎是某年阿三联赛的Problem 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次即可得到解。按照这个思路……我们可以通过三角函数不同组合构造出来的式子来做出许多种解法。。

HDU4779 Tower Defense

02/08/2015

题意:nxm的网格(1<=n,m<=200),有p个重塔、q个轻塔。可以两个重塔放在同一行(列),也可以一个重塔或一个轻塔单独放在一行(列),问有多少种合法的摆放方案。

 

思路:

考虑到只有重塔是特殊的,

我们可以枚举“存在i行有2个重塔,存在j列有两个重塔。”

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处理即可……”  考虑所求字符串的特性……

Older Posts