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

B题补充: B题的DP方法比较诡异(起码我理解了很久) 令fn[i][j]为有i个数j次交换位置的排列数量很明显,当i+1时,如果把新增的数放在最后一位,那么交换次数不变(新增的数为i+1,最大). 如果把新增的数放在第1到i位之间的话有i种放法, 对于每一种fn[i][j]的排列中我们总能找到一种序列使得{(.)(.)()(.)(.)…(i+1)},["()表示一个元素"] 中(i+1)和()交换位置后前i个元素的排列和其相同又因为(*)的位置可以有i种放法,以此我们发现,fn[i+1][j]=fn[i][j]+fn[i][j-1]×i 继续贴代码:

#include<iostream>
using namespace std;

__int64 fn[21][21] = {0};
__int64 njc[21] = {0,1};

__int64 gcd(__int64 a,__int64 b)
{
    if(a % b == 0)
        return b;
    return gcd(b,a % b);
}
int main()
{
    for(__int64 i = 2 ; i < 21 ; i ++)
        njc[i] = njc[i - 1] * i;

    for(int i = 0 ; i < 21 ; i ++)
        fn[i][0] = 1;

    for(int i = 2 ; i < 21 ; i ++)
    {
        //放在最后一位
        for(int j = 1 ; j < i - 1 ; j ++)
            fn[i][j] += fn[i - 1][j];

        //不放在最后一位
        for(int j = 1 ; j < i ; j ++)
            fn[i][j] += fn[i - 1][j - 1] * (i - 1);
    }

    int t,w,h,s;
    cin>>t;
    while(t --)
    {
        cin>>w>>h>>s;
        int tol = w * h;

        __int64 tmpInt = 0;
        for(int i = 0 ; i < s ; i ++)
            tmpInt += fn[tol][i];


        if(tmpInt == njc[tol])
            cout<<1<<endl;
        else if(tmpInt == 0)
            cout<<0<<endl;
        else
        {
            __int64 base = gcd(tmpInt,njc[tol]) ;
            cout<<tmpInt / base<<"/"<<njc[tol] / base<<endl;
        }
    }
    return 0;
}

Problem C

这是一个简单的几何题,题意大致是给出几个目标图形的坐标,然后输入两个人的三次投标的坐标点,而坐标如果在N目标图形中,则加N分,结果是输出得分高的人名,或者如果平手输出Tied. 由于输入得图形值包括多变形和圆,多变形直接用模板,圆很简单,圆心和投标所在点的距离≤半径即可. 具体代码如下:

#include<iostream>
#include<cmath>
using namespace std;

#define eps 1e-8
struct point{double x,y;};
#define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
double xmult(point p1,point p2,point p0){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}


//判点在凸多边形内或多边形边上,顶点按顺时针或逆时针给出
int inside_convex(point q,int n,point* p)
{
    int i,s[3]={1,1,1};
    for (i=0;i<n&&s[1]|s[2];i++)
        s[_sign(xmult(p[(i+1)%n],q,p[i]))]=0;
    return s[1]|s[2];
}

class rec
{
public:
    point p1,p2,p3;
    double r;
    int type;//1矩形,2三角型,3三圆形

    int isInside(point pt)
    {
        if(type == 1)
        {
            point rep[4];
            rep[0].x = p1.x;
            rep[0].y = p1.y;
            rep[1].x = p2.x;
            rep[1].y = p1.y;
            rep[2].x = p2.x;
            rep[2].y = p2.y;
            rep[3].x = p1.x;
            rep[3].y = p2.y;
            return inside_convex(pt,4,rep);
        }
        else if(type == 2)
        {
            point rep[3];
            rep[0].x = p1.x;
            rep[0].y = p1.y;
            rep[1].x = p2.x;
            rep[1].y = p2.y;
            rep[2].x = p3.x;
            rep[2].y = p3.y;
            return inside_convex(pt,3,rep);
        }
        else
        {
            return sqrt((pt.x - p1.x) * (pt.x - p1.x) + (pt.y - p1.y) * (pt.y - p1.y)) <= r;
        }
    }
};


