某岛

… : "…アッカリ～ン . .. . " .. .
June 19, 2012

COCI 2011/2012 Round #2

Brief description:

Problem A. najboljih
…

Problem B. okret
问迷宫是否有死路。

Problem C. zadaca
问两个巨大整数的 gcd 的后 9 位数字，巨大整数用 N 个 integer 的乘积表示。
( .. .N <= 1,000 .. .) Problem D. kompici 问 N 个数可以组成多少对 pair， pair 定义位有至少一个相同的 digit 。。 ( .. N <= 1,000,000 ..) Problem E. funkcija 有一定程度依赖的 for 循环计数问题... . Problem F. raspored 。。。

Analysis:

(前略。。)

Problem E. funkcija

E 是一道很值得进一步思考的问题。。
首先。。像是这样的一组 Input 。。

Input:
3
2 3
1 a
b a
Output:
9

（题目里要求说。。Xi, Yi 不可以同时为字母。。但是去除这个限制。也是一个 will defined 的问题。。但似乎就不解了。。）
。。。于是依赖关系形成有根树森林（有多个左孩子和右孩子的“二叉树”。。）
。。之后迎刃照做就可以了。。（利用部分和进行状态转移。。具体做法也可以参考这里。。）

Problem F. raspored
。F 首先第一问可以通过排序后贪心的方法得到。。原理参照排序不等式。。
。。以下假定读者默认排序不等式的正确性。。

于是处理第二问。。发现修改过程。。。需要的是一种支持 O(1) 插入、O(1) 删除 和 二分查找的数据结构。。
进一步分析可以将题目中所说的两种代价分离。。第一个可以直接 O(1) 维护。。第二个将所有的需求时间插入到一颗平衡树中动态维护。。。

需要额外添加一些域。。

1. sz[] 用以维护子树的规模
2. ss[] 维护子树的关键字权和。
3. cost[] 维护子树所引起的代价。。

因为需要 sz[] 域所以考虑用 sbt 实现平衡树。。。于是这道题的真正核心是：

cost[x] = cost[lx] + cost[rx] + LL(ss[lx] + key[x]) * (sz[rx] + 1) 。。。

…

...
int A[8], O[8];
 
bool comp(int a, int b){
    return A[a] > A[b];
}
 
int main(){
    REP(i, 8) RD(A[i]), O[i] = i;
    sort(O, O+8, comp);
 
    int s = 0; REP(i, 5) s += A[O[i]];
    cout << s << endl;
 
    REP(i, 8) A[O[i]] = i;
 
    s = 5; REP(i, 8) if (A[i] < 5){
        if (--s) cout << i + 1 << " ";
        else cout << i + 1 << endl;
    }
}

.. .
const int N = 11;
bool Map[N][N];
int n, m;
 
int main(){
 
    //freopen("in.txt", "r", stdin);
 
    RD(n, m); char t; REP_2(i, j, n, m){
        RC(t); if (t == '.') Map[i][j] = true;
        else Map[i][j] = false;
    }
 
    int Dead = 0; REP_2(x, y, n, m) if (Map[x][y]){
        int cnt = 0; REP(ii, 4){
            int xx = x + dx[ii], yy = y + dy[ii];
            if (xx < 0 || yy < 0 || xx >= n || yy >= m) continue;
            if (Map[xx][yy]) ++cnt;
        }
 
        if (cnt == 1) Dead = 1;
    }
 
    cout << Dead << endl;
}

.. .
template<class T> inline void OT(const T &x){
    if (flag) REP(i, 9 - log(D) / log(10)) putchar('0');
    printf("%d\n", x);
}
 
inline void MUL(int &a, int b){
    LL t = (LL)a * b; if (t > MOD) flag = true;
    a = t % MOD;
}
 
const int N = 1009;
int D, a[N], b[N]; bool flag = false;
int n, m;
 
int main(){
 
    //freopen("in.txt", "r", stdin);
 
    D = 1; REP_C(i, _RD(n)) RD(a[i]); REP_C(i, _RD(m)) RD(b[i]);
 
    int d; REP_2(i, j, n, m){
        d = __gcd(a[i], b[j]);
        a[i] /= d, b[j] /= d, MUL(D, d);
    }
 
    OT(D);
}

LL A[1024]; int mask;
LL res, t;
 
LL Cn2(LL x){
    return x * (x - 1) / 2;
}
 
int main(){
 
    //freopen("in.txt", "r", stdin);
 
    Rush {
        for (mask = 0,RD(t); t; t /= 10) mask |= _1(t % 10);
        ++A[mask];
    }
 
    FOR(s, 1, 1024) {
        res += Cn2(A[s]);
        FOR(t, s+1, 1024) if (s&t)
        res += A[s] * A[t];
    }
 
    OT(res);
}

.. .
const int N = 26, C = 100000, CC = C + 9;
VI lc[N], rc[N]; int s[N][CC], ls[N][CC], rs[N][CC], l[N], r[N]; bool root[N];
string buff; int res, n;
 
int stoi(const string &s){
    int res = 0; REP(i, SZ(s)){
        res *= 10, res += s[i] - '0';
    }
    return res;
}
 
void stat(int x){
    REP_1(i, C) ls[x][i] = sum(ls[x][i-1], s[x][i]);
    DWN_1(i, C, 1) rs[x][i] = sum(rs[x][i+1], s[x][i]);
}
 
