天天看點
傳回

Codeforces #310（div2）

A. Case of the Zeros and Ones

題意: 我愛消除 - - 相鄰的01就會被消除 問最後能剩下多少~

思路: 仔細觀察我們發現 隻要存在不相同的數 那麼它們一定會被消除 最後一定為全0或者全1序列

那麼答案就是abs(n_'0' - n_'1')了

參考code:

//
//  Created by TaoSama on 2015-06-27
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n;
string s;

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(cin >> n >> s) {
		int cnt = 0;
        for(int i = 0; i < n; ++i)
			if(s[i] == '0') ++cnt;
		cout << abs(n - 2 * cnt) << '\n';
    }
    return 0;
}

B. Case of Fake Numbers

題意: 有一些gear 它們的tooth是 逆時針0-n-1放置的 奇數位置的是逆時針轉 偶數位置是順時針 問同時轉多少次 可以使得序列變成0-n-1

思路: 枚舉兩個gear的合法狀态 判斷後面的gear是否合法 根據鴿籠原理 枚舉n^2次就夠了 (據說n次就可以了？)

參考code:

//
//  Created by TaoSama on 2015-06-27
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, a[1005];

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(cin >> n) {
        for(int i = 1; i <= n; ++i) cin >> a[i];
        if(n == 1) {
            cout << "YES\n";
            continue;
        }
        bool ok = false;
        for(int t = 0; t <= 1e7; ++t) {
            int x = (a[1] + t) % n, y = ((a[2] - t) % n + n) % n;
            if(x == 0 && y == 1) {
                bool can = true;
                for(int i = 3; i <= n; i ++) {
                    if(i & 1) {
                        int x = (a[i] + t) % n;
                        if(x != i - 1) {
                            can = false;
                            break;
                        }
                    } else {
                        int y = ((a[i] - t) % n + n) % n;
                        if(y != i - 1) {
                            can = false;
                            break;
                        }
                    }
                }
                if(can) {
                    ok = true;
                    break;
                }
            }
        }
        cout << (ok ? "YES" : "NO") << endl;
    }
    return 0;
}

C. Case of Matryoshkas

題意: 俄羅斯套娃 - - 反正 仔細讀題吧  最後就是求1開頭的鍊有多長 其它的都要拆開

思路: 題讀懂大家應該都會 - -

參考code: 

//
//  Created by TaoSama on 2015-06-27
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, k;
vector<int> a[N];

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(cin >> n >> k) {
        long long Max = 1, idx, ans = 0;
        for(int i = 1; i <= k; ++i) {
            int m; cin >> m;
            a[i].clear();
            for(int j = 1; j <= m; ++j) {
                int x; cin >> x;
                a[i].push_back(x);
            }
        }
        for(int i = 1; i <= k; ++i) {
            int cnt = 1;
            if(a[i][0] == 1) {
                idx = i;
                for(int j = 1; j < a[i].size(); ++j) {
                    if(a[i][j] - a[i][j - 1] == 1) ++Max;
                    else break;
                }
            }
            ans += a[i].size() - 1;
        }
        long long sum = n - Max + 1;
        ans = ans - (a[idx].size() - 1) + (a[idx].size() - Max) + sum - 1;
        cout << ans << endl;
    }
    return 0;
}

D. Case of Fugitive

題意: 給相鄰的島放橋 然後相鄰島的距離範圍 給出了計算公式 其實就是[l2 - r1, r2 - l1]這個區間 然後看能不能放 可以輸出放的姿勢

思路: 貪心 兩種思路都行 如果降序排序l,r 那麼每次對于r找一個滿足它的最大的橋 然後判斷這個橋滿不滿足l 

必須每個島間都找到橋 找不到就是no 記錄一下橋就好了

當然升序類似~ - - 

參考code:

//
//  Created by TaoSama on 2015-06-28
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 2e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

typedef long long LL;
pair<pair<LL, LL>, int> a[N];
set<pair<LL, int> > s;
int n, m, ans[N];

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(cin >> n >> m) {
        LL _l, _r, l, r;
        cin >> _l >> _r;
        for(int i = 1; i < n; ++i) {

            cin >> l >> r;
            a[i] = {{_r - l, _l - r}, i};
            _l = l, _r = r;
        }
        s.clear();
        for(int i = 1; i <= m; ++i) {
            LL x; cin >> x;
            s.insert({x, i});
        }
        sort(a + 1, a + n);

        bool ok = true;
        for(int i = 1; i < n; ++i) {
            LL l = -a[i].first.first, r = -a[i].first.second;
            auto k = s.lower_bound({r, INF});
            if(k == s.begin()) {
                ok = false;
                break;
            }
            k--;
            if(k->first < l) {
                ok = false;
                break;
            }
            ans[a[i].second] = k->second;
            s.erase(k);
        }
        if(ok) {
            cout << "Yes\n";
            for(int i = 1; i < n; ++i)
                cout << ans[i] << ' ';
            cout << '\n';
        } else cout << "No\n";
    }
    return 0;
}

