dqcsm1964-CSDN博客

转载 NOIP 提高组取得480分以上的成绩有多难?

不知道为什么LZ以480作为一个分界线。我觉得NOIP一定程度上也可以反应选手（包括NOI选手）的思维水平和代码能力。第零个分界线是1=，1=（ZJ除外）凭实力凭运气都可以拿。二者有一即可。第一个分界线是400有能力拿400+的选手，可以说初步达到了算法竞赛入门，不是靠运气，对程序设计有一定自己的想法，可以稳拿一等。正常人类只要有稍微靠谱的指导+大量时间的训

2017-11-09 15:43:52 15096 2

转载 IOI 金牌再传秘笈：水平不高怎么拿NOIP一等奖？

Part I. 赛场策略与技巧* 首先，如果你的水平已经远超NOIP，自然是想怎么考怎么考了。* 同理，如果你什么都不会，那么策略再好也是没用的。* 因此，下面说的策略、技巧主要是针对水平中等，游走在分数线附近的同学们的。赛场策略的最终目标就是一句话：多拿分。这是考试，为了分数应当使用任何你能想到的手段。(当然作弊啥的除外......)

2017-11-09 15:35:05 5831

转载 NOIP复赛复习（十八）反转问题与弹性碰撞

一、反转问题算法概览：给定一个01串，现有翻转规则：翻转某一个位置时其后面2个位置也会跟着翻转，也就是每次翻转都会翻转3个连续的位置。要将01串全部翻转为0，求最小的翻转次数。形似这类题的问题叫做反转问题，也可以叫开关问题，对于这类题通常有以下的特点，思考一下就可以想到。 1、若某一个位置被翻转了n次，则其实际上被翻转了n%2次，因为翻转2k次相当与没翻转，翻转2k+1次相当于翻

2017-11-06 14:00:06 712

转载 NOIP复赛复习（二十）剪枝与坐标离散化

一、剪枝在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。剪枝算法按照其判断思路可大致分成两类：可行性剪枝及最优性剪枝。 POJ2676给你一个9*9的九宫格，有部分已经填上了数字，要求将九宫格

2017-11-06 13:59:07 421

转载 NOIP复赛复习（十九）栈与双端队列的运用

