青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

posts - 33,  comments - 33,  trackbacks - 0
Selecting World Finals Teams on Mars I
題解：
dfs模擬
代碼：
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

const int N = 10005;

struct Node
{
    int id;
    int s;
    friend bool operator < (const Node& _n1,const Node& _n2)
    {
        if(_n1.s == _n2.s)
            return _n1.id < _n2.id;
        return _n1.s > _n2.s;
    }
};

vector<int> graph[N];//contest info
vector<int> contest[N];//contest(i) contains team
vector<int> result[N];
string name[5005];
int s[5005];
bool visited[N];

int n,m;

void init()
{
    for (int i = 1; i <= n; ++i)
    {
        graph[i].clear();
        contest[i].clear();
        result[i].clear();
    }
    memset(visited,0,sizeof(visited));
}

void input()
{
    int x,y;
    for (int i = 0; i < n+m - 1; ++i)
    {
        scanf("%d %d",&x,&y);
        if(x <= n && y <= n)
        {
            graph[x].push_back(y);
            graph[y].push_back(x);
        }
        else
        {
            int kx = min(x,y);
            int ky = max(x,y);
            contest[kx].push_back(ky - n);
        }
    }
    char buf[300];
    int k;
    for (int i = 1; i <= m; ++i)
    {
        scanf("%s %d",buf,&k);
        name[i] = string(buf);
        s[i] = k;
    }
}

void dfs(int _cur)
{
    visited[_cur] = true;
    if(graph[_cur].size() == 0)//leaf
    {
        vector<Node> tmp;
        Node node;
        for (int i = 0 ; i < contest[_cur].size(); ++i)
        {
            node.id = contest[_cur][i];
            node.s = s[node.id];
            tmp.push_back(node);
        }
        sort(tmp.begin(),tmp.end());
        int kn;
        if(_cur != 1)
            kn = min(2,(int)tmp.size());
        else
            kn = (int)tmp.size();
        for (int i = 0; i < kn; ++i)
        {
            result[_cur].push_back(tmp[i].id);
        }
    }
    else
    {
        vector<Node> tmp;
        Node node;
        for (int i = 0; i < graph[_cur].size(); ++i)
        {
            int next = graph[_cur][i];
            if(!visited[next])
            {
                dfs(next);
                for (int j = 0; j < result[next].size(); ++j)
                {
                    node.id = result[next][j];
                    node.s = s[node.id];
                    tmp.push_back(node);
                }
            }
        }
        for (int i = 0 ; i < contest[_cur].size(); ++i)
        {
            node.id = contest[_cur][i];
            node.s = s[node.id];
            tmp.push_back(node);
        }
        sort(tmp.begin(),tmp.end());
        int kn ;
        if(_cur != 1)
            kn = min(2,(int)tmp.size());
        else
            kn = (int)tmp.size();
        for (int i = 0; i < kn; ++i)
        {
            result[_cur].push_back(tmp[i].id);
        }
    }
}

void Test()
{
    init();
    input();
    dfs(1);
    vector<Node> tmp;
    Node node;
    for (int i = 0; i < result[1].size(); ++i)
    {
        node.id = result[1][i];
        node.s = s[node.id];
        tmp.push_back(node);
    }
    sort(tmp.begin(),tmp.end());
    for (int i = 0; i < tmp.size(); ++i)
    {
        printf("%s\n",name[tmp[i].id].c_str());
    }
}

int main()
{
    //freopen("data.txt","r",stdin);
    while (scanf("%d %d",&n,&m) != EOF)
    {
        Test();
    }
    return 0;
}



Hamilton Circles
題解：
找規律，矩陣快速冪
代碼：
#include <stdio.h>
#include<algorithm>
using namespace std;

int tc;

