《第一届CCF真题+部分答案1.0版教学提纲.docx》由会员分享，可在线阅读，更多相关《第一届CCF真题+部分答案1.0版教学提纲.docx（41页珍藏版）》请在三一文库上搜索。
1、第一届 CCF 真题+部分答案1.0版目前 CCF 一共搞了 4 届，这不是一个比赛，就是类似于4/6 级那种性质，一共5 题，每题满分 100 分，据了解，基本上对了 1 题就能拿到证，证上会有你的分数和排名，能考高分的尽量考高分，就像英语 6 级， 430 分和 600 多分，虽然都是发张纸给你，但还是有区别的， 第一题都比较简单，大家尽量把第一题拿下， 提交代码不会返回对错给你，以你最后一次提交为你的答案，结束后再打分，也就是说，你的代码可能有点小错误，但也许能得个 60 分， 80 分这样，大概就是这样 =.=第一届 CCF 第一题201403-1试题名相反数称：时间限1.0s制：内存
2、限256.0MB制：问题描述有 N 个非零且各不相同的整数。请你编一个程序求出它们中有多少对相反数 (a 和 -a 为一对相反数 ) 。输入格式第一行包含一个正整数 N 。(1 N 500) 。问题描第二行为 N 个用单个空格隔开的非零整数 , 每个数的绝对值不超过 1000, 保证这些整数各不相同。述：输出格式只输出一个整数 , 即这 N 个数中包含多少对相反数。样例输入5123-1-2样例输出2# include # include # include # include # include # define LL long long using namespace std ;int ma
3、in ()/freopen(in.txt,r,stdin) ;int n ;int a520 ;scanf(%d , &n) ;int i , j;int sum = 0 ;for (i = 0 ; i n ; i+)scanf(%d , &ai) ;for (i = 0 ; i n ; i+)for (j = 0 ; j n ; j+)if (i = j )continue ;if (ai = -aj)sum+ ;printf(%dn , sum/2) ;return 0 ;第一届 CCF 第二题试题名窗口称：时间限1.0s制：内存限256.0MB制：问题描述问题描在某图形操作系统中 , 有
4、 N 个窗口 , 每个窗口都是一个两边述：与坐标轴分别平行的矩形区域。窗口的边界上的点也属于该窗口。窗口之间有层次的区别 , 在多于一个窗口重叠的区域里 , 只会显示位于顶层的窗口里的内容。当你点击屏幕上一个点的时候 , 你就选择了处于被点击位置的最顶层窗口 , 并且这个窗口就会被移到所有窗口的最顶层 , 而剩余的窗口的层次顺序不变。如果你点击的位置不属于任何窗口 , 则系统会忽略你这次点击。现在我们希望你写一个程序模拟点击窗口的过程。输入格式输入的第一行有两个正整数, 即 N 和 M。 (1 N 10,1M10)接下来 N 行按照从最下层到最顶层的顺序给出N 个窗口的位置。 每行包含四个非负
5、整数x 1, y 1, x 2 , y 2, 表示该窗口的一对顶点坐标分别为(x 1, y 1) 和 (x 2 , y 2) 。保证 x 1 x 2,y 12。接下来 M 行每行包含两个非负整数x, y,表示一次鼠标点击的坐标。题目中涉及到的所有点和矩形的顶点的x, y坐标分别不超过 2559 和1439。输出格式输出包括 M 行 , 每一行表示一次鼠标点击的结果。如果该次鼠标点击选择了一个窗口 , 则输出这个窗口的编号 ( 窗口按照输入中的顺序从 1 编号到 N); 如果没有 , 则输出 IGNORED(不含双引号) 。样例输入3 40044115522661 10 04 40 5样例输出2
6、11IGNORED样例说明第一次点击的位置同时属于第1和第 2个窗口 , 但是由于第 2 个窗口在上面 , 它被选择并且被置于顶层。第二次点击的位置只属于第 1 个窗口 , 因此该次点击选择了此窗口并将其置于顶层。现在的三个窗口的层次关系与初始状态恰好相反了。第三次点击的位置同时属于三个窗口的范围, 但是由于现在第 1个窗口处于顶层 , 它被选择。最后点击的 (0, 5)不属于任何窗口。# include # include # include # include # include # define LL long long using namespace std ;struct windo
7、wint x1 ;int y1 ;int x2 ;int y2 ;int id ;w12;int main ()/freopen(in.txt,r,stdin) ;int n , m ;scanf(%d %d , &n , &m) ;int i , j;for (i = 1 ; i = 1 ; i-)if (x = wi.x1 & x = wi.y1 & y =wi.y2)num = wi.id ;window temp = wi ;for (int k = i ; k = n ; k+)wk = wk+1 ;wn = temp ;break ;if (i != 0 )printf(%dn ,
8、 num) ;elseprintf(IGNOREDn) ;return 0 ;第一届 CCF 第三题201403-3试题名称：时间限制：内存限制：问题描述：命令行选项1.0s256.0MB问题描述请你写一个命令行分析程序 , 用以分析给定的命令行里包含哪些选项。每个命令行由若干个字符串组成 , 它们之间恰好由一个空格分隔。这些字符串中的第一个为该命令行工具的名字 , 由小写字母组成 , 你的程序不用对它进行处理。在工具名字之后可能会包含若干选项 , 然后可能会包含一 些不是选项的参数。选项有两类 : 带参数的选项和不带参数的选项。一个合法的无参数选项的形式是一个减号后面跟单个小写字母, 如-a
9、或-b 。而带参数选项则由两个由空格分隔的字符串构成, 前者的格式要求与无参数选项相同, 后者则是该选项的参数 , 是由小写字母, 数字和减号组成的非空字符串。该命令行工具的作者提供给你一个格式字符串以指定他的命令行工具需要接受哪些选项。这个字符串由若干小写字母和冒号组成 , 其中的每个小写字母表示一个该程序接受的选项。如果该小写字母后面紧跟了一个冒号 , 它就表示一个带参数的选项 , 否则则为不带参数的选项。例如 , ab:m: 表示该程序接受三种选项, 即-a( 不带参数 ),-b( 带参数 ), 以及 -m( 带参数 ) 。命令行工具的作者准备了若干条命令行用以测试你的程序。对于每个命令
10、行 , 你的工具应当一直向后分析。当你的工具遇到某个字符串既不是合法的选项, 又不是某个合法选项的参数时, 分析就停止。命令行剩余的未分析部分不构成该命令的选项, 因此你的程序应当忽略它们。输入格式输入的第一行是一个格式字符串 , 它至少包含一个字符 , 且长度不超过 52 。格式字符串只包含小写字母和冒号 , 保证每个小写字母至多出现一次 , 不会有两个相邻的冒号 , 也不会以冒号开头。输入的第二行是一个正整数 N(1 N 20), 表示你需要处理的命令行的个数。接下来有 N 行 , 每行是一个待处理的命令行, 它包括不超过256 个字符。该命令行一定是若干个由单个空格分隔的字符串构成, 每
11、个字符串里只包含小写字母 , 数字和减号。输出格式输出有 N 行。其中第 i 行以 Case i: 开始 , 然后应当有恰好一个空格 , 然后应当按照字母升序输出该命令行中用到的所有选项的名称 , 对于带参数的选项 , 在输出它的名称之后还要输出它的参数。如果一个选项在命令行中出现了多次 , 只输出一次。如果一个带参数的选项在命令行中出 现了多次 , 只输出最后一次出现时所带的参数。样例输入albw:x4ls -a -l -a documents -blsls -w 10 -x -w 15ls -a -b -c -d -e -l样例输出Case 1: -a -lCase 2:Case 3: -
12、w 15 -xCase 4: -a -b第一届 CCF 第四题201403-4试题名称：时间限制：内存限制：问题描述：无线网络1.0s256.0MB问题描述目前在一个很大的平面房间里有 n 个无线路由器 , 每个无线路由器都固定在某个点上。任何两个无线路由器只要距离不超过r 就能互相建立网络连接。除此以外 , 另有 m 个可以摆放无线路由器的位置。你可以在这些位置中选择至多 k 个增设新的路由器。你的目标是使得第 1 个路由器和第 2 个路由器之间的网络连接经过尽量少的中转路由器。请问在最优方案下中转路由器的最少个数是多少 ?输入格式第一行包含四个正整数n,m,k,r。(2 n 100,1 k
13、 m 100, 1 r 10 8) 。接下来 n行, 每行包含两个整数x i和 y i , 表示一个已经放置好的无线路由器在 (x i , y i ) 点处。输入数据保证第1和第2 个路由器在仅有这n个路由器的情况下已经可以互相连接( 经过一系列的中转路由器 ) 。接下来 m 行, 每行包含两个整数x i和 y i , 表示 (x i , y i )点处可以增设一个路由器。输入中所有的坐标的绝对值不超过 10 8, 保证输入中的坐标各不相同。输出格式输出只有一个数 , 即在指定的位置中增设k个路由器后 , 从第 1 个路 由器到第 2 个路由器最少经过的中转路由器的个数。样例输入53130 0
14、5 50 30 53 53 34 43 0样例输出2第一届 CCF 第五题201403-5试题名称：时间限制：内存限制：问题描述：任务调度1.0s256.0MB问题描述有若干个任务需要在一台机器上运行。它们之间没有依赖关系, 因此 可以被按照任意顺序执行。该机器有两个 CPU 和一个 GPU。对于每个任务 , 你可以为它分配不 同的硬件资源 :1. 在单个 CPU 上运行。2. 在两个 CPU 上同时运行。3. 在单个 CPU 和 GPU 上同时运行。4. 在两个 CPU 和 GPU 上同时运行。一个任务开始执行以后 , 将会独占它所用到的所有硬件资源 ,不得中 断, 直到执行结束为止。第 i
15、 个任务用单个 CPU,两个CPU,单个 CPU 加 GPU,两个 CPU 加 GPU 运行所消耗的时间分别为 a i ,b i ,c i和 d i 。现在需要你计算出至少需要花多少时间可以把所有给定的任务完成。输入格式输入的第一行只有一个正整数n(1 n 40),是总共需要执行的任务个数。接下来的 n行每行有四个正整数a i , b i , c i , d i (a i , b i , c i ,di均不超过 10),以空格隔开。输出格式输出只有一个整数 , 即完成给定的所有任务所需的最少时间。样例输入3442274743333样例输出7样例说明有很多种调度方案可以在 7 个时间单位里完成给
16、定的三个任务 , 以下是其中的一种方案 :同时运行第一个任务 ( 单 CPU 加上 GPU)和第三个任务 ( 单 CPU), 它们分别在时刻 2 和时刻 3 完成。在时刻 3 开始双CPU运行任务 2, 在 时刻 7 完成。第二届 CCF 第一题201409-1试题名称：时间限制：内存限制：问题描述：相邻数对1.0s256.0MB问题描述给定 n 个不同的整数，问这些数中有多少对整数，它们的值正好相差 1。输入格式输入的第一行包含一个整数n，表示给定整数的个数。第二行包含所给定的n 个整数。输出格式输出一个整数，表示值正好相差1 的数对的个数。样例输入61026378样例输出3样例说明值正好相
17、差 1 的数对包括 (2, 3), (6, 7), (7, 8)。评测用例规模与约定1=n=1000，给定的整数为不超过10000 的非负整数。# include # include # include # include # include # define LL long long using namespace std ;int a1010 ;int main ()/freopen(in.txt,r,stdin) ;int n ;scanf(%d , &n) ;int i , j ;int sum = 0 ;for (i = 0 ; i n ; i+)scanf(%d , &ai) ;s
18、ort(a , a+n) ;for (i = 0 ; i n ; i+)if (ai+1 - ai != 1)continue;elsesum+ ;printf(%dn , sum) ;return 0 ;第二届 CCF 第二题201409-2试题名画图称：时间限1.0s制：内存限256.0MB制：问题描述在一个定义了直角坐标系的纸上，画一个 (x1,y1)到 (x2,y2)的矩形指将横坐标范围从 x1 到 x2，纵坐标范围从 y1到 y2 之间的区域涂上颜色。下图给出了一个画了两个矩形的例子。第一个矩形是 (1,1)到(4, 4) ，用绿色和紫色表示。第二个矩形是 (2, 3)到(6, 5)
19、 ，用蓝色和紫色表示。图中，一共有 15 个单位的面积被涂上颜色，其中紫色部分被涂了两次，但在计算面积时只计算一次。在实际的涂色过程中，所有的矩形都涂成统一的颜色，图中显示不同颜色仅为说明方便。问题描述：给出所有要画的矩形，请问总共有多少个单位的面积被涂上颜色。输入格式输入的第一行包含一个整数 n，表示要画的矩形的个数。接下来 n 行，每行 4 个非负整数，分别表示要画的矩形的左下角的横坐标与纵坐标，以及右上角的横坐标与纵坐标。输出格式输出一个整数，表示有多少个单位的面积被涂上颜色。样例输入211442365样例输出15评测用例规模与约定1=n=100，0=横坐标、纵坐标 =100。# inc
20、lude # include # include # include # include # define LL long long using namespace std ;int a110110 ;int main ()/freopen(in.txt,r,stdin) ;int n ;scanf(%d , &n) ;int i , j ;int x1 , y1 , x2 , y2 ;int sum = 0 ;while(n-)scanf(%d%d%d%d , &x1,&y1,&x2,&y2) ;for (i = x1+1 ; i = x2 ; i+)for (j = y1+1 ; j =
21、y2 ; j+)aij = 1 ;for (i = 1 ; i = 105 ; i+)for (j = 1 ; j = 105 ; j+)sum += aij ;printf(%dn , sum) ;return 0 ;第二届 CCF 第三题（ KMP ）201409-3试题名称：时间限制：内存限制：问题描述：字符串匹配1.0s256.0MB问题描述给出一个字符串和多行文字，在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感选项：当选项打开时，表示同一个字母的大写和小写看作不同的字符；当选项关闭时，表示同一个字母的大写和小写看作相同的字符。输入格式输入的第一行包含一个字符串S，由大
22、小写英文字母组成。第二行包含一个数字，表示大小写敏感的选项，当数字为 0 时表示大小写不敏感，当数字为 1 时表示大小写敏感。第三行包含一个整数n，表示给出的文字的行数。接下来 n 行，每行包含一个字符串，字符串由大小写英文字母组成，不含空格和其他字符。输出格式输出多行，每行包含一个字符串，按出现的顺序依次给出那些包含了字符串 S 的行。样例输入Hello15HelloWorldHiHiHelloHiHiGrepIsAGreatToolHELLOHELLOisNOTHello样例输出HelloWorldHiHiHelloHiHiHELLOisNOTHello样例说明在上面的样例中，第四个字符串
23、虽然也是 Hello ，但是大小写不正确。如果将输入的第二行改为 0，则第四个字符串应该输出。评测用例规模与约定1=n=100，每个字符串的长度不超过100。# include # include # include # include # include # define LL long long using namespace std ;const int N = 110;int nextN;char SN, TN , S1N;int slen, tlen;void getNext()int j, k;j = 0; k = -1; next0 = -1;while(j tlen)if(k
24、= -1 | Tj = Tk)next+j = +k;elsek = nextk;int KMP_Count()int ans = 0;int i, j = 0;if(slen = 1 & tlen = 1)if(S0 = T0)return 1;elsereturn 0;getNext();for(i = 0; i 0 & Si != Tj)j = nextj;if(Si = Tj)j+;if(j = tlen)ans+;j = nextj;return ans;int main ()/freopen(in.txt,r,stdin) ;int n , sum , tag ;int i ;ci
25、nT ;tlen = strlen(T);cintagn ;if(tag = 1)while(n-)cinS ;slen = strlen(S);sum = KMP_Count() ;if (sum = 1)coutSendl ;elsefor (i = 0 ; i S1 ;slen = strlen(S1);for (i = 0 ; i = 1)coutS1endl ;return 0 ;第二届 CCF 第四题 (bfs)201409-4试题名最优配餐称：时间限1.0s制：内存限256.0MB制：问题描述栋栋最近开了一家餐饮连锁店，提供外卖服务。随着连锁店越来越多，怎么合理的给客户送餐成为了
26、一个急需解决的问题。栋栋的连锁店所在的区域可以看成是一个nn 的方格图（如下图所示），方格的格点上的位置上可能包含栋栋的分店问题描（绿色标注）或者客户（蓝色标注），有一些格点是不能经过的述：（红色标注）。方格图中的线表示可以行走的道路，相邻两个格点的距离为1。栋栋要送餐必须走可以行走的道路，而且不能经过红色标注的点。送餐的主要成本体现在路上所花的时间，每一份餐每走一个单位的距离需要花费 1 块钱。每个客户的需求都可以由栋栋的任意分店配送，每个分店没有配送总量的限制。现在你得到了栋栋的客户的需求，请问在最优的送餐方式下，送这些餐需要花费多大的成本。输入格式输入的第一行包含四个整数 n, m, k
27、, d ，分别表示方格图的大小、栋栋的分店数量、客户的数量，以及不能经过的点的数量。接下来 m行，每行两个整数xi, yi，表示栋栋的一个分店在方格图中的横坐标和纵坐标。接下来 k 行，每行三个整数xi, yi, ci，分别表示每个客户在方格图中的横坐标、纵坐标和订餐的量。（注意，可能有多个客户在方格图中的同一个位置）接下来 d 行，每行两个整数，分别表示每个不能经过的点的横坐标和纵坐标。输出格式输出一个整数，表示最优送餐方式下所需要花费的成本。样例输入102331 18 81 5 12 3 36 7 21 22 26 8样例输出29评测用例规模与约定前 30%的评测用例满足： 1=n =20
28、。前 60%的评测用例满足： 1=n=100。所有评测用例都满足： 1=n=1000，1=m, k, d=n2 。可能有多个客户在同一个格点上。每个客户的订餐量不超过 1000，每个客户所需要的餐都能被送到。# include # include # include # include # include # include # define LL long long using namespace std ;int map110110 ;bool v110110 ;int n , m , k , d ;struct kehuint x ;int y ;int num ;s10010;stru
29、ct nodeint x , y , step ;int dx = 1,-1,0,0 ;int dy = 0,0,1,-1 ;int bfs(int sx , int sy )queue q ;int i , fx ,fy ;node now , t ;now.x = sx ;now.y = sy ;now.step = 0 ;q.push(now) ;memset(v , 0 , sizeof(v) ;vsxsy = 1 ;while(!q.empty()now = q.front() ;q.pop() ;for (i = 0 ; i 4 ; i+)fx = now.x + dxi ;fy
30、= now.y + dyi ;if (fx1 | fy n | fy n | mapfxfy = 1 | vfxfy = 1)continue ;if (mapfxfy = 2)return now.step+1 ;t.x = fx ;t.y = fy ;t.step = now.step+1 ;q.push(t) ;vfxfy = 1 ;int main()/freopen(in.txt,r,stdin) ;int i , j ;int t1 , t2 ;int st = 0 ;int sum = 0 ;scanf(%d%d%d%d , &n , &m , &k , &d) ;for (i
31、= 0 ; i m ; i+)scanf(%d%d , &t1 , &t2) ;mapt1t2 = 2 ;for (i = 0 ; i k ; i+)scanf(%d%d%d , &si.x , &si.y ,&si.num) ;for (i = 0 ; i d ; i+)scanf(%d%d , &t1 , &t2) ;mapt1t2 = 1 ;for (i = 0 ; i k ; i+)st = bfs(si.x , si.y ) ;sum += (st * si.num) ;printf(%dn , sum) ;return 0 ;第二届 CCF 第五题201409-5试题名拼图称：时间
32、限3.0s制：内存限256.0MB制：问题描述给出一个 n m的方格图，现在要用如下 L 型的积木拼到这个图中，使得方格图正好被拼满，请问总共有多少种拼法。其中，方格图的每一个方格正好能放积木中的一块。积木可以任意问题描旋转。述：输入格式输入的第一行包含两个整数n, m ，表示方格图的大小。输出格式输出一行，表示可以放的方案数，由于方案数可能很多，所以请输出方案数除以 1,000,000,007 的余数。样例输入6 2样例输出4样例说明四种拼法如下图所示：评测用例规模与约定在评测时将使用10 个评测用例对你的程序进行评测。评测用例 1 和 2 满足： 1=n=30， m=2。评测用例 3 和 4 满足： 1=n, m=6。评测用例 5 满足： 1=n=100， 1=m=6。评测用例 6 和 7 满足： 1=n=1000