C++

「置顶文章」联赛前的日记

Pre Info

题库

联赛题:(看下面总结)

Easy Mid Hard
无线网络发射器选址AC 花匠(背包) 借教室AC
生活大爆炸AC 摆花(背包)AC 关押罪犯
表达式求值AC 信息传递(暴力)AC mayan游戏
比例简化AC 联合权值(暴力)AC 斗地主
文化之旅(最短路)AC 子串
推销员 运输计划

难题:

UVa1635(数论) AC

Hankson(数论) AC 50

Cell(数论)

囤起来点题:

奇葩OJ系列:HRBUSTOJ-2010 哈尔滨理工大学

UESTC-251 电子科技大学

优先级队列:POJ 2010 POJ 2970 积水

好题:LA 3902

BZOJ: 1196(AC) 1271 1207(AC) 1816(AC) 1863 2282 //加粗的难题

POJ: 1505 2002 2018 2456 3104 3122 3258 3257 3273 3432 3579 3657

历年题目总结

2011普及组 2012普及组 2013普及组 2014普及组 2015普及组 2016普及组
数字反转EA 质因数分解E 计数问题E 珠心算E 金币E 买铅笔E
统计单词数EA 寻宝E 表达式求值EA 比例简化EA 扫雷E 回文日期E
瑞士轮MA 摆花M 小朋友数字 螺旋矩阵 求和 海港
表达式的值 文化之旅MA 车站分级 子矩阵 推销员M 0 魔法阵
2011提高组 2012提高组 2013提高组 2014提高组 2015提高组 2016提高组
铺地毯EA Vigenere密码E 转圈游戏EA 生活大爆炸EA 神奇的幻方EA 玩具谜题EA
选择客栈M 60 国王游戏M 火柴排队 联合权值MA 信息传递MA 天天爱跑步
mayan游戏H 开车旅行 货车运输 飞扬的小鸟H 5 斗地主H 30 换教室
计算系数EA 同余方程EA 积木大赛EA 无线网络EA 跳石头MA 组合数问题EA
聪明的质检员 借教室HA 花匠M 0 寻找道路EA 子串H 蚯蚓
观光巴士H 疫情控制H 华容道H 解方程 运输计划H 愤怒的小鸟

说明:[题目名称]-[E/M/H 难度级别]-[完成状态]

2011普及组 2012普及组 2013普及组 2014普及组 2015普及组 2016普及组
模拟 模拟
模拟 模拟 暴力
归并排序 动态规划
最短路 优先级队列
2011提高组 2012提高组 2013提高组 2014提高组 2015提高组 2016提高组
模拟 模拟 快速幂 模拟 模拟 模拟
维护区间最小值 高精度 公式推导 搜索
搜索 动态规划 搜索
杨辉三角 扩展欧几里得 模拟 暴力 二分 杨辉三角
二分+前缀和 最长不下降字序 最短路
搜索 搜索 图论

day1 - 13 days left

数论 - 二项式定理/杨辉三角

杨辉第n行递推公式:line[n][x] = line[n][x-1]*(n-x+1)/x

同余取模:加减乘 - 任何数均mod 除 - 不能mod

i.fac数组表示大整数 (方便除法运算)

ps 生成全部拓扑序需要将所有的入度为一的结点连在同一个新的结点后 从新的结点搜索 拓扑

AC:

Luogu 1313(杨辉三角 & 取模运算)

Luogu 2822 (杨辉三角 & 取模运算)

UVa 1635 (二项式定理 & fac表示大整数)

Luogu 2661(拓扑 & 暴力 & 搜索 & 模拟)

day2 - 12 days left

快速幂 & 矩阵快速幂 & 快速幂取模

搜索O(跑不出)会爆 P1351

fac gcd lcm

还有13天联赛,没回学校,希望老师不会打我…

AC:

Luogu 1351 (暴力 & 存图)

Luogu 1054 (模拟)

Luogu 2118 (尽情的暴力 & 模拟)

Luogu 2038 (暴力)

Luogu 1078 (最短路)

day3 - 11 days left

“ Mengbier 表示无力回天”

vector 和 前向星 存图 前向星没学明白啊啊啊啊(反正也用不上)

搜索强化,今天不捅咕dp

感谢国老师和机房大佬们关心,中午特地打来视频电话

能看懂别人的code和能自己写出来简直就是两码事啊 QAQ

20:05 准备憋一憋 salesman 求大佬指点 @机房小伙伴

结构体好处大大的——关键在于 数据的关联性(salesman逼我的)

为啥我想了好久,别人一个贪心就AC了???Mengbier 表示无力回天

