MyException - 我的异常网
当前位置:我的异常网» 编程 » 划水系列(八)小弟我在2013年编程之美全国挑战赛的

划水系列(八)小弟我在2013年编程之美全国挑战赛的资格赛中殴打水题

www.myexceptions.net  网友分享于:2013-04-10  浏览:2次
划水系列(八)我在2013年编程之美全国挑战赛的资格赛中殴打水题

祝自己生日快乐。嘻嘻,又大一岁了。

=================

(一)、 传话游戏

时间限制: 1000ms 内存限制: 256MB

描述

Alice和Bob还有其他几位好朋友在一起玩传话游戏。这个游戏是这样进行的:首先,所有游戏者按顺序站成一排,Alice站第一位,Bob站最后一位。然后,Alice想一句话悄悄告诉第二位游戏者,第二位游戏者又悄悄地告诉第三位,第三位又告诉第四位……以此类推,直到倒数第二位告诉Bob。两位游戏者在传话中,不能让其他人听到,也不能使用肢体动作来解释。最后,Bob把他所听到的话告诉大家,Alice也把她原本所想的话告诉大家。 

由于传话过程中可能出现一些偏差,游戏者越多,Bob最后听到的话就与Alice所想的越不同。Bob听到的话往往会变成一些很搞笑的东西,所以大家玩得乐此不疲。经过几轮游戏后,Alice注意到在两人传话中,有些词汇往往会错误地变成其他特定的词汇。Alice已经收集到了这样的一个词汇转化的列表,她想知道她的话传到Bob时会变成什么样子,请你写个程序来帮助她。

输入

输入包括多组数据。第一行是整数 T,表示有多少组测试数据。每组数据第一行包括两个整数 N 和 M,分别表示游戏者的数量和单词转化列表长度。随后有 M 行,每行包含两个用空格隔开的单词 a 和 b,表示单词 a 在传话中一定会变成 b。输入数据保证没有重复的 a。最后一行包含若干个用单个空格隔开的单词,表示Alice所想的句子,句子总长不超过100个字符。所有单词都只包含小写字母,并且长度不超过20,同一个单词的不同时态被认为是不同的单词。你可以假定不在列表中的单词永远不会变化。

输出

对于每组测试数据,单独输出一行“Case #c: s”。其中,c 为测试数据编号,s 为Bob所听到的句子。s 的格式与输入数据中Alice所想的句子格式相同。

数据范围

1 ≤ T ≤ 100

小数据:2 ≤ N ≤ 10, 0 ≤ M ≤ 10 

大数据:2 ≤ N ≤ 100, 0 ≤ M ≤ 100 


样例输入
2
4 3
ship sheep
sinking thinking
thinking sinking
the ship is sinking
10 5
tidy tiny
tiger liar
tired tire
tire bear
liar bear
a tidy tiger is tired
样例输出
Case #1: the sheep is thinking
Case #2: a tiny bear is bear

 

 这道题不废话,直接上。

 

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <map>

using namespace std;


//字符串分割函数
 std::vector<std::string> split(std::string str,std::string pattern)
 {
     std::string::size_type pos;
     std::vector<std::string> result;
     str+=pattern;//扩展字符串以方便操作
     int size=str.size();

     for(int i=0; i<size; i++)
     {
         pos=str.find(pattern,i);
         if(pos<size)
         {
             std::string s=str.substr(i,pos-i);
             result.push_back(s);
             i=pos+pattern.size()-1;
         }
     }
     return result;
 }

void Update(vector<string> & str,map<string,string> & w_map)
{
    map<string,string>::iterator it;
    for(int i=0;i<str.size();i++)
    {
        it = w_map.find(str[i]);
        if(it != w_map.end())
        {
            str[i]=it->second;
        }
    }
}

int main()
{
    int T;

    while(scanf("%d",&T) == 1)
    {
        for(int x=1;x<=T;x++)
        {
            int N,M;
            map<string,string> words_map;
            string s1,s2;
            string srcWords,tgtWords;

            scanf("%d%d",&N,&M);
            for(int i=1;i<=M;i++)
            {
                cin>>s1>>s2;
                words_map.insert(make_pair(s1,s2));
            }
            cin.get();//吃掉上一行换行符
            getline(cin,srcWords,'\n');
            vector<string> singleWord = split(srcWords," ");


            for(int i=1;i<=N-1;i++)
            {
                Update(singleWord,words_map);
            }
            printf("Case #%d: ",x);
            for(int i=0;i<singleWord.size()-1;i++)
                cout<<singleWord[i]<<" ";
            cout<<singleWord[singleWord.size()-1]<<endl;
        }

    }
    return 0;
}


 

(二)、 长方形

时间限制: 1000ms 内存限制: 256MB

描述

在 N × M 的网格上,放 K 枚石子,每个石子都只能放在网格的交叉点上。问在最优的摆放方式下,最多能找到多少四边平行于坐标轴的长方形,它的四个角上都恰好放着一枚石子。

输入

输入文件包含多组测试数据。

第一行,给出一个整数T,为数据组数。接下来依次给出每组测试数据。

