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

24 3ship sheepsinking thinkingthinking sinkingthe ship is sinking10 5tidy tinytiger liartired tiretire bearliar beara tidy tiger is tired

Case #1: the sheep is thinkingCase #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;}

在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;}

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）。

    查找：查找点所在的集合，即根节点。

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