游记——2020贵阳市初中毕业生升学考试

前言

今年,疫情爆发。然而贵州省的初三学子于3月14日便返回校园(雾),而且体育考试正常举行,学业考试和升学考试又分开进行,升学考试还整整推迟了21天。

真是多灾多难的一年啊。

Day -57:体育

大家头一天晚上都回到了学校(带着各种 \text{C} _6 \text{H} _{12} \text{O} _6 和运动饮料等等神奇的东西),目的是保证我们的睡眠(然而我半夜被蚊子咬醒过来三次)。第二天的早餐还是依旧难吃(pkupw的一贯尿性),表示肚子有点痛。吃完饭去拉肚子,天气也很阴沉(预示体考要凉??)。没管这么多,带上排球,跟着同班经常一起打球的兄弟下楼,上车去了。

考点还比较远,从清镇到普瑞大概花了一个小时(靠着旁边的人睡了一个小时)。下了车发现这学校是真tm的大(一个操场就秒杀我们的那种)还遇见我妈在考场外面等着,心里还是有点忐忑(也不知道为什么)领队老师问谁要上厕所,结果一车的人都说要去,于是我等了二十分钟才上得了厕所,谔谔。

进到考场之后就是走流程,检录,同时天上下起了大雨,旁边几个同伴瞬间懵逼,“下这个雨操场湿了还跑个jb的1km啊”。暗自骂了几句,也不想管那么多了,检录完就直接跟着队伍乱逛。(带队老师还有点小帅)

这个学校虽然大,但是体育馆是新修的,灰很多(差评),我们在场地里面练习排球的时候烟尘四起,和安塞腰鼓里面描绘的场景神似。关键是体育馆里面还挺冷的,不热身简直冷成憨批。

本来以为马上可以轮到我们考试了的,结果又耗了半天时间,告诉我们要等。没事,等就等嘛。等了半天,身份验证完拿到我们的ic卡(这玩意挺高级的),然后就开始考跳远了。跳远的设备很先进,但是对于踩线的蜜汁判定我也没搞懂过。垫子上面只有男生满分线(2.4m)和女生满分线(1.86m)两条白线,而且垫子也不滑,上去之前感觉也还不错。However,我最担心的还是发生了,我跳的第一次失误了,只跳了1.8m;第二次稍稍进步,我很明显的感受到我的脚飞过了那根白线但是由于落地的时候没有维稳重心,手往后撑地,导致了只有2.38m(差1cm满分是真的操蛋,机子测还不可能防水);第三次就更不稳了,手撑的更往后了,只有两米二。

其他和我一组的也表现不是很好,本来以为很多满分的结果都没有跳过去,甚至最好的只有两米二。大家的士气一度低迷。但也没有办法,只能到隔壁继续考排球了。

排球一向是我强项,一遍就直接过去了。现在还剩最后一个项目——1km。大家估算着时间差不多就把\text{C} _6 \text{H} _{12} \text{O} _6和Redbull混起来喝了,但是后面发生的事情才是真的迷惑。

一行人排队来到操场,结果开始下雨,考官喊我们等待。然而这个雨貌似没有想要停的感觉,一直下一直下一直下,等到有一部分先考完的同学回家了我们还没有开考(感觉\text{C} _6 \text{H} _{12} \text{O} _6的药效都过去了)。好在后来考务安排了人把操场的水扫干净了,不然积有水的操场是真的要命。

轮到我们这组了,如果我跑步没能满分的话体考满分就没希望了(我们这边满分50,你考49.5会给你折算成满分)。好在最后是拼了命跟着我们组的第一(是个打球很厉害的帅哥)跑,提前10s完成了1km。但讲真跑完这3分多种耗费了我一个小时恢复状态()。

走出考场,教务处贴心的给我们买了盒饭,随便拿了一碗吃了,就上车回学校了。

让人迷惑的是下午打球的时候有一人把胳膊摔断了(还是本班的hxd,听说是下楼梯的时候摔到的)。

于是体考就结束了,49.5pts,不算太差,也不算很好。

Day -1

先经历了令人泪目的告别,然后就收拾家伙离开学校(我估摸着这班的人不太可能再在一个教室里面上课了)。到家,听了各种注意事项,收检一下物品,然后就开始颓,刷了一下午的知乎。

睡的有点晚,11点。明天还要看考场,要凉。

Day 0:看考场

这考场离家是真的远,开车开了四十多分钟才到。学校叫做贵阳市第三中学,占地面积也不小。到了的时候已经是9:30了,看见一堆认识的人看完了考场往场外走。找不到考场的我慌的一批/

还好遇到了班主任,他和蔼地拿出了手机,给我看考场的楼层和教室。“第一教学楼四楼”。于是蠢到爆的我找楼梯都花了两分钟时间(bushi)。顺着一个个的教室找到自己的考场,签了到(负责的老师是个挺漂亮的小姐姐),找到自己的位置然后坐下。

突然发现这位置tm是晃的(不是吧,要让我坐这种桌子考三天试?)赶忙联系刚才那个小姐姐,结果被告知她不是负责这一块的?)还好旁边有一个老阿姨听到了,于是过来晃了晃我的桌子,然后告诉我垫张纸在下面(woc就这?)好在垫了纸之后真就不晃了。。安心坐下,听了下广播里放的听力(拿八年级期末听力糊弄谁呢),写了半张数学卷子,发现状态不对就懒得继续写了。去等我家小兄弟去。