E. Case of Chocolate

題意: 每次從主對角線的一個位置出發 吃一列或者一行 如果碰到吃過的或者出邊界  就不能吃了 問每次吃多少個

思路: 

Codeforces #310（div2）
Codeforces #310（div2）

n = 10^9很大 - - 是以先離線然後離散化坐标~   維護兩棵線段樹 X和Y  X表示被吃的格子的最大的y坐标 Y同理  一開始都是0

這樣 舉個例子 比如 3 4 U 查詢X(x = 3)得到這個max是0 然後ans = y - max = 4 - 0 = 4 然後用x = 3更新Y的[max = 0, y = 4]的區間

下次查詢6 1 L 查詢Y(y = 1)得到這個max是剛才的3 然後ans = x - max = 6 - 3 = 3  然後用y = 1更新X的[max = 3, x = 6]的區間

這樣就ok了 可以動态建樹不用離散化 改天補 然後set也可以搞

參考code:

//
//  Created by TaoSama on 2015-06-28
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 2e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1

struct SegTree {
    int Max[N * 6], lazy[N * 6];

    void push_up(int rt) {
        Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]);
    }

    void push_down(int rt) {
        if(~lazy[rt]) {
            Max[rt << 1] = max(Max[rt << 1], lazy[rt]);
            Max[rt << 1 | 1] = max(Max[rt << 1 | 1], lazy[rt]);
            lazy[rt << 1] = max(lazy[rt << 1], lazy[rt]);
            lazy[rt << 1 | 1] = max(lazy[rt << 1 | 1], lazy[rt]);
            lazy[rt] = -1;
        }
    }

    void build(int l, int r, int rt) {
        Max[rt] = 0; lazy[rt] = -1;
        if(l == r) return;
        int m = l + r >> 1;
        build(lson);
        build(rson);
        push_up(rt);
    }

    void update(int L, int R, int v, int l, int r, int rt) {
        if(L <= l && r <= R) {
            lazy[rt] = max(lazy[rt], v);
            Max[rt] = max(Max[rt], lazy[rt]);
            return;
        }
        int m = l + r >> 1;
        push_down(rt);
        if(L <= m) update(L, R, v, lson);
        if(R > m) update(L, R, v, rson);
        push_up(rt);
    }

    int query(int o, int l, int r, int rt) {
        if(l == r) return Max[rt];
        int m = l + r >> 1;
        push_down(rt);
        if(o <= m) return query(o, lson);
        else return query(o, rson);
    }
};

SegTree X, Y;
int n, q;
int ox[N], oy[N];
bool vx[N], vy[N];
char op[N][2];

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(scanf("%d%d", &n, &q) == 2) {
        memset(vx, false, sizeof vx);
        memset(vy, false, sizeof vy);
        vector<int> xs, ys;
        for(int i = 1; i <= q; ++i) {
            scanf("%d%d%s", ox + i, oy + i, op[i]);
            xs.push_back(ox[i]);
            ys.push_back(oy[i]);
        }
        sort(xs.begin(), xs.end());
        sort(ys.begin(), ys.end());
        xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
        ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
        X.build(1, xs.size(), 1); Y.build(1, ys.size(), 1);

        for(int i = 1; i <= q; ++i) {
            int x = lower_bound(xs.begin(), xs.end(), ox[i]) - xs.begin() + 1;
            int y = lower_bound(ys.begin(), ys.end(), oy[i]) - ys.begin() + 1;
//            pr(x); prln(y);
            if(*op[i] == 'U') {
                if(vx[x]) {
                    puts("0");
                    continue;
                }
                vx[x] = true;
                int Max = X.query(x, 1, xs.size(), 1);
//                pr(Max);
                printf("%d\n", oy[i] - Max);
                int k = lower_bound(ys.begin(), ys.end(), Max) - ys.begin() + 1;
//                pr(k); prln(ox[i]);
                Y.update(k, y, ox[i], 1, ys.size(), 1);
            } else {
                if(vy[y]) {
                    puts("0");
                    continue;
                }
                vy[y] = true;
                int Max = Y.query(y, 1, ys.size(), 1);
//                pr(Max);
                printf("%d\n", ox[i] - Max);
                int k = lower_bound(xs.begin(), xs.end(), Max) - xs.begin() + 1;
//                pr(k); prln(oy[i]);
                X.update(k, x, oy[i], 1, xs.size(), 1);
            }
        }
    }
    return 0;
}

