GoldenPotato137的小屋
  • 留言板
  • PCB信仰尺
  • IP签名图
GoldenPotato的ACM小屋
一名HITer/LLer/ACMer的ACM(前OI)博客
游记/自闭记/滚粗记

NOIp(大雾) CSP-S 2019 暴力记

咕咕咕 没了,打了整整两天暴力,我太菜了,嘤 目测分数远低于高一那场NOIp 开 倒 车

2019年11月17日 3条评论 1909点热度 14人点赞 阅读全文
未分类

AFO后记

我的OI生涯 咕咕咕 接下来的博客计划 接下来呢,我可能就没法刷太多题了,可能只会久不久写一点OI题目。 之后我的博客只要内容会更新学文化课的进度,感想,希望能帮助有困惑的同学,并希望证明一点:OIer是不会被打倒的! Update 2020/8/2 高考 全国三卷 655 大家哈工大见! 致谢 感谢无私帮助我的学长们,他们是: zyb学长 (泅荼) hb学长 (nnez_hb) lx学长 (LQAQC) xlw学长 (nnez_xiaoliwei) ... 感谢一路上与我并肩作战的同级同学们,他们是: wzj神仙…

2019年04月25日 2条评论 1094点热度 6人点赞 阅读全文
游记/自闭记/滚粗记

GXOI2019 退役记

DAY1被神题打爆狗头,T1骗了50分就持续自闭了。 DAY2开题5分钟立马锤了一个T1的假DP,然后还对这个假做法有蜜汁自信,拍都没拍就跑路了。 T2有点想法但又没有,总感觉隐隐约约可做但又不会写,最后锤的暴力。 T3暴力很显然,又用splay锤了一个20分的链。 结果是很凄惨的,T1爆零,T2,T3没有意外发生,RANK10退役。 怎么说呢,T1写爆是自己的策略严重失误。平时模拟赛的时候犯这种错误总是安慰自己说考场上不会犯的,事实证明,考场也只是自己平时状态的延续罢了。 如果我T1没有去写DP,就算写那20分的…

2019年04月11日 8条评论 1392点热度 7人点赞 阅读全文
其他

手把手带你入门GUIDE

什么是GUIDE GUIDE(GAIT Universal IDE)是由北航GAIT研究组开发的、专门为NOI选手设计的轻型集成开发环境。GUIDE具有跨平台、操作简单、支持C/C++/Pascal三种语言和单文件编译调试等优点。经过近一年的试用和修改之后,GUIDE 1.0.1版目前正式发布。 ——www.noi.cn 换句话来说,GUIDE是一个NOI官方指定的,在NOI Linux系统上预装的一款pascal/c/c++ IDE(集成开发环境)。 GUIDE有什么优点 我们GUIDE有一点好,就是出了什么bu…

2019年04月03日 16条评论 1466点热度 3人点赞 阅读全文
其他

一些坑点

填坑中 $\color{blue} {last update : Jan,21st,2019}$ 通用 $\color {red} {-1.仔细审题*2}$ 永远要有想法,不要觉得复杂度不对空间就不开够。空间永远开到最大值(或者说是自己不MLE的极限),以免发生复杂度正确但是空间没有开够的惨痛教训(NOI.ac WHZZT 邀请赛R1) 在会爆int的题目中,一定要仔细检查是否有会爆int的中间变量写了int。 (from NNEZ_R2_T1) 使用-=时,把-=后面的东西用括号括起来,防止可能出现的负负为正等S…

2019年02月22日 10条评论 2157点热度 0人点赞 阅读全文
后缀自动机

[Luogu P3975] [TJOI2015]弦论