rec m[1001];

int main()
{
    int s;

    scanf("%d",&s);

    for(int i = 0 ; i < s ; i ++)
    {
        char tp;
        getchar();
        scanf("%c",&tp);
        if(tp == 'R')
            scanf("%lf %lf %lf %lf",&m[i].p1.x,&m[i].p1.y,&m[i].p2.x,&m[i].p2.y),m[i].type = 1;
        else if(tp == 'T')
            scanf("%lf %lf %lf %lf %lf %lf",&m[i].p1.x,&m[i].p1.y,&m[i].p2.x,&m[i].p2.y,&m[i].p3.x,&m[i].p3.y),m[i].type = 2;
        else
            scanf("%lf %lf %lf",&m[i].p1.x,&m[i].p1.y,&m[i].r),m[i].type = 3;;
    }

    int t;
    scanf("%d",&t);
    while(t --)
    {
        point p1,p2;
        int score1 = 0,score2 = 0;
        for(int i = 0 ; i < 3 ; i ++)
        {
            scanf("%lf %lf",&p1.x,&p1.y);

            for(int j = 0 ; j < s ; j ++)
                score1 += m[j].isInside(p1);
        }

        for(int i = 0 ; i < 3 ; i ++)
        {
            scanf("%lf %lf",&p2.x,&p2.y);

            for(int j = 0 ; j < s ; j ++)
                score2 += m[j].isInside(p2);
        }

        if(score1 > score2)
        {
            printf("Bob\n");
        }
        else if(score1 < score2)
        {
            printf("Hannah\n");
        }
        else
        {
            printf("Tied\n");
        }
    }
    return 0;
}

Problem D

是概率问题+二分,因为没时间了所以没仔细考虑 D题补充: 赛后进行了代码补写,主要是枚举起点,二分终点,然后由于他是先选起点再选终点,而不是两个一起选,所以概率计算要注意下如果共有b个第i个作为起点,j个作为终点,则概率为(j-i+1)/(b*(b-i+1)); 再就是我WA了很多次,最后把输出的%.10g改成%.10lf就AC了,为什么我也不清楚,题目说是SpecialJudge,应该两种情况是一样的啊这里我也不清楚为什么WA.以后尽量少用%g吧代码如下:

#include<iostream>
using namespace std;

long list[200002];
char record[200003];

double GetPossiblitySmallThan(long maxn,long b,bool enableEqual);
int main()
{
    int t;
    long b,l,u;
    scanf("%d",&t);
    while(t --)
    {
        scanf("%ld",&b);
        scanf("%s",record);
        scanf("%ld %ld",&l,&u);

        list[0] = 0;
        for(long i = 1 ; i <= b ; i ++)
            list[i] = list[i - 1] + record[i - 1] - 'A';

        double p1 = GetPossiblitySmallThan(l,b,false);
        double p2 = GetPossiblitySmallThan(u,b,true);

        printf("%.10lf %.10lf %.10lf\n",p2 - p1, p1 , 1 - p2);
    }
    return 0;
}

double GetPossiblitySmallThan(long maxn,long b,bool enableEqual)
{
    double p = 0;
    for(long i = 1 ; i <= b ; i ++)
    {
        if(list[i] - list[i - 1] > maxn || (list[i] - list[i - 1] == maxn && !enableEqual))
            continue;
        long be = i;
        long ed = b;
        long md = (be + ed + 1) / 2;
        while(ed > be)
        {
            if(list[md] - list[i - 1] < maxn || (list[md] - list[i - 1] == maxn && enableEqual))
                be = md;
            else
                ed = md - 1;

            md = (be + ed + 1) / 2;
        }

        p += (double)(be - i + 1) / (double)b / (double)(b - i + 1);
    }
    return p;
}