int main(){
 
    //freopen("in.txt", "r", stdin);
 
    FLC(root, true); REP_C(i, _RD(n)){
        l[i] = 1, r[i] = C;
        cin >> buff; if ('a' <= buff[0] && buff[0] <= 'z') root[i] = false, lc[buff[0] - 'a'].PB(i); else l[i] = stoi(buff);
        cin >> buff; if ('a' <= buff[0] && buff[0] <= 'z') root[i] = false, rc[buff[0] - 'a'].PB(i); else r[i] = stoi(buff);
    }
 
    DWN(i, n, 0) {
        FOR_1(j, l[i], r[i]) {
            s[i][j] = 1;
            REP(ii, SZ(lc[i])) MUL(s[i][j], rs[lc[i][ii]][j]);
            REP(ii, SZ(rc[i])) MUL(s[i][j], ls[rc[i][ii]][j]);
        }
        stat(i);
    }
 
    res = 1; REP(i, n) if (root[i]){
        MUL(res, rs[i][1]);
    }
 
    OT(res);
}

.. .
 
const int N = 400009;
int lc[N], rc[N], key[N], sz[N]; LL ss[N], cost[N]; int root, tot;
int L[N], T[N]; LL S;
int n, m, v;
 
#define lx lc[x]
#define rx rc[x]
 
inline void Update(int x){
    if (x){
        sz[x] = sz[lx] + sz[rx] + 1, ss[x] = ss[lx] + ss[rx] + key[x];
        cost[x] = cost[lx] + cost[rx] + (ss[lx] + key[x]) * (sz[rx] + 1);
    }
}
 
inline void rotate(int &x, int lc[], int rc[]){
    int t = rx; rx = lc[t], lc[t] = x;
    Update(x), Update(t), x = t;
}
 
inline void maintain(int &x, int lc[], int rc[]){
    if (sz[lc[lx]] > sz[rx]) rotate(x, rc, lc);
    else {
        if (sz[rc[lx]] > sz[rx]) rotate(lx, lc, rc), rotate(x, rc, lc);
        else return;
    }
    maintain(::lx, ::lc, ::rc), maintain(::rx, ::rc, ::lc);
    maintain(x, ::rc, ::lc), maintain(x, ::lc, ::rc);
}
 
inline void Insert(int &x = root){
    if (!x){
        x = ++tot, sz[x] = 1;
        cost[x] = ss[x] = key[x] = v;
    }
    else {
        Insert(v < key[x] ? lx : rx), Update(x);
 
        //if (v < key[x]) if (sz[lc[lx]] > sz[rx]) rotate(x, rc, lc); else;
        //else if (sz[rc[rx]] > sz[lx]) rotate(x, lc, rc);
 
        if (v < key[x]) maintain(x, lc, rc);
        else maintain(x, rc, lc);
    }
 
}
 
inline int Delete(int &x = root){
    int res; if (v == key[x] || v < key[x] && !lx || v > key[x] && !rx){
        res = key[x];
        if (!lx || !rx) x = lx + rx;
        else {
            int _v = v; v = key[x] + 1;
            key[x] = Delete(lx), v = _v;
        }
    }
    else {
        res = v < key[x] ? Delete(lx) : Delete(rx);
    }
 
    Update(x);
    return res;
 
}
 
int main(){
 
    //freopen("in.txt", "r", stdin);
 
    RD(n, m); REP(i, n){
        RD(L[i], T[i]), S += L[i];
        v = T[i], Insert();
    }
 
    OT(S - cost[root]);
 
    int x, l, t, rk; DO(m){
        RD(x, l, t), --x, S -= L[x], S += L[x] = l;
        v = T[x], Delete(), v = T[x] = t, Insert();
        OT(S - cost[root]);
    }
}

.. .
const int N = 400009;
int lc[N], rc[N], key[N], sz[N]; LL ss[N], cost[N]; int root, tot;
int L[N], T[N]; LL S;
int n, m, v;
 
#define lx lc[x]
#define rx rc[x]
 
#define Update ss[x] = ss[lx] + ss[rx] + key[x], cost[x] = cost[lx] + cost[rx] + LL(ss[lx] + key[x]) * (sz[rx] + 1)
 
inline void Insert(int &x = root){
    if (!x){
        x = ++tot, sz[x] = 1;
        cost[x] = ss[x] = key[x] = v;
    }
    else {
        ++sz[x], Insert(v < key[x] ? lx : rx);
        Update;
    }
}
 
inline int Delete(int &x = root){
    int res; --sz[x]; if (v == key[x] || v < key[x] && !lx || v > key[x] && !rx){
        res = key[x];
        if (!lx || !rx) x = lx + rx;
        else {
            int _v = v; v = key[x] + 1;
            key[x] = Delete(lx), v = _v;
        }
    }
    else {
        res = v < key[x] ? Delete(lx) : Delete(rx);
    }
 
    Update;
    return res;
}
 
int main(){
 
    //freopen("in.txt", "r", stdin);
 
    RD(n, m); REP(i, n){
        RD(L[i], T[i]), S += L[i];
        v = T[i], Insert();
    }
 
    OT(S - cost[root]);
 
    int x, l, t, rk; DO(m){
        RD(x, l, t), --x, S -= L[x], S += L[x] = l;
        v = T[x], Delete(), v = T[x] = t, Insert();
        OT(S - cost[root]);
    }
}

External link:

http://user.qzone.qq.com/251815992/blog/1241924135

Posted by xiaodao
Category: COCI

« | »

  • Archives

    open all | close all