每组数据为三个用空格隔开的整数 N,M,K。

输出

对于每组测试数据,输出一行"Case #X: Y",其中X表示测试数据编号,Y表示最多能找到的符合条件的长方形数量。所有数据按读入顺序从1开始编号。

数据范围

1 ≤ T ≤ 100

0 ≤ K ≤ N * M

小数据:0 < N, M ≤ 30

大数据:0 < N, M ≤ 30000


样例输入
3
3 3 8
4 5 13
7 14 86
样例输出
Case #1: 5
Case #2: 18
Case #3: 1398

这道题真的是很恶心!WA了无数次,因为这道题,我学会了一种查错忍术:大量生成随机数然后和AC的同学校对答案之术!

思路:

在K的范围内,生成一个长方形,长x,宽y,利用公式,那么最多的长方形数量 ans = x * y * (x-1) *(y-1) ,然后把leave = K - x * y ,把这些剩下的石子放到尽可能长的边,如果x < M ,那么证明x这边还能延伸,就放到x中,否则就放到y这边,剩下石子组成长方形的公式是ans += x * leave * (leave - 1) /2,其中的x为尽可能的最长边。不断生成符合x *  y <= K的长方形,然后不断获取ans,取最大的就行了。

公式来源:

长方形x * y 中,因为每一个要数到的长方形都是有x边上的两个石子和y边上的两个石子组成的,所以一共是:C(2,X)* C(2,Y)

排列组合数学,很有意思~

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <fstream>

using namespace std;

typedef long long LL;

int main()
{
    /*
    生成2.txt 后,和AC的代码生成的2.txt CMD下FC命令一下:
    fc 2.txt my2.txt
    就能找到差异!
    ofstream f1("1.txt");
    if(!f1)
        return -100;
    f1<<10000<<endl;
    LL cnt = 0;
    for(int y=1;;y++)
    {
        int a,b,c;
        a = rand()%10;
        b = rand()%10;
        c = rand()%100;
        if(c <= a*b)
        {
            f1<<a<<" "<<b<<" "<<c<<endl;
            cnt++;
            if(cnt == 10000)
                break;
        }
    }
    f1.close();


    freopen("1.txt", "r", stdin);
    freopen("2.txt", "w", stdout);

    */
    int T;
    while(scanf("%d",&T) == 1)
    {
        for(int x=1;x<=T;x++)
        {
            LL N,M,K;
            scanf("%lld%lld%lld",&N,&M,&K);

            if(N>M) //让M > N
            {
                N = M+N;
                M = N-M;
                N = N-M;
            }
            int n = sqrt(K)>N?N:sqrt(K);
            int m = M;
            while(n * m > K)
                m--;

            LL ans = 0;
            LL res = 0;

            while(n >= 2 && m <= M )
            {
                LL k = K;
                res += (n*m*(n-1)*(m-1)) >>2 ;
                k -= m*n;
                if(m < M)
                    res +=  (m*k*(k-1)) >>1;
                else
                    res +=  (n*k*(k-1)) >>1;
                ans = res > ans ? res : ans;

                res = 0;
                n --;
                m = K/n;
            }
            printf("Case #%d: %lld\n",x,ans);
            //printf("Case #%d: %I64d %I64d %I64d %I64d\n",x,ans,N,M,K);
        }
    }
    return 0;
}


 

 

 

(三)、树上的三角形

时间限制: 2000ms 内存限制: 256MB

描述

有一棵树,树上有只毛毛虫。它在这棵树上生活了很久,对它的构造了如指掌。所以它在树上从来都是走最短路,不会绕路。它还还特别喜欢三角形,所以当它在树上爬来爬去的时候总会在想,如果把刚才爬过的那几根树枝/树干锯下来,能不能从中选三根出来拼成一个三角形呢?

输入

输入数据的第一行包含一个整数 T,表示数据组数。

接下来有 T 组数据,每组数据中:

第一行包含一个整数 N,表示树上节点的个数(从 1 到 N 标号)。

接下来的 N-1 行包含三个整数 a, b, len,表示有一根长度为 len 的树枝/树干在节点 a 和节点 b 之间。

接下来一行包含一个整数 M,表示询问数。

接下来M行每行两个整数 S, T,表示毛毛虫从 S 爬行到了 T,询问这段路程中的树枝/树干是否能拼成三角形。

输出

对于每组数据,先输出一行"Case #X:",其中X为数据组数编号,从 1 开始。

接下来对于每个询问输出一行,包含"Yes"或“No”,表示是否可以拼成三角形。

数据范围

1 ≤ T ≤ 5

小数据:1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ len ≤ 10000

大数据:1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000

样例输入
2
5
1 2 5
1 3 20
2 4 30
4 5 15
2
3 4
3 5
5
1 4 32
2 3 100
3 5 45
4 5 60
2
1 4
1 3
样例输出
Case #1:
No
Yes
Case #2:
No
Yes

这WA和RE了好多次,主要是边界没处理好,导致溢出。虽然我知道肯定是溢出,但是在检查溢出的时候还是费了好大功夫。。不应该啊~~