實在是不想寫了 - - 這幾天有點煩 - - 唉 - - 貼個别人寫的吧~ 反正大概是這樣~ 動态建樹:

/*
    Author: Zhouxing Shi
    Created on Jun27, 2015
*/
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define drep(i, a, b) for (int i = (a); i >= (b); --i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define pb(x) push_back(x)
#define mp(x, y) (make_pair(x, y))
#define clr(x) memset(x, 0, sizeof(x))
#define xx first
#define yy second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int inf = ~0U >> 1;
const ll INF = ~0ULL >> 1;
//***************************

map<pii, int> h;

int N, Q, x, y;
char dir[10];

struct node {
    node *ls, *rs;
    int m, lazy;
    node() { ls = rs = NULL; m = lazy = 0; }
    void cover(int d) {
        m = max(m, d);
        lazy = max(lazy, d);
    }
    void push() {
        if(!ls) ls = new node();
        if(!rs) rs = new node();
        ls->cover(lazy);
        rs->cover(lazy);
        lazy = 0;
    }
    void upd() {
        m = 0;
        if(ls) m = max(m, ls->m);
        if(rs) m = max(m, rs->m);
    }
} ;

struct segtree {
    node *rt;

    void modify(node *p, int L, int R, int l, int r, int d) {
        if(L == l && R == r) {
            p->cover(d);
            return;
        }
        p->push();
        int m = L + R >> 1;
        if(r <= m)
            modify(p->ls, L, m, l, r, d);
        else if(l > m)
            modify(p->rs, m + 1, R, l, r, d);
        else modify(p->ls, L, m, l, m, d), modify(p->rs, m + 1, R, m + 1, r, d);
        p->upd();
    }

    int query(node *p, int L, int R, int dest) {
        if(!p) return 0;
        if(L == R) return p->m;
        p->push();
        int m = L + R >> 1;
        if(dest <= m) return query(p->ls, L, m, dest);
        else return query(p->rs, m + 1, R, dest);
    }

} T[2];

int main() {
    T[0].rt = new node();
    T[1].rt = new node();
    scanf("%d%d", &N, &Q);
    rep(i, 1, Q) {
        scanf("%d%d", &x, &y);
        swap(x, y);
        scanf("%s", dir);
        if(h[mp(x, y)]) {
            puts("0");
            continue;
        }
        h[mp(x, y)] = 1;
        if(dir[0] == 'U') {
            int fst = T[0].query(T[0].rt, 1, N, y); // max
            printf("%d\n", x - fst);
            T[1].modify(T[1].rt, 1, N, fst + 1, x, y);
        } else {
            int fst = T[1].query(T[1].rt, 1, N, x); // max
            printf("%d\n", y - fst);
            T[0].modify(T[0].rt, 1, N, fst + 1, y, x);
        }
    }
    return 0;
}

啊  - - 還有叉姐的set姿勢 - - 模拟了一下覺得挺神奇的 - - 唉 - - 弱啊~

#include <cstdio>
#include <climits>
#include <set>

const int N = 200000 + 1;

typedef std::pair <int, int> Data;

int x[N], y[N], t[N];

int main()
{
    int n, q;
    scanf("%d%d", &n, &q);
    x[q] = y[q] = 0;
    std::set <Data> set;
    set.insert({0, q});
    set.insert({n + 1, q});
    for (int i = 0; i < q; ++ i) {
        char buffer[2];
        scanf("%d%d%s", x + i, y + i, buffer);
        t[i] = *buffer == 'U';
        std::set <Data>::iterator iterator;
        if (t[i]) {
            iterator = set.lower_bound({x[i], INT_MIN});
        } else {
            iterator = set.upper_bound({x[i], INT_MAX});
            iterator --;
        }
        if (x[i] == iterator->first) {
            puts("0");
        } else {
            int j = iterator->second;
            set.insert({x[i], i});
            if (t[i]) {
                printf("%d\n", y[i] - y[j]);
                y[i] = y[j];
            } else {
                printf("%d\n", x[i] - x[j]);
                x[i] = x[j];
            }
        }
    }
    return 0;
}
資料結構 資料結構 - 線段樹
上一篇: 線段樹（區間更新）codeforces 292E Copying Data
下一篇: ntpdate伺服器整理

繼續閱讀