澳门新萄京娱乐场 / Blog / 科技成果 / 卖萌是没有用的,2012集训队答辩
科技成果 7

卖萌是没有用的,2012集训队答辩

谷歌(Google) 前段时期运行了第二届 Nexus S 解迷挑衅赛(Nexus S Challenge
贰),就算又把中华新大陆排除在较量之外,但要么不影响大家自娱自乐,
点这里查看官方规则

NOIP2009题解

A1339.
JZPLCM(顾昱洲)

 

 

时限:3.0s  
内部存款和储蓄器限制:25陆.0MB  

废话少说,直接起初解题吧。

T1:潜伏者

试题来源

 

难点大要:给出壹段密文和破译后的当众,一个假名对应八个密文字母,供给破译一段密文,倘若有争持或有未出现密文无法破译输出failed,不然输出明文。

  2013华夏国训队命题答辩

第1题谜面:

3154, 75757, 854, 2737, 37553, 15059, 6278, 4085, 3634, 2414, 46483

科技成果,是还是不是冷到了?或许是因为影响不可以,开题后很久又交给了一条提示:”start
with the prime factors and see where they take
you”。居然是求质因数!@#$%^&*

那就起来吧,315肆=2×1577=2×1九×8三,此时贰、1九、八3都是质数,即成功了质因数分解,就那样类推,能够将一切数都解开。

但类似 [2,19,83 ]
的东西怎么成为真的的谜面呢?就用加密的鼻祖凯撒加密法试试好了,把 A-Z
的假名拿来和前贰多少个质数一一对应的交替(二对A,三对B,伍对C……10一对Z),于是谜面就成了那般:

[a, h, w], [e, t, y], [a, d, r], [d, g, i], [g, o, o], [e,
l, l], [a, n, u], [c, h, n], [a, i, v], [a, g, t], [i, n,
o]

这一群字母又是何等意思呢?那2个”goo”是否提示到了啥?只要字母调度下地点就应时而生了确实的谜面:

what year did google launch navigation(Google 啥时推出了导航服务?)

于是乎谜底来了:

2009

思路:纯模拟题

难点讲述

其3题谜面:

科技成果 1

 

哈哈,那不就是填字游戏同样的字谜么?先解开再说:

科技成果 2

但怎么用这个词吗?注意到谜面包车型大巴颜色未有,这不便是谷歌那套“蓝红黄,中蓝红”配色嘛……

科技成果 3

于是大家就用那个配色规律在每一种谜底里挑选3个字母,举个例子:“Folks”的谜底PEOPLE,高粱红,对应了“谷歌(Google)”中的“G”,也便是“谷歌(Google)”的第2、第5个假名,对应回“PEOPLE”,就得到“P”,依此类推,大家就有了谜底:

科技成果 4

Viva!那几个词笔者太熟了,意思是“棱镜”,哼哼哼,晕了没?

 

  给定1长度为n的正整数类别a,有q次询问,每一遍询问一段距离内全体数的lcm(即最小公倍数)。由于答案大概非常的大,输出答案模1000000007。

第伍题谜面:

科技成果 5

http://goo.gl/Z0U4p renumber digits rub ink long hiatus big redskin damp heat calming moon third felon neutral pink technical flyer robs enemy sea honour saintly chef two cents old enchanter sparkle biz crocus fiord dusty brown ruby queen rich garcons sardine gland sans broker hated seaman not tensely gloved barker noted cavern evilest trooper scarlet esquire educators role manly beer carrot nubs thinks bigger hawthorn holler nocturnal howls diurnal gripes mad realtor gas alternate civil oratory orange press english carol tallest peahen rare lotus clan idol concerning torment darn heel

本条还真长,你不会真读了啊……

先来看上边的网址,这几个网址指向了一幅恶搞版的“世界客车互联网图”,那和最上边那些五颜六色的数字怎么能组成起来呢?坐过客车就理解,换乘站广泛会用各个线路标记色来代表——于是做个硬汉的猜忌:数字圈的配色实际上是对应换乘站,而数字即换乘站名的假名序号。

科技成果 6

翻开大图请点这里

譬如,第二个色圈,配色是粉、黄、灰,于是找到图中这多个颜色的换乘站:Berlin,取第两个字母N。依此类推,就赢得了两个色圈暗藏的单词:

LONDON