思路就是:

1、建图

2、DFS一下,把从from结点到to结点的这条路标记出来,我用的是struct Node{int p;int w;}里面的元素记录父亲和边权重。

3、把爬过的边放到int  dis[]中,然后sort一下,取出a[i] a[i+1] a[i+2] ,判断a[i] + a[i+1] > a[i+2] 是否成立,速度很快,只要O(n)。

虽然AC了,但大数据应该会超时,无他,M*O(N)应该超了。。哎。。这已经无能为力了。。

 

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;


class CEdge
{
public:
    int dest;
    int weight;
    CEdge *Link;


    CEdge(int d,int w):dest(d),weight(w),Link(NULL){}
    CEdge():dest(-1),weight(-1),Link(NULL){}
    ~CEdge(){if(Link) delete Link;}

    void printEdge()
    {
        CEdge * e = Link;
        while(e)
        {
            cout<<e->dest<<" ("<<e->weight<<") ";
            e= e->Link;
        }
        cout<<endl;
    }

    void insertEdge(int d,int w)
    {
        CEdge *e = new CEdge();
        e->dest = d;
        e->weight = w;


        e->Link = Link;
        Link = e;
    }


};


class CGraph
{
public:
    int V;
    int E;
    vector<CEdge> edges;
    CGraph(int v,int e):V(v),E(e){init(V);}
    CGraph(int v):V(v),E(0){init(V);}
    ~CGraph()
    {
        //vector<CEdge>().swap(edges);
    }

    void insertEdge(int u,int v,int w)
    {
         if(u <= V && v <= V)
            edges[u].insertEdge(v,w);
    }

    void printGraph()
    {
        for(int i=1;i<=V;i++)
        {
            cout<<i<<": ";
            edges[i].printEdge();
        }
    }

    int getWeight(int u,int v)
    {
        CEdge *e = edges[u].Link;
        while(e)
        {
            if(e->dest == v)
                return e->weight;
            e = e->Link;
        }
        return -1;
    }

private:
    void init(int N)
    {
        for(int i=0;i<=N;i++)
        {
            edges.push_back(CEdge());
        }
    }
};


int dis[100010];
bool visited[100010];
int cnt=0;
struct Node
{
    int p;
    int w;
}p[100010];

void DFS_Visited(CGraph &g,int f,int t,bool* visited,Node* pp)
{
    if(f>0 && f<=g.V && t<=g.V && t>0)
    {
        CEdge *e = g.edges[f].Link;
        visited[f] = true;
        while(e)
        {
            int v = e->dest;
            if(!visited[v])
            {
                p[v].p=f;
                p[v].w=e->weight;

                if(v == t)
                    return;
                DFS_Visited(g,v,t,visited,p);
            }
            e = e->Link;
        }
    }
}


int main()
{
    int T;
    while(scanf("%d",&T) == 1)
    {
        for(int x=1;x<=T;x++)
        {
            int N;
            int u,v,w;
            scanf("%d",&N);
            CGraph g(N);
            for(int i=1;i<=N-1;i++)
            {
                scanf("%d %d %d",&u,&v,&w);
                g.insertEdge(u,v,w); //无向图
                g.insertEdge(v,u,w);
            }
            //g.printGraph();

            printf("Case #%d:\n",x);
            int ask;
            scanf("%d",&ask);
            while(ask--)
            {
                int f,t;
                scanf("%d%d",&f,&t);

                memset(visited,false,sizeof(bool)*(N+1));
                memset(p,0,sizeof(Node)*(N+1));


                DFS_Visited(g,f,t,visited,p);
                int v = t;
                cnt = 0;

                while(p[v].p != f && p[v].p != 0)
                {
                    dis[cnt] = p[v].w;
                    cnt++;
                    v = p[v].p;
                }
                dis[cnt]=p[v].w;

                sort(dis,dis+cnt+1);
                bool ans = false;
                for(int i=0;i<cnt-1;i++)
                {
                    int a = dis[i];
                    int b = dis[i+1];
                    int c = dis[i+2];
                    if(a+b > c)
                    {
                        ans = true;
                        break;
                    }
                }
                if(ans)
                    printf("Yes\n");
                else
                    printf("No\n");

            }
        }
    }
    return 0;
}

 

 /*修改于2013/4/7 第二次修改*/

听闻这道题大数据要用LCA(最近公共祖先),并查集做。

什么是LCA:

x = LCA(T,u,v)表示x是节点u和v的祖先,并且这个祖先的深度尽可能要深。

对于树T : (1,2)(1,3)(3 ,4)(3,5)

1 = LCA(T,5,2)

3 = LCA(T,3,4)//可见可以是结点本身

3 = LCA(T,4,5)

什么是并查集:

它是一种树形数据结构。处理一些不相交集合的合并和查询(果然是并和查,诚不我欺)。

初始化:把每个点所在集合初始化为本身,时间复杂度为O(n)。

    查找:查找点所在的集合,即根节点。

    合并:把两个集合合并成一个集合,合并前先查找下是否是同个集合。

 

 

 

 

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有