CCPC长春游记

今年下半年赛季第一场比赛,我们去了长春。

Day1:

被强行起了个大早,大约9点出的门,然而比起主席天没亮就出门还是太晚[话说他真的睡了吗],先是打车去了酒店,然后大巴去了机场,中间耽误了好久,大巴上看到主席在鄂尔多斯~~烤羊腿~~转机的画面……我还是继续睡觉吧……

到了机场已经是接近中午了,由于起得太早没来得及吃早餐(主席:喵~),一行人在机场吃50一份的快餐,可能是由于没糍早餐的报应,lz和mg都糍完了我的那份还在Loading,出门就涱了一波RP。

一路在飞机上睡觉,中途在通辽转机发现主席一伙人已经坐电车~~出去玩了~~找酒店,话说通辽机场阳光好充裕啊去晒日光浴……我还是睡觉吧。。

到了长春才发现自己带的旅行箱完全没用,本来以为零下几十度结果连零都没下1,到旅店时已经很晚了。本来想在下榻的酒店随便叫份外卖,结果被mg拉出去吃烤肉(为什么是烤肉),中间mg策划我们一行人去看电影(嘛反正我平常是不去这种资本主义横行的地方~~还不是因为穷~~),中间主席跑过来说要一起看,结果为了看电影,我点的最后一道菜只好打包带走

achieve

大晚上看了最晚一场电影看到半夜,话说明天还起得来吗?

Day2:

没有任何悬念的错过了酒店早餐,和主席它们跑去报道,从南边进去以后看到了一片建筑工地差点以为走错地方,向右拐进入一个小门,话说吉大好厉害好大好豪华好奢侈好享受好度假村,校园里居然有网吧游泳池商厦台球馆电影院美食城汉堡王,一行人打算在汉堡王刷关送的饭票,尽管门口有写让用实际上并不让用,然而等知道了这点的时候队都排完了……なるほど ,那个告示是故意引人入店的》

下午测试赛,发现我们的校徽被人换掉了-((‵□′))- 。我先看了A,结果由于没看出successive 是连续的意思,结果没做出来……,mg开启手算第二题模式,最后仔细一看发现不是Catalan数吗……实力1A,lz徒手找规律,过掉一到本来好像要gauss期望dp的题,我分类讨论一波,强行过掉C。我们队成功开启·真·无双做题模式,1人1T1A,结果榜单上没有我们,仔细一看交错号了(GG),交到了中科大(喵)去了

然后我们去了伪满皇宫,由于关门进不去,去了旁边的抗日战争主题博物馆,中间大家走散了,出来的时候,主席骗mg说我还没出来,结果mg已经出来了在出口的树下,,敢情被坑的是我……话说都快比赛了这么掉RP没问题吗~

晚上一行人去万达玩密室逃脱,路上被主席一路tc,我们玩得是星际迷航主题,开局是转盘语音容错率低差评,中途逃生舱把写得英文看成请误触碰(我不是故意的……),中间把密码器当工作人员使用的了(自带跳过重要线索光环),后面不明意义的圆盘需要跳回前几个房间,没注意到不做评价,解方程没有使用Hints好评,最后那个Hash表沦落到用Hint(不好意思说自己是竞赛党了),最后结局开船意义不明(强行凑谜题个数)

Day3:

早上起来随便喝了点豆浆上战场,开局看标题,mg默默给题目打上送分,进阶,不可做题的标签2

,开局mg开始手速题,迅速过了Triangle,忘了n=1时\(/gcd\)稍微在 Fraction 下欠了一个罚时,我开局看 Binary Indexed Tree不会做3,改看其它题,中途mg开kmp的Sequence I,由于白书kmp板子有点小问题稍微发了点时间,途中我给出了Harmonic Value Description的构造解做法,一共就几行,稍微挽回了一点罚时。

中途我把Ugly Problem 的解构造出来了,由于要用高精,mg让我上Java,然后mg和lz讨论其他题去了,由于之前想当然漏掉几种特判,再加上太久没用java差点交文件时把类名写错,不辛坑了一波队友(我对不起你们),将近1h才过掉这题,此时只剩下一个多小时了。

继续看题发现Sequence II 之前好像在哪里做过,好开心这不是主席树么(主席:喵~)。二话不说敲了10min板子,结果不小心写了动态开节点的线段树的板子(考得这么残念罪魁祸首),最终mg强行主席树手写成功(中途由于节点数开小了re了一发),然后最后剩15min实在写不了题,进入喝茶聊天给其它队制造压力mode。

