主题：第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]
最后更新于：2008-01-27 16:35:00
11 楼
yxs0001 [专家分：9560] 发布于 2008-01-27 17:46:00
/*
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
*/
#include <iostream>
using namespace std;
class CGhost
{
public:
int mx;
int my;
CGhost* NextX;
CGhost* ProX;
CGhost* NextY;
CGhost* ProY;
CGhost(){ mx = 0;my=0;NextX = NextY = ProX = ProY = NULL;}
CGhost(int x,int y){mx = x;my=y;NextX = NextY = ProX = ProY = NULL;}
void Print(){cout<<mx<<" "<<my<<endl;}
};
class CGhostS
{
private:
int num;
int maxx ,miny ;
CGhost* Head;
public:
CGhostS();
void Add(int x,int y);
void Die(CGhost* pg);
void Dashi(int x,int y);
void Print();
int GetMaxx(){return maxx;}
int GetMiny(){return miny;}
~CGhostS();
};
CGhostS::CGhostS()
{
num = 0;
maxx = INT_MIN;
miny = INT_MAX;
Head = new CGhost;
Head->NextX = Head->ProX = Head->NextY = Head->ProY = Head;
}
void CGhostS::Die(CGhost *pg)
{
pg->ProX->NextX = pg->NextX;
pg->NextX->ProX = pg->ProX;
pg->ProY->NextY = pg->NextY;
pg->NextY->ProY = pg->ProY;
delete pg;
num--;
if(num>0){
miny = Head->ProY->my;
maxx = Head->ProX->mx;
}
}
CGhostS::~CGhostS()
{
while(Head->NextY != Head){
Die(Head->NextY);
}
delete Head;
}
void CGhostS::Add(int x,int y)
{
CGhost *p;
CGhost *ap = new CGhost(x,y);
//y↓x↓
p = Head;
while((p=p->NextY) != Head){
if(p->my > y)
continue;
if((p->my < y) || (p->mx <= x))
break;
}
p->ProX->NextX = ap;
ap->NextX = p;
ap->ProX = p->ProX;
p->ProX = ap;
//x↓
p = Head;
while((p=p->NextX) != Head){
if(p->mx > x)
continue;
}
p->ProY->NextY = ap;
ap->NextY = p;
ap->ProY = p->ProY;
p->ProY = ap;
miny = Head->ProY->my;
maxx = Head->ProX->mx;
num ++;
}
void CGhostS::Dashi(int x,int y)
{
if((x > maxx) ||(y<miny))
return;
CGhost *p = Head;
while((p=p->ProY) != Head){
if(y < p->my)
return;
if(x <= p->mx){
CGhost *tmp = p->NextY;
Die(p);
p = tmp;
if((x > maxx) ||(y<miny))
return;
}
}
}
void CGhostS::Print()
{
CGhost* p=Head;
while((p=p->NextY)!=Head){
p->Print();
}
}
int main()
{
int g,b;
int x,y;
CGhostS cg;
cin>>g>>b;
for(int i=0;i<g;i++){
cin>>x>>y;
cg.Add(x,y);
}
for(int i=0;i<b;i++){
cin>>x>>y;
cg.Dashi(x,y);
}
cg.Print();
return 0;
}
12 楼
yunboy4 [专家分：10] 发布于 2008-01-27 19:36:00
//第1题
#include<stdio.h>
int main()
{
long int casee,n,k,j,x,y;
scanf("%d",&casee);
while(casee--)
{
scanf("%d",&n);
k=n-1;
for(x=2;x<=n;x++)
{
for(y=2;y<x;y++)
{
if(x%y==0)
{
k+=2;
}else if(x%y==1)
{
}
else
{
for(j=2;j<=y;j++)
{
if(x%j==0 && y%j==0)
{
k+=2;
break;
}
}
}
}
}
printf("%d\n",n*n-k);
//你的代码
}
return 0;
}
13 楼
yunboy4 [专家分：10] 发布于 2008-01-27 19:37:00
//第2题
#include<stdio.h>
typedef struct
{
int x;
int y;
}reat;
int main()
{
reat ghosts[200000];
reat ghost[200000];
reat pastors[200000];
reat pastor[200000];
reat inter;
int g,b,i,j,k;
scanf("%d %d",&g,&b);
for(i=0;i<g;i++)
{
scanf("%d %d",&ghosts[i].x ,&ghosts[i].y ); //读入鬼坐标
}
for(i=0;i<b;i++)
{
scanf("%d %d",&pastors[i].x ,&pastors[i].y ); //读入捉鬼大师坐标
}
//对pastors进行排序 y从大到小
for(i=0;i<b;i++)
{
for(j=b-1;j>i;j--)
{
if(pastors[j].y>pastors[j-1].y)
{
inter=pastors[j-1];
pastors[j-1]=pastors[j];
pastors[j]=inter;
}
else if(pastors[j].y==pastors[j-1].y)
{
if(pastors[j].x >pastors[j-1].x )
{
inter=pastors[j-1];
pastors[j-1]=pastors[j];
pastors[j]=inter;
}
}
}
}
//对pastors进行筛选 把重复的筛选掉 成为pastor
for(i=0,j=0;i<b;i++)
{
if(i!=0)
{
if(pastor[j].x >pastors[i].x)
{
pastor[++j]=pastors[i];
}
}
else pastor[j]=pastors[i];
}
b=j+1;
//对ghosts进行排序 使y从大到小排列
for(i=0;i<g;i++)
{
for(j=g-1;j>i;j--)
{
if(ghosts[j].y>ghosts[j-1].y)
{
inter=ghosts[j-1];
ghosts[j-1]=ghosts[j];
ghosts[j]=inter;
}
else if(ghosts[j].y==ghosts[j-1].y)
{
if(ghosts[j].x >ghosts[j-1].x )
{
inter=ghosts[j-1];
ghosts[j-1]=ghosts[j];
ghosts[j]=inter;
}
}
}
}
//让ghosts和pastor进行比对
for(i=0,j=0,k=0;i<b;i++)
{
if(i==0)
{
while(ghosts[j].y >pastor[i].y )
{
ghost[k++]=ghosts[j];
j++;
}
}
else if(i==b-1)
{
while(ghosts[j].y >pastor[i].y )
{
if(ghosts[j].x <pastor[i-1].x && ghosts[j].y <=pastor[i-1].y)
{
ghost[k++]=ghosts[j];
}
j++;
}
while(j<g)
{
if(ghosts[j].x <pastor[i].x)
{
ghost[k++]=ghosts[j];
}
j++;
}
}
else
{
while(ghosts[j].y >pastor[i].y )
{
if(ghosts[j].x <pastor[i-1].x && ghosts[j].y <=pastor[i-1].y)
{
ghost[k++]=ghosts[j];
}
j++;
}
}
}
g=k;
//输出
for(i=0;i<g;i++)
{
printf("%d %d\n",ghost[i].x ,ghost[i].y );
}
//你的代码
return 0;
}
您所在位置：