struct Matrix2x2
{
    Matrix2x2()
    {
        for (int i = 0; i < 2; ++i)
        {
            for (int j = 0; j < 2; ++j)
            {
                a[i][j] = 1;
            }
        }
    }
    long long a[2][2];
    void mul(Matrix2x2& _c)
    {
        long long b[2][2];
        b[0][0] = (a[0][0]*_c.a[0][0] + a[0][1]*_c.a[1][0])%1000000007 ;
        b[0][1] = (a[0][0]*_c.a[0][1] + a[0][1]*_c.a[1][1])%1000000007 ;
        b[1][0] = (a[1][0]*_c.a[0][0] + a[1][1]*_c.a[1][0])%1000000007 ;
        b[1][1] = (a[1][0]*_c.a[0][1] + a[1][1]*_c.a[1][1])%1000000007 ;
        a[0][0] = b[0][0];
        a[0][1] = b[0][1];
        a[1][0] = b[1][0];
        a[1][1] = b[1][1];
    }
};

Matrix2x2 param;
long long pas[2][2] = {3,2,1,1};

Matrix2x2 quickMul(Matrix2x2 _k,int _p)
{
    if(_p == 1)
        return _k;
    if(_p %2 == 1)
    {
        Matrix2x2 ret = quickMul(_k,_p/2);
        Matrix2x2 tmp = ret;
        ret.mul(tmp);
        ret.mul(_k);
        return ret;
    }
    else
    {
        Matrix2x2 ret = quickMul(_k,_p/2);
        Matrix2x2 tmp = ret;
        ret.mul(tmp);
        return ret;
    }
}

void Test()
{
    int n = 0;
    scanf("%d",&n);
    if(n == 1)
    {
        printf("%d\n",1);
    }
    else if(n == 2)
    {
        printf("%d\n",6);
    }
    else
    {
        Matrix2x2 pp =  quickMul(param,n - 2);
        long long ans1 = 4,ans2 = 2;
        long long ans3 = (pp.a[0][0]*ans1 + pp.a[0][1]*ans2)%1000000007;
        long long ans4 = (pp.a[1][0]*ans1 + pp.a[1][1]*ans2)%1000000007;
        printf("%lld\n",(ans3+ans4)%1000000007);
    }
}

int main()
{
    //freopen("data.txt","r",stdin);
    for (int i = 0; i < 2; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            param.a[i][j] = pas[i][j];
        }
    }
    scanf("%d",&tc);
    for (int i = 0; i < tc; ++i)
    {
        printf("Case %d: ",i+1);
        Test();
    }
    return 0;
}




Word Ladder
題解：暴搜，首先用hash預處理字符串建圖
代碼：
#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <vector>
using namespace std;

string name[6005];
vector<int> next[6005];
map<string,int> Map;
int visited[6005];
int len;
string start,end;

void input()
{
    len = 0;
    char buf[128];
    scanf("%s",buf);
    start = string(buf);
    scanf("%s",buf);
    end = string(buf);
    while (scanf("%s",buf) != EOF)
    {
        name[len] = string(buf);
        Map[name[len]] = len;
        ++len;
    }
}

void pre_process()
{
    for (int i = 0; i < len; ++i)
    {
        int cLen = name[i].length();
        string tmp = name[i];
        for (int j = 0; j < cLen; ++j)
        {
            char cl = tmp[j];
            for (int k = 'a'; k <= 'z'; ++k)
            {
                if(k != cl)
                {
                    tmp[j] = k;
                    map<string,int>::iterator it = Map.find(tmp);
                    if(it != Map.end())
                    {
                        next[i].push_back(it->second);
                    }
                }
            }
            tmp[j] = cl;
        }
    }
}

int BFS()
{
    memset(visited,0,sizeof(visited));
    queue<int> que;
    int startId = Map[start];
    int endID = Map[end];
    que.push(startId);
    visited[startId] = 1;
    while(!que.empty())
    {
        int curState = que.front();
        que.pop();
        if(curState == endID)
            return visited[endID] ;
        for (int i = 0; i < next[curState].size(); ++i)
        {
            int extState = next[curState][i];
            if (visited[extState] == 0)
            {
                visited[extState] = visited[curState] + 1;
                que.push(extState);
            }
        }
    }
    return -1;
}

