HNOI2019总结

时间:2022-12-23 14:22:00

HNOI2019总结

Day 1

开场看三道题,T1是个计算几何,T2是个操作树加\(border\),T3题意有点复杂。想T1想了半个多小时,发现那个钝角不是很会处理,但是40分暴力应该还是可以写,就是有点麻烦。再想T2,也没什么太好的思路,50分只会操作树\(+kmp+\)乱搞。大概9:00开始认真搞T3,看了看样例,感性理解下好像终结状态全都是连到\(n\),于是写了个爆搜,试了几组,好像是对的。发现\(w=0\)直接用\(n-3-\)与n相连的边的条数就行了,操作一条边也比较好做。写完之后发现\((x,n)\)的边不会再动,所以好像是个树的结构,算一次的话直接树形dp就行了。仔细思考了一下,每次树的一个节点都是一段区间,这个树好像就是一棵类似笛卡尔树的东西,操作某一条线相当于splay了一下,好像求个逆元就可以了。想出来大概10点,写到11点多拍上。然后写了一下T2的暴力\(kmp\)和对拍以及T1的20就下考了。

估分:20+20+100=140

实际:20+50+100=170

HNOI的数据强度可见一斑,肖大佬好像直接用暴力kmp拿了70..

Day 2

开场看三道题,好像都还比较清新。T1数据范围有点像bitset,T2看到\(k|p-1\)觉得应该需要一些原根一类的数学前置知识,T3一开始看有点像\(fft\),后来仔细一想是个最优化问题,只会\(O(n^3)\)暴力dp。感觉T3有点像什么dp优化,以为是要推一些结论然后单调队列,推了很久没推出来。于是先看T2,T2前20分直接暴力dp组合数。后面的很像SHOI的那个组合数问题,我只会\(O(k^2 log)\),当时没有去想fft,就先把暴力写了,去搞T1。先写了个30分,然后推了推发现一个联通块可以直接缩起来,如果是二分图要特殊考虑一下。然后想用这个缩起来后bitset。先把T3暴力写完去手写T1bitset,写完之后发现样例过不了,如果联通块大小为1时会有问题,当时因为考试已经快结束了,也没来得及想,就拿了暴力套了后面这部分交了。

估分:30+20+30=80

实际:30+20+30=80

考完出来说T2是单位根反演加上论文题

T1正解和我想的差不多,只要不往bitset方向想就行了。

T3完全走错方向了,50分贪心就行了

总结

总体来说还行,两天考下来没有挂分。但是D1T1没时间写,D2T1和D2T3稍微想偏了一点都有些遗憾。但是像D1T1的计算几何D2T2的单位根反演都是一些我不太熟悉的内容,还需要多学习。数据结构和一些贪心技巧还是不够熟练。希望能够在接下来的一段时间里补足。希望NOI加油。

计划

接下来的一段时间可能需要补上一些文化课的知识。对于计算几何和一些有关数论的高级知识是我的知识盲区,需要多了解一些这方面的知识。更重要的还是一些对思维能力方面的锻炼,一些基础算法的运用,以及对之前做过的题,考过的试的一些总结。还有之前一直没有做的一些题目,也需要完成。hnoi只是一个开始,接下来要更加努力。

