您所在位置：主题：第63次编程比赛
plane [专家分：310] 发布于 2008-01-23 11:41:00
大家都快放假了，春节也临近，所以弄两道比较简单的题目，希望大家喜欢。
[em11][em11]
1.Stan是个懒惰的孩子，他做任何事总希望能找到既省力又快捷的方法。Stan的父母开着一家餐馆。餐馆有n*n张桌子，排放成n*n的方阵，每个桌子都有一个坐标，左上角的桌子的坐标为(1,1),其右面的桌子坐标为(1,2),其下面的桌子的坐标为(2,1).....最右下角桌子的坐标为(n,n)。Stan每天都要帮助他父母擦桌子，他当然不打算自己一个人干，所以他召唤出了一只小精灵。
小精灵只有一项技能：当Stan擦了坐标为(x,y)的桌子时，小精灵会自动帮他把所有坐标为(kx,ky)(k=2,3,.........,,使得kx<=n，且ky<=n)的这些桌子擦干净。现在，Stan想知道对于n*n张桌子，他最少需要擦多少张桌子就能把桌子全部擦干净。
比如n=4时，Stan只要擦(1,1), (1,2), (1,3), (1,4), (2,1), (2,3), (3,1), (3,2), (3,4), (4,1), (4,3)这些桌子。
输入：
首先第一行，输入一个测试数量t,接下来t行，每行一个n。
输出：
t行，每行对应一个解，就是Stan最少要擦几张桌子。
样例：
输入：
3
1
2
3
输出：
1
3
7
为保证正确性，你可以按照如下格式编程
int main()
{
int case;
scanf("%d",&case);
while(case--){
//你的代码
}
return 0;
}
有两组测试数据:(1)0 <n <=1000,时间：5秒.内存:32MB
(2)0 <n <=1,000,000 时间：2秒.内存:32MB
2.世界上有鬼吗？如果有，那就一定有捉鬼大师。但捉鬼大师们法力有限，他们只能消灭位于他们东南面的鬼。也就是说，如果把捉鬼大师所在位置视为原点，那么他们只能消灭第四象限的鬼怪（位于x正半轴和y负半轴上的鬼也会被消灭）。
现在给出一些鬼和坐标和一些捉鬼大师的坐标，请问有多少个鬼不会被消灭？
输入：
第一行，给出两个数字g,b对应予鬼的个数和捉鬼大师的个数。接下来的g行，每行两个整数，是每个鬼的坐标（之间有一个空各分开），在接下来得b行，每行两个整数，是每个捉鬼大师的坐标（之间有一个空各分开），不会有重复的鬼或重复的捉鬼大师出现。
输出：
无法被消灭的鬼的坐标x,y，之间用一个空格分开。注意这些坐标输出顺序必须 按照y值得绛序排列，当y相等时，则按照x的绛序排列。
样例：
输入：
3 2
0 5
1 2
2 3
1 4
-2 3
输出：
0 5
建议：
int main()
{
int g,b;
scanf("%d %d",&g,&b);
for(int i=0;i<g;i++)
//读入鬼坐标
for(int i=0;i<b;i++)
//读入捉鬼大师坐标
//你的代码
return 0;
}
有两组测试数据:(1)0 <g,b<=8000,时间:2秒,内存：32MB
(2)0 <g,b<=150000,时间:2秒,内存：32MB
环境：p4 2.2 512M gcc or g++ 64位数据请使用long long int
如有问题请在这里提问
[url=http://www.programfan.com/club/post-266202.html ]http://www.programfan.com/club/post-266202.html [/url]
[em11][em11]
1.Stan是个懒惰的孩子，他做任何事总希望能找到既省力又快捷的方法。Stan的父母开着一家餐馆。餐馆有n*n张桌子，排放成n*n的方阵，每个桌子都有一个坐标，左上角的桌子的坐标为(1,1),其右面的桌子坐标为(1,2),其下面的桌子的坐标为(2,1).....最右下角桌子的坐标为(n,n)。Stan每天都要帮助他父母擦桌子，他当然不打算自己一个人干，所以他召唤出了一只小精灵。
小精灵只有一项技能：当Stan擦了坐标为(x,y)的桌子时，小精灵会自动帮他把所有坐标为(kx,ky)(k=2,3,.........,,使得kx<=n，且ky<=n)的这些桌子擦干净。现在，Stan想知道对于n*n张桌子，他最少需要擦多少张桌子就能把桌子全部擦干净。
比如n=4时，Stan只要擦(1,1), (1,2), (1,3), (1,4), (2,1), (2,3), (3,1), (3,2), (3,4), (4,1), (4,3)这些桌子。
输入：
首先第一行，输入一个测试数量t,接下来t行，每行一个n。
输出：
t行，每行对应一个解，就是Stan最少要擦几张桌子。
样例：
输入：
3
1
2
3
输出：
1
3
7
为保证正确性，你可以按照如下格式编程
int main()
{
int case;
scanf("%d",&case);
while(case--){
//你的代码
}
return 0;
}
有两组测试数据:(1)0 <n <=1000,时间：5秒.内存:32MB
(2)0 <n <=1,000,000 时间：2秒.内存:32MB
2.世界上有鬼吗？如果有，那就一定有捉鬼大师。但捉鬼大师们法力有限，他们只能消灭位于他们东南面的鬼。也就是说，如果把捉鬼大师所在位置视为原点，那么他们只能消灭第四象限的鬼怪（位于x正半轴和y负半轴上的鬼也会被消灭）。
现在给出一些鬼和坐标和一些捉鬼大师的坐标，请问有多少个鬼不会被消灭？
输入：
第一行，给出两个数字g,b对应予鬼的个数和捉鬼大师的个数。接下来的g行，每行两个整数，是每个鬼的坐标（之间有一个空各分开），在接下来得b行，每行两个整数，是每个捉鬼大师的坐标（之间有一个空各分开），不会有重复的鬼或重复的捉鬼大师出现。
输出：
无法被消灭的鬼的坐标x,y，之间用一个空格分开。注意这些坐标输出顺序必须 按照y值得绛序排列，当y相等时，则按照x的绛序排列。
样例：
输入：
3 2
0 5
1 2
2 3
1 4
-2 3
输出：
0 5
建议：
int main()
{
int g,b;
scanf("%d %d",&g,&b);
for(int i=0;i<g;i++)
//读入鬼坐标
for(int i=0;i<b;i++)
//读入捉鬼大师坐标
//你的代码
return 0;
}
有两组测试数据:(1)0 <g,b<=8000,时间:2秒,内存：32MB
(2)0 <g,b<=150000,时间:2秒,内存：32MB
环境：p4 2.2 512M gcc or g++ 64位数据请使用long long int
如有问题请在这里提问
[url=http://www.programfan.com/club/post-266202.html ]http://www.programfan.com/club/post-266202.html [/url]