考完后弦歌队刚飞机先遛了,留下我们和隔壁西电成员讨论题目解法,话说这次考这么惨4好伤心啊……败北航队dalao,%%众dalao,这次SJTU出的题目质量不错,但最后没有讲题差评。

晚上去了之前玩密室的万达,要么怎么说人家吉大地理位置好。接下来mg带我们队玩了一波街机厅,然后又去打了台球,中途去吃了日本寿司,mg点的太多结果又剩了一堆没吃完。晚上被mg带去网吧~~玩守望~~学习,话说网吧机子配置好好难怪mg经常去网吧。

Day4:

半夜本来想交Uber, 被mg说动走回酒店,结果走了0.5h发现南门校门锁了(bad end),没办法原路返回(0.5 h) ,结果实在受不了打车回去,打车地点离网吧不远sad story. 回到酒店,叫了pizza,结果左等右等pizza就是不来,mg由于手被冻僵了就先去睡了,我等着等着睡着了(最好3点半送到匹萨的时候我意识模糊的接了电话,让它放在楼下,话说直到最后我都没见到pizza)。

虽然和mg立志一定要吃到早餐,然而由于睡前实力忘了闹钟,结果睡到了中午12点5(mg表示中途起来叫我,我翻面继续睡,然后他也继续睡了……)。 为了弥补遗憾,我们一行人去了东北菜馆,点了一桌子菜,结果菜上来才发现是8个人的量,只好打包带走……

本来还打算试试电车,结果由于时间紧,又只好叫了Uber,就这样离开了长春还真是充满了遗憾呢……不过我还是先补完作业再说吧。

后记:主席又打算和妹子出去玩我就不写在正文里了。


  1. 长春当时的气温在7,8度左右 
  2. 结果好像都猜错了%%% 
  3. 正解是数位dp,统计2个数lcp中1的个数 
  4. 结果我们一个亿Ag,弦歌打铁(主席:我以后拒绝去这种5题不保铜的赛区)。 
  5. 本来计划好了去长春电影制片厂 

BZOJ 水题50乱做

[TOC] 1051: [HAOI2006]受欢迎的牛
显然受欢迎的牛一定在一个强连通分量里,缩点后看看有没有出度为0的点,如果有多个那么无解
4690: Never Wait for Weights
加权并查集
1269: [AHOI2006]文本编辑器editor
rope的使用方法http://blog.csdn.net/iamzky/article/details/38348653
1031: [JSOI2007]字符加密Cipher
后缀数组裸题
3238: [Ahoi2013]差异
后缀数组裸题
1041: [HAOI2008]圆上的整点
数学题,求(a^2+b^2=c^2)(c已知),a,b的正整数解个数
http://blog.csdn.net/csyzcyj/article/details/10044629
1014: [JSOI2008]火星人prefix
splay+hash+二分
1069: [SCOI2007]最大土地面积
平面土地上有N个点,选择其中的四个点,求围成的多边形最大面积。
n<=2000
求凸包,O(n^2)枚举对角线,两侧的点有决策单调性,用一个指针O(1)求
1090: [SCOI2003]字符串折叠
区间dp
3998: [TJOI2015]弦论
SAM


1066: [SCOI2007]蜥蜴
网络流,拆点
1015: [JSOI2008]星球大战starwar
倒着并查集
4443: [Scoi2015]小凸玩矩阵
网络流,动态加边/二分都行
1067: [SCOI2007]降雨量
线段树/RMQ都行,要分类讨论
1042: [HAOI2008]硬币购物
我们先算出不考虑限制时的方案数\(f_s\),如果一个硬币超出限制,那么至少要使用\(d_i+1\)次,此时答案为\(f_{s-c_i*(d_i+1)}\),我们可以用容斥定理解决问题
2298: [HAOI2011]problem a
考虑一个人的话:“有ai个人分数比我高,bi个人分数比我低”等价于“我的排名在\([L,R]\)区间中,这个区间中人的成绩相同“,然后就可以变成线段覆盖问题,贪心即可。
4653: [Noi2016]区间
将区间按长度排序,枚举最长区间长度,显然最短区间长度满足单调性,只需要确认“m个区间共同包含至少一个位置”,用线段树维护最大值即可。
1192: [HNOI2006]鬼谷子的钱袋
k个钱袋最多能凑出\(2^k-1\)的所有钱数
1800: [Ahoi2009]fly 飞行棋
暴力。
1856: [Scoi2010]字符串
回顾卡特兰数的推导过程,发现\(ans=C(n+m,n)-C(n+m,n+1)\)