int main()
{
    //freopen("data.txt","r",stdin);
    input();
    pre_process();
    int ret = BFS();
    printf("%d\n",ret);

    return 0;
}





Daka
題解：模擬
代碼：
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;

long long table[3] = {1L,100L,10000L};

struct Node
{
    int hh,mm,ss,yyyy,MM,dd;
    friend bool operator < (const Node& _node1,const Node& _node2)
    {
        if(_node1.yyyy == _node2.yyyy)
        {
            if(_node1.MM == _node2.MM)
            {
                if(_node1.dd == _node2.dd)
                {
                    if(_node1.hh == _node2.hh)
                    {
                        if(_node1.mm == _node2.mm)
                        {
                            return (_node1.ss < _node2.ss);
                        }
                        return _node1.mm == _node2.mm;
                    }
                    return _node1.hh < _node2.hh;
                }
                return _node1.dd < _node2.dd;
            }
            return _node1.MM < _node2.MM;
        }
        return _node1.yyyy < _node2.yyyy;
    }
};
Node nodes[20000];

long long getHash(const Node& _node)
{
    return (long long)(_node.dd)*table[0] + 
                (long long)(_node.MM)*table[1]+
                (long long)(_node.yyyy)*table[2];
}

int getTime(const Node& _node)
{
    return (_node.ss) + (_node.mm*60) + (_node.hh*3600);
}

Node mEx1,mEx2;
Node mHa1,mHa2;

int main()
{
    //freopen("data.txt","r",stdin);
    mEx1.mm = 0;mEx1.hh = 7;mEx1.ss = 0;
    mEx2.mm = 30;mEx2.hh = 8;mEx2.ss = 0;
    mHa1.mm = 0;mHa1.hh = 16;mHa1.ss = 0;
    mHa2.mm = 30;mHa2.hh = 21;mHa2.ss = 0;
    int mTEx1 = getTime(mEx1);int mTEx2 = getTime(mEx2);
    int mTHa1 = getTime(mHa1);int mTHa2 = getTime(mHa2);
    int morEx = 0,halfEx = 0;
    Node node;
    int len = 0;
    set<long long> Set;
    set<long long> Set2;
    while(scanf("%d %d %d %d %d %d",&(node.hh),&(node.mm),&(node.ss),&(node.yyyy),&(node.MM),&(node.dd)) != EOF)
    {
        nodes[len++] = node;
    }
    sort(nodes ,nodes + len);
    for(int i = 0 ; i < len ; ++i)
    {
        int time = getTime(nodes[i]);
        if((time >= mTEx1) && (time <= mTEx2))
        {
            if(Set.find(getHash(nodes[i])) == Set.end())
            {
                Set.insert(getHash(nodes[i]));
                ++morEx;
            }
        }
        else if((time >= mTHa1) && (time <= mTHa2))
        {
            int hashCode = getHash(nodes[i]);
            int j = i;
            while(j < len && (getHash(nodes[j]) == hashCode))
                ++j;
            if(i != j)
            {
                j = j-1;
                if(getTime(nodes[j]) - getTime(nodes[i]) >= 30*60)
                {
                    ++halfEx;
                }
            }
            i = j ;
        }
    }
    if(morEx <= 10)
        printf("%d ",10 - morEx);
    else
        printf("0 ");
    if(halfEx <= 20)
        printf("%d\n",20 - halfEx);
    else
        printf("0\n");
    return 0;
}


A Problem about Tree
題解：當更換樹的根結點時，只有原根結點到更新的根結點之間經過的路徑的所有結點的父子關系發生變化。
代碼：
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

const int N = 10005;

vector<int> graph[N];

int father[N];

