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

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>
            
中日韩在线视频|
亚洲国产精彩中文乱码av在线播放|
久久免费午夜影院|
亚洲少妇一区|
亚洲精品久久久一区二区三区|
欧美在线视频一区二区|
日韩写真视频在线观看|
影音先锋久久久|
国产欧美日韩免费看aⅴ视频|
欧美日韩岛国|
老司机成人网|
久久久久久久97|
欧美一区二区在线|
亚洲在线免费|
亚洲一区免费看|
亚洲少妇中出一区|
夜夜嗨av一区二区三区四区|
亚洲黄色免费网站|
欧美国产日韩一区二区三区|
久久综合伊人77777|
欧美制服丝袜|
欧美一区二区视频97|
亚洲欧美日韩中文视频|
亚洲专区免费|
亚洲在线视频|
亚洲一区影院|
欧美一级黄色录像|
欧美一区不卡|
久久精品99国产精品|
欧美在线视频免费播放|
久久av资源网|
久久久久国内|
久久亚洲捆绑美女|
毛片精品免费在线观看|
老司机aⅴ在线精品导航|
老巨人导航500精品|
裸体一区二区三区|
欧美成人一区二免费视频软件|
蜜臀91精品一区二区三区|
美日韩精品视频免费看|
欧美mv日韩mv国产网站|
欧美激情免费在线|
亚洲高清视频的网址|
亚洲国产一区二区三区a毛片|
亚洲二区在线视频|
99视频精品全国免费|
在线午夜精品自拍|
香蕉久久一区二区不卡无毒影院|
欧美亚洲三区|
久久天天狠狠|
欧美日产国产成人免费图片|
欧美性一二三区|
国产精品视频区|
国语自产精品视频在线看一大j8
|
久久久噜噜噜|
久热精品视频在线|
亚洲福利一区|
一区二区三区欧美|
亚洲欧美视频在线|
久久人人九九|
欧美日本一区|
国产精品私拍pans大尺度在线|
国产欧美一区二区白浆黑人|
好吊成人免视频|
日韩视频国产视频|
性色av一区二区怡红|
久久亚洲国产精品一区二区|
亚洲电影在线免费观看|
国产精品99久久久久久久久|
欧美一区二区播放|
欧美国产国产综合|
国产欧美日韩一区|
亚洲精品中文字幕女同|
久久er精品视频|
亚洲国产经典视频|
亚洲欧美日本在线|
欧美国产日产韩国视频|
国产欧美精品一区|
亚洲日本中文字幕|
久久国产精品网站|
亚洲经典在线看|
午夜视频在线观看一区二区|
暖暖成人免费视频|
国产在线视频欧美|
野花国产精品入口|
久久综合九色99|
一区二区三区久久久|
麻豆91精品91久久久的内涵|
国产精品美女在线|
亚洲人成网站色ww在线|
欧美一区二区网站|
日韩视频一区二区三区在线播放|
欧美在线黄色|
国产精品亚洲一区二区三区在线|
亚洲日本中文|
美国成人直播|
亚洲欧美在线看|
欧美三级小说|
亚洲美女中出|
欧美成年人视频网站|
午夜视频在线观看一区二区三区|
欧美日韩亚洲一区二|
亚洲大胆人体视频|
久久久亚洲欧洲日产国码αv|
99视频一区|
欧美日韩国产天堂|
亚洲精品乱码久久久久久日本蜜臀|
久久久久久一区二区|
亚洲一区二区三区四区五区黄|
欧美日韩国产麻豆|
日韩小视频在线观看|
欧美激情精品|
农村妇女精品|
亚洲国产一区在线|
欧美成人资源网|
久久蜜桃av一区精品变态类天堂|
国产日韩欧美一区二区三区在线观看
|
狠狠久久综合婷婷不卡|
欧美在线一二三四区|
亚洲天堂黄色|
国产精品久久国产精品99gif|
日韩亚洲精品视频|
亚洲人成网站精品片在线观看|
免费视频最近日韩|
亚洲人成网在线播放|
欧美护士18xxxxhd|
麻豆av一区二区三区久久|
亚洲夫妻自拍|
亚洲国产电影|
欧美激情五月|
亚洲小说区图片区|
亚洲午夜av|
国产精品一区二区三区四区五区
|
亚洲视频在线观看免费|
亚洲另类在线一区|
久久久久久久网|
欧美日韩在线免费观看|
一区二区黄色|
一本久久青青|
国产精品久久久久久一区二区三区|
久久久亚洲人|
欧美日韩在线影院|
久久午夜国产精品|
欧美日韩国产亚洲一区|
久久日韩粉嫩一区二区三区|
欧美韩日视频|
久久久99国产精品免费|
欧美国产日韩精品|
久久精品国产一区二区电影|
欧美国产日韩一二三区|
久久精品国产免费观看|
欧美国产日本高清在线|
久久精品首页|
国产精品v欧美精品v日本精品动漫|
久久夜色精品国产|
国产精品白丝av嫩草影院|
免费日本视频一区|
国产精品亚洲第一区在线暖暖韩国|
欧美高潮视频|
国产手机视频一区二区|
亚洲经典三级|
在线成人av网站|
亚洲欧美日本精品|
一区二区三区高清在线|
欧美一区二区三区在线观看视频
|
亚洲欧洲日韩综合二区|
欧美一进一出视频|
亚洲一区二区三区视频播放|
美女视频黄免费的久久|
欧美在线日韩精品|
欧美日韩亚洲一区二区三区|
欧美激情一区二区三区在线
|
亚洲欧美国产另类|
中文亚洲欧美|
欧美黄色免费网站|
免费视频一区|
国产一区二区成人久久免费影院|
一本久道久久综合狠狠爱|
亚洲区一区二|
久久偷窥视频|
榴莲视频成人在线观看|
国产一区999|
亚洲欧美综合精品久久成人|
亚洲视频在线观看视频|
欧美精品一区二区三区在线看午夜
|
亚洲国产精品一区|
久久精品免费电影|
欧美在线不卡视频|
国产精品日韩欧美一区二区三区
|
久久精品国产77777蜜臀|
亚洲欧美日韩另类精品一区二区三区
|
亚洲精品视频中文字幕|
最新中文字幕亚洲|
老鸭窝亚洲一区二区三区|
老牛影视一区二区三区|
国产综合第一页|
欧美一区二区三区在线视频
|
国产伦精品一区二区三区在线观看|
一本久久知道综合久久|
亚洲午夜激情网页|