ECUST 09年 校赛个人赛第八场(最后一场)总结

懒惰了,暂时休息一下

这次我只AC了一题(在结束的那一刻,另一题在题目来源地网站上AC了,我们的OJ上仍然WA,我们OJ的Special Judge真是—_—!)

H题是用木棒拼数字,给出木棒数量,要求算出拼出的最大和最小数字

最大数字部分很明显7要用3根棒,1用2根棒,所以如果是奇数就是7+K个1,k=(n-1)/2 -1偶数直接n/2个1

最小数字部分比较麻烦,因为分几种情况,我是DP解决的,也可以找规律,DP的话要注意0和6都是用6根棒,而0不能作为第一个数字

代码如下:

#include<iostream>
using namespace std;
class cal
{
public:
    int num[10];
    int length;
    void Equal(cal a);
    bool sThan(cal a);
    cal AandB(cal a);
};
cal Num[101];
int main()
{
    freopen("h.in","r",stdin);
    freopen("h.out","w",stdout);
    int i,j;

    for(i = 0 ; i < 101 ; i ++)
        for(j = 0 ; j < 10 ; j ++)
            Num[i].num[j] = 0;

    Num[2].num[1] = 1;Num[2].length = 1;
    Num[3].num[7] = 1;Num[3].length = 1;
    Num[4].num[4] = 1;Num[4].length = 1;
    Num[5].num[2] = 1;Num[5].length = 1;
    Num[6].num[0] = 1;Num[6].length = 1;
    Num[7].num[8] = 1;Num[7].length = 1;


    for(i = 8 ; i < 101 ; i ++)
    {
        Num[i].Equal(Num[2].AandB(Num[i - 2]));
        for(j = 3 ; j < 8 && i - j >= 2 ; j ++)
        {
            if(Num[j].AandB(Num[i - j]).sThan(Num[i]))
                Num[i].Equal(Num[j].AandB(Num[i - j]));
        }
    }


    int t;
    scanf("%d",&t);
    while(t --)
    {
        int n;
        scanf("%d",&n);
        if(n == 6)
            printf("6 111\n");
        else
        {
            for(i = 1 ; i < 10 ; i ++)
                if(Num[n].num[i])
                    break;
            int b1 = i;
            printf("%d",b1);
            for(i = 0 ; i < 10 ; i ++)
                for(j = 0 ; (j < Num[n].num[i] && i != b1)
                    || (j < Num[n].num[i] - 1 && i == b1); j ++)
                    printf("%d",i);
            putchar(' ');

            if(n % 2)
                printf("7");
            else
                printf("1");
            n = n / 2 - 1;
            while(n --)
                putchar('1');
            putchar('\n');
        }

    }
    return 0;
}

cal cal::AandB(cal a)
{
    cal tmpCal;
    tmpCal.length = length + a.length;
    for(int i = 0 ; i < 10 ; i ++)
        tmpCal.num[i] = num[i] + a.num[i];

    tmpCal.num[0] += tmpCal.num[6];
    tmpCal.num[6] = 0;

    int j;
    for( j = 1 ; j < 10 ; j ++)
        if(tmpCal.num[j])
            break;
    int b1 = j;

    if(tmpCal.num[0] && b1 > 6)
        tmpCal.num[0] --,tmpCal.num[6] ++;

    return tmpCal;
};

bool cal::sThan(cal a)
{
    if(length < a.length)
        return true;
    else if(a.length > length)
        return false;
    else
    {
        int i;
        for(i = 1 ; i < 10 ; i ++)
            if(num[i])
                break;
        int b1 = i;
        for(i = 1 ; i < 10 ; i ++)
            if(a.num[i])
                break;
        int b2 = i;

        if(b1 < b2)
            return true;
        else if(b1 > b2)
            return false;
        else
            for(i = 0 ; i < 10 ; i ++)
                if(a.num[i] != num[i])
                    return num[i] > a.num[i];
    }

    return false;
};

void cal::Equal(cal a)
{
    for(int i = 0 ; i < 10 ; i ++)
        num[i] = a.num[i];

    length = a.length;


    num[0] += num[6];
    num[6] = 0;

    int j;
    for( j = 1 ; j < 10 ; j ++)
        if(num[j])
            break;
    int b1 = j;

    if(num[0] && b1 > 6)
        num[0] --,num[6] ++;

}

然后是I题

其实I题很水,就是前两天写的点到线段距离的改版,只不过这是线段到线段间的最短距离

题目按顺时针或逆时针输入,数据量只有100,所以任然暴搜解决

代码如下:

