diff options
Diffstat (limited to 'blog/post/2017-05-08.html')
| -rw-r--r-- | blog/post/2017-05-08.html | 407 |
1 files changed, 407 insertions, 0 deletions
diff --git a/blog/post/2017-05-08.html b/blog/post/2017-05-08.html new file mode 100644 index 0000000..0725132 --- /dev/null +++ b/blog/post/2017-05-08.html @@ -0,0 +1,407 @@ +<html><head> +<meta charset="utf-8"> +<meta name="viewport" content="width=device-width,initial-scale=1"> +<meta name="theme-color" content="#000000"> +<title>Chrisoft::Blog</title> +<script type="text/javascript" src="/panel.js"></script> +<script type="text/javascript" src="/blog/footnoter.js"></script> +<script type="text/javascript" src="/blog/aes-js.js"></script> +<script type="text/javascript" src="/blog/scrypt.js"></script> +<script type="text/javascript" src="/blog/sha256.js"></script> +<script type="text/javascript" src="/blog/decryptor.js"></script> +<link rel="stylesheet" type="text/css" href="/common.css"> +<link rel="stylesheet" type="text/css" href="/panel.css"> +<link rel="stylesheet" type="text/css" href="/theme0a.css" id="theme0a"> +<link rel="stylesheet" type="text/css" href="/theme0b.css" id="theme0b"> +<link rel="stylesheet" type="text/css" href="/theme1a.css" id="theme1a"> +<link rel="stylesheet" type="text/css" href="/theme1b.css" id="theme1b"> +<link rel="stylesheet" type="text/css" href="/theme2a.css" id="theme2a"> +<link rel="stylesheet" type="text/css" href="/theme2b.css" id="theme2b"> +<link rel="stylesheet" type="text/css" href="/theme3a.css" id="theme3a"> +<link rel="stylesheet" type="text/css" href="/theme3b.css" id="theme3b"> +<link rel="stylesheet" type="text/css" href="/blog/blogext.css"> +<script> +function ol() +{ + window.onresize=function() + { + if(window.innerWidth<768) + setupevents(); + else unsetevents(); + } + window.onresize(); + _decryptonload(); +} +function loadTheme(){ + var thm=document.cookie.replace(new RegExp("(?:(?:^|.*;\\s*)thm\\s*\\=\\s*([^;]*).*$)|^.*$"),"$1"); + if(thm.length<2||'0123z'.indexOf(thm[0])==-1||'abz'.indexOf(thm[1])==-1)thm='zz'; + var ent=""; + var d=new Date(); + if(thm[0]=='z') + { + var m=d.getMonth()+1; + if(m>=3&&m<6)thm='0'+thm[1]; + else if(m>=6&&m<9)thm='1'+thm[1]; + else if(m>=9&&m<12)thm='2'+thm[1]; + else thm='3'+thm[1]; + } + if(thm[1]=='z') + {if(d.getHours()>=18||d.getHours()<6)thm=thm[0]+'b';else thm=thm[0]+'a';} + ent=`theme${thm}`; + var R=new RegExp('theme[0-4][ab]'); + for(var i=0;i<document.styleSheets.length;++i) + { + if(R.exec(document.styleSheets[i].ownerNode.id)!==null&&document.styleSheets[i].ownerNode.id!=ent) + document.styleSheets[i].disabled=true; + else document.styleSheets[i].disabled=false; + } + var thmcolor=""; + switch(thm[0]) + { + case '0':thmcolor=thm[1]=='a'?'#f59dda':'#2f0933';break; + case '1':thmcolor=thm[1]=='a'?'#9df59d':'#090933';break; + case '2':thmcolor=thm[1]=='a'?'#edb47b':'#1f1205';break; + case '3':thmcolor=thm[1]=='a'?'#a0cdfa':'#051933';break; + } + document.querySelector("meta[name=theme-color]").setAttribute('content',thmcolor); +} +loadTheme(); +</script> +</head> +<body onload="ol()" style="overflow-x:hidden;"> + <div id="panel" class="TText"> + <ul id="panellist"> + <li><a href="/"><h1>Chrisoft</h1></a></li> + <li><a href="/blog"><h2>Blog</h2></a></li> + <li><a href="#"><h3 id="title">2017省赛流水帐</h3></a></li> + <li><span>Tags</span> + <ul id="tagslist"> + <li><a href="/blog/list/contest/">contest</a></li><li><a href="/blog/list/acmicpc/">acmicpc</a></li></ul> + </li> + <li id="tocouter"> + <span>Table of Contents</span> + <ul id="tocroot"> + <li><a class="toctarg" href="#tocanch0">「一句话题解」和其他</a></li></ul> + </li> + <li style="margin-left:-0.5em"><a id="prevp" href="2017-04-11.html">Prev post</a></li> + <li style="margin-left:-0.5em"><a id="nextp" href="2017-06-09.html">Next post</a></li> + </ul> + </div> + <div id="content"> + <h2 id="titleh" class="TText" style="font-wight:normal;">2017省赛流水帐</h2> + <div id="datetags" class="TText" style="margin-bottom:1em;">2017-05-08<br>#contest #acmicpc</div> + <hr><div id="article" class="TText"> +<article> +<script async="" src="//cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML" charset="utf-8"></script> +提要： +<ul> + <li><s>虽然又双叒丢了冠军但是大概是大学打的最刺激的一场比赛</s>（单从比赛本身来讲）</li> + <li><s>到底是7个赞助商辣鸡还是主办方太抠</s></li> + <li><s>裁判组垃圾</s></li> + <li><s>我太辣鸡，还是队友new bee</s></li> + <li>为Pz默哀</li> +</ul> +<p> +对于我这种五一假期早早就翘了OS课实验跑回家拒绝训练的咸鱼来说，好像根本没把这种级别的比赛当回事 +<s>（原因自然是因为我有队友的大腿可抱啦）</s>。所以赛前的一切事务也没怎么上心…… +包括<enlarged>起队名</enlarged>这种「重要事务」。因为某种所谓的「传统」， +辣鸡专科学校的队伍在省赛的时候总想用队名搞事情， +<a id="n1" href="#note1" class="note">[1]</a> +征集搞事所用「系列」时我随手发了个「宇宙××」系列，然后就莫名其妙得票最高了。 +可是某个可恶的宇宙××，竟然违背汹涌的民意搞「暗箱操作」。于是我们被钦定了这么一个队名…… +</p> +<div style="text-align:center;"> + <img width="40%" src="//filestorage.chrisoft.org/blog/img/csc.png" decoding="async"> +</div> +<p> +嗯这是我们实验室的某个真·linguist在比赛结束后偷偷告诉我的。二？<s>所以#2的命运应该是从这时确定的……</s> +</p> +<p>后来几人为了抗议队名钦定发生了下图中的事件……</p> +<div style="text-align:center;"> + <img width="40%" src="//filestorage.chrisoft.org/blog/img/20170508_144329.jpg" decoding="async"> + <br> + <reduced>图中所示为宇宙××的机位……</reduced> +</div> +<p> +好吧下面开始进入正题……坐着辣鸡专科学校的校车颠了5个多小时到了青岛，然后发现司机不知道路…… +后来历尽曲折，顺着某条羊肠小道准备接近目的地的时候却发现需要爬一个我们的辣鸡校车爬不上去的坡…… +于是就被逐下车了。 +</p> +<p> +青岛的气候不知道比济南高到那里去了（虽然午间太阳下当然还是晒）。 +办入住手续的时候看到了大概是跟他的gf在一起的Pz。想跟他说几句话的时候这家伙却说要上厕所然后走开了。 +嗯……大概是嫌我太弱不要我了。然后就开过来一辆客货两用车，后备箱掀开一看，里面居然满满的都是盒饭， +也就是我们的午饭……主办方印象分-- 当然原谅色选手服之类的事情就不用说了。网上都说烂了。<s>我再帮他说一遍， +我等于……我也等于……我也有责任吧？</s> +</p> +<p> +正午时分终于进了入住的房间，感觉环境还不错。<s>就是电视太辣鸡了，啥都没有的安卓系统+只有模拟信号。</s> +然而我们却没有时间享受一下床的温暖，因为<enlarged>12:40就要集合去参加开幕式和热身赛</enlarged>？！？ +而且房间只有一把椅子，所以我只能看着先抢走椅子的队友兼室友宇宙××吃盒饭…… +然后他就连续不断地吃到了十二点半……于是我不得不缩在床边用一种奇怪的姿势吃盒饭。。。还好最后没有出事。 +</p> +<p> +开幕式上讲的东西都是老生常谈，当然除了一个浪潮某领导所说的「青岛离山东太远」之外。 +<s>可以看出这个家伙肯定是青岛直辖的坚定支持者。</s>热身赛则是三个中文大水题。1h不到AK后开始乱搞。 +测了测机器性能发现i5-6600竟然比不上i7-6600U……然后发现用的是对skylake超不友好的4.4版本的kernel。 +赛场布局十分紧凑，各种用料也是相当节省（这当然不是夸主办方的话）。 +键盘也是十分古老的布局，用宇宙××的话来讲「1/4的时间在用来删除打错的字符」……然而最后还是只能认栽。 +弃疗之后准备离场，却被告知不可离场。于是开始寻找有没有什么可以玩的东西，然后就发现了扫雷。 +结果一局都没玩完就被通知可以走了，也是相当的尴尬。 +</p> +<p> +晚上回去之后以为官方提供的晚饭也是辣鸡盒饭，所以我们队三人果断点了外卖。 +后来发现虽然官方晚餐实际上并不是盒饭，但也是转一圈下来就没什么可吃的东西了的那种。 +后来的时间就变得十分无聊。宇宙××看着电视上播放的一部叫做《产科医生》的电视剧入迷，我则在……不好， +因为当时太困所以什么都想不起来了……后来发生的事情就是躺在床上一闭眼就丧失了对外界的感知…… +</p> +<p> +关于比赛过程，请见下方的『「一句话题解」与其他』段。 +</p> +<p> +闭幕式，三大段广告之后开始揭榜。主办方将4:3的内容伸长到一块分辨率超低的竖长条形屏幕上， +他们这是生怕有人能看清吗……揭榜主持人是令人吃惊的不专业 +<a id="n2" href="#note2" class="note">[2]</a>， +滚榜程序也是错误百出（乱来的颜色等等）。 +</p> +<p> +最后因为61分钟的用时被SKD-1864踩，rank 2。Pz则比较惨。作为老同学我表示心情还是十分复杂的。 +当然了，到了区域赛难度的比赛，如果我们还是现在这个水平，他肯定还是可以随意虐爆我们。 +</p> +<p> +还有我真是太辣鸡了所有签到题都要错几次（ +</p> +<h2 id="tocanch0" class="tvis">「一句话题解」和其他</h2> +<p> +正如你看到的这里是一句话题解区域其实这里不仅包含题解还包含一句话题目描述和解题时的心路历程之类题目出场顺序按照解题顺序排列 +</p> +<ul> +<li> + Y: + <p class="nospace"> + <span>问键盘上某个字母键的左边或右边是什么键。</span><br> + <span>当我看到宇宙××坐在键盘前写下<code>#include<map></code>的一刻我就知道大事不好了</span> + <span>因为我已经隐约看到了屏幕上即将出现的类似<code>m['Q']='W';m['W']='E';</code>之类的语句</span> + <span>于是果断抢走机位用不到10行秒掉了这道题。</span> + </p> +</li> +<li> + Z: + <p class="nospace"> + <span>给定两个字符串判断第二个是否可能为由第一个交换两个不同位置的元素得来。</span><br> + <span>因为字符串长度1000所以打算冒个险试试STL瞎搞然后就TLE了后来用聪明的方法重写了一遍AC</span> + <span>聪明的方法是计算两个字符串有多少个位置字符不同若为2个则一定可</span> + <span>若为0个且有元素在串中出现超过一次则也可</span> + <span>因为题目只要求交换的元素所处位置不同并未要求交换的元素不同</span> + <span>其他情况则不可。</span> + </p> +</li> +<li> + X: + <p class="nospace"> + <span>佳佳的魔法药水原题。</span><br> + <span>首先更正一下这题大概是某古代OI网站上的一次模拟赛题目</span> + <span>然后就是宇宙××说这道题他已经做烂了所以就让他再施展一次吧</span> + <span>其实还不就是个最短路</span> + <span>当年写树形DP写到炸。</span> + </p> +</li> +<li> + I: + <p class="nospace"> + <span>求fib(x)%2的值。</span><br> + <span>若x%3不为0则为1否则为0</span> + <span>虽然x可以有1000位但是被3整除的数的规律应该是小学知识吧</span> + <span>然后我就因为把<code>while(~scanf())</code>写成<code>while(scanf())</code></span> + <span>结果TLE了一发。</span> + </p> +</li> +<li> + F: + <p class="nospace"> + <span>对于给定abc问以下命题是否成立对于任意x若a*x^2+b*x+c=0则x是整数。</span><br> + <span>一眼看上去是初中数学对吧</span> + <span>但是它其实是高中数学因为题目中并没有限定x是实数</span> + <span>虽然我在写第一版代码的时候还只有初中知识水平但是WA了数发之后瞬间具有了高中知识水平</span> + <span>到最后发现其实我连小学文化都没有因为我以为a=b=c=0时x可以取任何数于是我就认为任何数等于任何整数</span> + <span>改正之后发现仍然WA于是不得不认为出题人没有高中文化水平改掉了Δ<0的特判</span> + <span>事实证明出题人就是没有高中文化水平。</span> + </p> +</li> +<li> + G: + <p class="nospace"> + <span>给定nm求sum(i^m%(10^?+7),1,n)。</span><br> + <span>宇宙××乍一看卧槽矩阵快速幂然后就开始推</span> + <span>结果发现m在[0,10]内于是宇宙××果断开始写暴力</span> + <span>然而为什么一句话描述中10的指数是问号呢因为题目上写的是8</span> + <span>而第一次提交的大佬队也是最后的rank1队写的8WA了改成9就A了于是他们非常愤怒</span> + <span>而因为这支大佬队就在我们左前方所以我们很幸运。</span> + </p> +</li> +<li> + J: + <p class="nospace"> + <span>有N种商品每种有c<sub>i</sub>个每个的基础价值为v<sub>i</sub>且可以为负</span> + <span>在第j天你要售出一种商品得到j*v<sub>i</sub>的价值</span> + <span>你可以选择从某天之后不再出售任何商品或者直到所有商品售完为止</span> + <span>确定一种出售商品的顺序以获得的最大价值。</span><br> + <span>贪心价值为正的货物一定售出且基础价值越高的越晚售出</span> + <span>此后按剩余物品价值递减的顺序在首部添加价值为负数的商品直到总价值开始减少为止</span> + <span>伟大的宇宙××很快就1A了这道题。</span> + </p> +</li> +<li> + C: + <p class="nospace"> + <span>数轴上有N个点第i个点位于p<sub>i</sub>处对于每个点每秒会分裂为两个并分别移动到原位置正负一处</span> + <span>问T秒后w位置有多少个点。</span><br> + <span>组合数学乱搞这种东西当然不是我做的啦</span> + <span>我也不知道他们第一发发生了什么。</span> + </p> +</li> +<li> + D: + <p class="nospace"> + <span>一个六边形地图可以向左下右下或者正下方走问从某起点走到另一点有多少种方案。</span><br> + <span>递推式是很明显的但是N<sup>2</sup>的复杂度在10<sup>5</sup>的数据下肯定炸</span> + <span>于是就开始试图化简或者找规律然而都没卵用</span> + <span>最后听了伟大的宇宙××的建议把坐标系换成平面直角系然后枚举斜向走的步数和位置</span> + <span>虽然我一开始也这么想了但是感觉坐标变换会比较食屎于是就没搞</span> + <span>但是听宇宙××这么一说不表示一下也不好于是就假装算了一下结果发现特别简单</span> + <span>然后就去打代码这次我的代码竟然1A了真是不容易啊哦不还是因为伟大的宇宙××英明可惜就是不知道错。</span> + </p> +</li> +<li> + K: + <p class="nospace"> + <span>你有T分钟解N道题第i道题在第m分钟解出得到的分数是a<sub>i</sub>-d<sub>i</sub>*m</span> + <span>第i题需要c<sub>i</sub>分钟解出</span> + <span>你不能同时解多道题问在最优策略下你能得到多少分。</span><br> + <span>看上去非常dp的一道题于是自然就交给宇宙××了</span> + <span>但是N可以到2000所以根本没法表示状态</span> + <span>突然宇宙××灵光一现想起了他之前知道的某种全序关系</span> + <span>对于两个题目若其中某个在另一个之前解出这两题的总分更高则在最后顺序中这两题的顺序与此时相同</span> + <span>然后这道题就转换成了一个普通的背包了</span> + <span>伟大的宇宙××就把它1A了。</span> + </p> +</li> +<li> + A: + <p class="nospace"> + <span>变种Nim在产生一堆空堆前选手可以选择一种额外的操作让所有石子堆中的石子个数减少K</span> + <span>已知初始时石子堆数n为质数给定初始状态问何方必胜。</span><br> + <span>不怎么会博弈的我只能打酱油</span> + <span>显然要分n=2和其他情况讨论</span> + <span>专注数学题100年的队友推出了结论然后WA了</span> + <span>于是开始对n>3尝试打表不过发现与结论无异</span> + <span>后来又尝试各种更改仍然都是WA</span> + <span>然而我们三个zz一直没有发现n=2其实就是wythoff问题</span> + <span>到比赛结束前20分钟左右宇宙××拯救了世界大呼eureka</span> + <span>于是到283分钟6发过掉了这道题。</span> + </p> +</li> +<li> + B: + <p class="nospace"> + <span>对于给定的Nd求存在多少长度为N位的允许有前导零的数满足</span> + <span>它的平方的最后N位的每一位与原数中对应位差距不超过d</span> + <span>数字之间的差是循环的且N<=18。</span><br> + <span>虽然我一开始以为这道题不可做但是最后被我们戏剧性地搞了出来</span> + <span>题目给出了提示d=0时可能的序列只有4种</span> + <span>所以我认为d>0的序列可以由这四个序列衍生出来</span> + <span>但题目未给出序列足够位数的内容所以我想出了在序列前枚举添加数字并验证性质的扩展方式</span> + <span>然而我觉得并没有什么卵用所以我也没告诉队友</span> + <span>然而宇宙××这时告诉我可以用这种方法推出任意d的情况而且他认为这就是正解</span> + <span>不过我感觉这样肯定无法解出因为按照我的想法结果的规模是指数级增长的</span> + <span>但是宇宙××坚持我写一发试试而且还强迫我手写了高精度</span> + <span>写完之后发现对于一个d可以由N=18推出其他任何情况的答案于是计划打表</span> + <span>然而发现答案规模真的是按位增长的跑了好久得出了d=1 N=17时的结果大约为1.8*10^8左右</span> + <span>然后这时候电脑就开始卡起来了一看内存已经几乎占满交换空间也用了80%以上了</span> + <span>这时候我一看打出来的那一部分表</span> + <span>我草这怎么都是乘以3啊</span> + <span>我草这怎么都这么多0啊</span> + <span>我草这不是乘以5吗</span> + <span>于是就发现了规律</span> + <span>然后就过了</span> + <span>后就过了</span> + <span>就过了</span> + <span>过了</span> + <span>了。</span> + </p><div> +\[ ans = +\begin{cases} +4 &\text{if } d=0 +\\ +4\times 3^{n-1} & \text{if } d=1 +\\ +8\times 5^{n-1} & \text{if } d=2 +\\ +8\times 7^{n-1} & \text{if } d=3 +\end{cases} +\] + </div> + <p></p> +</li> +</ul> +<p> +所以上面就是所有的「一句话题解」了。E和H都没做所以当然没有。然而值得注意的是出题人还是不太用心， +不仅没有高中文化水平不知道复数，把10^9+7打成10^8+7，还把E题题意写错了（H%lim应为a[e[i]]%lim否则样例错误）。 +大概是主办方没有请出题人亲临现场，裁判组也不知道错。（虽然我们给威海校赛出题的时候也发生了类似的事故…… +但是这是省赛啊，ICPC官网上比赛名录中有的比赛啊 <s>而且我当时也知道错了</s>） +像主办方太抠这样的事情倒是次要的，中间提交长时间不返回结果也不太重要， +但我希望以后的省赛不要出现题目出错裁判组不负责任的情况了。 +</p> +<p> +所以，连续第三年，山大又丢了冠军。于是明年继续努力吧。不过依今年的情况看，明年我们大概就不是主力队了…… +</p> +<p> +外部链接 +</p> +<ul> +<li><a href="https://www.zhihu.com/question/59433867">相关知乎问题</a></li> +<li><a href="http://acm.qust.edu.cn/ranklist/"><s>最终榜单（已失效）</s></a> <a href="//filestorage.chrisoft.org/blog/data/sdcpc2017ranklist.html">镜像</a></li> +</ul> +<p> +最后放几张旅游照片 +</p> +<div style="text-align:center;"> + <img width="80%" src="//filestorage.chrisoft.org/blog/img/20170506_101422.jpg" decoding="async"> + <br> + <img width="40%" src="//filestorage.chrisoft.org/blog/img/20170507_080324.jpg" decoding="async"> + <img width="40%" src="//filestorage.chrisoft.org/blog/img/20170507_080334.jpg" decoding="async"> + <br> + <img width="80%" src="//filestorage.chrisoft.org/blog/img/20170507_144512.jpg" decoding="async"> + <br> + <img width="80%" src="//filestorage.chrisoft.org/blog/img/20170508_074642.jpg" decoding="async"> + <br> + <img width="80%" src="//filestorage.chrisoft.org/blog/img/20170508_074729.jpg" decoding="async"> +</div> +</article> +</div><br><hr> + <div class="TText" id="notediv" style="font-size:80%;"><span class="TText"><a id="note1" href="#n1">[1]</a>: 好吧其实我个人不喜欢这种搞事……<br></span><span class="TText"><a id="note2" href="#n2">[2]</a>: 表现为因没有排练导致的对ACM系列比赛揭榜的基本规则的完全不了解<br></span></div> + <div id="insanch" style="height:3em;"></div> + <div id="footer" style=""> + <div id="pagesw" class="TText" style="width:100%;height:0.5em;"></div> + <div style="text-align:center;" class="TText"> + Proudly powered by SSBS <reduced style="font-size:70%;">(the static stupid blogging system)</reduced> 2.5 + <br> + Content licensed under CC BY-SA 4.0. <span id="purgep" style="display:none;font-size:70%;">This page has passphrase(s) stored. Click <a href="javascript:_purgep()">here</a> to purge.</span> + </div> + </div> + <div id="cmdbuf" class="TText" style="transition:500ms;padding:1em;font-size:2em;color:white;position:absolute;background-color:rgba(0,0,0,0.6);left:50%;top:50%;transform:translate(-50%,-50%);pointer-events:none;opacity:0;"> + </div> + </div> + <div id="decryptui" style="display:none;opacity:0;color:white;z-index:1000;position:fixed;left:0;top:0;width:100%;height:100%;background-color:rgba(0,0,0,0.4);transition:opacity 0.5s;"> + <div id="decryptdlg" class="TText" style="padding:10px 20px;position:absolute;left:50%;top:50%;transform:translate(-50%,-50%);background-color:rgba(0,0,0,0.6);"> + <div id="keyhint" style="margin-bottom:8px;"></div> + <div style="margin-bottom:8px;">Key: <input id="keyinp" type="text" style="color:#fff;"></div> + <div style="height:2.25em;"> + <button id="btndecrypt" onclick="decryptor(decid,document.getElementById('keyinp').value);" style="position:absolute;left:20px;">Decrypt</button> + <button onclick="hidedecryptui();" style="position:absolute;right:20px;">Cancel</button> + </div> + + </div> + + +</div></body></html>
\ No newline at end of file |