一、栈的运用通过活用栈等简单的数据结构，可以巧妙地降低一些算法的复杂度。POJ 2559题意：n个宽度为1，高度为h[i]（1）组成的柱形图，求里面包含的长方形的最大面积；思路：如果确定了长方形的左端点L和右端点R，那么最大可能高度就是min{h[i]|L（一般做题区间都是左闭右开，便于计算），时间复杂度O(n^3)，考虑优化区间最小值，可以降为O(n

2017-11-06 13:58:08 454

转载 NOIP复赛复习（十七）尺取法与折半枚举

一、尺取法尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以尺取法是一种高效的枚举区间的方法，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情

2017-11-06 13:57:06 454

转载 NOIP复赛复习（十六）预处理与前缀和

一、预处理所谓预处理，顾名思义，就是事先计算好需要的值或事先处理某些东西，有时候你会发现你做一个题目出现了TLE，原因就是重复的计算会导致效率不高（或者说你的预处理不够“优雅”）。 A、直接把结果预处理XTUOJ 1052题意：某一个数字集合定义如下：1.0属于这个集合；2.如果x属于这个集合，那么2x+1,3x+1也属于这个集合；

2017-11-06 13:55:56 512

转载 NOIP复赛复习（十四）字符串算法巩固与提高

一、Trie树 1.定义：通过字符串建成一棵树，这棵树的节点个数一定是最少的。例如：4个字符串"ab","abc","bd","dda"对应的trie树如下：其中红色节点表示存在一个字符串是以这个点结尾的。一个性质：在树上，两个点u,v满足u是v的祖先，那么u代表的字符串一定是v代表的字符串的前缀。 2.Trie树的插入：可

2017-11-05 19:18:31 700

转载 NOIP复赛复习（十一）基础算法巩固与提高

一、倍增算法：定义：用f[i][j]表示从i位置出发的2j个位置的信息综合（状态）一个小小的问题：为什么是2j而不是3j,5j,…？因为，假设为kj，整个算法的时间复杂度为(k-1)logk，当k=2时，时间复杂度最小。这个算法的三个应用： 1.倍增ST表：应用：这个ST表是用来解决RMQ问题（给你n个数，m次询问，每次询问[l,

2017-11-05 19:16:51 481

转载 NOIP复赛复习（十二）数论算法巩固与提高

一、数论 1.数整数、自然数（大于等于0的整数）、正整数（大于0的整数）、负整数、非负整数、非正整数、非零整数、奇数偶数。 2.整除性设a,b∈Z，如果存在c∈Z并且a=bc，则称b|a（b为a的因子，“|”表示“能整除”） 3.质数如果一个数，只有1和自身作为因子的数，叫做质数（素数）。

2017-11-05 19:12:55 873

转载 NOIP复赛复习（十五）动态规划巩固与提高

经典例题：数字金字塔（Luogu 1216）写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。我们现在这里讨论搜索如何实现：状态：目前在第x行第y列行动：向左走，向右走例如：一个底边为4的三角形共有八种状态：我们按照一般的搜索思路，进行深度优先搜索

2017-11-05 19:09:49 985

转载 NOIP复赛复习（十三）图论算法巩固与提高

一、图的存储 1、邻接矩阵假设有n个节点，建立一个n×n的矩阵，第i号节点能到达第j号节点就将[i][j]标记为1（有权值标记为权值），样例如下图： /*无向图，无权值*/int a[MAXN][MAXN];//邻接矩阵int x,y;//两座城市for(int i=1;i{

2017-11-05 19:07:00 756

转载 NOIP复赛复习（一）常见问题与常用策略

数学类问题1. 精度处理（高精度、实数处理、各种浮点类型处理方法）2. 组合数学问题（斐波那契数列、第二类数、卡特兰数、Polya原理、排列组合计数、加法原理与乘法原理）3. 进制问题（特定二进制串的统计、二分查找、利用二进制进行路径、状态描述、二进制转换）4. 递推与递归关系（递推关系式、通项公式、数列、博弈问题）5. 数位、数字、特定数值的查找、统计（数

2017-11-02 08:58:10 2713

翻译 NOIP复赛复习（二）竞赛环境与注意事项

一、比赛不提供纸质试题，只提供电子版试题文件。该文件压缩包保存在计算机桌面上。监考人公布密码后，选手自行解密试题。试题解压密码会影响一个人的心情，一定要一次输对，注意大小写，不要边输入边检查，要对自己有自信。二、黑龙江复赛选手上机为windows操作系统。中国计算机学会将使用NOI linux下的Arbiter评测系统进行评测。Linux与Win

2017-11-02 08:49:14 3398

转载 NOIP复赛复习（三）文件读写与数论模板

文件读入读出假设题目名为“add”，那么文件夹名为“add”，c++程序名为“add.cpp”，读入文件名为“add.in”，输出文件名为“add.out”。四个的拼写均不可有误，包括大小写差异。千万不要调试后就忘记修改文件读入读出了。 #includeint main(){ freopen("add.in","r",stdin);//read fr

2017-11-02 08:46:39 1490

转载 NOIP复赛复习（四）读写外挂与高精度模板

读入输出挂读入输出挂就是逐个字符地读入数据，从而让读入更加快速。输出挂的原理也是一样的，都是通过将输出数字变成输出字符以加快速度。当然输入输出外挂一般用在大量输入输出的情况下，这样性价比才高一些，否则得不偿失。void Rd(int &res){ res=0;char p; while(p=getchar(),p do{

2017-11-02 08:42:37 437

转载 NOIP复赛复习（五）程序对拍与图论模板

程序对拍所谓“对拍”，顾名思义，就是让两者相互比对。所谓“两者”，一是你要测试的程序，二是一个答案在该程序在一定范围（时间/空间）内结果必定正确的程序（一般是用暴力求解的程序）。对拍一般需要造数据程序（data.exe），保证正确性的暴力对拍程序（test.exe）与测试程序（以moo.exe为例）。下面是对拍的代码，写在txt中再转成.bat即可。:loopdata.ex

2017-11-02 08:35:34 830

转载 NOIP复赛复习（六）算法分析与排序模板

算法分析算法分析的目的是预测算法所需的资源，如计算时间（CPU 消耗）、内存空间（RAM 消耗）、通信时间（带宽消耗）等，以及预测算法的运行时间，即在给定输入规模时，所执行的基本操作数量，或者称为算法复杂度。算法的运行时间取决于输入的数据特征，输入数据的规模和运行时间的上限（因为运行时间的上限是对使用者的承诺）。算法分析一般忽略掉那些依赖于机器的常量，而关注运行时间的增长趋势。一般

2017-11-02 08:33:45 497

转载 NOIP复赛复习（七）STL容器与字符串模板

STL容器STL 容器是一些模板类，提供了多种组织数据的常用方法。常用的STL容器包括pair（组合）、list（列表，类似于链表）、vector（向量，类似于数组）、priority_queue（优先队列）、set（集合）、map（映射）、stack（栈）等，通过模板的参数我们可以指定容器中的元素类型。1、pair相当于一个Struct，访问方式举个例子：pa

2017-11-02 08:32:02 377

转载 NOIP复赛复习（八）STL算法与树结构模板

NOIP复赛复习（八）STL算法与树结构模板STL算法STL 算法是一些模板函数，提供了相当多的有用算法和操作，从简单如for_each（遍历）到复杂如stable_sort（稳定排序），头文件是：#include 。常用STL 算法库包括：sort快速排序算法、二分查找算法、枚举排列算法等。1、 sort排序系列sort：对给定区间所有元素进行

2017-11-02 08:29:35 498

转载 NOIP复赛复习（十）怎样才能拿到高分？

摘要考场策略和程序测试是信息学竞赛中非常重要的环节，很多优秀的选手在很多比赛中总是会在这两个环节上犯下这样和那样的错误，导致得到的分数和实力不成正比，最后留下了无尽的遗憾。本文将探讨一些这两个环节上值得注意的地方，提出一些可行的方法，分享一些经验，以此希望帮助选手们在比赛中发挥水平，减少失误，告别遗憾。前言信息学竞赛本身是一个美好的东西，她包含着奋斗、努力、追求、

2017-11-02 08:26:21 2297

转载 NOIP复赛复习（九）如何设计测试数据？

有些同学参加一次信息学比赛之后，自我感觉非常不错，但是测评结果成绩却并不理想。造成这种情况的原因有多方面，但是我认为其中不可忽视的一大原因就是在写完程序之后，他们并不知道如何保证程序的正确性。在这里，我就这个问题提出一点自己的看法。先从考试的时间分配问题讲起。很多同学觉得考试时间很充分，NOIP有三个小时，写完4个程序绰绰有余（编者注：目前普及组复赛为一场3.5小时4题，提高组复赛为两场，

2017-11-01 09:27:52 1145

dqcsm1964的博客