#include<stdio.h>
#include<math.h>
double GetLineDistance(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4);
double disBetweenPointAndLine(double x0,double y0,double x1,double y1,double x2,double y2);

double X1[100],Y1[100],X2[100],Y2[100];
int main()
{
    int t;
    scanf("%d",&t);
    while(t --)
    {
        int n,m,i,j;
        double out = 100000000;
        scanf("%d",&n);
        for(i = 0 ; i < n ; i ++)
            scanf("%lf %lf",&X1[i],&Y1[i]);

        scanf("%d",&m);
        for(i = 0 ; i < m ; i ++)
            scanf("%lf %lf",&X2[i],&Y2[i]);

        for(i = 0 ; i < n ; i ++)
            for(j = 0 ; j < m ; j ++)
            {
                double tmpDou = GetLineDistance(X1[i],Y1[i],X1[(i + 1) % n],Y1[(i + 1) % n]
                    ,X2[j],Y2[j],X2[(j + 1) % m],Y2[(j + 1) % m]);
                if(out > tmpDou)
                    out = tmpDou;
            };

        printf("%.8lg\n",out / 2);
    }
    return 0;
}



//{(x1,y1),(x2,y2)}{(x3,y3),(x4,y4)}
//导入点到直线或线段的距离模板

double GetLineDistance(double x1,double y1,double x2,double y2,double x3,double y3,double x4,double y4)
{
    double tmpDouble = disBetweenPointAndLine(x1,y1,x3,y3,x4,y4);
    if(tmpDouble > disBetweenPointAndLine(x2,y2,x3,y3,x4,y4))
        tmpDouble = disBetweenPointAndLine(x2,y2,x3,y3,x4,y4);
    if(tmpDouble > disBetweenPointAndLine(x3,y3,x1,y1,x2,y2))
        tmpDouble = disBetweenPointAndLine(x3,y3,x1,y1,x2,y2);
    if(tmpDouble > disBetweenPointAndLine(x4,y4,x1,y1,x2,y2))
        tmpDouble = disBetweenPointAndLine(x4,y4,x1,y1,x2,y2);

    return tmpDouble;
}

double disBetweenPointAndLine(double x0,double y0,double x1,double y1,double x2,double y2)
{
    //化为ax+by+c=0的形式
    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)
    {
        d = sqrt((x0 - x1) * (x0 - x1) + (y0 - y1) * (y0 - y1));
        if(d > sqrt((x0 - x2) * (x0 - x2) + (y0 - y2) * (y0 - y2)))
            d = sqrt((x0 - x2) * (x0 - x2) + (y0 - y2) * (y0 - y2));
    }

    return fabs(d);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏智能算法

十张GIFs让你弄懂递归等概念

链接:http://codingpy.com/article/10-gifs-to-understand-some-programming-concepts/(...

3929
来自专栏蜉蝣禅修之道

网络流算法Dinic的Python实现

1504
来自专栏数据结构与算法

cf932E. Team Work(第二类斯特灵数 组合数)

$$m^n = \sum_{i = 0}^m C_{n}^i S(n, i) i!$$

1094
来自专栏潇涧技术专栏

Python Algorithms - C7 Greedy

Python算法设计篇(7) Chapter 7: Greed is good? Prove it!

1122
来自专栏云霄雨霁

子字符串查找----各种算法总结

2380
来自专栏落影的专栏

iOS开发-OpenGL ES入门教程4

教程 OpenGL ES入门教程1-Tutorial01-GLKit OpenGL ES入门教程2-Tutorial02-shader入门 OpenGL E...

3395
来自专栏数据结构与算法

MatrixTree速成

前言 MatrixTree定理是用来解决生成树计数问题的有利工具 比如说这道题 MatrixTree定理的算法流程也非常简单 我们记矩阵A为无向图的度数矩阵 ...

3487
来自专栏算法修养

整数划分总结

整数划分问题: 笼统上说就是将一根整数划分成若干个整数之和的方案数。整数划分很多不同的问法,也有隐晦的问法。比如n个苹果放到m个盘子里,比如n个砖块堆成m个...

3176
来自专栏冰霜之地

Google S2 中的 CellID 是如何生成的 ?

笔者在《高效的多维空间点索引算法 — Geohash 和 Google S2》文章中详细的分析了 Google S2 的算法实现思想。文章发出来以后,一部分读者...

3602
来自专栏Flutter入门

Android OpenGL ES(二)-正交投影

平移矩阵和单位矩阵和类似。但是向量[x,y,z,1]前乘这个平移矩阵后的结构就是平移矩阵中定义的偏移量。

3481

扫码关注云+社区

领取腾讯云代金券