信息学竞赛的常见题型与解题思路

2011年安联杯安徽省青少年信息学奥林匹克竞赛 小学组试题

安徽 安庆 2011.4.1612011年安联杯安徽省青少年信息学奥林匹克竞赛

小学组试题

AOI 2011

比赛时间：2011年4月16日08:00至12:00

题目名称三次方求和最高得分字母项链源文件名cubsum.pas/c/cppmaxvalue.pas/c/cppnecklace.pas/c/cpp输入文件名cubsum.inmaxvalue.innecklace.in输出文件名cubsum.outmaxvalue.outnecklace.out试题类型传统型传统型传统型满分100100100是否有部分分否否否时限1秒1秒1秒内存限制128M128M128M

注意事项1.务必看清题目，严格按照所要求的格式输入、输出。2.在调试程序时请先使用题目中的示例数据，然后再自行设计多组测试数据进行调试。3.测试有严格的时间限制，请尽可能优化算法。4.命名规则：(1)每题都规定了该题的英文名称。(2)程序文件和数据文件的主文件名都是该题的英文名字。(3)程序文件扩展名采用语言环境的默认扩展名。(4)数据文件都是文本文件，输入和输出文件的扩展名分别是.in和.out。5.程序应从输入文件读取数据，并严格地按照规定的输出格式将结果输出到输出文件中。输入数据文件和输出数据文件都与程序在同一个目录中，由于程序所在目录是不确定的，因此不允许在程序中含有盘符信息和任何形式的路径信息。6.选手在竞赛结束时应在D盘根目录下建立以参赛号命名的文件夹，并将所完成各题的源程序文件放到该文件夹中。测试以评测组编译的可执行文件为准，测试系统使用的是标准的编译指令处理源程序，没有附加任何编译选项，请选手按照考试机器上语言环境的默认配置来编译调试自己的程序。

2011年安联杯安徽省青少年信息学奥林匹克竞赛 小学组试题

安徽 安庆 2011.4.162题目

1.三次方求和（cubsum）

信息学奥林匹克竞赛试题题型归类与总结

数学类问题

 精度处理（高精度、实数处理、COMP、EXTENDED、REAL类型处理方法）

 组合数学问题（Fibonacci数列、第二类数、卡特兰数、POLYA原理、排列组合计数、加法原理与乘法原理）

 进制问题（特定二进制串的统计、二分查找、利用二进制进行路径、状态描述、二进制转换）

 递推与递归关系（递推关系式、通项公式、数列、博弈问题）

 数位、数字、特定数值的查找、统计（数值处理、质因子分解、幂次分解、数值表达式、添加运算符、分式与实数运算）

 数学杂题（回文数字、矩阵处理、约瑟夫与反约瑟夫问题）

 数学剪枝（无解判定、解线性方程组、限定搜索范围）

 相关公式、定理、原理的应用

 寻找规律、归纳整理递归与递推关系式

 按照数学方法构造、二进制转化等技巧性处理

 注意事项：

 规律准确（小数据手工推算、搜索程序验证）

 数据类型是否合理、数据范围是否超界（大数据处理）

字符、字串处理类问题

 读入、分离和统计问题（文件结束符、行结束符、空格符、回车符、字符组合分离、统计）

 插入、删除、修改、替换等相关编辑问题（字符距离、优美编辑、初始状态与目标状态的变换、迭代等处理性问题）

 KMP算法及其改正

 回文串、高精度运算及其以字符（串）作为处理对象的相关问题

 一般性字符处理

 动态规划方法

 字符树（查找、树的前序、中序、后序遍历）

 注意事项：

 读入时小心（READ、READLN语句及结束标记）

 字符串类型与字符数组存贮及其压缩存取

统计类问题

 方案总数统计（矩阵、三角形划分方案统计、问题解集个数统计）

 特定、离散元素统计（机场跑道、01统计、天外来客等二进制统计问题）

 横向、纵向规模化问题（数据范围、数据维数巨大）

 离散化问题（卫星覆盖、图形周长）

 一般性统计问题（时间复杂度（自创试题））

一本通信息学奥赛2059

信息学奥赛是近年来备受关注的一项竞赛活动，它旨在培养学生的信息学素养和创新精神，激发他们对计算机科学的兴趣和热情。近日，我们看到了一本通信息学奥赛2059的考题，令人过目不忘。本文将对这些题目进行一一分析，以期帮助大家更好地了解并应对这一挑战。

