题解

128 条题解

  • 2
    @ 2015-10-15 19:20:46

    很简单的一道题。关键就是深搜(DFS)要想好。
    我们对目前的“龙”设定为NOW变量。假设他现在是ABCDE。
    枚举所有还能用的字符串(用use来统计被用了几次) 比如,有个字符串是DEAAA;
    因为不能是包含关系
    我们先从now中取出BCDE。看看能不能跟需要的拼接上,显然前4位是DEAA,不可以。
    一直取,当我们取到DE的时候正好匹配。那么拼接上,now变成了ABCDEAAA,继续回溯。

    这里有个剪枝。就是我们DE的时候匹配OK了,接下来就不用匹配这个字符串了,因为很容易证明,就算又一次匹配上了也不会比现在的结果要好。(想想看?对吧);

    但是实际上这个剪纸有没有都无所谓。时间是足够的。

    最后匹配结束后,计算now的长度是否大于ans。是就保存
    最后退出

    给出如下代码。
    ###pascal code
    program CODE1018;
    var s:array[1..25] of string;
    ans,i,n:longint;
    use:array[1..25] of longint;
    f:string;
    procedure main(now:string);
    var i,j,len:longint;
    a,b:string;
    begin
    len:=length(now);
    for i:=1 to n do
    if use[i]<2 then
    for j:=2 to length(now) do
    begin
    a:=copy(now,j,length(now)); b:=copy(s[i],1,length(now)-j+1);
    if a=b then
    begin
    inc(use[i]); now:=now+copy(s[i],length(now)-j+2,length(s[i]));
    main(now);
    dec(use[i]); now:=copy(now,1,len);
    end;
    end;
    if length(now)>ans then
    ans:=length(now);
    end;

    begin
    readln(n); ans:=0; fillchar(use,sizeof(use),0);
    for i:=1 to n do
    readln(s[i]);

    readln(f);
    for i:=1 to n do
    if s[i][1]=f then
    begin
    inc(use[i]); main(s[i]); dec(use[i]);
    end;
    write(ans);
    end.

  • 1
    @ 2018-02-04 23:26:27

    不是很懂第7个点Otz,于是借(zhao)鉴(ban)了楼下的方法,DFS时长达0.8s就停止搜索

    #include <iostream>
    #include <ctime>
    
    class Timer
    {
    public:
        struct NeverUsedException {};
    
    private:
        enum class _Status
        {
            NeverUsed,
            Running,
            Stopped
        };
    
        clock_t _startClock;
        clock_t _endClock;
        _Status _status;
    
    public:
        Timer():_status(_Status::NeverUsed) {}
    
        void start()
        {
            _status = _Status::Running;
            _startClock = clock();
        }
        void stop()
        {
            if (_status == _Status::Running)
            {
                _status = _Status::Stopped;
                _endClock = clock();
            }
        }
        bool isRunning()
        {
            return _status == _Status::Running;
        }
        bool isStopped()
        {
            return _status == _Status::Stopped;
        }
        double ellapse()
        {
            switch(_status)
            {
            case _Status::Running:
                return 1.0 * (clock() - _startClock) / CLOCKS_PER_SEC;
            case _Status::Stopped:
                return 1.0 * (_endClock - _startClock) / CLOCKS_PER_SEC;
            case _Status::NeverUsed:
                throw NeverUsedException();
            }
        }
    };
    
    using namespace std;
    
    int N;
    string str[20];
    char firstCh;
    int dist[20][20]; // linkable[a][b] = true if str[a] -> str[b]
    int vis[20];
    Timer timer;
    
    void input()
    {
        cin >> N;
        for (int i = 0; i < N; i++)
            cin >> str[i];
        cin >> firstCh;
    }
    
    int getDist(const string& A, const string& B)
    {
        size_t maxLen = min(A.length(), B.length()) - 1;
        for (size_t len = 1; len <= maxLen; len++)
        {
            bool success = true;
            for (size_t i = A.length() - len, j = 0; j < len; i++, j++)
                if (A[i] != B[j])
                    success = false;
            if (success)
                return (int)(B.length() - len);
        }
        return -1;
    }
    
    void judgeLinkable()
    {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                dist[i][j] = getDist(str[i], str[j]);
    }
    
    int dfs(int cur)
    {
        int ans = 0;
        vis[cur] += 1;
        for (int to = 0; to < N; to++)
            if (vis[to] < 2 && dist[cur][to] != -1 && timer.ellapse() < 0.8)
                ans = max(ans, dist[cur][to] + dfs(to));
        vis[cur] -= 1;
        return ans;
    }
    
    int main()
    {
        input();
        judgeLinkable();
    
        timer.start();
        int ans = 0;
        for (int i = 0; i < N; i++)
            if (str[i][0] == firstCh)
                ans = max(ans, (int)str[i].length() + dfs(i));
    
        printf("%d\n", ans);
        return 0;
    }
    
  • 0

    #include <iostream>
    #include <cstring>
    #include <time.h>
    using namespace std;
    clock_t start, finish;

    char primary_data[45][500],s,present_dragon[500];
    bool judge[25][2];
    int n,present_max,present_length=1,common_length;
    bool judge_dragon(char a[],char b[])
    {
    int length_a,length_b;

    length_a=strlen(a);
    length_b=strlen(b);

    for(int i=1;i<=min(length_a,length_b-1);i++)
    {
    bool present_judge=1;
    for(int j=length_a-i;j<=length_a-1;j++)
    {
    if(a[j]!=b[j-length_a+i])
    present_judge=0;
    }
    if(present_judge)
    {
    common_length=i;
    return 1;
    }
    }
    return 0;
    }
    void dfs(int p)
    {
    finish = clock();
    if(finish-start>900000)
    return;
    for(int i=1;i<=n;i++)
    {
    if((judge[i][0]==0||judge[i][1]==0)&&judge_dragon(present_dragon,primary_data[i]))
    {
    int l,l2;
    l=strlen(present_dragon);
    l2=strlen(primary_data[i]);
    judge[i][0]==0?judge[i][0]=1:judge[i][1]=1;
    for(int j=l;j<=l+l2-common_length;j++)
    present_dragon[j]=primary_data[i][common_length+j-l];

    present_max=max(l+l2-common_length,present_max);

    dfs(p+1);
    judge[i][0]==1?judge[i][0]=0:judge[i][1]=0;
    for(int j=l;j<=l+l2-common_length;j++)
    present_dragon[j]=0;
    }

    }

    return;
    }
    int main()
    {
    ios::sync_with_stdio(false);
    start = clock();

    cin>>n;
    for(int i=1;i<=n;i++)
    cin>>primary_data[i];
    cin>>s;
    present_dragon[0]=s;
    dfs(0);
    cout<<present_max<<endl;
    return 0;
    }

  • 0
    @ 2017-01-22 17:35:54

    const
    maxn=20;
    var
    s:array[1..maxn] of string;
    head:char;
    best,i,n:integer;
    add:array[1..maxn,1..maxn] of integer;
    used:array[1..maxn] of integer;

    procedure calcadd;
    var
    i,j,k,t,min:integer;
    ok:boolean;
    begin
    for i:=1 to n do
    for j:=1 to n do
    begin
    if length(s[i])<length(s[j]) then min:=length(s[i]) else min:=length(s[j]);
    for k:=1 to min-1 do
    begin
    {check}
    ok:=true;
    for t:=1 to k do
    if s[j,t]<>s[i,length(s[i])-k+t] then
    begin
    ok:=false;
    break;
    end;
    if ok then break;
    end;
    if ok then
    add[i,j]:=length(s[j])-k
    else
    add[i,j]:=0;
    end;
    end;

    procedure search(last,len:integer);
    var
    i:integer;
    begin
    if len>best then
    best:=len;
    for i:=1 to n do
    if (add[last,i]>0)and(used[i]<2) then
    begin
    inc(used[i]);
    search(i,len+add[last,i]);
    dec(used[i]);
    end;
    end;

    begin
    readln(n);
    for i:=1 to n do
    readln(s[i]);
    readln(head);
    calcadd;
    best:=0;
    fillchar(used,sizeof(used),0);
    for i:=1 to n do
    if s[i,1]=head then
    begin
    used[i]:=1;
    search(i,length(s[i]));
    used[i]:=0;
    end;
    writeln(best);
    end.

    • @ 2021-08-08 21:34:59

      cnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnmcnm

  • 0
    @ 2016-08-02 10:26:17

    这卡时搜索很可以。。。
    另:数据存在没有龙的情况
    ``` c++
    #include <iostream>
    #include <cstdio>
    #include <ctime>
    #include <cstring>
    using namespace std;

    string stra[30];
    int times[30];
    clock_t b;
    string beg;
    int n;
    int ans = 0;

    bool ispre(string &pre, string &str)
    {
    return str.find(pre) == 0 && pre != str;
    }

    size_t dfs(const string & str)
    {
    //cout << str << endl;
    if (clock() - b >= 800) return 0;
    size_t len = str.length();
    string beh;
    size_t cnt = 0;
    for (size_t i = len-1; i >= 1; i--) {
    beh = str[i]+beh;
    for (size_t j = 1; j <= n; j++) {
    if (times[j] && ispre(beh, stra[j])) {
    times[j]--;
    cnt = max(cnt, dfs(stra[j]) + stra[j].size() - len + i);
    times[j]++;
    }
    }
    }
    return cnt;
    }

    int main()
    {
    b = clock();
    cin >> n;
    for (int i = 1; i <= n; i++) {
    cin >> stra[i];
    times[i] = 2;
    }
    cin >> beg;
    beg = "s"+beg;
    size_t ans = dfs(beg);
    if (ans == 0) cout << 0 << endl;
    else cout << ans+1 << endl;
    return 0;
    }

  • 0
    @ 2016-07-18 20:21:39

    什么叫不能存在真包含 DEFGEF 和EFG不能相连? 看你们的程序没对这点处理啊

  • 0
    @ 2016-03-27 17:54:27

    呵呵~~ 第六个点超时过不去吗?
    这时就要用到**FP的系统单元**了**!**
    开始程序时计时,当到0.9秒时输出。。因为第六个数据卡时间,而算到后面的结果都是都是一样的。
    测试数据 #0: Accepted, time = 0 ms, mem = 920 KiB, score = 12
    测试数据 #1: Accepted, time = 0 ms, mem = 916 KiB, score = 12
    测试数据 #2: Accepted, time = 0 ms, mem = 920 KiB, score = 12
    测试数据 #3: Accepted, time = 15 ms, mem = 916 KiB, score = 12
    测试数据 #4: Accepted, time = 0 ms, mem = 916 KiB, score = 12
    测试数据 #5: Accepted, time = 0 ms, mem = 916 KiB, score = 12
    测试数据 #6: Accepted, time = 906 ms, mem = 928 KiB, score = 16
    测试数据 #7: Accepted, time = 0 ms, mem = 920 KiB, score = 12
    Accepted, time = 921 ms, mem = 928 KiB, score = 100
    ```pascal
    uses sysutils;
    type int=longint;
    var
    time,tt:tdatetime;
    n,max,i,ans:int;
    s:array[0..21]of string;
    f,long:array[0..21]of int;
    m:char;
    procedure dfs(x:int);
    var
    i,t,j:int;
    begin
    if ans>max then max:=ans;
    tt:=now*86400;
    if tt-time>0.9 then
    begin
    writeln(max);
    halt;
    end;
    for i:=1 to n do if f[i]<2 then
    begin
    if long[x]<long[i] then t:=long[x]-1 else t:=long[i]-1;
    for j:=long[x] downto long[x]-t+1 do
    if copy(s[x],j,long[x]-j+1)=copy(s[i],1,long[x]-j+1) then
    begin
    inc(f[i]);
    ans:=ans+long[i]-long[x]+j-1;
    dfs(i);
    ans:=ans-long[i]+long[x]-j+1;
    dec(f[i]);
    break;
    end;
    end;
    end;

    begin
    readln(n); max:=0;
    for i:=1 to n do
    begin
    readln(s[i]);
    long[i]:=length(s[i]);
    end;
    for i:=1 to n do f[i]:=0;
    readln(m);
    time:=now*86400;
    for i:=1 to n do if s[i][1]=m then
    begin
    inc(f[i]);
    ans:=long[i];
    dfs(i);
    dec(f[i]);
    end;
    writeln(max);
    end.
    ```
    不用谢我,我叫**红领巾!**

    • @ 2016-03-28 22:13:13

      666

    • @ 2016-04-23 17:21:35

      系统单元是怎么存在与运用的呢???

    • @ 2016-08-27 15:39:37

      noip好像不允许使用sysutils

    • @ 2016-10-02 14:54:02

      噢,这样啊,谢谢~

  • 0
    @ 2016-03-18 23:32:51
    #include <iostream>
    #include <cmath>
    #include <queue>
    using namespace std;
    int n,m,ans;
    char list[110][110];
    pair <int,int> p0;
    queue<pair <int,int> > q;
    int dx[12] = {-1,-1,-1,0,0,1,1,1,-2,0,0,2},
        dy[12] = {-1,0,1,-1,1,-1,0,1,0,-2,2,0};
    void bfs(pair <int,int> p0)
    {
        pair <int,int>  p;
        q.push(p0);
        list[p0.first][p0.second] = '-';
        while(q.size())
        {
            p = q.front();
            q.pop();
            for (int i = 0; i < 12; i++)
            {
                pair <int,int> np;
                np.first = p.first + dx[i];
                np.second = p.second + dy[i];
                if (abs(np.first-p.first)+abs(np.second-p.second) <= 2 && list[np.first][np.second] == '#')
                {
                    q.push(np);
                    list[np.first][np.second] = '-';
                }
            }
        }
    }
    
    
    int main()
    {
        int i,j;
        while (cin >> n >> m)
        {
            for (i = 0; i < n; i++)
                for (j = 0; j < m; j++)
                    cin >> list[i][j];
    
            for (i = 0; i < n; i++)
                for (j = 0; j < m; j++)
                    if (list[i][j] == '#')
                    {
                        ans++;
                        p0.first = i;
                        p0.second = j;
                    bfs(p0);
                    }
            cout << ans << endl;
        }
        return 0;
    }
    
  • 0
    @ 2015-12-25 14:27:01

    适时地使用windows API可以帮助AC
    朴素搜索有一个点卡时间。经过推测可知该测试点一定是极端数据,搜出的所有解应该都是一样的。
    于是启用 GetTickCount() 函数,当程序运行超过900ms时直接输出答案结束程序,AC

    void search(int index, int length, const int numWords){
    int i;
    if(length > maxLength)
    maxLength = length;
    if(GetTickCount()-beginTime >= 900){
    printf("%d\n", maxLength);
    exit(0);
    }
    for(i=0; i<numWords; i++){
    if(graph[index][i] && usedTimes[i]<2){
    usedTimes[i]++;
    search(i, length+graph[index][i], numWords);
    usedTimes[i]--;
    }
    }
    }

  • 0
    @ 2015-09-17 20:34:30

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<cstring>
    #include<vector>
    using namespace std;
    const int MAXN = 50;

    vector<pair<int, int> > v[MAXN];
    char s[MAXN][MAXN], a;
    int slen[MAXN], ans = 0, big = 0;
    int vis[MAXN];

    void dfs(int node){
    for(int i=0; i<v[node].size(); i++)
    if(vis[v[node][i].first] < 2){
    vis[v[node][i].first]++;
    ans += v[node][i].second;
    dfs(v[node][i].first);
    vis[v[node][i].first]--;
    ans -= v[node][i].second;
    }
    big = max(big, ans);
    }

    int main()
    {
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
    scanf("%s", s[i]);
    slen[i] = strlen(s[i]);
    }
    scanf("%s", &a);
    for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++){
    int len = slen[i] - slen[j];
    if(len < 0)
    len = 0;
    for(int z=slen[i]-1; z>=len; z--){
    int flag = 1;
    for(int y=z; y<slen[i]; y++)
    if(s[i][y] != s[j][y-z]){
    flag = 0;
    break;
    }
    if(flag){
    v[i].push_back(make_pair(j, slen[j]-slen[i]+z));
    break;
    }
    }
    }
    for(int i=1; i<=n; i++)
    if(s[i][0] == a){
    memset(vis, 0, sizeof(vis));
    ans = slen[i];
    vis[i]++;
    dfs(i);
    }
    printf("%d", big);

    return 0;
    }
    只需要暴力即可

  • 0
    @ 2015-08-10 15:38:40

    其实spfa更快但是也接近了0ms吧

    记录信息

    评测状态 Accepted
    题目 P1311 单词接龙
    递交时间 2015-08-10 15:37:27
    代码语言 C++
    评测机 VijosEx
    消耗时间 27 ms
    消耗内存 564 KiB
    评测时间 2015-08-10 15:37:28

    评测结果

    编译成功

    foo.cpp: In function 'int dfs(int, int)':
    foo.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for( i = 0 ; i < linker[ pos ].size() ; i++ )
    ^

    测试数据 #0: Accepted, time = 0 ms, mem = 560 KiB, score = 16

    测试数据 #1: Accepted, time = 12 ms, mem = 556 KiB, score = 16

    测试数据 #2: Accepted, time = 15 ms, mem = 560 KiB, score = 16

    测试数据 #3: Accepted, time = 0 ms, mem = 564 KiB, score = 16

    测试数据 #4: Accepted, time = 0 ms, mem = 560 KiB, score = 16

    测试数据 #5: Accepted, time = 0 ms, mem = 560 KiB, score = 16

    Accepted, time = 27 ms, mem = 564 KiB, score = 96
    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <vector>
    #include <queue>

    using namespace std;

    int n;
    char s[20 + 2][2000 + 2];
    int i , j , k , l , f;
    int len[20 + 2];
    bool flag;

    vector < int > linker[20 + 2];
    vector < int > di[20 + 2];

    int max( int a , int b )
    {
    if( a > b )
    return a;
    return b;
    }
    int power[20 + 2] = { 0 , 1 , 3 , 9 , 27 , 81 , 243 , 729 , 2187 , 6561 , 19683 , 59049 , 177147 , 531441 , 1594323 , 4782969 , 14348907 , 43046721 , 129140163 , 387420489 , 1162261467 };

    int dfs( int pos , int sta )
    {
    int i;
    int c[20 + 2];
    int t = sta;
    for( i = n ; i >= 1 ; i-- )
    {
    c[i] = t / power[i];
    t %= power[i];
    }
    int ans = 0;
    for( i = 0 ; i < linker[ pos ].size() ; i++ )
    if( c[ linker[ pos ][i] ] != 2 )
    ans = max( ans , dfs( linker[ pos ][i] , sta + power[ linker[ pos ][i] ] ) + di[ pos ][i] );
    return ans;
    }

    int main()
    {
    scanf( "%d" , &n );
    for( i = 1 ; i <= n + 1 ; i++ )
    cin >> s[i];
    for( i = 1 ; i <= n + 1 ; i++ )
    len[i] = strlen( s[i] );
    for( i = 1 ; i <= n + 1 ; i++ )
    for( j = 1 ; j <= n ; j++ )
    {
    k = len[i];
    while( 1 )
    {
    k--;
    flag = 0;
    if( len[i] - k > len[j] - 1 )
    break;
    for( f = k , l = 0 ; f < len[i] && l < len[j] - 1 ; f++ , l++ )
    if( s[i][f] != s[j][l] )
    {
    flag = 1;
    break;
    }
    if( !flag )
    {
    linker[i].push_back( j );
    di[i].push_back( len[j] - ( len[i] - k ) );
    break;
    }
    if( k == 0 )
    break;
    }
    }
    cout << dfs( n + 1 , 0 ) + 1 << endl;
    system( "pause" );
    return 0;
    }

  • 0
    @ 2015-08-07 16:18:28

    然而我就来发题解。
    #include<cstdio>
    #include<cstring>
    int a[25],b[25],ans,n;
    char ss[25][110];
    void dfs(int x,int y)
    {
    int i,j,k,l;
    for(i=1;i<=n;i++)
    if(b[i]<2)
    for(j=0;j<a[x];j++)
    if(ss[i][0]==ss[x][j])
    {
    for(l=1,k=j+1;k<a[x]&&ss[i][l]==ss[x][k];k++,l++);
    if(k<a[x]) continue;
    b[i]++;
    dfs(i,y+a[i]-l);
    b[i]--;
    }
    if(y>ans)ans=y;
    }
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<=n;a[i]=strlen(ss[i]),i++) scanf("%s",ss[i]);
    scanf("%s",ss[0]);
    a[0]=strlen(ss[0]);
    dfs(0,a[0]);
    printf("%d\n",ans);
    return 0;
    }

    • @ 2017-10-13 14:43:19

      你这题解不对啊!!!(。・д・。)

  • 0
    @ 2015-06-22 10:54:50

    用邻接矩阵+dfs即可,感谢楼下各位神犇的错误总结

    #include<stdio.h>
    #include<string.h>
    int n;
    char s[21][2000];
    int way[21][21],length[21]={0},hash[21]={0};
    char st;
    int max=-1;

    int min(int a,int b)
    {
    if(a<b) return a;
    else return b;
    }

    void dfs(int s,int ans)
    {
    int i,flag=0;

    for(i=1;i<=n;i++)
    if(way[s][i]!=0 && hash[i]<2) {hash[i]++;dfs(i,ans+length[i]-way[s][i]);hash[i]--;flag=1;}

    if(flag==0 && ans>max) max=ans;
    }

    int main( )
    {

    int i,j,k,z,flag=0;

    scanf("%d\n",&n);

    for(i=1;i<=n;i++)
    {
    gets(s[i]);
    length[i]=strlen(s[i]);
    }

    st=getchar( );

    for(i=0;i<=n;i++)
    for(j=0;j<=n;j++)
    way[i][j]=0;

    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    {

    for(k=1;k<=min(length[i],length[j])-1;k++)
    {
    flag=0;

    for(z=1;z<=k;z++)
    if(s[j][k-z]!=s[i][length[i]-z]) {flag=1;break;}

    if(flag==0) {way[i][j]=k;break;}
    }

    }

    for(i=1;i<=n;i++)
    if(s[i][0]==st) {hash[i]++;dfs(i,length[i]);hash[i]--;}

    printf("%d",max);

    return 0;
    }

  • 0
    @ 2015-05-26 16:12:38

    此水题本人交了3次才过,特此总结一下下面的先人犯的错:
    1、“包含关系”指两个不同字符串间存在某个字符串是另一个字符串的前缀或后缀,同一个字符串间是没有“包含”这个可能的,即可以自连(如tact自连成为tactact);
    2、两个字符串间应删去尽可能少的字符,如hexe和exet合并后应为hexexet(删去了重复的一个e,而不是exe)。

    • @ 2016-07-18 20:00:30

      这题说的真不清楚 /(ㄒoㄒ)/~~

  • 0
    @ 2014-08-16 17:29:00

    #include<cmath>
    #include<cstring>
    #include<iostream>
    using namespace std;
    string str[21];
    int n,f[21][21],sum[21]={0},ans=0;
    char ch;
    int check(int x,int y)
    {
    int d;
    for(d=1;d<min(str[x].size(),str[y].size());d++)
    if(str[x].substr(str[x].size()-d,d)==str[y].substr(0,d))
    return d;
    return 0;
    }
    void dfs(int x,int len)
    {
    int i;
    if(len>ans)
    ans=len;
    for(i=1;i<=n;i++)
    if(f[x][i]&&sum[i]<2)
    {
    sum[i]++;
    dfs(i,len+str[i].size()-f[x][i]);
    sum[i]--;
    }
    }
    main()
    {
    ios::sync_with_stdio(0);
    int i,j;
    cin>>n;
    for(i=1;i<=n;i++)
    cin>>str[i];
    cin>>ch;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    f[i][j]=check(i,j);
    for(i=1;i<=n;i++)
    if(str[i][0]==ch)
    {
    sum[i]++;
    dfs(i,str[i].size());
    sum[i]--;
    }
    cout<<ans;
    }

  • 0
    @ 2013-08-15 14:43:43

    本来WA三个点然后瞎改改竟然AC了==|||
    Var n,i,ans:longint;
    k:char;
    f:array[1..100] of boolean;
    a:array[1..100] of string;
    Function gcd(a,b:string):longint;
    Var i,j:longint;
    Begin
    For i:=length(a) downto 1 do If copy(a,i,length(a)-i+1)=copy(b,1,length(a)-i+1) then exit(length(a)-i+1);
    exit(0);
    End;
    Function max(a,b:longint):longint;
    Begin
    If a>b then exit(a) else exit(b);
    End;
    Function work(word:string):longint;
    Var i,j:longint;
    Begin
    work:=length(word);
    For i:=1 to n do
    If not f[i] then
    If (gcd(word,a[i])<>0) and (gcd(word,a[i])<>length(word)) then
    Begin
    f[i]:=true;
    work:=max(work,work(a[i])+length(word)-gcd(word,a[i]));
    f[i]:=false;
    End;
    End;
    Begin
    readln(n);
    For i:=1 to n do Begin readln(a[i]); a[n+i]:=a[i]; End;
    n:=n*2;
    readln(k);
    For i:=1 to trunc(n/2) do
    If a[i,1]=k then
    Begin
    fillchar(f,sizeof(f),false);
    f[i]:=true;
    ans:=max(ans,work(a[i]));
    End;
    writeln(ans);
    readln;
    End.

  • 0
    @ 2009-11-10 13:21:09

    预处理一下。

    搜索一下。

    AC一下。

    就好了。

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

    真是悲剧……

    每次在学校做嗷嗷错……

    结果回家重新写一遍直接就AC……

    狂郁闷啊!!

    呜呜~~~~(>_

  • 0
    @ 2009-11-04 17:10:23

    编译通过...

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

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

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

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

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

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

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

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

  • 0
    @ 2009-10-30 20:31:23

    编译通过...

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

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

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

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

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

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

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

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

    我就是按照题目中的描述去做了,感觉题目描述的很清楚。。貌似没有楼下的各位所说的特殊情况,一次AC

信息

ID
1311
难度
5
分类
搜索 点击显示
标签
递交数
3155
已通过
1011
通过率
32%
被复制
15
上传者