1801: [Ahoi2009]chess 中国象棋
炮的攻击范围为,横行竖行,跳过一个棋子打一个,距离不限
故原题为求\(n*m\)的矩阵中同行同列只能放至多2个炮的方案数
\(f_{i,j,k}\)表示到第i行,j列放了一个,k列放了2个的方案数
4641: 基因改造
在允许置换的情况下kmp是可以的,hash应该也行
我觉得我应该改改KMP的模板了。。
4602: [Sdoi2016]齿轮
dfs走一遍
3926: [Zjoi2015]诸神眷顾的幻想乡
由于叶子节点不超过20个,所以可以用SAM。
注意拷贝叶子节点时只拷贝c个节点不然会TLE.
4627: [BeiJing2016]回转寿司
线段树裸题
4619: [Wf2016]Swap Space
贪心,证明看得不是很懂
http://www.cnblogs.com/gangding/p/5705400.html
1016: [JSOI2008]最小生成树计数
回忆Kruskal的建立方法,显然每个长度后图的连通性是一定的,具有相同权值的边不会超过10条,dfs就行。
1061: [Noi2008]志愿者招募
经典的问题
https://www.byvoid.com/blog/noi-2008-employee/
3295: [Cqoi2011]动态逆序对
cdq,三维偏序(白书原题)
3996: [TJOI2015]线性代数
经过一堆变形我们发现\(ans=\sum_{i=1}^{n}\sum_{j=1}^{n} B_{i,j}a_i a_j-\sum_{i=1}^nC_ia_i\)
我们把这转化为最大权闭合子图最小割
答案=所有点正权值之和-最小割
3875: [Ahoi2014]骑士游戏
令f_i为杀死i的最小代价,那么有\(f_i=min(K_i,\sum_v{f_{v_i}})\)
状态之前的转移有环,我们考虑《SPFA算法的优化及应用》中提到的算法


3997: [TJOI2015]组合数学
安利Dilworth定理:http://blog.csdn.net/popoqqq/article/details/45171469
4448: [Scoi2015]情报传递
询问离线,树链剖分
1070: [SCOI2007]修车
费用流经典模型
http://www.cnblogs.com/Sky-Grey/p/3862019.html
4418: [Shoi2013]扇形面积并
扫描线,用树状数组+二分判断
1406: [AHOI2007]密码箱
\(x^2=1 \mod n\)等价于\(n|(x-1)(x+1)\)然后暴力枚举因子就行
1038: [ZJOI2008]瞭望塔
半平面交,把分段点(包括边界)取出来
2618: [Cqoi2006]凸多边形
拆成一堆直线半平面交
4517: [Sdoi2016]排列计数
错排公式\(D(0)=1,D(1)=0,D(i)=(i-1)(D(i-1)+D(i-2))\)
有个求一段阶乘的逆元的小技巧

4516: [Sdoi2016]生成魔咒
1.裸sam+map
2.求出反序后字符串的SA,每次添加一个字符串,考虑其对height前后字符串的影响
4514: [Sdoi2016]数字配对
我们发现两个数能配对,则它们分解质因子后的数的个数奇偶性不同,我们可以建出二分图,费用流乱搞


2243: [SDOI2011]染色
树链刨分,把情况转成子节点到父节点的两条链会比较好讨论
3531: [Sdoi2014]旅行
树链剖分,拆成n棵树。记得动态开点减少结点数
3631: [JLOI2014]松鼠的新家
对于加法操作差分,将对链的操作转换为点始末节点的操作,避免后效性,在子节点\(s_i\)+1表示从它开始到根节点均+1,最后统计一遍就行
4034: [HAOI2015]T2
树链剖分时,可用dfs序剖分

3626: [LNOI2014]LCA
操作离线,然后

后加每个点的时候是把从这个点到根的路径的点权全部+1
然后查询就是查询某个点到根的路径的点权和