AC:

Luogu 1351 (暴力 & 存图)Vector AC 50

Luogu 1219 (深搜)AC 87

Luogu 1226 (快速幂模版)

Luogu 1072 (数论)AC 50 [fac高精防TLE]

Luogu 2672 (优先级队列 & 贪心)AC 60 [别人写贪心过了 我的贪心就60 不开心]

《高中必刷题-数学选修2-1》我学过的部分 (逃

今日总结:一定要爱上结构体,暴力,贪心,暴搜。AC 60 + AC 60 > AC 100 + WA,天堂有路你不走,题海∞苦作舟,继续加油!

day4 - 10 days left

优先级队列优化的Dijkstra 下图秒懂(秒懂dijkstra)

macOS终于装上gdb了:brew install gdb

看大佬花式虐题 戳我

LA 3902 写不出来啊啊啊smg

继续练搜索

AC:

Luogu 1434 (记忆化搜索 | dp)

HDU 1874 (最短路)这道题特坑,编号是从0开始标的,导致我一直WA

HDU 2554 (最短路)题号记错了,反正就是一道很简单的最短路了,大家伙儿都会的

POJ 2010(二分 | 优先级队列)

day5 - 9 days left

dp学一上午没弄明白,我太弱了

vector存图算是弄明白了,开心😄 存图这方面本宝宝不愁了

下午遇到了一道题,写了半天存图,结果最后还是用了并查集

22:24 线性动归 -> 最长递减子序列问题 HRBUST 2010

耶耶耶,这个自己写出来了诶,开心~

AC:

Luogu 1077 (dp)

BZOJ 1196 (二分 & 并查集 | 最小生成树)

HRBUST 2010 (dp)

day6 - 8 days left

今天主要推dp,有了昨儿的LIS,应该好理解些了。

BZOJ 1207 是一道很好的题,真的很好。

(气愤)为啥Luogu最短路板题卡SPFA

不能颓不能颓。。。

AC:

BZOJ 1816 (二分判断)

BZOJ 1207 (dp)

Luogu 1358 (数论 & 杨辉三角)

Luogu 1551 (并查集模版)

Luogu 3367(同上,半夜水两题)

day7 - 7 days left

今日主要看 dp 和 并查集

并查集简化find()操作: int find(int x){return fa[x]=x?x:fa[x]=find(fa[x]);}

有时间做了 POJ3257 dp

简单说一下NOIP2012 借教室的思路:

/*
审题:“也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订
单无法完全满足,则需要停止教室的分配,通知当前申请人修改订单” 这句话是二分判断的依据,为了
保证操作次数尽可能的少,引进了一个变量[it]用来维护一段区间内的订单数目。
*/

AC:

HDU 1232 (并查集模版)

Luogu 1083 (二分&前缀和)NOIP 2012 借教室

Luogu 1020

day8 - 6 days left

2011 d1t2 选择客栈 AC 60

2014 d1t3 飞扬小鸟 AC 5

以上2小时完成

Linux 环境测试,GUIDE 和 GDB调试

试机可以写一个SPFA,无向图,数据如下:结果cd /Users/YZB/Head/Brains/Memory/2017/OI/Algorithm/SPFA/Model/testdata/testdata.out

5 7 1
1 2 4
1 3 29
3 2 6
2 5 3
3 5 4
4 5 6
1 4 4

day9 - 5 days left

2014 d2t2 寻找道路 AC

2013 d2t2 花匠 WA

以上2小时完成

AC:

POJ 1505 (二分答案)

卡了好久 销售员 那道题 没爱。

周末愉快~

day 10 - 4 days left

今天上午洛谷挂了。。。

AC:

rqnoj 73 (搜索)

Luogu 1433 (搜索)

Luogu 1036 (搜索)

day 11 - 3 days left

今天处理一下读入,天啦噜,读入优化居然没scanf快,是我瞎了吗。

今天终于AC油滴拓展,好开心!(BJS 22:28)

AC:

HDU 5492

Luogu 1378 (搜索)

day 12 - 2 days left

继续练习回溯和广搜。

AC:

Luogu 1596 (BFS模版)—10min

Luogu 1020 (dp)

Luogu 1019

day 13 - 1 days left

练习Dijkstra,其实我觉得在比赛前看不会的算法不好,没错,我现在的确不会Dij…

AC:

一些水题

沉着,冷静,没有思路上厕所

请记住,NOIP 不怕暴力,怕瞎算,不怕不会,怕不敢

在 NOIP 里面,30 分绝不是小数目

请一定要分模块调试,不要从头跟到尾

分享到