等了半天,小兄弟终于来了(全考场就他一个没来签到了)。签完到,进去考场,听力早就不放了,然后发现他的桌子比我的还晃(woc这考场真的牛)解决方案还是垫纸(笑了)。观察了一下考场的钟表和桌子,匆匆离去。

走之前拍了张考场名单,发现30人的考场有14个本校的,顿时信心大增。

下午回家收拾了东西,睡了3小时,晚上就回考场旁边的酒店住了。10: 20 上的床,然而盖了被子觉得热,不盖被子觉得冷,硬是折腾到了12点过(预示我语文要凉???)。但好歹最后是睡着的。而且有NesCafe护体,第二天应该不会困。

Day 1:语文/理综

早上7点醒的,困死。出门等电梯等了半天,干脆不等了,从24楼直接走楼梯下来到大堂吃早餐,下去的时候看到一堆本校的,感觉良好。早餐不算太难吃,泡了包NesCafe,感觉没那么困了。

上了厕所,便进了考点,排了很长的队但也没耗很久时间。进去之后和小兄弟直奔考场,监考是一个凶巴巴的老阿姨,跟我们讲喊我们提前上好厕所再进去,于是我们两个只得在教学楼逛了一大圈,遇到很多同班的,都拥抱了下互相加油。逛了约莫十分钟下了楼看到班主任,班主任反手就塞了两本万唯给我们复习(才不会告诉你我复习了的一个没考),发现看不进去书,然后就又和小兄弟一起从二楼逛到四楼(bushi),上了厕所,才慢摇慢摇进了考场,这个时候才八点半。

进了考场之后昏昏沉沉的,趴在桌子上躺了一会,就坐起来发呆了。八点四十五的时候大喇叭突然想起来,通知监考发放答题卡。另外一个监考是个帅哥,帅哥挨个挨个给我们发了答题卡,我拿到之后填完信息就开始看题:

草,作文叫“找到一个好办法”,什么神奇的东西

文言文大题里面有一个“爽然”,还让我们解释是什么意思,貌似不简单。

哎哎哎分析表达效果,一看就是那种4分我只能做到1分的鬼东西。

不管了不管了,就这样吧。

又过了几分钟,试卷发下来了。急忙看题:选择题第一道我就不会,名著阅读考西游记和简爱,现代文考了一篇通讯一篇说明文,文言文考了《小港渡者》,古诗赏析考了王维的《新晴野望》。总体看上去貌似不算太难。

10分钟切完基础题,然后就是开阅读。第一篇是一篇关于疫情后城市复苏的通讯,20分钟弄过去了,纠结了一道选择题。于是开始第二篇,是用第一人称写的人的免疫系统,题也不难。文言文和古诗赏析就像平时一样,就这样过去了。

考试还剩1h10min的时候,到作文了,审题审了半天(毕竟我初三可是写一篇作文跑题一篇),然后想到一个不错的idea,身为一个OIer,依照惯例去上了个厕所。/回来就开始肝作文,弄完发现还有半个小时,开始从头检查。

检查了半天发现没什么问题,但是在综合性学习那里纠结了一下,改了下答案,然后。。。就tm收卷了(铃声响之后有个人笔没停监考不带管的???)就这样结束了,出考场的时候被堵了半天,差评。

中午几个同班的一起到酒店的一个房间里面吃了点东西,然后就回自己房间复习下午的理综了(然而还是什么都没复习到),回想了一下物理老师特意强调的凸透镜成像,在万唯的那一页停留良久,然后闭眼假装休息了一下(?)就到1:50了。跟几个同学一起,去考场去了(顺便路上买了瓶矿泉水)。

下午一进考场之后雨就开始下大了。送别几个同班的之后等我女票(她今天没有带伞),等的时候和班主任和物理老师闲聊了一会。最后真没想到等了好久,两点半才等到她入场,送她到考场之后上了个厕所就飞奔回自己考场去了。

下午的监考是一个大叔一个阿姨(大叔很凶),估计理综要凉。

答题卡发下来,速度瞟题:作图题一个光线从水中入射到空气,一个画小磁针方向,一个画受力分析,压轴是一个 p-s 图象(鬼知道又是什么),化学看不出什么猫腻,等试卷下发了。

试卷下来之后两分钟就开考了。开考铃一响旁边的人立马翻回第一页开始写(???,只有我一个慢慢悠悠的在浏览后面的题))))))。人傻了。看到化学有几道没见过的题,表示有点难受。

开考5分钟后,翻回第一面从化学选择题开始搞,没想到的是这次化学选择压轴考了推断题(真心没想到会搞这个,果然换了批新的出题人),平时没练过推断题的我在这题上卡了五分钟,但最终发现这题是个sb题。然后开搞物理选择题。发现道送命题:修建火神山的时候上百台挖掘机一起工作增大了挖掘机总的A. 机械效率、B. 功率、C. 功、D. 有用功。我tm怎么觉得BCD都是对的,选了个功率走人不管了。选择压轴不是太难,思考两分钟直接跳过。

开搞物理选择题,又发现一送命题:立扫帚利用了什么原理,仔细调整利用了该原理的什么条件。毫不犹豫的抱着拿不到分的态度填上去一个二力平衡和二力作用在同一直线上就走人了。填空压轴这次比较水,但是答案比较神奇:7.5V。然后就是开搞简答了。简答比较常规,都能作出答案出来。作图就压轴动了点脑子然后就进实验了。

