头部背景图片
ThetaS |
ThetaS |

椭圆笔记(一)

2017-11-19

椭圆笔记(一)

标签:中点弦,暴力求解,韦达定理,点到直线距离

一如既往不正经的部分

NOIP结束以后,顿时感觉肩上的担子轻了许多。集训的时候,我特别羡慕那些能在教室里普通地听着课,普通地完成老师布置的作业,就这样当着乖乖学生的那些同学。与其在一个挪一下凳子都会引起所有人注意的封闭机房每天头痛3~4个小时,还是在灯光明亮的教室中有心无心地听着老师讲课舒服得多。

集训结束了,我们又变成了一千多普通学生中的一份子。可是我的内心,没有了当初盼望的幸福感,取而代之的是空虚和一丝伤感。不是因为我停了3个星期的课,听不懂老师究竟在讲什么,而是感觉在自己不知道的情况下,失去了重要的东西。。。

“既然省一已经没有保送了,那你的重心应该在自己的学业上,为什么还在竞赛上砸这么多时间?”我的班主任曾经问过我这一个问题,我不记得当时自己是怎么敷衍过这个问题的,然而就在昨晚听歌的时候,突然明白了自己空虚和伤感的理由。并且对于班主任的问题,有了更优的答案。现在的话,应该能说得出来。

“因为爱。”

废话也是要有节制的,赶紧放歌,不然后面的东西讲不完的(笑):

好的,正片开始。

椭圆是高中相当重要的一个部分。公式虽然不多,但是因其拓展性极高,可以搭配其他各类知识整合考察,经常作为压轴题出现。经过一段时间椭圆的学习,先把一下填空和选择题常用的方法在这篇文章做一下讲解和归档。

货车运输(从零开始的LCA学习)

2017-11-08

算法标签: 最大生成树,倍增求LCA

一如既往不正经的开头

如果我说从零开始,你的第一反应会是什么呢?是刚开始尝试做某件事情时的懵懂无知,还是经历了大风大雨之后,在经历了血的教训和失败的洗礼之后昂起头来舍弃一切,从头开始。每个人都有作为萌新的一天,每个人的面前都有着这么一个大佬。也许我们在短时间内没有办法超过这位大佬,也许很长一段时间也不行。羡慕或者是嫉妒,还可能说出“他们有什么了不起”这类话。然而当我们面对又一群新人用同样的眼神看着我们的时候,在我们的内心深处,或许又明白了一些什么。大佬,不过是比我们先走一步的人,或者是比我们稍微有一些天赋的同龄人。

然而我们每一天都在面对新的东西,意味着我们每一天都在某一个领域当着“新人”,比如我和今天我们要讲的LCA。以前看LCA是一个很高大上的东西,模板题怎么也磕不下来(倍增被卡了),自从弄了一道货车运输,感觉自己自己对倍增这个神奇的想法有了更深的理解。由于这次的想法和代码实现都比较抽象,theta强烈建议各位拿出草稿纸按着代码执行模拟一遍 。除非你的脑内存特别大,已经看到了结果,否则模拟一遍你一定会惊奇的感叹道:“神奇的二进制 ”(引用于lanshui_Yang,那位让我搞清楚倍增的博主,在此表示感谢)。

然而Theta个人觉得,看我博客的应该都是与我年龄相仿的人,所以个人觉得“从零开始 ”这个短语你们更多想到的应该是RE:从零开始的异世界生活 吧!(笑)。一首从零开始的异世界生活的ED stay alive 送给大家。只要我们还活着,就一定还有无限可能:

DP的胜利(11月4日DAY1T1)

2017-11-05

被“轻描淡写”的DP

每次玩比赛看题解的时候,总有一部分题被人打上奇怪的标签。对于含有这些标签的题目,老师和神犇们总是轻描淡写的就这么过了。比如,以下这些话是否曾在你耳边响起过呢?“哦!!!这题啊,额。。。不就一个简单的期望DP吗?”,“这一题就一个树上DP然后xjb乱搞一下就得了,你自己意会一下(你倒是告诉我xjb省略了什么部分啊)”,“这就是一个状压DP裸题,你对着模板打一下改一改就出来了(改不出,下一个)”,这样的话还有很多很多,theta的DP也不是很会打。那么,这次我们就拿一道画风不对的DP题目来做样例吧!话说有大佬说DP不过是优雅的暴力罢了

栏目导语

2017-11-05

栏目导语

还有一周就是NOIP了,然而theta发现自己有很多错题没有纠正啊(所有的题解全磕在试炼场上了)。这些题目都是theta爆零或者得到超低分的题目。没错,暴力分都没拿到。没有拿完基础分的人还敢当高产up主?!

为什么要建立这一个栏目?

一个是theta我自己的个人总结,毕竟总结才能提升嘛!另外我还会渗透一些考场上的心里活动和想法,也方便和我有相似心态的同学有前车之鉴。当然,如果后来我弄出了部分解,也会在文章中分享。(考试时拿完部分分才是王道)

