28 条题解

  • 0
    @ 2017-10-08 14:32:15
    #include<iostream>
    #include<algorithm>
    #include<cstdio>
    #include<vector>
    #include<queue>
    #include<map>
    #include<iomanip>
    #include<cmath>
    #include<cstring>
    #define maxa 200+10
    #define FOR(i,x,y) for(i=x;i<=y;++i)
    using namespace std;
    struct point
    {
        int x,y;
    };
    struct node
    {
        string name;
        vector<point> v;
        double d;
    }e[maxa];
    double dis(point p,point q)
    {
       return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
    }
    bool comp(node p,node q)
    {
        if(p.d!=q.d)
        {
            return p.d<q.d;
        }
        else
            return p.name<q.name;
    }
    int main()
    {
        int n,m,l;
        scanf("%d%d%d",&n,&m,&l);
        int mod = 260;
        char s[mod];
        int i,j,k;
        for(i=0;i<n;++i)
        {
    
            scanf("%s",s);
            for(j=0;j<m;++j)
            if(s[j]=='#')
            {
                e[0].v.push_back(point{i,j});
            }
        }
        FOR(i,1,l)
        {
            scanf("%s",s);
            e[i].name = s;
            FOR(k,0,n-1){
               scanf("%s",s);
            FOR(j,0,m-1)
            if(s[j]=='#')
            {
                e[i].v.push_back(point{k,j});
            }
            }
            double ans = 0;
            FOR(j,0,e[i].v.size()-1){
            double tot = maxa*10;
            FOR(k,0,e[0].v.size()-1)
            if(dis(e[0].v[k],e[i].v[j])<tot)
            {
                tot = dis(e[0].v[k],e[i].v[j]);
            }
            if(tot>ans)
                ans = tot;
            }
            e[i].d = ans;
        }
        sort(e+1,e+l+1,comp);
        FOR(i,1,l)
        {
            cout<<e[i].name<<endl;
            cout<<fixed<<setprecision(5)<<e[i].d<<endl;
        }
        return 0;
    }
    
    
  • 0
    @ 2017-07-08 16:36:56

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    int read()
    {
    int x=0;char c;int f=1;
    for(c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
    for(;c>='0'&&c<='9';c=getchar())x=(x<<3)+(x<<1)+c-'0';
    return x*f;
    }

    struct nio{
    double maxx;
    string h;
    }st[250];
    bool comp(const nio &a,const nio &b)
    {
    if(a.maxx!=b.maxx)return a.maxx<b.maxx;
    return a.h<b.h;
    }
    struct node{
    int x,y;
    }sc[10005];
    int n,m,l;double dis[105][105];
    int tot=0;
    bool sign[105][105];

    int main()
    {
    //freopen("x.in","r",stdin);
    char s,h[260];
    n=read();m=read();l=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
    dis[i][j]=1e+9;
    cin>>s;
    if(s=='#'){
    sc[++tot].x=i;
    sc[tot].y=j;
    }
    }

    for(int i=1;i<=l;i++)
    {
    st[i].maxx=-1;
    cin>>st[i].h;
    for(int j=1;j<=n;j++)
    {
    for(int k=1;k<=m;k++)
    {
    cin>>s;
    if(s=='#'){
    if(!sign[j][k])
    {
    for(int g=1;g<=tot;g++)
    {
    double len=sqrt((sc[g].x-j)*(sc[g].x-j)+(sc[g].y-k)*(sc[g].y-k));
    dis[j][k]=min(dis[j][k],len);
    sign[j][k]=1;
    }
    }
    st[i].maxx=max(st[i].maxx,dis[j][k]);
    }
    }
    }
    }
    sort(st+1,st+l+1,comp);
    for(int i=1;i<=l;i++)
    {
    cout<<st[i].h<<endl;
    printf("%.5f\n",st[i].maxx);
    }
    }

  • 0
    @ 2009-11-10 00:55:46

    这个,排序已经改成描述的双关键字了………………

    预处理学校到每个'.'的最近距离,DFS一下,记忆化搜索。

    后面就直接读结果比较一下取最大值,最后双关键字排序,都是小菜一碟。

    这题差点把我做残了,郁闷。

  • 0
    @ 2009-11-09 14:08:42

    枚举,O(nml^2),过了。。。

  • 0
    @ 2009-11-06 20:53:15

    各位大哥大姐,这里是写题解的地方,请不要乱贴 东西,这样会 浪费初学者的时间。

    请各位多多合作,谢谢!

  • 0
    @ 2009-11-04 17:31:00

    原本 是单关建字 的

    有改过来了 郁闷

  • 0
    @ 2009-11-03 00:09:22

    受不了了,一样的代码

    比赛时测是30,现在AC

  • 0
    @ 2009-11-02 06:53:14
    • -难怪我怎么感觉快排打错出现30分- -
      囧到了
      原来是数据问题啊
  • 0
    @ 2009-11-01 23:39:27

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 0ms

    ├ 测试数据 12:答案正确... 0ms

    ├ 测试数据 13:答案正确... 0ms

    ├ 测试数据 14:答案正确... 0ms

    ├ 测试数据 15:答案正确... 0ms

    ├ 测试数据 16:答案正确... 0ms

    ├ 测试数据 17:答案正确... 0ms

    ├ 测试数据 18:答案正确... 0ms

    ├ 测试数据 19:答案正确... 0ms

    ├ 测试数据 20:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    呵呵!~~~rp++啊,秒掉!

  • 0
    @ 2009-11-01 19:09:38

    太搞笑了,标程都30,看到他双关键字排序了。

    编译通过...

    ├ 测试数据 01:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 05:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 06:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 11:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 12:答案正确... 0ms

    ├ 测试数据 13:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 14:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 15:答案正确... 0ms

    ├ 测试数据 16:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 17:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 18:答案错误... ├ 标准行输出

     ├ 错误行输出

    ├ 测试数据 19:答案错误...程序输出比正确答案长

    ├ 测试数据 20:答案错误... ├ 标准行输出

     ├ 错误行输出

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:30 有效耗时:0ms

  • 0
    @ 2009-11-01 15:29:45

    题目出的真好,只要按题目做就是30分,无视句话就AC,原来为了压分数还可以这么做,了得了得。

  • 0
    @ 2009-11-01 14:51:10

    数据好弱

  • 0
    @ 2009-11-01 13:34:56

    数据绝对有问题...

    30分的,双关键字快排改冒泡按距离排序就AC

  • 0
    @ 2009-11-01 00:06:18

    数据我可以说没有问题……

    程序完全可以秒杀

  • 0
    @ 2009-10-31 21:03:22

    垃圾数据

  • 0
    @ 2009-10-31 20:43:18

    BS

    办比赛能不能把数据出正确啊

    第一题 VJ接受不了

    第二题 数据有错

    真是受不了

  • 0
    @ 2009-10-31 16:28:31

    见面不如闻名`\

  • 0
    @ 2009-10-31 16:19:01

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ├ 测试数据 11:答案正确... 56ms

    ├ 测试数据 12:答案正确... 0ms

    ├ 测试数据 13:答案正确... 0ms

    ├ 测试数据 14:答案正确... 0ms

    ├ 测试数据 15:答案正确... 0ms

    ├ 测试数据 16:答案正确... 0ms

    ├ 测试数据 17:答案正确... 0ms

    ├ 测试数据 18:答案正确... 0ms

    ├ 测试数据 19:答案正确... 0ms

    ├ 测试数据 20:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:56ms

    • -
      没有秒杀~~~
      最后好像快排是过不了的,
      好像要冒泡或选择才能过
  • 0
    @ 2009-10-31 16:17:44

    Accepted 有效得分:100 有效耗时:0ms

    确实很阴

  • 0
    @ 2009-10-31 15:17:59

    不用按名字顺序排,用冒泡排大小就行!!!

    好阴的数据,好阴的题!!!!!!

信息

ID
1650
难度
8
分类
模拟 点击显示
标签
递交数
692
已通过
78
通过率
11%
被复制
1
上传者