这次的实验没考凸透镜(我????),考了个特别简单的平面镜成像,然后就是一道常规电学实验和一个牛顿摆(这题送走了不少人),感觉都很常规。计算题第一道电学的简单到爆,第二个考了火箭的也很神奇。感觉物理88有望???

开搞化学,但是发现化学不简单——给了酒精的爆炸极限和闪点让你解释为什么使用酒精的时候要注意防止与明火接触,要说这个比较常规的话下面一问问你家用消毒的时候是擦拭酒精还是喷洒。不管了,选擦拭,走人。

金属和酸碱盐大题也不是很难,只是酸碱盐大题耗费了点脑子,花了点时间之后上了个厕所,发现最后也是还有半个小时,遂检查。

物理没检查个什么东西出来,倒是化学查了好几个错,顿时心里有点慌????查完错,时间也就差不多到了。打铃,收卷,流程结束。

出了考场,议论了一下试题,发现貌似没有什么问题,可能作图题扣一分。心满意足的跟平时一起打球的兄弟回了酒店。

草草吃了晚饭,在群里议论了下考题,Day 1 就这样结束了。

晚上写游记,跟兄弟一起刷了点数学题组,睡觉。

Day 2:数学/文综

一早起来,发现还是有点困,怕是数学要凉(结果真凉了)

跟几个同班的同学一起从酒店出发,路上买了一瓶瓶装的 NesCafe (甜到发腻真tm难喝),貌似真的没有那么困了?

进考场,发现有一同班的在复习,遂马上拍照发群进行制裁。之后也没发生什么,开始考试了。

说实话,考数学之前我内心是非常紧张的:整个初三下半学期数学成绩都飘忽不定的,都在140上下徘徊而且做不做得完卷子还是运气问题。一直期待着中考能不能咸鱼翻身,卷子发下来的时候内心是抖的。

先拿到答题卡,24题没图???一看就不简单,25题的图是一个正方形里面变花样,看来又是几何综合。23题的圆的综合题看上去有点小难,剩下的没看出什么猫腻来。

卷子放下来,国际惯例先全部浏览通读,发现10题简单到炸的时候我的内心是欢喜的,发现15题是道静态几何求线段长的时候我的内心是凝固的,发现24题考的是二次函数综合应用题的时候我的内心是崩溃的。这他妈考的都是什么玩意儿啊??!

9点,开考。2分钟切完1-14题,15题读完题面之后发现毫无思路就直接跳了。开考半小时的时候我已经处理完答题卡第一面,开搞第二面。反比例函数的题也非常常规,圆的综合题没卡很久,几个相似暴力过去就完了。现在还剩一个小时,整张卷子剩余24,25,15。

我上了个厕所,内心想着“我想AK”,然而上完厕所回来之后,这三道题联合起来给我扇了一耳屎,这一耳屎成功把我扇下140。

24题越读越发现不对——这tm没有那么简单啊,第一题求 y 关于 x 关系式就是一个分段函数(一段二次函数一段常函数),第二问做着还比较顺利,但第三问直接就tm傻了,方程都列不出来(是我笨没得跑了)。一小时二十分钟后无果,开搞25题。

25题第一问直接搞过去,第二问开始全程懵逼:这tm显然,不会证明。于是第二问乱口胡了一个过程(自认为没问题),然后第三问混了点分,此时二十五分钟又过去了,倒计时15分钟铃也响了,我整个人也傻掉了。

赶紧整理下心态,往前再读一遍15题,仍无果,果断放弃。检查了一遍卷子,然后,,,就打铃了。我的140的梦也没了。

出了考场立马去找同校数学最好的人,发现15题蒙上去的答案是一样的,心里有点小欢喜。手机一开机马上联系数学老师,一顿语音飙过去就是骂出题人,引起旁人侧目。到了校门口看到本校的一个数学老师,简单聊了几句就走人了。卷子没有写好,但是饭还是要吃的,同学帮忙点了砂锅饭,味道还不错。

已经下午一点了,简单假装看一下文综,再假装休息一下(实际没有睡着),就又出发去考场了。

今年文综不一样的一个地方就是文综变成闭卷考试了(微笑),而初三的政治完全划水的我表示政治什么东西都记不得(完蛋咯)。历史还好,没有怎么去记也能考一个大概的分。最最最好的是我们的文综仍不计入总分,采用打等级的制度(暗自窃喜自己不会被刷下去)。

以往考文综的时候都普遍无聊(文综题普遍要么第一眼出答案,要么完全想不到,所以做的很快),好在这次有草稿纸。进了考场,打铃,先发呆发了15分钟,思考了一下人生和上午没写出来的15题。之后5分钟切完30道选择题(怎么我记得以往是32道来着)慢慢发呆,慢慢写,感觉没什么压力就写完了。

晚上和几个玩的好的去了趟金阳万达,一起去吃味千拉面(表示上次在SH玩的时候在东方明珠楼底吃的就是这家),然后回酒店,休息。

比较意外的是今晚睡的很晚,11点半过才睡得着。

Day 3:英语/毕业典礼/毕业聚餐

仍然是七点醒过来,贼困(虽然考英语睡觉已经习惯了)。

