我是一个高二的OIer,离我正式退役的日子已经不超过一年了.在这个时期,与其写一些回忆性的文字,不如跳出"自我"的范畴,以一种比较全局的角度和大家一起分享一些我对OI的认知和看法.目的是让初三高一的学弟学妹看清眼前的路,让高二高三的人了解自己走过的足迹. 一.独特的模式 知识的更新 我们先从OI的比赛日程谈起.选手获得NOIP一等奖后,可以报名参加WC(时间为1-2月).而在5月,选手即使没有通过省选进入省队,也可以报名参加CTS(C).其中WC和CTS(C)不仅是信息集训队的两轮选拔

分治虽然是基本思想,但是OI中不会出裸分治让你一眼看出来,往往都是结合到找规律里面. 先来个简单的: 奇妙变换 (magic.pas/c/cpp) [问题描述]   为了奖励牛牛同学帮妈妈解决了大写中文数字的问题,牛牛妈妈特地抽出一个周末的时间带着牛牛来到梦幻儿童乐园游玩.   在游乐园,牛牛看到了一个非常有意思的游戏:游戏一开始,电脑屏幕上只有一个序列“A”,而后的每一次变化都把序列中的“A”变成“AB”,“B”变成“A”.游戏一直继续„„,最后屏幕上得到了序列“ABAABABAABAABAB

前言 矩阵是高等代数学中的常见工具,也常见于统计分析等应用数学学科中,矩阵的运算是数值分析领域的重要问题. 基本介绍 (该部分为入门向,非入门选手可以跳过) 由 m行n列元素排列成的矩形阵列.矩阵里的元素可以是数字.符号或数学式. 比如一个$m\times n$的矩阵可以表示为: $$ A=\begin{bmatrix}a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\

OI中常犯的傻逼错误总结 问题 解决方案 文件名出错,包括文件夹,程序文件名,输入输出文件名  复制pdf的名字  没有去掉调试信息  调试时在后面加个显眼的标记  数组开小,超过定义大小,maxn/maxm搞错? 注意要开双向边的,状态1<<x,相同大小的数组开一起,不要小敲一个0  inf开小/大  极限数据验证 多组数据部分变量容易忘记清空  有多组数据一定要认真查看每一个参与的变量是否需要清空 if后面加分号   不要急  DP.贪心之类的题,最好要拍一拍,不要过度自信  对拍很重要!

序言 这本来是用Word写的,但是后来我换了系统所以只能用markdown迁移然后写了...... $\qquad$本文主要投食给那些在Windows下活了很久然后考试时发现需要用命令行来操作时困惑万分以及觉得GDB很好吃的人 $\qquad$以及---- $\qquad$经常眼瞎看不见i++和j++的区别 $\qquad$经常访问a[-1]然而使编译器无可奈何(除非在使用O2的情况下的明显访问越界)的人 ... $\qquad$正式地说,本文介绍GCC&&GDB命令在OI中的应用. 提要

