本文收录了北京青少年科技教育协会主办的北京中小学信息学能力测评活动(BCSP-X)考试初中组的四套编程题样题。
商品降价
要求描述
为了实现在家里躺着挣钱的梦想，小 A 在某网站开了几家店铺。为了举行开业酬宾活动，小A 决定把所有原价为偶数位的商品降价为奇数位，例如，原价 1050现在只卖 998。
可是，店里卖的东西实在太多了，他需要统计一下现在店里有最多多少种商岛价格是偶数位的。他把这个问题交给了你。
已知小A有T家店铺，每家店铺商品价格在某个区间内。具体而言，这个问题可以转化为：给定整数T代表有T组样例，每个样例由两个端点 A和B组成，表示需要在区间［A,B］内计算符合以下条件的整数个数：数字的位数为偶数。
例如，在区间［1.100］内，符合条件的整数为10、11、12….99，共90个。它们的数位都是2位（2是个偶数）。
输入
首先是第一行一个整数T，代表有T组样例。
接着每个样例的一行包含两个正整数 A,B描述了区间的左右端点。
数据范围
- 对于 20%的数据保证：T≤10,1≤A=B≤1000000000
- 对于 30%的数据保证：T≤10, 1≤A≤B≤1000000
- 对于 80%的数据保证：T≤10, 1≤A≤B≤1000000000, B-A≤1000000
- 对于 100%的数据保证：T≤10, 1≤A≤B≤1000000000
输出
输出T行，每行一个整数代表答案。
道路网络
要求描述
为追求城市的发展，A 城决定建设新的道路网络，这项规划计划建设 n 条道路。然而，每条道路的建设过程都面临着额外的挑战，因此为了保证项目的正常完工，需要准备充足的资金。
在道路的建设中，每当施工中的道路与已经建成的道路交汇时，必须搭建桥梁防止影响修建好的道路正常运行。而这个额外的建设环节，将产生额外的开支，需要注意的是，由于道路情况不同，因此每条道 路所需要建设的桥梁都有其独特的建设花费， vi 代表了在与已建成道路交汇时所需投入的资金。
我们将需要建设的区域视为一个大小无限的平面坐标系。这里的 n 条道路可以看作 n条不重合的直线 （这些直线有可能平行），每条直线都经过特定的点 (xi, yi) ，并具有一定的斜率ki 。市政府需要制定预算，确保在最坏的情况下也能够完成新区道路建设。现在需要你提前计算出最坏的情况所需要的资金， 以便于市政府提前准备好充足的资金完成该项目的建设。
输入
第一行一个整数 n 代表道路的数量。
接下来 n 行每行四个整数xi,yi,ki,vi 。
对于第 i 条道路，xi,yi 代表道路经过的点的坐标，ki 代表道路的斜率，vi 代表建桥产生费用。
数据范围
对于 10%的数据保证：
1≤n≤10，1≤k≤100000，1≤v≤100000
对于 40%的数据保证：
1≤n≤1000，1≤k≤100000，1≤v≤100000
对于 60%的数据保证：1≤n≤100000，1≤k≤100000，1≤v≤100000
对于 100%的数据保证：
1≤n≤100000，-100000≤k≤100000，1≤v≤100000，-100000≤x,y≤100000
输出
输出一行一个整数代表答案。
神奇的字典
要求描述
神秘的海底九万里处有一个鱼人国度，鱼人们非常聪明，会制作武器捕猎，也会利用海草和小海星圈养自己的食物（各种各样的鱼）。但是鱼人们有一个最大的缺陷：语言不通！
因此鱼人国度的国王决定要兴起一波学英文的潮流，用英文来替代“咿咿呀呀”的嚎叫。
但是对于鱼人们来说，英文实在太难了。你作为鱼人国英文最好的鱼，被国王任命制作一本字典，来帮助鱼人国的国民们进行英文的查询及学习。
字典包含 w 个由小写字母构成的单词（鱼人没有大写字母），每个查询字典的鱼人会给出一个由字符串 s 和正数 k 构成的询问，需要字典自动弹出在 w 个单词里，字典序排序第 k 位，且前缀为 s 的单词在字典中的位置。若不存在，则输出-1。
输入
第 1 行为两个正整数 w，n。分别表示单词的数量和鱼人询问的次数。
第 2 行到第 w+1 行，每行输入一个字符串，表示字典中的一个单词。
最后 n 行，每行输入一个整数 k 和一个字符串 s，表示鱼人的一次询问。
数据范围
对于 20% 的数据，有 w<=200,n<=100,每个单词长度不超过 100。
对于 60% 的数据，有 w<=5000,n<=200,每个单词长度不超过 200。
对于 100% 的数据，有 w<=30000,n<=1000,每个单词长度不超过 1000。
输出
输出 n 行，每行一个整数，表示查询结果。
最强塔防
要求描述
古埃及法王有着一个巨大的宝库，里面珍藏着无数价值连城的珠宝。由于觊觎宝库的坏蛋很多，因此法王邀请你帮他设计一个环形的防守圈，来抵御强盗的入侵。他想在宝库周围均匀地布置上 n 个炮塔（注意：由于是环形，首尾相接，第一个炮塔和第 n 个炮塔是相邻的），塔防的位置很重要，每个位置适合摆的炮塔都不一样，也就是说每个位置摆放不同的炮塔获得的战斗力是不同的。
如第一个位置摆放三种炮塔获得的战斗力分别是：1，3，2，此时摆放中射炮获得的战斗力最高；而第二个位置摆放三种炮塔获得的战斗力分别是：3，1，2，此时摆放低射炮获得的战斗力最高。
我们的军火库中有三种炮塔，分别为低射对地炮，中射迫击炮以及高射对空炮。法王希望这一圈炮塔摆的很有层次感，所以任何一个位置的炮塔要比它相邻的两个炮塔的高度都高或者都低（高射炮>中射炮>低射炮），并且在此条件下，法王想要你设计出一套方案，使得防御力也就是战斗力最高。
输入
第一行为一个正整数 n，表示需要摆的炮塔个数。
接下来 n 行，每行 3 个不超过 10000 的正整数 ai,bi,ci，按顺时针顺序表示了第 i个位置摆低射,中射以及高射炮能获得的战斗力。
第 i 个位置的炮塔与第 i+1 个位置的炮塔相邻，特别地，第 1 个位置的炮塔与第 n个位置的炮塔相邻。
数据范围
对于 20% 的数据，有 n≤10；
对于 40% 的数据，有 n≤100；
对于 60% 的数据，有 n≤1000；
对于 100% 的数据，有 4≤n≤100000，1≤ ai,bi,ci≤10000，并保证 n 一定为偶数。
输出
一个正整数，为最大的战斗力之和。
这四套试题已经录入到我们的OJ系统中，包括测试用例也已经准备好了，可以通过：BCSP-X官方模拟题访问。