按照前两天的流程吃完饭,上厕所,然后出发去考场。

在考场外面读了一下作文句子,然后盲猜作文不考疫情。

进考场,拿到答题卡,看到作文标题给你写好了:“Good Living Habits Make Me _____ ”暗自笑道自己没猜错。

8:59 的时候开始播放听力,暗自觉得听力要凉凉??差点睡下去倒是真的。

整张卷子不难,任务型阅读有道谚语翻译不会,最后期望得分145

毕业典礼和毕业聚餐不太愉快,但是想到和这一班人分开也是挺难受的。

Day x:出成绩

7.28 出成绩了。

头天晚上本来想蹲到12点的,但发现没有用,教育局说是10点那应该就是10点了,睡觉睡觉。

早上醒来的有点早,等我妈去上班之后才起的床,此时9:00 a.m. 还剩最后一个小时,但是挺无聊的,然后说开一把游戏准备打完几把之后出成绩。

和平精英打开,和一个学弟开了一把双排,打野打了20多分钟之后,正当跑毒之时,一大个电话打进来:

成绩可以查了

成绩可以查了

成绩可以查了

我:???????傻逼教育局

打完之后很快的打开电脑输入报名号和名字。没有卡顿,成绩出来了。

之前期望得分:120+138+146+148+50=602

查到实际得分:127+136+145+147+50=605

果然语文眷顾我哈哈哈哈哈。

排名查不到,根据各大学校放的榜可以大概得知市排名12-13左右。今年状元618,是个大哥

算是解放了奥

解题报告 P2822 组合数问题

题目内容

P2822

大意:给定 tkt 次给出 nm,询问所有的 0\leq i\leq n,0\leq j\leq \min \left ( i, m \right ) 有多少对 (i,j) 满足 k|\binom{i}{j}

解题思路

因为数据范围中 n,m\leq 2000,所以不能直接把组合数存储起来,而注意到一个数据点中 k 是固定的,因此可以定义 f_{i,j} 为对于所有的 x\in[0,i]y\in[0,\min(j,x)] 中满足 k|\binom x y\binom x y 的个数。

可以使用递推法预处理所有的 \binom i j\bmod k,然后使用二维前缀和来处理 f_{i,j},每次 O(1) 回答询问。

c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
    {
        for(int j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(c[i][j]==0);
        }
        f[i][i+1]=f[i][i];//下面解释
    }

上面是处理 f 的部分。每次求出组合数直接取模方便判断是否能被 k 整除。二维前缀和的递推都很容易看懂,但是对于最后的 f[i][i+1]=f[i][i]; 的理解是:由于每次 f[i][j] 都要加上 f[i-1][j],而不处理最后的 f[i][i+1] 的话会造成处理下一排时 f[i-1][j] 为 0,所以要进行这样的处理。

还有就是数据中可能有 n,这时候要进行特判

完整代码:

#include <cstdio>
#include <cctype>

//快读

int c[2005][2005];
int f[2005][2005];

int main()
{
    int t=read(),k=read();
    c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
    {
        for(int j=1;j<=i;j++)
        {
            c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(c[i][j]==0);
        }
        f[i][i+1]=f[i][i];
    }
    while(t--)
    {
        int n=read(),m=read();
        printf("%d\n",f[n][m>n?n:m]);
    }
    return 0;
}

当然还有另一种方法就不需要特判,如下:

#include <cstdio>
#include <cctype>

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

int c[2005][2005];
int f[2005][2005];