void dfs(int _father,int _cur)
{
    father[_cur] = _father;
    for (int i = 0; i < graph[_cur].size(); ++i)
    {
        if (father[graph[_cur][i]] == 0)
        {
            dfs(_cur,graph[_cur][i]);
        }
    }
}

void init(int _n)
{
    for (int i = 1; i <= _n; ++i)
    {
        graph[i].clear();
    }
}

void query(int _x,int _y)
{
    int chi = _x;
    int par = father[_x];
    while (par != -1)
    {
        if(par == _y)
        {
            printf("%d\n",chi);
            return;
        }
        chi = par;
        par = father[par];
    }
    printf("%d\n",father[_y]);
}

void Test()
{
    int n,q;
    scanf("%d %d",&n,&q);
    init(n);
    int a,b;
    for (int i = 1; i < n; ++i)
    {
        scanf("%d %d",&a,&b);
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    memset(father,0,sizeof(father));
    dfs(-1,1);
    int x,y;
    for (int i = 0; i < q; ++i)
    {
        scanf("%d %d",&x,&y);
        query(x,y);
    }
}

int main()
{
    int tc;
    scanf("%d",&tc);
    for (int i = 0; i < tc; ++i)
    {
        Test();
    }
    return 0;
}







posted on 2011-05-24 20:39 bennycen 閱讀(1429) 評論(0)  編輯 收藏 引用 所屬分類: 算法題解
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            
欧美日韩精品一区视频|
国产专区综合网|
中文在线资源观看网站视频免费不卡|
亚洲国产欧美一区二区三区同亚洲|
性欧美1819性猛交|
精品91在线|
亚洲国产婷婷综合在线精品|
欧美激情一区在线|
亚洲欧美成人一区二区三区|
亚洲视频在线一区|
中文av一区特黄|
国产香蕉97碰碰久久人人|
另类尿喷潮videofree|
久久久之久亚州精品露出|
亚洲伦理在线|
亚洲天天影视|
尤物精品国产第一福利三区|
亚洲高清不卡在线观看|
欧美日韩国产成人在线免费|
午夜伦欧美伦电影理论片|
久久精品视频在线播放|
99精品国产99久久久久久福利|
99riav久久精品riav|
国产欧美精品xxxx另类|
免费日韩av电影|
欧美日韩国产综合视频在线|
久久久国产精品亚洲一区
|
欧美在线观看日本一区|
久久er99精品|
宅男噜噜噜66一区二区|
欧美黄在线观看|
国产精品裸体一区二区三区|
猫咪成人在线观看|
欧美三级乱码|
另类综合日韩欧美亚洲|
国产精品国色综合久久|
亚洲娇小video精品|
国产精品一区二区久激情瑜伽|
亚洲成人中文|
牛牛精品成人免费视频|
欧美在线一级va免费观看|
免费欧美在线视频|
久久久亚洲国产美女国产盗摄|
欧美精品一区二区三区一线天视频|
久久久美女艺术照精彩视频福利播放
|
亚洲欧美日韩一区二区|
欧美大片在线观看|
麻豆久久精品|
国产一区久久久|
亚洲一二区在线|
亚洲无线观看|
欧美大片专区|
欧美成人精品高清在线播放|
国产日韩欧美一区在线|
亚洲视频在线观看视频|
亚洲香蕉在线观看|
欧美日韩国内|
亚洲美女淫视频|
99re66热这里只有精品3直播|
乱中年女人伦av一区二区|
久久久久高清|
好吊日精品视频|
久久精品国产清高在天天线|
久久成年人视频|
国产亚洲一区二区三区在线观看|
国产精品99久久久久久久久|
亚洲视频专区在线|
欧美日韩一二区|
中国成人黄色视屏|
亚洲女同同性videoxma|
国产精品久久久久久久久久久久久久|
日韩一级大片|
亚洲欧美一区二区在线观看|
国产精品影音先锋|
欧美在线视频二区|
美女在线一区二区|
亚洲国产片色|
欧美激情视频一区二区三区不卡|
91久久国产综合久久蜜月精品|
99精品99|
国产精品视频xxxx|
欧美在线一级va免费观看|
久久久久国产成人精品亚洲午夜|
激情欧美一区二区|
欧美国产一区视频在线观看|
亚洲人午夜精品免费|
亚洲一区二区在线播放|
国产酒店精品激情|
久久久久国产精品午夜一区|
亚洲国产91|
性8sex亚洲区入口|
在线成人av.com|
欧美日韩国产小视频|
亚洲欧美激情一区二区|
亚洲毛片一区|
国产精品日韩一区二区三区|
欧美在线视频观看|
亚洲欧洲视频|
久久久久久久精|
亚洲毛片在线观看.|
国产精品日韩欧美综合|
老巨人导航500精品|
一本色道久久99精品综合|
久久国产综合精品|
日韩午夜电影|
国产在线精品一区二区中文|
欧美激情按摩|
久久久精品动漫|
亚洲美女网站|
欧美成人资源|
欧美有码在线视频|
99ri日韩精品视频|
国产一区二区三区黄视频|
欧美日韩一区二区三区|
久久亚洲国产精品日日av夜夜|
亚洲视频专区在线|
亚洲欧洲另类|
欧美www在线|
欧美一区免费视频|
在线亚洲精品|
91久久精品一区|
激情综合视频|
国产欧美精品|
国产精品久久久久9999吃药|
欧美国产精品久久|
久久婷婷亚洲|
久久超碰97中文字幕|
亚洲一区二区三区777|
99香蕉国产精品偷在线观看|
欧美国产专区|
欧美1区2区视频|
久久一综合视频|
久久久久一区二区三区|
久久成人免费视频|
亚洲欧美日韩在线一区|
中日韩男男gay无套|
一区二区三区成人|
日韩亚洲成人av在线|
亚洲人成在线免费观看|
最新国产乱人伦偷精品免费网站|
精品成人免费|
亚洲高清视频在线观看|
欧美日韩亚洲成人|
欧美人交a欧美精品|
欧美电影在线观看完整版|
卡通动漫国产精品|
欧美高清在线一区二区|
欧美激情一二区|
欧美另类久久久品|
欧美日韩午夜|
国产精品捆绑调教|
国产亚洲人成a一在线v站|
国产日韩亚洲欧美精品|
红桃视频亚洲|
亚洲欧洲日夜超级视频|
99re66热这里只有精品4|
亚洲视频在线二区|
新67194成人永久网站|
欧美在线观看网址综合|
久久久久欧美精品|
你懂的国产精品|
欧美黑人一区二区三区|
亚洲欧洲在线看|
亚洲综合日韩|
久久久久九九九|
欧美精品一区二区三区在线看午夜|
欧美日韩精品免费观看视一区二区|
欧美性片在线观看|
黄页网站一区|
日韩视频在线一区二区三区|
亚洲一级在线|
久久久久久久成人|
亚洲精品国久久99热|
亚洲视频在线观看三级|
久久精品一区二区国产|
欧美久久久久久久|
国产色产综合产在线视频|
亚洲国产一区二区三区青草影视
|
国内免费精品永久在线视频|
尤物yw午夜国产精品视频明星|
日韩亚洲不卡在线|
久久国产精品黑丝|
亚洲精品乱码久久久久久蜜桃91
|
蜜桃伊人久久|
国产精品女主播一区二区三区|
激情综合亚洲|
亚洲欧美日韩视频一区|
欧美高清视频免费观看|
亚洲欧美日韩国产|
欧美大片在线影院|
韩日精品在线|
亚洲欧美日本日韩|
欧美激情亚洲激情|
欧美一区=区|
国产精品久久毛片a|
最新国产乱人伦偷精品免费网站|
久久激情一区|
亚洲视屏在线播放|
欧美日韩国产成人精品|
亚洲国内高清视频|