1191: [HNOI2006]超级英雄Hero
二分图匹配
1143: [CTSC2008]祭祀river
用floyd求传递闭包,建图,原题求最长反链=最小链覆盖
证明:http://www.bubuko.com/infodetail-664202.html
路径不能相交的最小路径覆盖可以用二分图做
路径可以相交的最小路径覆盖(也就是最小链覆盖)可以用floyd求传递闭包建图,转成前面那个用二分图做
2227: [Zjoi2011]看电影(movie)
公式题:ans=(k+1)^(n-1)*(k-n+1)/k^n
神一般的证明:http://www.cnblogs.com/devilpi/articles/3817691.html
1179: [Apio2009]Atm
tarjen缩点+跑一遍dij
4419: [Shoi2013]发微博
用户没有传递性(SB读错题),只有直接关系能看到信息
差分后得到,\(ans_i=t2-t1+t3-t4+...+t_n-t_{n-1}\)暴力维护

CoderCup 2015 游记

:-O 我果然还是没忍住写了这篇游记

以下内容均为黑历史,大家忘掉即可。

话说2015年暑假,在经历过延后1月放假,和提早一周开学集训(请允许我做个悲伤の表情)后,突然从王冠教练那里得到了这份邀请函。

本着不去白不去的念头(喂!!),我给Prime队报上了名(Flag起)

然后出发前一周突然得知王伟戌缓考马哲没法来!!(事后才知道它没参加考试老师却给了73的事

反正最后把神犇mg拉过来了,一行人浩浩荡荡地杀向北京。

Day -1:

明明和hobo说好提前准备行李,收拾的,可是那天晚上他没把箱子拿来(出发前只打算拿一个箱子登机),结果不得不明天早起拿箱子。

Day 1:

6:00 AM 我做什么虐大早上起来收拾行李各种吵醒同学伤不起。

到了临时据点(hobo的土豪思远社)之后,又被拉回去叫请假条(我真的不想吵醒同学),回来以后简单的吃了M记

艰难的从西安一路辗转北京然后是地铁,到旅馆后发现mg走错地方了,只好在旅馆等他。

然而hobo去人大泡妹子去了,于是我顺便跟去见最强德语系Acmer CCR, 估计是我认识的Oier中专业最猎奇的。。然而人赢

去了以后看到CCR在外语系招生处搭台顺带 和妹子聊天,聊到了xjtu, 之后回去放东西,一边参观人大,一边看到了妹子i,j,k,l,n 这个人赢

之后去食堂吃饭,据说人大20多处食堂,CCR一年未能尝遍一半,想象xjtu满打满算才2个(康桥,梧桐)不禁以泪洗面..

CCR请客,带我去新专修的食堂,他点了份咖喱鸡,我要了份鱼丸(说这个绝对不是tucaoXJTU) ,看来他在人大混得不错。。。和2妹子组队+CF红名(红名改革后失去该成就)人赢

晚上遇见mg,大家一起刷BZOJ水题。。

Day 2:

今天只是去看场地,反正最后只有景琦去。。

我和mg一觉睡到中午,午餐外卖日料,之后水题一下午。。

晚上的时候让景琦带插板回来*(最后他忘了),得知他这一天主要在泡妹子(换了一个)

Day 3:

一大早去了场地,mg拿出了他心爱的HKB神级键盘,由于我不懂VIM只能觉得这个键盘小巧又漂亮。。

开始练习赛,反正未能抢到一血。。

然后我看场地它们出去上厕所成功遇到岛娘(我错过了),之后我也被赶出去了。。

 正赛开始。,。

mg开A题抢一血,中间我们过了水题H,G,然后mg线段树 1小时左右轻松过A

mg发现I题是模板高斯消元开始手速场,然而由于用了景琦提供的错误的sjtu模板不幸被坑,,后来终于AC  2小时

中间我试图过C ,然而看错题, 试图过B 然而OutputLimit exceed

于是我们在接下来卡题模式开启,,我和mg轮流做C,反正最后dp没过。。

没过。。。 

没过。。

(柏拉图说:重要的事情说3遍)

由于在2:30以后基本是我在敲代码,,,我获得【 1个黑锅】

于是就这么结束了,

Cu牌。。

下午,它们领我们去颁奖时都不好意思去,,,(后来才知道不去取消奖项,详见北大,这样就没有路费了的说)

最后mg回宾馆,jq又去报妹子(怎么我身边全是人赢)

我悲伤的在颁奖现场画圈圈。。一个两个。。三个四个。。

值得一提的是当时现场抽了10+次奖,奖品从iwatch到奇奇怪怪手机不等,,考虑到实际到场人数,不得不说获奖概率极高。。

(我旁边有人抽到奖,有人被抽到多次(生日攻击) ) 。。。然而好像还是没我什么事的样子。。

最后啃完了现场送的M记以后拍照走人。。我站在后面应该不会被拍进去??

晚上回到宿舍和mg它们聊天。。

mg和hobo 就 高端烧耳机 》》高端烧键盘?? hobo高端烧外语游戏(我觉得这个还是有希望的。。)mg高端烧各种音游。。(经过尝试得出自己好像没希望)。。

大家都是人赢啊。。人赢啊。。人赢啊。。

我的Ipad的充电线不见了666666

由于第二天mg要去四川成都看女友(都说凡是认识我的都人赢的反向Flag啊。。)

大晚上晕晕昏昏沉沉的睡着了(真”没心没肺)

Day 4:

一大早去了欢乐谷决定放松心情,,决定拍几张照片放微博以试签到)