int main()
{
    int t=read(),k=read();
    c[0][0]=c[1][1]=c[1][0]=1;
    for(int i=1;i<=2000;++i)
        c[i][0]=1;
    for(int i=2;i<=2000;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=(c[i-1][j-1]%k+c[i-1][j]%k)%k;
    for(int i=1;i<=2000;i++)
        for(int j=1;j<=2000;j++)
            f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+(i>=j && c[i][j]==0);
    //这里和上面一样,但是一定要注意判断这里的c[i][j]有没有意义,否则会抱灵
    while(t--)
    {
        int n=read(),m=read();
        printf("%d\n",f[n][m]);
    }
    return 0;
}

NOI Online 2020 Round 2 PJ 游记

前言

菜死了

Day 0

还在学校和文化课苦苦挣扎,差点忘了有这场比赛的存在

Day 1

最近几天一直腰痛(不排除 AS 的可能),遂中午一从学校出来就去了医院检查,谁知道医院 tm 没号了,遂苦逼的赶回家。

回到家想起来今天有 NOIOL,于是吃完饭打开电脑开始看题

第一眼:T1 模拟,T2 搜索,T3 dp,于是直接从 T2 开搞

看题面名字:荆轲刺秦王,我估摸着这就是一个普通的走迷宫然后存储状态就可以了,于是菜到爆的我写了两小时的暴搜,拍完样例后发现没问题就直接走了。

那时的我并没有意识到我处理士兵的方式是 O(n^3) 级别的,不 T 才怪,然后搜索也是傻傻的用 STL 搞,于是乎最后 55 pts 走人。

T1 第一眼看着没思路,分析了几分钟之后发现有点像贪心,然后就想到一个二分答案+前缀和水过去了,注意了下精度问题,发现无大碍,滚去看 T3,发现不会做,写了个输出随机数,卒。

期望得分:100+70+0

Day 2

官方题解出来了,发现 T2 要用差分,T3 是道计数(我没学过计数/kk)于是已经做好滚粗的准备(

Day x

出成绩了,刚好从学校回来,测了民间数据发现 T2 只有 55 分,结果确实只有 55 分,T3 的输出随机数一分没得(好吧我人品确实太惨了)只有 T1 所幸没被卡精度成功 AC。

总结:下次做任何题都要记得估计时间复杂度,不然像这次一样直接爆炸。

最终结果:100+55+0=155

解题报告 P2858 [USACO06FEB]Treats for the Cows G/S

题目内容

P2858

大意:n 个元素的序列,每次可以从头或者尾去掉一个元素,获得的收益是这个元素的权值乘上该次去除的次数,求最大收益。

解题思路

不难发现,这题由于去除元素的顺序对最终的结果是有影响的,所以不能直接贪心,考虑使用 dp。

这题一眼看上去像是一个区间 dp,那我们先开始寻找如何定义状态。考虑我们已经去除了 [i,j] 以外的所有元素,可以发现外面元素去除的顺序已经不重要了,满足无后效性,说明可以这样定义状态:f_{i,j} 表示还剩 [i,j] 时可以达到的最大收益。

转移:当我们达到 [i,j] 时,要么是去掉了第 i-1 个元素,要么是去掉了第 j+1 个元素,设当前的天数为 d,第 i 个元素为 v_i,则有状态转移方程

f_{i,j}=\max(f_{i-1,j}+dv_{i-1},f_{i,j+1}+dv_{j+1})

那么枚举区间长度的时候就必须从大到小枚举,为了方便可以在枚举区间长度的同时枚举天数

最后统计答案的时候答案为 ans=\displaystyle\max_{i=1}^n\lbrace f_{i,i}+nv_i\rbrace,输出即可。

#include <cstdio>
#include <cctype>

//快读

//max

const int maxn=2005;
int v[maxn],f[maxn][maxn];

int main()
{
    int n=read();
    for(int i=1;i<=n;i++)
        v[i]=read();
    for(int len=n-1,day=1;len>=1;len--,day++)//从n-1开始枚举区间长度
        for(int i=1,j=i+len-1;j<=n;i++,j++)
            f[i][j]=max(f[i][j+1]+v[j+1]*day,f[i-1][j]+v[i-1]*day);
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i][i]+n*v[i]);
    printf("%d\n",ans);
    return 0;
}

当然,这题正序枚举区间长度也是可以的,只是倒序的更好理解我太菜不会

解题报告 UVA816 Abbott的复仇 Abbott’s Revenge

题目内容

原文在文末,须认真阅读。

大意:给定一个迷宫,进入某个交叉点的方向不同,允许走出的方向也不同,求出从起点到终点的最短路并输出路径,如无解,输出 No Solution Possible

解题思路

思路就是一个 bfs,第一次到达终点时一定是最短路,遍历每个节点的时候存储上一个状态就可以逆推回去了。状态使用三元组 (r,c,dir) 表示。

但是此题需要注意很多细节:

  • 起点只能往起点规定的方向走,不能任意出发
  • IO 时的空格和换行问题
  • 方向的转换
  • (r_0,c_0,dir_0) 不能直接作为初始状态,需要先移动一格

代码的思路参照了紫书,p[r][c][dir] 存储此状态的上一个状态,d[r][c][dir] 存储到达此状态的最短路(相当于vis),has_edge[r][c][dir][turn] 存储当前状态能不能朝 turn 方向转弯。

思路很明了,注意细节即可,顺便吐槽 UVa 的毒瘤 IO,同时需要仔细阅读英文题面理解题面的意思。

#include <string>
#include <queue>
#include <iostream>
#include <cstring>

using namespace std;

string maze_name;
int r0,c0,r1,c1,r2,c2;
char dir0;

struct node//bfs时的遍历状态
{
    int r,c,dir;//三元组存储
    node(){}
    node(int _r,int _c,int _dir)
    {
        r=_r,c=_c,dir=_dir;
    }
};

const char* dirs="NESW";
const char* turns="FLR";

inline int dir_id(char c)
{
    return strchr(dirs,c)-dirs;//将字母返回数字id
}

inline int turn_id(char c)
{
    return strchr(turns,c)-turns;//将字母返回数字id
}

inline bool chk(int r,int c)//防越界
{
    return 1<=r && r<=9 && 1<=c && c<=9;
}

const int dr[] = {-1,0,1,0};
const int dc[] = {0,1,0,-1};

bool has_edge[10][10][4][4];
node p[10][10][4];
int d[10][10][4];


inline node walk(const node &now,int turn)//返回某个状态转弯之后的状态
{
    int dir=now.dir;
    if(turn==1)//左转
        dir=(dir+3)%4;
    else if(turn==2)//右转
        dir=(dir+1)%4;
    return node(now.r+dr[dir],now.c+dc[dir],dir);//返回转完之后的状态
}

void print(node u)//打印路径
{
    vector<node> way;
    while(true)
    {
        way.push_back(u);//加入路径
        if(!d[u.r][u.c][u.dir])
            break;
        u=p[u.r][u.c][u.dir];//然后回溯上一个状态
    }
    way.push_back(node(r0,c0,dir_id(dir0)));
    int cnt=0;
    for(int i=way.size()-1;i>=0;i--)
    {
        if(cnt%10==0)
            cout<<' ';
        cout<<" ("<<way[i].r<<','<<way[i].c<<')';
        if(++cnt%10==0)
            cout<<endl;
    }
    if(way.size()%10)//注意io细节
        cout<<endl;
    return;
}

