2016年八月
« 十    
 123456
78910111213
14151617181920
21222324252627
28293031  

最近所更新的↓

☆在这里搜索文章

Siroi edit by Tusik

歡迎來到咱的小站ヽ(✿゚▽゚)ノ

08/06/2014
00:00/00:00

嘗試在置頂的文章設置了音樂播放器【

由於剛剛建立的緣故,文章比較少……

無論閣下是來查找題解或是看在下的吐槽打發時間都是十分歡迎的~☆。

如果對於網站排版有什麼建議,請聯繫我:

Email: wangzhpp@gmail.com

QQ: 446079414

 

希望諸位能夠在這裡度過開心的時光!

京子prpr

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。


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

組隊訓練計劃試做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:化简式子后发现,每一个人所占领的区域为它的质心对于其余所有质心连线的垂直平分线的半平面交。

安利一款游戏~Eternal Senia~

07/04/2015

公式站:http://senia.ftp.cc/

TE
「我也…最喜歡姐姐了……」——永恆的塞妮亞


(病娇?)少女为了追赶上姐姐的背影,
重新拾起(大宝剑)利刃,踏入永恒之塔去寻找姐姐的故事。(结果发现姐姐你丫原来也是病娇呀!

“一款任何人都可以轻松体验的ARPG”   ——作者言

迷茫与不安的少女,心中怀着对姐姐强烈的情感,在寻找姐姐的路途中不断地成长……
CG
攀爬的越来越远,少女不断地回忆起和姐姐的往事……
对姐姐的感情愈来地强烈……不仅仅是依赖与爱慕,对于失去姐姐的恐惧与担忧也满满地占据了少女的内心。

然而最终在塔顶等待着少女的却是(……x并不剧透

游戏流程比较短,大概只有3-5个小时。
满收集率是比较容易达成的,不过要注意一下第二大关的三个回廊(玩到那里就知道我说的是啥了)。
除了力量回廊意外,智慧与勇气回廊都只能进入一次。
如果想要达成满收集率的话,在进入那里的时候需要格外小心不要遗漏了宝箱……不然就只能在最后Load一下重新玩一遍啦。。

不过收集率和最终结局并没有什么关系(。

故事共含有三个结局,其中作为True End的END3很明显地暗示了游戏应当还是会有续篇的。

值得一提的是,从剧本到RM的脚本都是作者独立完成的。(大胆断言作者一定很喜欢百合的小姐姐!
正式版的立绘则是外包的,
BGM虽是收集而来,不过可以感觉得到其选用十分用心。
无论是攻击的效果音,还是每个场景、每个剧情的背景BGM,在情感的表达上都是完美地切合于剧本的。
然而不难看得出,在剧本的文本上还是欠缺了火候,操作手感也由于RM引擎而受到了极大的限制。。。。

与其说是ARPG,不如说是加入了战斗与收集要素的微型绘本。

总之作为一个流程很短的休闲向的独立制作游戏,游戏性与剧本都是值得尝试的程度,
虽然称不上是上等佳作,但是比较让人期待续集 (只是想看姐♀妹之情啦。。

http://steamcommunity.com/app/351640/#scrollTop=0 ;现在在steam上可以免费下载,公式站里也有相关信息。

https://www.facebook.com/seniafans  官方脸书中含有Gift Code:1215
通关END3后解锁的特典房间内有各个人物与怪物的背景以及官方吐槽(……

休闲放松时可以稍微玩一玩wwww
啊顺便一提有英文版本,可以稍微拿来练习一下英语(。。

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

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。

辭舊迎新!

02/18/2015

QQ图片20150219001047

时间是有魔力的呢!

每一年的这个时候,都会万分期待——今年都会发生什么呢,自己又会成(退)长(步)一些嘛?……

下定决心的这两年来,自己所收获的与所失去的如今都历历在目,

「我也终于到了可以闭着眼睛品味一整天十年前回忆的年纪了呢!」。。

总而言之,新的一年也请各位多多指教啦!

(笨手笨脚的总会麻烦大家呢= =

己未,おはよう!

48768800_p0

【图片来自p站,画作id=48768800,画师id=1107369。

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