(然而由于种种原因手机没电了。。我wtf连个照都拍不了装逼失败,,

为了惩罚自己做了2次过山车。。。(要排很长的队) 话说为什么我一点都不害怕(都说没心没肺。。)

Day 5:

今天因为要打长春的·区域赛~网络赛 所以呆在房间。。

然而由于各种原因 景琦跑出去看妹子了(据说没换。。存疑。。)

最后只有我留在房间打,做了1T以后 不得不下去退房。,。。12:00在宾馆门口提着行李箱风中凌乱。。。

都 是 景琦 害得拉。。 (最后那场区域赛网络赛我xjtu一个名额都没有。。这锅他得背)

于是索性去五棵松会见高中时的同桌+死党 王永鑫。。

他高考后跑到HK刷了一堆经验点以后,成功混入中财大。。现在大一。。

我告诉了大二的悲伤生活。。他默默地莞尔一笑。。

中午我们在五棵松附近不知名快餐店见面,,他请了我一份鸡腿饭+豆浆(说好的全聚德呢),我们在五棵松拍照留念发微信。。如果景琦的VPN给力的话我就发到FB上。。

然后我们去钟楼玩耍,,因为搞错地点被Taxi撂在了离钟楼1km Manhattan距离的:钟楼地铁站

话说这钟楼风格的M记怎么和福州三坊七巷那家那么像。。。怎么又是M记

本来想去不过因为门票太贵没去

最后去逛了逛钟楼附近有名的电玩一条街。。

之后王永鑫和他另外2个同学走了

我一边啃冰棍,一边看路上车追尾的时候

被jq一个电话叫去机场,,,让我歇会儿会死你个人赢。。

最后到机场搞到很晚才走。。

本来想拿行程单结果硬是要用寄的,,不知道寄了多久。。

到学校8,9点了发现自己居然来得及去洗洗澡。。

真是充(dao)实(mei)的1 week

全篇完

Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] 题解

A.