void bfs()
{
    cout<<maze_name<<endl;
    queue<node> q;
    memset(d,-1,sizeof d);
    memset(p,0,sizeof p);
    q.push(node(r1,c1,dir_id(dir0)));//先将初始状态加入
    d[r1][c1][dir_id(dir0)]=0;
    while(!q.empty())
    {
        node now=q.front();
        q.pop();
        if(now.r==r2 && now.c==c2)//到达终点
        {
            print(now);
            return;
        }
        for(int i=0;i<3;i++)//枚举转弯的方向
        {
            node to=walk(now,i);//转个弯
            if(has_edge[now.r][now.c][now.dir][i] && chk(to.r,to.c) && d[to.r][to.c][to.dir]<0)//判断是否合法
            {
                d[to.r][to.c][to.dir]=d[now.r][now.c][now.dir]+1;
                p[to.r][to.c][to.dir]=now;
                q.push(to);
            }
        }
    }
    cout<<"  No Solution Possible"<<endl;//注意行首空格
}

bool read_maze()
{
    memset(has_edge,0,sizeof has_edge);
    cin>>maze_name;
    if(maze_name=="END")
        return false;
    cin>>r0>>c0>>dir0>>r2>>c2;
    r1=r0+dr[dir_id(dir0)];//注意(r0,c0)不能直接作为初始状态
    c1=c0+dc[dir_id(dir0)];
    int r,c;
    string tmp;
    while(true)//读入迷宫的点
    {
        cin>>r;
        if(!r)
            break;
        cin>>c>>tmp;
        while(tmp!="*")
        {
            int dir=dir_id(tmp[0]);
            for(int i=1;i<tmp.size();i++)
                has_edge[r][c][dir][turn_id(tmp[i])]=true;
            cin>>tmp;
        }
    }
    bfs();
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    while(read_maze());
    return 0;
}

题目原文

Description

The 1999 World Finals Contest included a problem based on a dice maze. At the time the problem was written, the judges were unable to discover the original source of the dice maze concept. Shortly after the contest, however, Mr. Robert Abbott, the creator of numerous mazes and an author on the subject, contacted the contest judges and identified himself as the originator of dice mazes. We regret that we did not credit Mr. Abbott for his original concept in last years problem statement. But we arehappy to report that Mr. Abbott has offered his expertise to this years contest with his original and unpublished walk-through arrow mazes.
As are most mazes,a walk-through arrow maze is traversed by moving from intersection to intersection until the goal intersection is reached. As each intersection is approached from a given direction, a sign near the entry to the intersection indicates in which directions the intersection can be exited.
These directions are always left, forward or right, or any combination of these.
Figure 1 illustrates a walk-through arrow maze. The intersections are identified as (row, column) pairs, with the upper left being (1,1). The Entrance intersection for Figure 1 is (3,1), and the Goal intersection is (3,3). You begin the maze by moving north from (3,1). As you walk from (3,1) to (2,1), the sign at (2,1) indicates that as you approach (2,1) from the south (traveling north) you may continue to go only forward. Continuing forward takes you toward (1,1). The sign at (1,1) as you approach from the south indicates that you may exit(1,1) only by making a right. This turns you to the east now walking from (1,1) toward (1,2). So far there have been no choices to be made. This is also the case as you continue to move from (1,2) to (2,2) to (2,3) to (1,3). Now, however, as you move west from(1,3) toward (1,2), you have the option of continuing straight or turning left. Continuing straight would take you on toward (1,1), while turning left would take you south to (2,2). The actual(unique) solution to this maze is the following sequence of intersections: (3,1) (2,1) (1,1) (1,2) (2,2) (2,3) (1,3) (1,2) (1,1) (2,1) (2,2) (1,2) (1,3) (2,3) (3,3).
You must write a program to solve valid walk-through arrow mazes. Solving a maze means (if possible) finding a route through the maze that leaves the Entrance in the prescribed direction, and ends in the Goal. This route should not be longer than necessary, of course.

Input

The input file will consist of one or more arrow mazes. The first line of each maze description contains the name of the maze, which is an alphanumeric string of no more than 20 characters. The next line contains, in the following order, the starting row, the starting column, the starting direction, the goal row, and finally the goal column. All are delimited by a single space. The maximum dimensions of a maze for this problem are 9 by 9, so all row and column numbers are single digits from 1 to 9.
The starting direction is one of the characters N, S, E or W, indicating north, south, east and west, respectively.
All remaining input lines for a maze have this format: two integers, one or more groups of characters, and a sentinel asterisk, again all delimited by a single space. The integers represent the row and column, respectively, of a maze intersection. Each character group represents a sign at that intersection. The first character in the group is N,S,E or W to indicate in what direction of travel the sign would be seen. For example,’S’ indicates that this is the sign that is seen when travelling south.(This is the sign posted at the north entrance to the intersection.) Following this first direction character are one to three arrow characters. These can be L,F or R indicating left, forward, and right, respectively.
The list of intersections is concluded by a line containing a single zero in the first column. The next line of the input starts the next maze, and so on. The end of input is the word END on a single line by itself.