1.第一道题目是关于二进制数的转换和运算。题目要求将十进制数转换为二进制数，并进行加法和减法运算。这是信息学奥赛中常见的知识点，考生需熟练掌握。

2.接下来是关于数学逻辑的问题。考生需要解答一系列命题的真假性，并进行逻辑运算。这需要灵活思维和清晰逻辑思维。

3.第三题是关于图论的问题。考生需要通过邻接矩阵或邻接表表示图，并进行相关运算和分析。这是信息学奥赛常见的一类题型。

4.第四道题目是动态规划的问题。考生需要设计一个动态规划算法来解决一个实际问题。这需要考生对动态规划算法的理解和应用。 5.第五题是关于字符串匹配的问题。考生需要使用字符串匹配算法来解决一个实际问题。这需要考生对字符串算法的熟悉和应用。

6.第六题是关于树结构的问题。考生需要设计一个树的数据结构，并实现相关操作。这是信息学奥赛的一个常见题型。

7.第七题是关于排序算法的问题。考生需要设计一个排序算法来解决一个实际问题。这需要考生对各种排序算法的理解和应用。

8.第八题是关于图像处理的问题。考生需要设计一个图像处理算法来实现一定的功能。这需要考生对图像处理的理解和应用。

9.第九题是关于数据库设计的问题。考生需要设计一个数据库结构，并实现相关的操作。这是信息学奥赛的一个重要题型。

10.第十题是关于网络编程的问题。考生需要设计一个简单的网络编程程序，并实现其功能。这需要考生对网络编程的理解和应用。

11.第十一题是关于算法分析的问题。考生需要分析一个给定的算法的时间复杂度和空间复杂度。这需要考生对算法分析的理解和掌握。

12.第十二题是关于线性代数的问题。考生需要解答一系列关于矩阵和向量的问题。这是信息学奥赛中的一个重要知识点。 13.第十三题是关于数论的问题。考生需要解答一系列关于素数和因子的问题。这需要考生对数论知识的熟悉和掌握。

信息学竞赛中的⼀些经典思维（题）

倍增

倍增字⾯上意思是：成倍地增加。当模拟⼀个过程时，⼀步⼀步进⾏太慢，考虑把模拟的步数⼆进制分解；经过⼀些预处

理，每次可以模拟 2i 步，从⽽达到优化复杂度的⽬的。

倍增主要模型有RMQ，LCA等。

例题

给出⼀个长度为 n 的环和⼀个常数 k，每次可以从第 i 个点跳到第 (i + k) mod (n+1) 个点，总共跳 m 次。第 i 个点的权值为

a[i]，求 m 次跳跃的起点的权值之和 mod 1e9 + 7 。

数据范围：1≤n≤106,1≤m≤1018,1≤k≤n,0≤a[i]≤109

问题分析

这⾥显然不能暴⼒模拟跳 m 次。因为 最⼤可到 1018 级别，如果暴⼒模拟的话，时间承受不住。

所以就需要进⾏⼀些预处理，提前整合⼀些信息，以便于在查询的时候更快得出结果。如果记录下来每⼀个可能的跳跃次数

的结果的话，不论是时间还是空间都难以承受。

倍增思想：每个数都可以表⽰成⼆进制的形式， 对于从每个点开始的 2i 步，记录⼀个 go[i][x] 表⽰第 x 个点跳 2i 步之后的终

点，⽽ sum[i][x] 表⽰第 x 个点跳 2i 步之后能获得的点权和。对于跳 2i 步的信息，预处理的时候可以看作是先跳了 2i−1 步,

再跳了 2i−1 步。

即有 sum[i][x]=sum[i−1][x]+sum[i−1][go[i−1][x]]，且go[i][x]=go[i−1][go[i−1][x]] 。

例如，从1到14的整个跳跃过程由 23+22+20 三步组成。也就是说，对于环上这 n 个位置，预处理出每⼀个位置向前跳 1,

2, 4, ... 次的位置，则必然能够到达 m。

实现代码

#include

using namespace std;

const int mod = 1000000007;

int modadd(int a, int b) {

if (a + b >= mod) return a + b - mod; // 减法代替取模，加快运算