ECUST 09年 校赛个人训练赛第五场总结

今天战绩还行，AC了5题，今天总体没有太复杂的算法题，不过测试数据强度比之前有所增加 我的钱四题很早就过了，但是第五题很晚才出主要是代码写得太混乱，思路也错了两次 我过的题有五道，分别是ABCDG

A Coming Near

A题是计算两个多边形的最近距离

由于数据量不是很大，所以O（n^2）的算法就能过,也就是枚举,每一个用例的最坏情况是310001000

具体是先枚举每两个点的距离,记录最小值

再枚举每个点到另一个多边形上每条直线的距离,记录最小值即可

不过lpld的因为越界导致的WA问题值得借鉴(及时把long型转为double型)

#include<iostream>
#include<cmath>
using namespace std;
struct vertex
{
    long x,y;
};

vertex prisonA[1000],prisonB[1000];

double disBetweenAB(int posA,int posB)
{
    double tmp1 = prisonA[posA].x - prisonB[posB].x;
    double tmp2 = prisonA[posA].y - prisonB[posB].y;
    return sqrt(tmp1 * tmp1 + tmp2 * tmp2);
}
double disBetweenPointAndLine(long x0,long y0,long x1,long y1,long x2,long y2)
{
    double a = y1-y2;
    double b = x2-x1;
    double c = x1*y2-x2*y1;
    double d = (a*x0+b*y0+c)/sqrt(a*a+b*b);
    double xp = (b*b*x0-a*b*y0-a*c)/(a*a+b*b);
    double yp = (-a*b*x0+a*a*y0-b*c)/(a*a+b*b);
    double xb = (x1>x2)?x1:x2;
    double yb = (y1>y2)?y1:y2;
    double xs = x1+x2-xb;
    double ys = y1+y2-yb;
    if(xp > xb || xp < xs || yp > yb || yp < ys)
        return 50000000;
    else
        return fabs(d);
}

int main()
{
    int m,n;
    while(scanf("%d %d",&n,&m),n || m)
    {
        int i,j;
        for(i = 0 ; i < n ; i ++)
            scanf("%ld %ld",&prisonA[i].x,&prisonA[i].y);
        for(i = 0 ; i < m ; i ++)
            scanf("%ld %ld",&prisonB[i].x,&prisonB[i].y);
        double tmpDouble = disBetweenAB(0,0);
        for(i = 0 ; i < n ; i ++)
            for(j = 0 ; j < m ; j ++)
                if(disBetweenAB(i,j) < tmpDouble)
                    tmpDouble = disBetweenAB(i,j);
        for(i = 0 ; i < n ; i ++)
            for(j = 0 ; j < m ; j ++)
            {
                double tmpDouble2 = disBetweenPointAndLine(prisonA[i].x,prisonA[i].y
                    ,prisonB[j].x,prisonB[j].y,prisonB[(j+1)%m].x,prisonB[(j+1)%m].y);
                if(tmpDouble2 < tmpDouble)
                    tmpDouble = tmpDouble2;
            };

        for(i = 0 ; i < m ; i ++)
            for(j = 0 ; j < n ; j ++)
            {
                double tmpDouble2 = disBetweenPointAndLine(prisonB[i].x,prisonB[i].y
                    ,prisonA[j].x,prisonA[j].y,prisonA[(j+1)%n].x,prisonA[(j+1)%n].y);
                if(tmpDouble2 < tmpDouble)
                    tmpDouble = tmpDouble2;
            };

        printf("%.2lf\n",tmpDouble);
    }
    return 0;
}

B Love Letter

B题是要求重新排列单词,使之成为字典里的单词,以此读懂别人打乱加密的Love Letter

这题很简单,直接一个一个单词查找就行了,不过要注意一下换行的位置,因为题目要求输出和输入一样

继续贴代码:

#include<iostream>
#include<cstring>
using namespace std;
char dir[101][25];
int dirCharNum[101][26] = {0};
int lenDir[101];
char tmpChar[50];
void check(char c[],int n)
{
    char cN[26] = {0};
    for(int i = 0 ; i < n ; i ++)
    {
        int len = strlen(c);
        if(len != lenDir[i] || c[0] != dir[i][0] || c[len - 1] != dir[i][lenDir[i] - 1])
            continue;

        memset(cN,0,sizeof(cN));
        for(int j = 0 ; j < len ; j ++)
            cN[c[j] - 'a'] ++;
        int isMatch = 1;
        for(int k = 0 ; k < len ; k ++)
            if(cN[k] != dirCharNum[i][k])
            {
                isMatch = 0;
                break;
            };

        if(isMatch)
        {
            printf("%s",dir[i]);
            break;
        }
    }
}
int main()
{
    int n;
    cin>>n;
    int i,j;
    for(i = 0 ; i < n ; i ++)
    {
        scanf("%s",dir[i]);
        lenDir[i] = strlen(dir[i]);
        for(j = 0 ; j < lenDir[i] ; j ++)
            dirCharNum[i][dir[i][j] - 'a'] ++;
    }

    while(scanf("%s",tmpChar) != EOF)
    {
        check(tmpChar,n);
        if(getchar() == '\n')
            printf("\n");
        else
            printf(" ");
    }
    return 0;
}