Output

For each maze, the output file should contain a line with the name of the maze, followed by one or more lines with either a solution to the maze or the phrase No Solution Possible. Maze names should start in column 1, and all other lines should start in column 3,i.e., indented two spaces. Solutions should be output as a list of intersections in the format(R,C) in the order they are visited from the start to the goal, should be delimited by a single space, and all but the last line of the solution should contain exactly 10 intersections.

解题报告 UVA297 四分树 Quadtrees

题目内容

UVA297

大意:一个 32*32 的黑白图像可以用一棵四分树表示,方法是用根节点表示整张图像,然后子树描述四个正方形,如果某个小正方形里面又有白色又有黑色,则这个儿子节点为灰色并且递归向下建树。

给出两棵四分树的前序遍历,求两张图合并起来之后的黑像素点个数。

解题思路

根据四分树的递归性,直接模拟填充颜色并统计并集的答案即可。

其中 draw(int x1,int y1,int w) 表示当前以 s_p 为根的四分树描述的是以 (x_1,y_1) 为左上角,边长为 w 的正方形区域。如果当前的根为灰色,则需要按顺序往四个子树递归(四个顺序就是象限的顺序),如果为黑色,说明整块区域都是黑色的,直接 O(w^2) 填充,白色的话直接不管即可。

#include <cstdio>
#include <cstring>

char s[1024+5];
int buf[33][33];
int ans,p;

void draw(int x1,int y1,int w)
{
    char ch=s[p++];
    if(ch=='p')
    {
        draw(x1+w/2,y1    ,w/2);//1
        draw(x1    ,y1    ,w/2);//2
        draw(x1    ,y1+w/2,w/2);//3
        draw(x1+w/2,y1+w/2,w/2);//4
    }
    else if(ch=='f')
        for(int i=x1;i<x1+w;i++)
            for(int j=y1;j<y1+w;j++)
                if(!buf[i][j])
                    buf[i][j]=1,ans++;//直接填充并记录答案
    return;
}

int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        ans=0;
        memset(buf,0,sizeof buf);//记得每组数据间的清零操作
        scanf("%s",s);
        p=0;
        draw(1,1,32);
        p=0;
        scanf("%s",s);
        draw(1,1,32);
        printf("There are %d black pixels.\n",ans);
    }
    return 0;
}

解题报告 UVA839 天平 Not so Mobile

题目内容

UVA839

以前序遍历的形式给出一棵二叉树天平,给出每边的力和力臂,求整个天平能不能平衡。

解题思路

首先是 IO,由于天平是以前序遍历的形式给出来的,因此考虑直接在递归读入并直接求解。

某个天平平衡当且仅当它的每一个子天平平衡且它自身平衡,所以当读入有子天平的天平时继续往子天平递归,然后返回上来的是描述是否平衡的 bool 值,同时本层也返回本身是否满足平衡即可。

#include <cstdio>
#include <cctype>

inline int read_int()
{
    //快读被省略了
}

bool read(int &W)//W参数为子天平重量的引用,可以很方便的往上层传子天平值
{
    int WL=read_int(),DL=read_int(),WR=read_int(),DR=read_int();
    bool b1=true,b2=true;
    if(!WL)//如果有左儿子
        b1=read(WL);
    if(!WR)
        b2=read(WR);//如果有右儿子
    W=WL+WR;//当前天平的重量
    return b1 && b2 && WL*DL==WR*DR;//左右儿子都平衡且自身平衡时为true
}

int main()
{
    int t=read_int();
    int W;
    while(t--)
    {
        printf("%s\n",read(W=0)?"YES":"NO");
        if(t)
            printf("\n");//最后不输出多余空行
    }
    return 0;
}

解题报告 UVA548 树 Tree

题目内容

UVA548

给定一棵二叉树的中序遍历和后序遍历,找出一个叶子节点,使得满足从根节点到该叶子节点经过的路径上节点编号的和最小的前提下该叶子节点的编号也最小

解题思路

思路非常类似于求先序排列,关键都是在于后序遍历序列的最后一位一定是该子树的根节点,由此进行向下的递归遍历整棵树并直接在递归的时候统计答案。

难点在于 IO,可先使用 getline() 直接读入一行然后再用 stringstream 提出每一个数字来。

代码中的 int build(int l1,int r1,int l2,int r2,int sum) 表示中序遍历为 in_o[l1]in_o[r1],后序遍历为 post_o[l2]post_o[r2]sum 表示当前从根节点到当前根节点的路径经过的点权总和。

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

const int maxn=1e4+5;
int in_o[maxn],post_o[maxn],lson[maxn],rson[maxn],n;

void read(string s,int *a)
{
    stringstream ss(s);
    n=0;
    int x;
    while(ss>>x)
        a[n++]=x;
    return;
}


int ans,ans_sum;

int build(int l1,int r1,int l2,int r2,int sum)
{
    if(l1>r1)
        return 0;
    int root=post_o[r2];
    sum+=root;
    int p=l1;
    while(in_o[p]!=root)
        p++;
    int cnt=p-l1;
    lson[root]=build(l1,p-1,l2,l2+cnt-1,sum);
    rson[root]=build(p+1,r1,l2+cnt,r2-1,sum);
    if(!lson[root] && !rson[root])
        if(sum<ans_sum || (sum==ans_sum && root<ans))
            ans_sum=sum,ans=root;
    return root;
}