OI中的莫比乌斯反演 莫比乌斯函数 想要学习莫比乌斯反演,首先要学习莫比乌斯函数. 定义 莫比乌斯函数用\(\mu(x)\)表示.如果\(x\)是\(k\)个不同质数的积,则\(\mu(x) = (-1)^k\),否则\(\mu(x) = 0\)(此时\(x\)一定是某个或某些平方数的倍数).\(x = 1\)时,相当于\(x\)由\(0\)个不同质数组成,所以\(\mu(1) = 1\). \[ \mu(x)=\left\{ \begin{array}{rcl} 1 & & {x = 1

在OI中,题目有三类: 传统题 交互题 提交答案题 今天来了解一下第三类 概述 传统题:给你一个题面,你需要交一个程序,评测姬会用你的程序运行你看不到的一些测试点,用输出和正确答案比较 提交答案题:给你一个题面,把一堆输入也给你发下来,你通过各种玄学把输出算出来,再把输出交上去. 一般还会发一个checker来帮助你测试分数 有时还会把题目原来的游戏发下来供你颓废理解题意 为什么有这种题 我们可以猜想一下: 评测姬可能一时半会儿跑不出来 可能一个程序解决不了 可能要让你知道输入你才做得出来 特点

OI中组合数的若干求法与CRT 只是下决心整理一下子呢~ 说明:本篇文章采用\(\binom{a}{b}\)而不是\(C_{a}^b\),以\(p\)指代模数,\(fac_i\)指代\(i!\),\(inv_i\)指代\(i\)在\(\mod p\)下的逆元,\(invf_i\)指代\(i!\)在\(\mod p\)下的逆元. 一般性的组合数求法 计算式: \[\binom{m}{n}=\frac{m!}{n!\times (m-n)!}\] 一. 杨辉三角法 \[\binom{m}{n}=\b

OI中字符串读入和处理 在NOIP的"大模拟"题中,往往要对字符串进行读入并处理,这些字符串有可能包含空格并以\n作为分割,传统的cin >> scanf() 等等,不可能达到要求,因为这些都是以\n space (空格) \t (Tab) \r 作为分割符. 通用处理方法 所以要处理字符串输入时,要以getline()作为输入,输入后构造为[字符串流],然后可以进行[分割]后进行任意处理.这是比较通用的做法,几乎可以适应所有情况. #include<vector&g

众所周知,OI中其实就是算法竞赛,所以时间复杂度非常重要,一个是否优秀的算法或许就决定了人生,而在大多数情况下,我们想出的算法或许并不那么尽如人意,所以这时候就需要一中神奇的的东西,就是底层优化: 其实底层优化比较简单,比如我们经常使用的 register还有快读,这些都可以进行优化.还有fread,但是fread在一些情况(尤其是在重要的的比赛时)但是还是给出下面的优化 <<|; char buffer[L],*S,*T; #define getchar() ((S==T&&

快速傅里叶变换(FFT)                                                                               ---- LLppdd 前言 关于这篇文章     非常高兴能有机会来探讨快速傅里叶变换,也就是大家熟知的 \(FFT\) 在 \(OI\) 中的运用.以前了解过一次 \(FFT\) ,现在过了几个月,数学和 \(OI\) 水平都有了一定的进步之后,再回过来重新思考它,应该有了更深的了解,所以准备写一篇较为详细的文章

感觉这题真的特别有意思,涉及了 OI 中很多非常有意思.非常美的手法,比如--平衡两部分的时间复杂度.\(n \ln n\) 的那个 Trick等等,真的一种暴力的美学. 题目大意: 多组询问,求 \(f_{n,m}=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \varphi(i\cdot j)\),\(1 \le n,m \le 1e5\),\(T \le 1e4\). 解法: 这里用一个套路一点的式子:\(\varphi(i\cdot j)=\frac{\v

Preface 可并堆,一个听起来很NB的数据结构,实际上比一般的堆就多了一个合并的操作. 考虑一般的堆合并时,当我们合并时只能暴力把一个堆里的元素一个一个插入另一个堆里,这样复杂度将达到\(\log(|A|)+\log(|B|)\),极限数据下显然是要T爆的. 所以我们考虑使用一种性价比最高的可并堆--左偏树,它的思想以及代码都挺简单而且效率也不错. 学习和参考自这里 What is Leftist Tree 左偏树,顾名思义就是像左偏的树,但是这样抽象的表述肯定是不符合我们学OI的人的背板子

以下是我个人OI生涯中遇到的坑点的一个小总结,可能是我太菜了,总是掉坑里,请大佬勿喷 1,多重背包的转移的循环顺序 //默认每个物品体积为一(不想打码……) //dp[i]表示占用背包容量i所能获得的最大价值 ;i<=n;i++) ;j--) //sum表示背包最大容量 ;k<=num;k++) //num表示这个物品的数量,k表示选取当前物品k件 if(j>=k) dp[j]=min(dp[j],dp[j-k]+value); 简单的多重背包模板,对于学过的人,大概清晰易懂吧 //dp

数据结构 在维护树上路径时,如果只是点的独立的加减,可以考虑用括号序来维护(拆成两部分) 需要求树上很多路径中k近/距离和 一类,考虑点分治/在点分树上解决. 子树求和可以转化为DFS序上区间求和 树状数组可以区间查询/修改(差分) 需要查询序列上区间数据结构,只要满足总和是可以接受的范围,可以用线段树,每个区间维护一个这样的数据结构(例如AC自动机等) 多维偏序问题,排序可以降维,CDQ分治可以降维,剩下只需要树状数组/线段树 树上连通块有概率出现,再加上和的次方,往往可以拆开来,变成任意选K

LINK:梦中漫步 当然也可以去一本通的Oj/loj上交(loj可能没有.. 期望好题.期望和dp往往是在一起的. 前置知识:1. 期望是线性可加的.2.和的期望等于期望的和. 从u出发每次随机选一条边走 问走到v的期望经过的边数. 寒假的时候就在思考这道题了 当时yy了一个LCA乱搞的方法 wa的不省人事. 重新分析:考虑设\(f_i\)表示从u出发到i这个点的期望经过的边数. 列出转移 发现转移有环 暴力高斯消元 显然不可行. 刚才列出的两个知识 和的期望等于期望的和. 这个东西告诉我们 u

The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants. Given any two nodes in a binary tree, you are supposed to find their LCA. Input Specification: Each input file contains one test

不行啊最近备考简直变成文化狗了= =..我还脑洞大开想学俄语什么心态.. 简单地说一下FFT(来,跟我一起念,法〰法〜塔,法斯特~福铝页~圈死佛而母).. FFT本来是做信号变换用的,当然OI和信号变换搭不上边.但是大家都知道,FFT可以快速求卷积.这可以说是由复数的性质决定的. FFT是什么 FFT,是DFT的一种实现.它可以在$\Theta \left( n\log_2{n}\right)$(其中n为输入规模)时间内完成DFT. 也就是说,FFT是DFT的一种具体实现.因此,与其问FFT是什

作为一位OIer,代码调试的能力必不可少. 今天梳理一下自己进行代码调试的方法,下面只是一些个人的总结. 代码的评价有三部分: 正确性 强健性 高效性 检查也应该从这三部分出发. [正确性] 打完代码,直接运行一遍样例和一些自己准备的数据,若答案不对,则进行以下检查: ①直接检查一遍自己的代码 ②如果还是找不到问题,就开始动态调试 样例和准备的数据都正确了,然后再总体地观览一遍整个代码,这样答案的正确性就不容置疑了. [强健性] 强健性检查的就是一些常出现的问题,这需要平时的积累.暂时的积累有:

传说,Pascal中有一个函数——fillchar.这是高手们装*用的利器,也是大家的神器(大家好才是真的好). 神器介绍: 百度百科说:“Fillchar是Turbo/Borland Pascal的System单元的一个标准过程,它的使用格式是:FillChar(var X; Count: Word; value),它的功能是,把指定变量X在内存段中所占的低Count个字节赋为相同的值value, 其中value是填充的值,只能是Byte.Char或Boolean等单字节类型的值.在Free

为什么我的Floyd会输出负数啊? 为什么我的代码写对了却全都爆零了啊? 那么很可能是你的INF取大/小了! 那么inf到底应该取什么值呢? 首先,inf应该要比一般的题目中出现的数据要大,但是又不能超过max_int. 1e9是一个好选择! 为什么不是0x7fffffff呢?这不是int的最大值吗 因为有的时候(例如Floyd等算法)会出现两个inf相加的情况,如果inf取max_int则加法会造成溢出,而取1e9则不会出现这样的情况. 但是初始化会不会很麻烦? 答案是肯定的,谁都不愿意为了一