程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> Codeforces Round #288 (Div. 2)

Codeforces Round #288 (Div. 2)

編輯：關於C++

A,B,C水

D。

有一個串，長度為n+2，

現在知道他的所有n個長度為3的子串是什麼

求出原始的串

這題跟POJ 2337有點像

最後抽象出的問題就是求歐拉通路：

將每個長度為3的子串，前兩個字母(數字）看成一個結點，後兩個字母(數字）看成一個結點，

然後這個子串就相當於一條從前一個結點到後一個結點的邊

歐拉通路的要求就是所有邊都要走一遍，所以最後就是求歐拉通路了

結點的個數最大為62*62，邊的數量顯然就是n了

因為兩個字母（數字）hash成數字的話也就是62*62種

首先要判斷這個歐拉通路是否存在

首先計算每個結點的入度和出度，

然後如果一個有向圖存在歐拉通路。

則任意結點的出度跟入度的差的絕對值不大於1

並且統計abs(出度-入度)==1 的結點的數量，假設為x個

則x必然為0或者2

如果為0個，則歐拉通路在任意一點都可當做起點

如果為2個，則歐拉通路從（出度-入度）==1 的結點出發

求歐拉通路的時候我們dfs即可，每條邊會有一個編號，保證每條邊只走一次。

但是需要注意的是，這個n是有20萬的，重邊和自環多了會出一些問題。

所以我就將重邊看成1條，但是對其計數，在dfs的時候用邊的數量當做是否訪問過的標記

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MAXN 111111
#define MAXM 1122222
#define INF 1000000007
#define eps 1e-8
using namespace std;
int n;
typedef pair PII;
vector g[66 * 66];
int num[66 * 66];
int in[66 * 66], out[66 * 66];
int fa[66 * 66], v[66 * 66];
int en[66 * 66][66 * 66];
int vis[222222], nv[222222];
int st[222222];
char s[211111][6];
int find(int x) {
    if(x == fa[x]) return x;
    int t = find(fa[x]);
    fa[x] = t;
    return t;
}
void join(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if(fx != fy) fa[fx] = fy;
}
int getc(char c) {
    if(c >= 'a' && c <= 'z') return c - 'a';
    if(c >= 'A' && c <= 'Z') return c - 'A' + 26;
    return c - '0' + 52;
}
int ind;
void dfs(int u, int eid) {
    for(int i = 0; i < g[u].size(); i++) {
        int tid = g[u][i].second;
        if(vis[tid]) {
            vis[tid] --;
            dfs(g[u][i].first, tid);
        }
    }
    if(eid) st[ind++] = eid;
}
int main()
{

    scanf("%d", &n);
    for(int i = 0; i < 66 * 66; i++) fa[i] = i;
    for(int i = 1; i <= n; i++) {
        scanf("%s", s[i]);
        int a = getc(s[i][0]);
        int b = getc(s[i][1]);
        int c = getc(s[i][2]);
        int id1 = a * 62 + b;
        int id2 = b * 62 + c;
        v[id1] = 1; v[id2] = 1;
        join(id1, id2);
        if(en[id1][id2] == 0) en[id1][id2] = i, g[id1].push_back(PII(id2, i));
        in[id2]++;
        out[id1]++;
        vis[en[id1][id2]]++;

    }
    int tmp = -1, flag = 0;
    for(int i = 0; i < 66 * 66; i++) {
        if(!v[i]) continue;
        if(tmp == -1) tmp = find(i);
        else {
            if(tmp != find(i)) {
                flag = 1;
                break;
            }
        }
    }
    int cnt = 0, src = -1;
    for(int i = 0; i < 66 * 66; i++) {
        if(!v[i]) continue;
        if(abs(in[i] - out[i]) >= 2) {
            flag = 1;
            break;
        } else if(abs(in[i] - out[i]) == 1) {
            cnt ++;
            if(out[i] - in[i] == 1) src = i;
        }
    }
    if(src == -1) src = tmp;
    if(flag) {
        printf("NO\n");
    } else if(cnt == 0 || cnt == 2) {
        dfs(src, 0);
        printf("YES\n");
        for(int i = ind - 1; i >= 0; i--) {
            int tid = st[i];
            if(i == ind - 1) printf("%s", s[tid]);
            else printf("%c", s[tid][2]);
        }
        printf("\n");
    } else {
        printf("NO\n");
    }
    return 0;
}

題意是

給出n個區間。

然後第i個區間表示的是第i個左括號與右括號的下標距離范圍

求出一個合法的括號序列並且滿足這些范圍

然後後來想了想，貌似是個記憶化dp，而且並不難。。

令dp[i][j]表示第i個到第j個左括號是否都成功的匹配到了右括號

那麼在dfs的時候，對於dp[i][j] ，我們枚舉i被第幾個右括號匹配了，顯然是從第i個右括號枚舉到第j個右括號，假設被第k個右括號匹配並且滿足之前給的范圍了

然後就可以去尋找其子狀態 dp[i + 1][k] 以及dp[k+1][j]

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define MAXN 111111
#define MAXM 1122222
#define INF 1000000007
#define eps 1e-8
using namespace std;
int dp[666][666];
int l[666], r[666];
char s[3333];
int n;
int p[3333];
int dfs(int L, int R) {
    if(L > R) return 1;
    if(dp[L][R]) return dp[L][R];
    for(int i = L; i <= R; i++) {
        if(i - L + 1 >= l[L] && i - L + 1 <= r[L] ) {
            if(dfs(L + 1, i) == 1 && dfs(i + 1, R) == 1) {
                p[L] = (i - L) * 2 + 1;
                return dp[L][R] = 1;
            }
        }
    }
    return dp[L][R] = -1;
}
int main()
{
    scanf("%d", &n);
    int flag = 1;
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &l[i], &r[i]);
        if(l[i] % 2 == 0) l[i]++;
        if(r[i] % 2 == 0) r[i]--;
        if(l[i] > r[i]) {
            flag = 0;
        }
        l[i] = (l[i] + 1) / 2;
        r[i] = (r[i] + 1) / 2;
    }
    if(flag == 0) {
        printf("IMPOSSIBLE\n");
        return 0;
    }
    dfs(1, n);
    if(dp[1][n] != 1) {
        printf("IMPOSSIBLE\n");
        return 0;
    }
    int j = 0;
    for (int i = 1 ; i <= n; i++){
        while(s[j]) ++j;
        s[j] = '(';
        s[j + p[i]] = ')';
    }
    puts(s);
    return 0;
}