CCC 2015 总结&回顾

最后一次CCC就在上周四悄悄地结束了……能参加也算是在帝都的福利吧。

3h，5题。最终结果290分，和第9&10名分数一样但是似乎因为提交比较晚于是被卡在了线下……简直是noip差5分的重演。

题目大意（数据范围记不清了，选用的字母也和原题有差异）：

1.Pairs

给一个N和一个M以及一组有N个数的数列{an}，求满足以下两个条件的数对的个数：

a. i < j

b. ai + aj <= M

其实可以发现a的限制只是表示每个数不能自己与自己相加且交换顺序相加是相同的一对。因此我们可以sort成升序之后再处理。

然后进行协同查找。sort之后取两个变量作为数组下标的指针i,j，初始值分别为1和n。每一次循环中移动j，保证i<j，直至ai+aj <= M，然后ans就可以加上j-i。每次循环结尾i向后移动一格。当i == j时循环停止。

时间复杂度是nlogn+n，其实还是O(nlogn).

100.

2. Mismatch

给两个只含有小写字母的字符串a/b，并给两个数字x/y。请问将字符串a复制x次组成的新字符串A与字符串b复制y次组成的新字符串B在首位对齐时相同位置上字符不同的位数有多少个。输入数据保证A的长度与B相同。

考场上只想到了既然给了输入数据的保证，那么总长度一定是a与b长度最小公倍数的倍数。但是数据范围太大眼见过不了，于是就这样写了暴力模拟最小公倍数之内的部分然后再乘，30。

后来机智的同学发现其实这道题很数学，两个字符串的对应与它们的最大公约数很有关。

e.g.

abc

abcde

(3,5)=1.所以以第一个字符串的角度看，每个字符都和所有下面的字符比较了一遍；

abcdabcdabcd

abcdef

(4,6)=2.同样以第一个字符串的角度看，每个字符都与下面每两个字符比较一遍。（对于a,比较第1,3,5个）

3. Symmetric Cross 

输入M，N，以及M*N的只有0和1组成的矩阵。问半径最大的symmetric cross半径是多大，以及中心的坐标。symmetric cross的定义是一个十字，在将其以中心为轴旋转90°之后与原十字相同。

例：

0 0 0 0 0

0 1 0 0 0

0 0 0 1 0

最大的十字是以（2,2）为中心的半径为1的十字。（非原样例数据）

暴力枚举30……

4. Maze

有两个人在一个有N间房间的迷宫中探险，一个人从一个房间走到下一个房间需要2min，另一个人从一个房间走到下一个房间需要1min。给出一个长度为N的数列，其中ai = j表示第i个房间通向第j个房间。路是单向的。两个人从任意两个不同的房间出发，输出他们从出发到第一次相遇的最短时间。输入数据保证这两个人一定会碰面。

哇这道题绝对是考场上觉得最简单的一题……

由题意可以知道，有n扇门和n条路，那么至少有1个环。假如有2个或多个环呢，那么两个人就可以分别陷在不同的环里永远绕下去。但是输入数据保证不会出现这一点，可知整个图有且仅有一个环。

那么我们就可以让走得慢的人从环上最长的支链的那一端开始出发。由于环和支链在其他地方都没有交点，我们可以保证让另一个人之前在环上怎么绕两个人都不会相遇。那么我们一定可以构造这样一种情况使得走的慢的人刚刚到达环上的点时，走的快的人刚好在他前面那一格。

100.

5.Pass the courses

对于每个学生都有一个努力值X和一个天赋值Y，对于每一门课也都有相应的两个值a和b。当且仅当a*X + b*Y > 1时，该学生能够通过这门课。（X,Y,a,b均为实数）

有Q次操作，每次操作规则如下：

输入的第一个字符为0：建立一个新的课程。输入该课程的a,b,以及编号。

输入的第一个字符为1：删除某个课程。输入该课程的编号。

输入的第一个字符为2：查询某个学生。输入该学生的X,Y，若该学生能够通过所有现存课程，输出1；否则输出0.

暴力30……