送大家一句话:一个男人可以被毁灭,但他绝不会被打败;一个真男人可以跌倒,但他从不会在同一个地方跌倒第二次。

病名为优化

2017-11-02

病名为优化

明明是正解,为什么又有几个点莫名T了?!这是在搞事情吧,怎么又T了!我们身边的神犇经常碰到一个问题,明明打出了正解,却被评测机卡了几个点,白白丢了几十分。然而看到旁边用一个n^2暴力算法加一大堆玄学优化的竟然AC了?!神犇的内心就此受到了10000点真实伤害 在OI的赛场上,很有可能会出现这样的情况,那就是几乎正解算法+普通优化<= 暴力算法+玄学优化集合(什么优化都给他怼上去) 。那么这次,我们就来讲讲一些比较常用的优化。

先放一首歌,歌名我估计大家都猜到了。没错,最近突然走红的爆曲,病名は愛だった

这次主要讲的是快速幂和读入优化两个优化方法,看快速幂证明觉得蛋疼可以先看读入优化,要看卡常数的神犇们可以先撤了。

通往奥格瑞玛的道路(SPFA+二分)

2017-11-01

通往奥格玛瑞的道路(Luogu P1462)

导语(这次不是废话了)

作为洛谷的原创题,这道题将两种看似没啥关系的数据结构很好滴结合在了一起(theta语文不好没办法很好地表达自己对这道题的感情)。典型的二分问法(什么什么最大的最小值),嵌套图论中的最短路算法,theta一直想出这样一道题(可能是因为我只会最短路和二分了吧),但是一知道不该怎么做。下次我可以试着出一下并查集+二分看看。但是,就像我爱我的女朋友(假设情况,theta没有女朋友呢,希望大家介绍一个),我的女朋友也不一定会对我忠诚一样,做这道题路程也并不顺利,很多小细节没有处理好,导致全部处理好之后已经是30次以后了(被莫名其妙的点卡了,而且没法下数据)。这些小错误我在后面一会一 一公开。

那么先放一首歌来轻松一下吧 ,出自动画 此花亭绮谭 ,演唱是为多部治愈系动画配过op的eufonius,还请大家静下来好好聆听。 theta你还说这次导语不是废话 :

好的,正片开始。

星球大战(逆向思维好题)

2017-10-30

星球大战(Luogu P1197,结尾有彩蛋)

写在前面的话:

这道题刚看到的时候确实感觉有点骚,以至于我一个很厉害的后辈说:“读题读到一半,想都不想,赶紧关了”。也许解出这道题打个并查集就差不多了,可是不良出题人的大数据让我们朴素的愿望就这么落空了。没错单打并查集如果你没有WA,也会TLE的。Theta比较水,这题是在大佬的“帮助”下才弄懂A过去的。 明明看了题解 还想给自己找借口

先放一首歌冷静冷静(讲实话,panama是theta觉得还算好听的网红曲了):

拓展并查集的使用

2017-10-26

拓展并查集的使用

##在正片开始之前的唠叨:
比赛将至,我们OI队伍的人都集结在了小黑屋进行集训。开始的一两天肯定是兴奋无比的,,可是还没过几天,theta就感到自己身体有点吃力了(theta是那种很需要睡眠,可是都睡不够的人)。在此提醒各位OI大佬们,身体是革命的本钱,千万不要为了一个WA点而浪费了自己的睡眠时间啊!毕竟人生还很长,健康很重要。

一首Gravity献给大家,不是泽野大佬的版本。


一道SPFA简单题引发的思考

2017-10-23

#一道SPFA简单题引发的思考

Luogu P1339[USACO 09OCT] Heat Wave

以下两个条件,只要您具备其一,这篇文章可以跳过了:

  1. 能熟练打出SPFA,并且使用STL中的vector+结构体存储
  2. dijsktra用户
  3. Theta 默认读者朋友们有一定的图论基础,基础比较薄弱的请先自行搜索SPFA,邻接表

P1314无序字母对解析

2017-10-21

P1314 无序字母对

因为这篇文章有点长,在开始枯燥的阅读之前,先放bgm把气氛燃出来。不然感觉你们看到后面要睡着了(笑)。

bgm来自泽野大佬的Dragon Rises,
(一部好像很中二的医学片的燃曲)。

题目大意:

给定n个各不相同的无序字母对(区分大小写,无序即字母对中的两个字母可以位置颠倒)。请构造一个有n+1个字母的字符串使得每个字母对都在这个字符串中出现。

输入格式

第一行输入一个正整数n。以下n行每行两个字母,表示这两个字母需要相邻。

输出格式

输出满足要求的字符串。
  如果没有满足要求的字符串,请输出“No Solution”。
  如果有多种方案,请输出前面的字母的ASCII编码尽可能小的(字典序最小)的方案