C Change Base

C题是一道进制转换题,稍微思考一下就能推出公式了,然后每次处理mod一个10007就行

(注: a % c + b % c = ( a + b ) % c ( a b ) % c = ( a % c b % c ) % c )

代码：

#include<iostream>
#include<cstring>
using namespace std;
char input[1002];


long TypeTo10(char c[],int m,int mod)
{
    int tmpInt = 0;
    int len = strlen(c);

    for(int i = 0 ; i < len ; i ++)
        tmpInt = (tmpInt * m + c[i] - '0') % mod;

    return tmpInt;
}
int main()
{
    int t,m;
    cin>>t;
    while(t --)
    {
        cin>>m>>input;
        cout<<TypeTo10(input,m,10007)<<endl;
    }
    return 0;
}

D Equation

D题要用Hash的思想,但是因为是long型的数据而且数据量不大(1000*1000),可以不写哈希函数,直接映射

我的代码如下:

#include<iostream>
using namespace std;

long hash[2000001];
long ro[3000001] = {0};
long f2[1001];
int main()
{
    int t;
    long r;
    for(r = 0 ; r <= 1000 ; r ++)
        f2[r] = r * r;
    cin>>t;
    while(t --)
    {
        scanf("%ld",&r);
        if(ro[r])
        {
            printf("%ld\n",ro[r]);
            continue;
        }
        memset(hash,0,sizeof(hash));

        long i,j;
        for(i = 0 ; f2[i] <= r && i <= 1000 ; i ++)
            for(j = 0 ; j <= i; j ++)
                if(j == i)
                    hash[f2[i] + f2[j]] ++;
                else
                    hash[f2[i] + f2[j]] += 2;

        long tmpInt = 0;

        for(i = 0 ; f2[i] <= r && i <= 1000 ; i ++)
            if(r - f2[i] <= 2000000)
                tmpInt += hash[r - f2[i]];

        printf("%ld\n",tmpInt);
        ro[r] = tmpInt;
    }
    return 0;
}

G Fermat square prime

G题是计算能用a^2+b^2表示的素数(a,b为素数)

我的大体思路是先筛出素数表,再把素数依次组合,算出所有能这么表示的数

最后再读入数据,判断读入的数据是否是能以a^2+b^2的素数

代码如下:

#include<iostream>
using namespace std;
#define MAXN 1000001
long prime[MAXN],numPrime = 0;
int a[MAXN] = {0};
int isFQSP[MAXN] = {0};
long f2[1000] = {0};
int main()
{
    //线性筛素数复杂度O(n)这个很重要，由于数据量小，可以打表
    long i,j,k;
    for(i = 2 ; i < 1000 ; i ++)
    {
        if(!a[i])
            prime[numPrime ++] = i;
        for(j = 0 ; j < numPrime && prime[j] * i <MAXN ; j ++)
        {
            a[prime[j] * i] ++;
            if(i % prime[j] == 0)
                break;
        }
    }

    for(i = 0 ; i < numPrime && prime[i] < 1000; i ++)
        f2[prime[i]] = prime[i] * prime[i];

    for(i = 0 ; i < numPrime && prime[i] < 1000; i ++)
        for(j = 0 ; j <= i ; j ++)
            if(f2[prime[i]] + f2[prime[j]] < MAXN && !a[f2[prime[i]] + f2[prime[j]]])
                isFQSP[f2[prime[i]] + f2[prime[j]]] ++;

    int t;
    scanf("%d",&t);
    while(t --)
    {
        scanf("%ld",&k);
        if(isFQSP[k])
            printf("yes\n");
        else
            printf("no\n");
    }
    return 0;
}

这次总体感觉前期不错，后期就一直卡住了，想到的算法错误浪费了我很多时间 最后一题的思路错误导致一直WA，以后需要注意，思路清晰很重要。