题面 P3975 [TJOI2015]弦论 Solution 看到题面要求不同情况下的$K$小串,给人一种自动机上做DP就可以写的感觉。 因此,我们考虑用后缀自动机来解决这个问题。我们先建出SAM。 对于$k=0$的情况,肥肠好写。根据SAM的常识,在SAM上任意走都是原串的一个子串。题目要求求出第$k$小不重复子串,既是让我们求出SAM的前$k$条路径。因为这里的$k$很大,我们是不能暴力走的。因此,我们可以设$f[i]$表示从$i$出发有多少条路径,转移非常显然,$f[i]=\sum f[j]$(j为i能到的点…

2019年04月10日 0条评论 533点热度 0人点赞 阅读全文
图论

最小树形图构造(朱刘算法)学习笔记

什么是最小树形图 最小树形图就是给定一个$n$个点的有向图,我们钦定一个根,现在要找$n-1$条边,在根能到达其他所有点的前提条件下,使得$n-1$条边的总长度尽可能小。 怎么找最小树形图 这里就得用到朱刘算法了。朱刘算法是一个$O(n \cdot m)$的算法。当然,还有Tarjan巨神的$O(nlogn)$的算法。但我太菜了,并学不会 图出自这里 上面这张图很好的诠释了朱刘算法的主要内容: 我们算法主要有以下几个步骤: 1. 找到到达每个点的长度最小的入边(根节点不找) 2. 这些边如果连成一颗树则结束; 3.…

2019年04月09日 2条评论 1139点热度 1人点赞 阅读全文
图论

UVA10972 RevolC FaeLoN

题面 UVA10972 RevolC FaeLoN Solution 这题就比较牛皮。 我们先来考虑一下图联通的话怎么做。显然,我们可以先把图按边双缩点,边双内部是肯定不用加任何一条有向边就能改成强连通分量的(易证)。 缩完点之后,图一定会变成一颗树。接下来我们依旧可以像这道题那样贪心。我们数一下广义叶子数有多少,要加的边的个数一定为$sum/2$(向上取整)。 连边方式如图所示: 接下来再来考虑不连通的情况。显然,我们可以发现,对于多颗树来说,我们依旧可以照样刚刚那样贪心。我们左右两棵树在叶子那里连边即可。 因此…

2019年04月09日 0条评论 592点热度 0人点赞 阅读全文
图论

UVA610 Street Directions

题面 UVA610 Street Directions Solution 先来解释一下题面意思:我们现在有一个联通的无向图,我们要把整个图改造为有向图,在保证强连通的情况下使得双向边尽可能少。 我们不妨思考一下:如果一条双向边被我们改造为了单向边,会导致某一个方向上的断开。因此,我们先对原图做边双缩点,桥边是不可能被改造为单向边的(因为改造后直接导致边双间不能互相联通)。除了桥边之外,其他边都是可以改造为单向边的。 因此,我们可以在每一个边双里面做一个dfs来连单向边,桥边直接连上双向边即可。 时间复杂度$O(n)…

2019年04月09日 0条评论 512点热度 0人点赞 阅读全文
图论

[USACO06JAN]冗余路径Redundant Paths

题面 P2860 [USACO06JAN]冗余路径Redundant Paths Solution 首先,我们可以发现题目要求每一个点到其他所有点的路径不只有一条,这本质上就是要我们把这个图所有的桥都消除掉。 要消除掉桥,首先必须要把边双先缩起来。缩边双很简单:和求强连通分量一模一样,唯一要注意的是我们要多记录一个$fa$,防止我们求$low$的时候直接把$fa$算进来。 求完边双之后,我们会发现原图变成一个树的形式。想象一下:我们要把这个树上所有的单边去掉,我们只需要把叶子节点两两连起来即可。(注意,这里的叶子节…

2019年04月08日 0条评论 547点热度 2人点赞 阅读全文
图论

[Luogu P3225 [HNOI2012]矿场搭建

题面 P3225 [HNOI2012]矿场搭建 Solution 这题比较妙。 首先,根据常识,如果一个点爆了,当且仅当它是割点的时候才会影响整个图的连通性。 因此,我们考虑把这道题往点双那方面想。 接下来我们思考这个问题:对于一个点双,我们什么时候需要在它这里面放置逃生通道: 1. 如果与它相连的点双块只有一个:如果爆的是割点,则必须在当前块中的任意点建一个通道;如果爆的是普通点,则当前块则可以与别的块照样联通。 2. 如果与它相连的点双块有两个以上:无论爆的是割点还是普通点,都不影响它里面的其他点到其他块去逃生…

2019年04月08日 0条评论 469点热度 0人点赞 阅读全文
动态规划

[Luogu P4606] [SDOI2018]战略游戏

题面 P4606 [SDOI2018]战略游戏 Solution 圆方树上圆方果, 圆方树下你和我。 圆方树前建虚树, 欢乐多又多。 . 好吧,我们来说正题。 这题就比较强。根据常识,如果我们爆掉的点能影响这个图的连通性,那么,这个点一定是割点。 因此,我们要先对原图做Tarjan求点双。接下来,我们考虑用圆方树来解决一个问题。 我们先考虑暴力怎么做,我们先对原图求出圆方树。接下来,我们发现,对答案有贡献的点一定是孩子有被选定的点的圆点,并且这个点的总共被选定的孩子数不等于总共被选定数(因为如果这个点被割掉了,其被…

2019年04月08日 0条评论 545点热度 1人点赞 阅读全文
12345…12

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

NNEZ的Friends呢
  • %%%hzq dalao
  • 单向%%%神仙Maxwei_wzj
  • 可爱(?)的ComputerEngine 学弟
  • 安心退役的(?)wpy dalao
  • 把我按在地上锤的lizbaka julao
外校的Friends呢
  • %%% OItby
  • %%%神仙 冒泡ioa
  • %%%神仙attack204
  • allenyou
  • ChenHacker's Blog
  • Chhokmah姐姐() 的博客
  • CpZhao
  • stO神仙 gzy Orz
  • Woshiluo's Notebook
  • 可爱的suqingnian dalao
文章归档
  • 309
  • 65
  • 80,187
  • 23,375

COPYRIGHT © 2020 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

桂ICP备20002051号