Codeforces Round #121

Brief description:

Problem A. Dynasty Puzzles
略。(.G[a][b] 表示以 a 開始 b 結尾的最長串的長度。。最後統計所有 G[a][a] ….

Problem B. Demonstration
讀題壓力巨大,那個啥。。大概的意思是有一個一行 n 的位置,每個位置有一個價值 ai …
然後對立的兩個勢力進行如下的博弈 .
..
A 勢力(以下簡稱進攻方)的目的是得到一個儘可能靠左的位置,
每回合它可以選擇任意一個位置佔據。

B 勢力(以下簡稱防禦方)的目的是使得進攻方的結果儘可能糟糕,
。。每當進攻方選擇了一個位置之後,防禦方可以有以下兩個決策。

1. 花費 ai 塊錢。。讓 A 勢力滾回老家結婚。(該位置永遠無法再次選擇,並且 A 勢力自動獲得最靠右的那個格子)
2. 預算不足。。佔據就佔據吧。。

問一個 k 回合,防禦方資金為 B 的遊戲,進攻方所能得到的最好成績。。

然後題目里一大段不自然的文字大概是說。。
1. 防禦方的策略是貪心的。。(只要有錢就封殺直到沒錢。。
2. 排除一些 bug 情況。。比如如果遊戲途中某個位置進攻方佔領了,它還可以向更左邊的位置進軍。。

。。。
(於是這個題讀懂以後基本演算法就已經給你了。。(為毛我感覺大家做法和我都不一樣 0w0 。。。
。。按 ai 對位置進行排序。。(注意最後一個位置的價值是沒有意義的。。用 0 替代。。
。。之後二分判定。。(。。從大到小。。遇到我們要的格子時暫跳過。。留到最後一回合。。。
。之後再從左到右掃描一遍找到第一個 ≥ 這個值的位置即可。。。)

Problem C. Fools and Roads:
給定一顆 n 個結點的樹,以及 m 對訪問信息。
問每條邊被經過了多少次。。

Problem D. Metro Scheme:
給定一個地鐵圖。。。(。地鐵分兩類。。A 類線形。。B 類環形。。)
。。滿足圖是一個仙人掌圖。。(。一個點最多只可能在一個環上。。)
。問形成這個圖最多和最少需要幾條地鐵線呢。。

Problem E. Thwarting Demonstrations:
給定一個長度為 n 的數組,問在所有區間和之中 (。。共 C(n, 2) 組)。。
第 k 大的是多少。
(.. n <= 10^5 .. .)

Analysis:

Problem C. Fools and Roads:
。。動態樹。(。類似去年多校的 這題。。
。輕重鏈樹鏈剖分。。或者 LCA() + DFS() 都可行。。)

Problem D. Metro Scheme:
。。貌似最多的就是邊數。。於是最小的怎麼求 。。0w0?。。
我就去看了一眼 bjin 的代碼。。發現只要先統計下歐拉路徑的數目。。再在原圖上找環就行了。。。
前者統計下奇數度定點數目 / 2 。。。後者可以直接在圖上縮環。。0w0。。複雜度 O(n)。。。

Problem E. Thwarting Demonstrations:
二份答案判定,則子問題為,大於等於 x 的區間和的數量超過 k 嗎?
這個經典的子問題解決辦法有很多,這裡用實現最容易的樹狀數組。
大概是這個樣子。。

bool f(LL x, LL k) {
    RST(C); REP(i, n){
        Add(lower_bound(a, a + n, s[i]) - a + 1, 1);
        k -= Sum(lower_bound(a, a + n, s[i+1] - x + 1) - a);
        if (k <= 0) return true;
    }
    return false;
}

。。。。

int G[26][26], n;

int main(){

    while (scanf("%d", &n) != EOF && n){

        string s; REP(i, n){
            cin >> s; int a = s[0] - 'a', b = s[SZ(s)-1] - 'a';
            REP(i, 26) if (G[i][a]) checkMax(G[i][b], G[i][a] + SZ(s));
            checkMax(G[a][b], SZ(s));
        }

        int ans = 0; REP(i, 26){
            checkMax(ans, G[i][i]);
        }

        cout << ans << endl;
    }
}
const int N = 100009;

int A[N], O[N]; LL B;
int n, k;

bool comp(int a, int b){
    return A[a] > A[b]  || A[a] == A[b] && a < b;
}

bool f(int x){

    x = O[x];

    int i = 0, t = k - 1; LL b = B;

    while (t){
        if (O[i] == x) ++i;
        b -= A[O[i]];
        ++i, --t;
    }

    return b < A[x];
}

int main(){

    RD(n, k); cin >> B; REP(i, n) RD(A[i]), O[i] = i; A[n-1] = 0;
    sort(O, O + n, comp);

    if (!f(0)){
        cout << n << endl;
        return 0;
    }

    int l = 0, r = n - 2;

    while (l < r){
        int m = (l + r + 1) / 2;
        if (f(m)) l = m;
        else r = m - 1;
    }

    REP(i, n) if (A[i] >= A[O[l]]){
        cout << i + 1 << endl;
        return 0;
    }
}
const int N = 100009, M = 2 * N;

int l[N], r[N], p[N], w0[N], w1[N], delay[N]; bool rt[N];
// Link-cut tree
int hd[N], nxt[M], a[M], b[M];
// Adjacent list

int n, ans;

#define lx l[x]
#define rx r[x]

// private:

inline void Inc(int x, int d){
    if (x == 0) return;
    w0[x] += d, w1[x] += d, delay[x] += d;
}

inline void Release(int x){
    if (x == 0) return;

    if (delay[x]){
        Inc(lx, delay[x]), Inc(rx, delay[x]);
        delay[x] = 0;
    }
}

inline void Update(int x){
    w1[x] = w0[x] + w1[lx] + w1[rx];
}

inline void Set(int l[], int y, int x){
    l[y] = x, p[x] = y;
}

#define z p[y]
inline void Rotate(int x){
    int y = p[x];

    if (!rt[y]) Release(z), Set(y == l[z] ? l : r, z, x);
    else p[x] = z;

    Release(y), Release(x);

    if (x == l[y]) Set(l, y, rx), Set(r, x, y);
    else Set(r, y, lx), Set(l, x, y);

    if (rt[y]) rt[y] = false, rt[x] = true;
    Update(y);
}

inline void Splay(int x){
    while (!rt[x]) Rotate(x);
}

inline int Access(int x){
    int y = 0; do{
        Splay(x), Release(x);
        rt[rx] = true, rt[rx = y] = false, Update(x);
        x = p[y = x];
    } while (x);
    return y;
}

// public:

void Query(int x, int y){
    Access(y), y = 0; do{
        Splay(x); Release(x); if (!p[x]) OT(w1[rx] + w1[y]);
        rt[rx] = true, rt[rx = y] = false; Update(x);
        x = p[y = x];

    } while (x);
}

void Modify(int x, int y, int w){
    Access(y); y = 0; do{
        Splay(x), Release(x); if (!p[x]) Inc(rx, w), Inc(y, w);
        rt[rx] = true, rt[rx = y] = false, Update(x);
        x = p[y = x];
    } while (x);
}

#define v b[i]
inline void dfs(int u = 1){
    for(int i=hd[u];i;i=nxt[i]) if (!p[v]){
        p[v] = u, dfs(v);
    }
}


int main(){

#ifdef LOCAL
    //freopen("in01.txt", "r", stdin);
#endif

    FOR_C(i, 2, _RD(n) << 1){
        RD(a[i], b[i]), a[i|1] = b[i], b[i|1] = a[i];
        nxt[i] = hd[a[i]], hd[a[i]] = i; ++i;
        nxt[i] = hd[a[i]], hd[a[i]] = i;
    }

    FLC(rt, true), p[1] = -1, dfs(), p[1] = 0;

    int x, y; DO_C(RD()){
        RD(x, y); Modify(x, y, 1);
    }

    FOR(i, 1, n) Query(a[i<<1], b[i<<1]);
}
const int N = 100009;
VI adj[N];
int n, m, ans;

int main() {

#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

    int a, b; RD(n, m); REP(i, m){
        RD(a, b), --a, --b, adj[a].PB(b), adj[b].PB(a);
    }

#define deg(x) SZ(adj[x])

    REP(i, n) if (deg(i)&1) ++ans;
    ans >>= 1;

    REP(i, n) if (deg(i) == 2){
        a = adj[i][0], b = adj[i][1];
        if (a == b){
            CLR(adj[a]);
            ++ans;
        }
        else {
            adj[a][adj[a][0] == i ? 0 : 1] = b;
            adj[b][adj[b][0] == i ? 0 : 1] = a;
        }
    }

    printf("%d %d\n", ans, m);
}
const int N = 100009;
int C[N]; LL s[N], a[N];
int n; LL k;

void Add(int x, int d){
    for (int i=x;i<=n;i+=low_bit(i)) C[i] += d;
}

LL Sum(int x){
    LL res = 0; for(int i=x;i;i^=low_bit(i)) res += C[i];
    return res;
}

bool f(LL x, LL k) {
    RST(C); REP(i, n){
        Add(lower_bound(a, a + n, s[i]) - a + 1, 1);
        k -= Sum(lower_bound(a, a + n, s[i+1] - x) - a);
        if (k <= 0) return true;
	}
	return false;
}

//((s[r] - s[l-1]) >= x)
//s[l-1] <= s[r] - x ...

int main() {

#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d %I64d", &n, &k);
	//scanf("%d %lld", &n, &k);

	REP(i, n) s[i+1] = s[i] + RD();
    REP(i, n) a[i] = s[i]; sort(a, a + n);

	LL l = -1e14 - 1, r = 1e14 - 1;
	while (l <= r) {
		LL m = (l + r) / 2;
		if (f(m, k)) l = m + 1;
        else r = m - 1;
	}

	printf("%I64d\n", l);
	//printf("%lld\n", l - 1);
}

External link:

http://www.codeforces.com/contest/191/room/1