int main()
{
    string in,post;
    while(getline(cin,in) && getline(cin,post))
    {
        read(in,in_o);
        read(post,post_o);
        ans_sum=0x7f7f7f7f;
        build(0,n-1,0,n-1,0);
        cout<<ans<<endl;
    }
    return 0;
}

解题报告 UVA122 树的层次遍历 Trees on the level

题目内容

UVA122

大意:给定一棵二叉树,每个节点按照从根节点到它的移动序列(L 或 R)表示,如果能构成合法的二叉树,输出这棵二叉树的层次遍历,否则输出 not complete

解题思路

不能单纯的使用开一个很大的数组来堆式存储二叉树了,因为 2^{256}-1 会炸空间,所以需要使用指针来动态开点存储二叉树。

struct node
{
    bool have_value;//是否被赋值过
    int val;//节点的值
    node *left,*right;//指向左右儿子的指针,默认为NULL
    node():have_value(false),left(NULL),right(NULL){}//构造函数
};

然后就是读入一棵树了:

char s[maxn];

bool read()
{
    failed=false;
    remove_tree(root);//释放内存
    root=newnode();//指定新的根节点
    while(1)
    {
        if(scanf("%s",s)!=1)//如果输入结束了
            return false;
        if(!strcmp(s,"()"))//如果一棵树到头了
            break;
        int v;//读入该节点的值使用
        sscanf(&s[1],"%d",&v);//sscanf大法好
        addnode(v,strchr(s,',')+1);//将逗号以后的所有值传入addnode函数进行开点操作
    }
    return true;
}

动态开点:

使用 new 操作符可以动态开一个空间,同样用 delete 可以释放空间:

inline node* newnode()
{
    return new node();
}

void remove_tree(node *now)
{
    if(now==NULL)//如果节点为空
        return;
    remove_tree(now->left);//递归释放左子树
    remove_tree(now->right);
    delete now;//删除当前节点
}

传入括号内的内容进行开点

void addnode(int v,char *s)
{
    int n=strlen(s);
    node *u=root;//因为给出的点的形式都是从根开始遍历的
    for(int i=0;i<n;i++)//根据提示一步步往下走
    {
        if(s[i]=='L')
        {
            if(u->left==NULL)
                u->left=newnode();
            u=u->left;
        }
        else if(s[i]=='R')
        {
            if(u->right==NULL)
                u->right=newnode();
            u=u->right;
        }
    }
    if(u->have_value)//如果这个点已经被赋过值了,那么显然输入错误
        failed=true;
    u->val=v;//赋值
    u->have_value=true;//打标记
    return;
}

最后就是层次遍历了,可以使用 bfs 实现

bool bfs(vector<int> &ans)
{
    queue<node*> q;//存储待访问节点
    ans.clear();
    q.push(root);
    while(!q.empty())
    {
        node *now=q.front();
        q.pop();
        if(!now->have_value)//如果当前节点未赋值
            return false;//说明信息不完整
        ans.push_back(now->val);//计入答案
        if(now->left!=NULL)
            q.push(now->left);
        if(now->right!=NULL)
            q.push(now->right);//分别加入左右儿子节点
    }
    return true;
}

具体的思路就是动态开点,动态维护,然后进行 bfs。唯一的坑点是行末不能输出多余空格

#include <cstdio>
#include <cstring>
#include <queue>

using std::queue;
using std::vector;

struct node
{
    bool have_value;
    int val;
    node *left,*right;
    node():have_value(false),left(NULL),right(NULL){}
};

const int maxn=258;
bool failed;
node* root;

inline node* newnode()
{
    return new node();
}

void remove_tree(node *now)
{
    if(now==NULL)
        return;
    remove_tree(now->left);
    remove_tree(now->right);
    delete now;
}

void addnode(int v,char *s)
{
    int n=strlen(s);
    node *u=root;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='L')
        {
            if(u->left==NULL)
                u->left=newnode();
            u=u->left;
        }
        else if(s[i]=='R')
        {
            if(u->right==NULL)
                u->right=newnode();
            u=u->right;
        }
    }
    if(u->have_value)
        failed=true;
    u->val=v;
    u->have_value=true;
    return;
}

char s[maxn];

bool read()
{
    failed=false;
    remove_tree(root);
    root=newnode();
    while(1)
    {
        if(scanf("%s",s)!=1)
            return false;
        if(!strcmp(s,"()"))
            break;
        int v;
        sscanf(&s[1],"%d",&v);
        addnode(v,strchr(s,',')+1);
    }
    return true;
}

bool bfs(vector<int> &ans)
{
    queue<node*> q;
    ans.clear();
    q.push(root);
    while(!q.empty())
    {
        node *now=q.front();
        q.pop();
        if(!now->have_value)
            return false;
        ans.push_back(now->val);
        if(now->left!=NULL)
            q.push(now->left);
        if(now->right!=NULL)
            q.push(now->right);
    }
    return true;
}

void print(vector<int> &ans)
{
    for(int i=0;i<ans.size()-1;i++)
        printf("%d ",ans[i]);
    printf("%d\n",ans[ans.size()-1]);
    return;
}

int main()
{
    vector<int> ans;
    while(read())
    {
        if(bfs(ans) && (!failed))
            print(ans);
        else
            printf("not complete\n");
    }
    return 0;
}