There is a polyline going through points (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – ... - (2kx, 0) – (2kx + x, x) – ....

We know that the polyline passes through the point (a, b). Find minimum positive value x such that it is true or determine that there is no such x.

题解:所有线的斜率均为\(k=\pm1\)

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i< =n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x< <1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define eps (1e-10) #define F (100000007) typedef long long ll; typedef double ld; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} ld a,b; int main() { // freopen("A.in","r",stdin); // freopen(".out","w",stdout); cin>>a>>b;
if (a

B."Or" Game

已知n个数,执行k次操作:将任意一个数乘x,求最大or和

(1 ≤ n ≤ 200 000, 1 ≤ k ≤ 10, 2 ≤ x ≤ 8).

解法:由于 \(x\geqslant2\) 我们应该将位数最大的那个1挪到尽可能高位,因此,应反复乘同一个数

用线段树预处理区间or和,然后枚举执行操作的数即可

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i< =n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x< <1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (200000+10) typedef long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} ll a[MAXN],x; int n,k; class SegmentTree { ll minv[MAXN*4]; int n; public: SegmentTree(){MEM(minv) } SegmentTree(int _n):n(_n){ MEM(minv) } void mem(int _n) { n=_n; MEM(minv) } void build(int x,int L,int R) { int M=(L+R)>>1;
if (L==R) {minv[x]=a[L];return;}
else
{
if (L< =M) build(Lson,L,M); if (Mql=ql,this->qr=qr;
if (ql>qr) return 0;
return _query_min(1,1,n);
}

ll _query_min(int x,int L,int R)
{
if (ql< =L&&R<=qr) return minv[x]; ll ans=0,M=(L+R)>>1;
if (ql< =M) ans|=_query_min(Lson,L,M); if (M< qr) ans|=_query_min(Rson,M+1,R); return ans; } }S; int main() { // freopen("B.in","r",stdin); // freopen(".out","w",stdout); cin>>n>>k>>x;
For(i,n) scanf("%I64d",&a[i]);
sort(a+1,a+1+n);

S.mem(n);
S.build(1,1,n);

ll e=0;
For(i,n)
{
ll ans=0;
ans|=S.query_min(1,i-1);
ans|=S.query_min(i+1,n);

ll t=a[i];
For(i,k) t*=x;
ans|=t;
e=max(e,ans);
}
cout<

 C .已知序列a1, a2, ..., an (|ai| ≤ 10 000,1 ≤ n ≤ 200 000). 求x,

使序列a1 - x, a2 - x, ..., an - 的子段和的绝对值最小.

解法:二分x,如果最大子段和与最小子段和平均值\(\geqslant 0\),则说明x太大.

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i< =n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x< <1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define eps (1e-8) #define MAXN (200000+10) typedef long long ll; ll mul(ll a,ll b){return (a*b)%F;} ll add(ll a,ll b){return (a+b)%F;} ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;} void upd(ll &a,ll b){a=(a%F+b%F)%F;} int n; double a[MAXN]; double ans; bool check(double x) { double mins=a[1]-x,maxs=a[1]-x; double t1=0,t2=0; For(i,n) { t1=max(t1+a[i]-x,a[i]-x); maxs=max(maxs,t1); t2=min(t2+a[i]-x,a[i]-x); mins=min(mins,t2); } ans=maxs; return (mins+maxs)/2 <0; } int main() { // freopen("c.in","r",stdin); // freopen(".out","w",stdout); cin>>n;
For(i,n) scanf("%lf",&a[i]);

double l=-2000000000,r=2000000000;
int k=150;
while (k--)
{
double m=(l+r)/2;
if (check(m)) r=m;
else l=m;
}
check((l+r)/2);
printf("%.7lf\n",ans);
return 0;
}

有关PhpMyAdmin,MySQL的学习记录

SELECT * FROM `wp_options` WHERE 1

SELECT `option_id`, `option_name`, `option_value`, `autoload` FROM `wp_options` WHERE 1
INSERT INTO `wp_options`( `option_name`, `option_value`, `autoload`) VALUES (1,2,3)
UPDATE `wp_options` SET `option_id`=[value-1],`option_name`=[value-2],`option_value`=[value-3],`autoload`=[value-4] WHERE 1
UPDATE `wp_options` SET `option_value`=[value-3],`autoload`=[value-4] WHERE 1
WHERE 后为条件
SELECT * FROM `wp_options` WHERE 1
MySQL 关系型数据库
Office Access 管理数据库

主键:
用户 [主:用户ID]
邮箱 [主:邮箱ID]
无主键的表 [用户ID,邮箱ID]

用户 [主:用户ID] ->无主键的表 [用户ID]
邮箱 [主:邮箱ID] ->无主键的表 [邮箱ID]
M方法 :直接把数据库实例化成对象
D方法 :特殊的函数,特殊时间调用
Php : Mysqli

马克飞象 in maxiang.info 语法简要

#x     ##x        ###x        1-3级标题

1.(空格)a

2.(空格)b   有序列表

* a

* b 无序列表

[link](www.baidu.com)   link

``` php

echo 'a';

```    

代码

hellp ` echo 'a' `   单行代码

马克飞象扩展:

1.数学表达式

块:

$$ a+b =1 $$   

行内:

$ a+b = \alpha \beta \delta $

$ \sigma {a^b} ^c _d $

$ \frac{a}{b} \int{adx} $

表格

|aaaa|bbbbb|ccccc|

|:-|:-:|---:|                    左对齐 居中 右对齐 PS这行必须加

|a|b|c|

|a|b|c|

**粗体**

*斜体*

脚注[^demo] 

 

 

部分关于如何在php中使用正则表达式的研究

php:

preg_match ($preg ,$str,$match); 是否匹配到

preg_match_all ($preg ,$str,$match); 匹配数量 $match可以不加

var_dump ( $match );

$preg='\a\'; a为正则表达式

\w 一个字符 \d 一个数字 \s空格回车

\W \D \S 前面取补集

[A-Z] 区间

[^A-Z] 区间取补集

\w|\d |或运算

^x 强制匹配行首

x$ 强制匹配行尾 (最多匹配1次)

\d{4} 匹配连续出现4次 (‘1234’,‘2222’)

\d(i,j) 匹配连续出现i到j次

\d? 0<=k<=1 <-匹配次数 \d+ k>=1

\d* k>=0

\\1 表示本次匹配中第一个出现的()中的内容

*? 匹配尽可能短

ACM/ICPC 2014(西安) 游记

我10.25号和陈景琦,王伟戌组队参加了ACM ICPC 西安站。

 -1 Day:

    之前去向辅导员请假,免了美(wu)好(liao)的新生养成。

Friday:

    晚上被王伟戌抓去食堂天井聊天了,,话说头一次知道康桥食堂中间那一块叫作天井,,,到了以后王伟戌学长找我们训话,大致交代了一下注意事项,后来由与我接了通电话,要去取箱子提前解散。。(王伟戌:你还定了箱子?我:储物箱。。。o+0)

1 Day: (Day 0 呢? 我就这么写怎么地)

    大早上起了个大早,结果我TNT集合时间推迟2h,改成了11点,我何苦起那么早为哪般。。。接下来继续收拾行李(?)本来想带三国杀,后来想起福建省队专业Flag被迫打消念头。。。蒟蒻94蒟蒻。虽然时间推迟了还是10点55出门,差点被吐槽。。到了那里以后开始找人,原来它们都在校门口呢我还在国旗附近转悠(其实是行李拿多了跑得太慢我会说?TNT跑步还得练 PS:我的1km怎么办...)反正有惊无险(哪惊了) 地到了。王伟戌吐槽我带2个包,说绝对不用到,不带都行(被他说中了,不听学长言是不对的·)本以为包量大车(想多了),结果打的去西工大(车费啊...)到了以后好像有点迟(午餐快没le,废话11点出的门有午餐见鬼),但是还是比其他队早到(什么Flag?好像我们后走的)不管怎么说我们这个队就在报道处死等。。饿成平面了都。。让你不带午餐)后来它们姗姗来迟居然去食堂吃过了。。(职业被队友卖只此一家别无分号)最后在王冠大大的带领下完成了报道。。

   赶紧去食堂把,有点残羹冷炙也是好的,,,巨神们保佑。。结果居然还真有(好评,这又是啥Flag)西工大食堂就是大,难怪叫西工大(喂)事后我们看了一场盛大的开幕式,外面的大型显示屏就那么滚着宣传短片。。然后进了会场,,还是那一段,,西工大ACM宣传片+华为广告植入也是醉了,,

    听了(??,???,????)的发音以后知道了XXX顺利开幕(多懒。。要你管具体内容早忘了)测试热身被虐赛下午开始,,连热身赛都没AK是要闹哪样。。。后面做的香港人一口地道粤语丝毫听不懂对面还坐着清华。。据说比赛还在aqiyi全程直播,,欢迎观看由sg2p带来的年度大片《蒟蒻是怎样卖萌的》(标题好眼熟??被发现了吗)

   晚上跟着大巴去了旅店(明明是豪华总统级别墅),先去登记,然后到处找房间,,,据说为了讨吉利没有7相关的房号。。好评ACM吉利专用。。老板(娘)你用心了。。到了房间以后发现这栋有2层还在一楼附近找到了室内游泳池(可能是大号温泉)是要闹哪样,,不过看环境好像弃置了多年我也没敢用。,,233333

   晚上陈景琦发动了被动技能小米wifi为我们带来了网络不过好像距离太远。。我们住的房间在2层,, 1层靠近楼梯的位置有一台电脑可以上网(土豪套间)游泳池旁边有娱乐室,里面有能自动洗牌跟换蓝绿的色背面的麻将桌,,多么的土豪啊,我们几个人围在旁边不会打麻将玩洗牌多次(乡巴佬),天黑了,陈景琦打算和我打红色警戒,,一晚上最终没有建出局域网。。大Flag,,陈景琦有一台Ipad MINI没有设密码之后躺床上玩。

Day 2:

   第一天的作死导致了第二天早上起不来,22333第一次闹钟迷迷糊糊的让景琦关了闹钟以后差点睡过头但还是错过了酒店的自助早餐,醒来时知道他们已近走了,,充充收拾行李,结果在外面随便买了面包(景琦买了奥利奥)结果等车车半天不来,,看到有队员优先在旁边早点铺吃早餐(谁说迟的)反正排了N久的队等了半天上了车,默默啃面包,,,景琦索性饿着(戒了?)反正到了那边以后还早就充满幸福地去食堂早餐了,,然后进入会场,,,掏出了厚厚的《C++ Primer》好书,用烂的《牛津英汉词典》(学习如此刻苦还不赶紧拜拜攒RP,,,算了都是1队的·)眼前是一台配置尚可的电脑有Linux系统,,,一个神秘(跪)的棕色文件袋(谍战啊。。)时间开始默默地开始看题,,,

第一题水题,,,陈景琦开始敲代码,,,稍微检测了一下水了1A,没抢到'首杀'(废话都是手速犇这怎么比)然后默默地看题,,,B题代码题(复杂模拟过)。。这个时候最后一题王伟戌有了想法,,,好像有不对。。。我提出先去敲对拍准了。。题目好像搞错了,再改,,OK了。(之后我一直做电脑那)对拍一下哪里有问题,,再改一下,,,王伟戌给我讲了个证明没怎么听懂反正再改,,再敲,,最终发现某一列少1其他都对,然后改了以后不知怎么的AC了好奇怪。。???(A了就行管那么多,,事后没给代码。,。彻底不知道当时怎么A的了)截至目前毫无罚时好开心。。其实是Flag。。。后面就是了

看了半天,没思路。。2个队友给出了F题做法,,开始愉快的敲,,发现哪里不对,,看看题,,,结果看错了,,(闹哪样),赶紧该算法,,发现黑书上集合公式能用,,,算了一半发现取模要用除法(逆元上场)这什么坑爹题啊,要写逆元就要写exgcd,,没准备模板现场推,,王伟戌完成那一步代码(中国好学长)然后写好了,交,,T(><)不应该啊,,,仔细看看,,确实是慢,,,把逆元注释掉就秒了,,再仔细看看,,负数取模用while(a<0) a+=p;是要闹哪样,,,赶紧改了,,发现P写错了。。再改,,

终于提交了,居然不出结果?等半天,期间陈景琦没按捺住又交了1次,,事后证明完全不需要。,(没赛场经验),然后我们去看I英语题,,翻译出来,,写,,没时间了(事后证明确实没时间),然后F出结果了,wa,,醉了,赶紧改,,发现是由于边界问题??试了几个数据以后终于A了,,这么多罚时怎么见人。。A完就剩10min了得了啥也干不成了,不像OI能检查检查,,最终大家愉快肯汉堡火腿,,我中间还去了趟WC。。

事后在主持人倒计时10,9,。。1.比赛结束,,据说有在比赛最后1s提交AC的,,(HGH死不冥目。。详见APIO游记)

反正最后大家没事干了大家各种和气球合影,,我们是3个对面是一堆,,后面是一堆,,蒟蒻没人权,,事后讨论中我们发现那题The Promblem that make  you happy 我提出的从结果倒推居然是对的(可惜没写。。啪飞,,废话没时间了谁写)

之后开始了闭幕式,其实就是大家挨个上去做广告,有华为,还有上海互娱?反正看了一堆广告。。互娱发传单我还填了的说。。。然后就是喜闻乐见的成绩开榜环节,,我们F题是最后做的,所以有升了1回,,当然也就1回因为没做其他题。。最后居然弄了个Cu..聊胜于无。

之后我上去领奖了。。景琦帮令一个同去的队领奖(丢不起人先走了)。。。反正我们就get 了2Cu(弱校的悲哀)话说我们的教练王冠居然还上去颁奖了真是意想不到(说这种话没问题吗。。。作死节奏)

之后回去的路上我们决定做项目。。。是的,,大巴回来以后我们去打的打不到用滴滴打车。。结果最终用走的。。锻炼身体(是该练了)之后在陈景琦的强烈要求下去了M记(说好的锻炼ne),,CJQ一人要了2汉堡。。反正在一顿McDonald's后计划成型了当晚建群

后记:由于苹果电脑的(?)问题&期末考好像暂时停工了。。。要抓紧了,不然会批不到办公室,然后没有场地训练。。然后明年继续Cu。。。(立Flag是不对的、啊啊啊啊-1经验加持)