London?这又在暗中表示什么啊?其实,假若您对大不列颠及苏格兰联合王国具有领悟就能知道,London的大巴系统一分配外的很大,共有1二条路径和300多少个车站,连London地铁图都改成了音讯设计的标准。而此前的那幅“世界大巴网络图”就是1幅翻版的伦敦地铁图:

科技成果 7

如此那般多数、且无壹重复的站名(全表见
wiki页面
,共30五个)不正是绝好的字符加密素材么?这好比给本就生气Infiniti的Geek们打了一针鸡血。那就飞快来配对啊!那个指鹿为马的主张还真有人这样做了,当然,他用的是程序……

可怕的事追根究底发生了!程序相称的结果表示,那正是不错解题思路!简单讲,谜面中的每对词组都以London某大巴站名字母的重排列,唯1的两样是,出题人在每对词组中刻意隐去了1个字母……

举个例证:谜面第八组词“third
felon”对应“North田野先生s”车站,并隐去了最终的字母“s”,所以第七组取“S”,就那样类推落成43遍相称,并把字符串加上空格、标点,谜底发表:

Please send me a Nexus S, so Google goodies I can access!(送我台Nexus S尝点Google的甜头嘛~)

 

还真是肉麻又隐晦的一句话啊,那不正是撒娇卖萌吗,但那是不曾用的,同样把你推倒。

 

输入格式

T二:汉克son的意味题

  第二行,八个整数,n,
q,分别代表数列长度和询问个数。

标题大体:给出a0,a一,b0,b一求满意条件的x的个数;

  上边n行,每行一个整数,第i行的平头为ai
  上边q行,每行五个整数l,
r,表示掌握下标i在[l, r]范围内的ai的lcm。

                     条件:gcd(x,a0)=a1;x,b0最小公倍数为b1;

出口格式

思路:分解质因数,要是对于2个质因数y,a0含有a0c个y,a壹包括a壹c个y,b0含有b0c个y,b一饱含b1c个y。

  q行。对于每个询问,输出一行,表示对应的答案。

那便是说轻易得到,如若a0c<a一c,那么就无解;假设a0c=a1c,那么x至少含有a一c个y;借使a0c>a一c,那么x只大概包涵a一c个y。

样例输入

同理,要是b一c<b0c,那么就无解;若是b1c=b0c,那么x至多含有b1c个y;假诺b一c>b0c,那么x只可能带有b1c个y。

3 3
123
234
345
1 2
2 3
1 3

透过,能够求出对于每3个质数,x大概包括多少个它,并求出一共有稍许种采纳格局。然后依据乘法原理,将每三个质数的取舍方案数乘起来,就获得了答案。

样例输出

 ———————————————————-

9594
26910
1103310  

 20壹7.5.6填补题解:

数据范围

  明天又做了二回,然后对地点自个儿的做法壹脸懵逼,推测是事先就没看懂吧然后贴了题解???

n,q<10w,ai<=1e9。

  然后就各样焦虑,物色到了二个特级有道理的题解:

 

  能够表明gcd(x/a1,a0/a一)==一,鲜明要是不对等一,则gcd(x,a0)<a1;

那题这么神作者显著要放上来啊。

  然后得以证实gcd(b1/x,b1/b0)==1,鲜明如若不对等一,则lcm(x,b0)<b一;

先是5一Nod的数额是通过弱化的,并未那么强。

  这样的话,明显就能够枚举b1的享有因数,sqrt(b壹),加上gcd复杂度是logb一,所以单组数据复杂度是sqrt(b壹)*log2(b1).

对此5一Nod的多寡,大家得以用1种比较皮的格局艹过去。

 

有些数的LCM正是对每一个质数的指数取max。
对此过量sqrt(x)的质数,那几个指数最大是一。所以对于这一个数,大家只供给看清在那些区间内是还是不是出现过就能够了。那么些难点能够用莫队算法+桶实现。
对于小于等于sqrt(x)的质数,经过打表开掘那种质数只会有约四16个。大家能够把每五个数S[i]分解质因数后存进4二十个表里,每趟询问对那47个质数分别来二遍区间求最值。因为表定型后不涉及修改操作,能够行使ST表把单次询问下跌到O(壹)。
故此说那道题供给写八个程序。
莫队算法转移的复杂度是O(壹)的,该有的复杂度是O(n*sqrt(n))。
倍增算法预管理的复杂度是O(50*n*log(n))的,管理询问复杂度是O(50*n)的。
由于那题空间不是很足,要对每种小质数3个3个管理ST表,空间复杂度为O(n*log(n)+n*50)。

T叁:最优贸易

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

网站地图xml地图