HNOI2019总结的更多相关文章

  1. HNOI2019游记

    \(day~?\) 我们的老师告诉我说,你这次省选目标分:\(70\),拿不到,家法伺候.但其实,我的目标是不爆零!!! \(day~-1\) 这天晚上,我们的指导老师给我们试了一下ZJOI2019, ...

  2. Loj #3059. 「HNOI2019」序列

    Loj #3059. 「HNOI2019」序列 给定一个长度为 \(n\) 的序列 \(A_1, \ldots , A_n\),以及 \(m\) 个操作,每个操作将一个 \(A_i\) 修改为 \(k ...

  3. Loj #3056. 「HNOI2019」多边形

    Loj #3056. 「HNOI2019」多边形 小 R 与小 W 在玩游戏. 他们有一个边数为 \(n\) 的凸多边形,其顶点沿逆时针方向标号依次为 \(1,2,3, \ldots , n\).最开 ...

  4. 【BZOJ5491】[HNOI2019]多边形(模拟,组合计数)

    [HNOI2019]多边形(模拟,组合计数) 题面 洛谷 题解 突然特别想骂人,本来我考场现切了的,结果WA了几个点,刚刚拿代码一看有个地方忘记取模了. 首先发现终止态一定是所有点都向\(n\)连边( ...

  5. 【BZOJ5492】[HNOI2019]校园旅行(bfs)

    [HNOI2019]校园旅行(bfs) 题面 洛谷 题解 首先考虑暴力做法怎么做. 把所有可行的二元组全部丢进队列里,每次两个点分别向两侧拓展一个同色点,然后更新可行的情况. 这样子的复杂度是\(O( ...

  6. Loj #3055. 「HNOI2019」JOJO

    Loj #3055. 「HNOI2019」JOJO JOJO 的奇幻冒险是一部非常火的漫画.漫画中的男主角经常喜欢连续喊很多的「欧拉」或者「木大」. 为了防止字太多挡住漫画内容,现在打算在新的漫画中用 ...

  7. Loj 3058. 「HNOI2019」白兔之舞

    Loj 3058. 「HNOI2019」白兔之舞 题目描述 有一张顶点数为 \((L+1)\times n\) 的有向图.这张图的每个顶点由一个二元组 \((u,v)\) 表示 \((0\le u\l ...

  8. Loj #3057. 「HNOI2019」校园旅行

    Loj #3057. 「HNOI2019」校园旅行 某学校的每个建筑都有一个独特的编号.一天你在校园里无聊,决定在校园内随意地漫步. 你已经在校园里呆过一段时间,对校园内每个建筑的编号非常熟悉,于是你 ...

  9. HNOI2019 游记

    HNOI2019 游记 Day 0 其实考前几天,心里还是挺慌的.结果最后 Day 0 的时候,因为种种原因反而释然了.也许是觉得,在这一步退役,也没有什么好害怕的吧. OI 本身就是一项偶然性太大的 ...

随机推荐

  1. Gogs - 基于 Go 语言的自助 Git 服务

    Gogs(Go Git Service) 是一个基于 Go 语言的自助 Git 服务.Gogs 的目标是打造一个最简单.最快速和最轻松的方式搭建自助 Git 服务.使用 Go 语言开发使得 Gogs ...

  2. 关联规则之Aprior算法(购物篮分析)

    0.支持度与置信度 <mahout实战>与<机器学习实战>一起该买的记录数占所有商品记录总数的比例——支持度(整体) 买了<mahout实战>与<机器学习实战 ...

  3. 消息推送之GCM

    利用GCM进行消息推送 原理 1.接收端向GCM注册registerid 2.发送端发消息给GCM服务器 这个过程需要三个参数: (1)API Key (2)registerid (3)传递的数据 3 ...

  4. 怎么让LinearLayout充满ScrollView

    ScrollView里只能放一个元素.    当ScrollView里的元素想填满ScrollView时,使用"fill_parent"是不管用的,必需为ScrollView设置: ...

  5. Oracle----Key Word

    desc|describe table_name DCL----column ----add -- add one column alter table product ); -- add multi ...

  6. vertical-align&colon;middle的居中细节调整

    使用vertical-align:middle可以让行级元素垂直居中,但这个居中是以文字的中线来计算的,而文字的中线在不同的字体上不同,甚至相同的字体在不同的浏览器上显示的都不同.所以直接使用vert ...

  7. js 中 setTimeout&lpar;&rpar;的用法

    setTimeout()在js类中的使用方法   setTimeout (表达式,延时时间)setTimeout(表达式,交互时间)延时时间/交互时间是以豪秒为单位的(1000ms=1s) setTi ...

  8. Java数据库连接--JDBC基础知识&lpar;操作数据库:增删改查&rpar;

    一.JDBC简介 JDBC是连接java应用程序和数据库之间的桥梁. 什么是JDBC? Java语言访问数据库的一种规范,是一套API. JDBC (Java Database Connectivit ...

  9. 【原创】KMP算法代码(C)

    //s是模式字符串,t是匹配字符串(可以看我上一篇文章中的叙述) int KMP(const char * s , const char * t) { int slen = strlen(s) , t ...

  10. Android:getContext&lpar;&rpar;&period;getSystemService&lpar;&rpar;

    一.介绍 getSystemService是Android很重要的一个API,它是Activity的一个方法,根据传入的NAME来取得对应的Object,然后转换成相应的服务对象 二.语法 Windo ...