# 09年8月14日 ECUST ACM 练习赛总结

A题是POJ的3507 Judging Olympia这题是队友干掉的,我没看

B题是POJ的3508 Hide That Number同样是队友AC掉,我没看

$$l = l \mod 4 \times (n - 1 - 2k )$$

x=k,y=k//设初值,就是l为0时的值
if(l<n-2k)
x+=l
else if(l<2n-4k-1)
x+=n-2k-1,y+=l-n+2k+1
else if(l<3n-6k-2)
y+=n-2k-1,x+=3n-6k-l-3
else
y += 4n-8k – 4 – l

#include<iostream>
using namespace std;

#define MAXN 2000
struct Position
{
int x,y;
};

Position GetPosition(long n,long k,long l);

bool check(int n,int k);

long mat[MAXN][MAXN];
long matMol[MAXN][MAXN];

int main()
{
int n,t = 0;
while(scanf("%d",&n), n)
{
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < n ; j ++)
scanf("%ld",&mat[i][j]) , matMol[i][j] = i * n + j + 1;

int k;
for( k = 0 ; k <= (n - 1) / 2 ; k ++)
if(!check(n,k))
break;

if(k <= (n - 1) / 2)
printf("%d. NO\n", ++ t);
else
printf("%d. YES\n", ++ t);
}
return 0;
}

Position GetPosition(long n,long k,long l)
{
Position tmpPos;
tmpPos.x = tmpPos.y = k;
if(n - 1 - 2 * k)
l = l % (4 * (n - 1 - 2 * k));
else
return tmpPos;

if(l < n - 2 * k)
tmpPos.x += l;
else if(l < 2 * n - 4 * k - 1)
tmpPos.x += n - 2 * k - 1 , tmpPos.y += l - (n - 2 * k) + 1;
else if(l < 3 * n - 6 * k - 2)
tmpPos.y += n - 2 * k - 1,tmpPos.x += 3 * n - 6 * k - l - 3;
else
tmpPos.y += 4 * n - 8 * k - 4 - l;

return tmpPos;
}

bool check(int n,int k)
{
long pos2 , i;
long numSum = 4 * (n - 1 - 2 * k);

Position tmpSource = GetPosition(n,k,0);

for(pos2 = 0 ; pos2 < numSum ; pos2 ++)
{
Position tmpPos = GetPosition(n,k,pos2);
if(mat[tmpPos.y][tmpPos.x] == matMol[tmpSource.y][tmpSource.x])
break;
}
if(pos2 >= 4 * numSum)
if(numSum)
return false;
else
return mat[tmpSource.y][tmpSource.x] == matMol[tmpSource.y][tmpSource.x];

for(i = 1 ; i < 4 * numSum ; i ++)
{
tmpSource = GetPosition(n,k,i);

Position tmpPos = GetPosition(n,k,pos2 + i);
if(mat[tmpPos.y][tmpPos.x] != matMol[tmpSource.y][tmpSource.x])
return false;
}

return true;
}

D题是POJ的3510 A Tale from the Dark Side of the Moon 字符串处理,我直接交给Ultramanhu解决了,这题有个奇妙的陷阱就是字符串中间出现一个EOF就终止了,这让我们WA了几次

E题是POJ的3511 Fermat’s Christmas Theorem 这题大意是算出[l,u]区间内的素数个数及能表示为a2+b2的素数个数 这题只要简单的DP记录一下个数就行,主要是筛质数,这个很简单就不多说了 代码如下:

//Problem E
#include<iostream>
#include<cstring>
using namespace std;

const long MAXP = 1000003;
long prime[MAXP] = {0},num_prime = 0;
int isNotPrime[MAXP] = {1, 1};

int isTrue[MAXP]={0};

long numPrimeLess[MAXP] = {0};
long numPrimeNoMat[MAXP] = {0};

int main()
{
for(long i = 2 ; i <  MAXP ; i ++){
if(! isNotPrime[i])
prime[num_prime ++]=i;
for(long j = 0 ; j < num_prime && i * prime[j] <  MAXP ; j ++)
{
isNotPrime[i * prime[j]] = 1;
if( !(i % prime[j]))
break;
}
}

for(long i = 0 ; i < 1000 ; i ++)
for(long j = 0 ; j < 1000 && i * i + j * j <= MAXP; j ++)
isTrue[i * i + j * j] = 1;

for(long i = 2 ; i < MAXP ; i ++)
{
numPrimeNoMat[i] = numPrimeNoMat[i - 1] + (!isNotPrime[i]);
numPrimeLess[i] = numPrimeLess[i - 1] + (!isNotPrime[i] && isTrue[i]);
}

long l,u;
while(scanf("%ld %ld",&l,&u),l != -1 || u != -1)
{
long b = l>0?l:0;
long e = u>0?u:0;
printf("%ld %ld %ld %ld\n",l,u,numPrimeNoMat[e] - numPrimeNoMat[b] + !isNotPrime[b]
,numPrimeLess[e] - numPrimeLess[b] + (!isNotPrime[b] && isTrue[b]));
}
return 0;
}

F题是POJ的3512 Incidental Points. 题意是让你输入一些点的平面坐标,有一条线段能穿过最大数量的点,求最大点的数量 因为这类型的题以前写过而且留了代码就直接改完贴了 代码:

#include<iostream>
#include<cmath>
using namespace std;
char str[1000];
#define EPS 1e-10
struct point
{
double x,y;
};
struct node
{
double k;
};
int cmp(const void * a, const void * b)
{
return((*(double*)a-*(double*)b>0)?1:-1);
}

node numK[1005 * 1005 / 2];
point pt[1005];
int main()
{
int n = 0 , maxNum = 1 , tmpNum = 0,t = 0;
int end = 0;
while(gets(str))
{
if((str[0] == '-' && str[1] == '-') && end)
break;
else if(str[0] == '-' && str[1] == '-')
{
end = 1;

for(int i = 0 ; i <  n ; i ++)
{
int pos = 0;
for(int j = i + 1 ; j < n ; j ++)
if(fabs(pt[i].x - pt[j].x) > EPS)
numK[pos ++].k = (pt[j].y - pt[i].y) / (pt[j].x - pt[i].x);
else
numK[pos ++].k = 2000000;

qsort(numK,pos,sizeof(numK[0]),cmp);
int tmpNum = 2;
for(int j = 1 ; j < pos ; j ++)
{
if(numK[j].k == numK[j - 1].k)
tmpNum ++;
else
{
if(tmpNum > maxNum)
maxNum = tmpNum;
tmpNum = 2;
}
}
if(tmpNum > maxNum)
maxNum = tmpNum;
}

printf("%d. %d\n",++ t,maxNum);
maxNum = 1;
n = 0;
}
else
sscanf(str,"%lf %lf",&pt[n].x,&pt[n].y) , n ++,end = 0;
}
return 0;
}

G题是一道需要Hash的题,Hash我不熟,而且到时间结束我都没能研究出来STL库的map类.没能出 后面的题我基本都没看,貌似后面的题难度都比较高

167 篇文章28 人订阅

0 条评论

3068

3299

48510

3368

3749

5997

1938

841

2K4

4369