20191108测试总结

又爆零了。。。明天再爆零我女装(flag)

T1:WOJ4803

2019高考原题,推一下式子就可以直接O(n)过了,甚至不需要矩阵快速幂。我考试的时候大概傻了。。。

#include <iostream>
#include <cstdio>
#define mod 1000000007
using namespace std;
int n, aa, bb, a, b, c, x, y, inv, f[20000005];
void exgcd(int p, int q)
{
    if (!q)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(q, p % q);
    int tmp = x;
    x = y;
    y = tmp - p / q * y;
    return;
}
int main()
{
    scanf("%d%d%d", &n, &aa, &bb);
    a = (long long)(mod + 1 - aa) * bb % mod;
    b = ((long long)aa * bb % mod + (long long)(mod + 1 - aa) * (mod + 1 - bb) % mod) % mod;
    c = (long long)aa * (mod + 1 - bb) % mod;
    exgcd(c, mod);
    inv = (x % mod + mod) % mod;
    f[0] = 0;
    f[1] = 1;
    for (int i = 2; i <= 2 * n; ++i)
        f[i] = ((long long)(mod + 1 - b) * f[i - 1] + (long long)(mod - a) * f[i - 2]) % mod * inv % mod;
    exgcd(f[2 * n], mod);
    inv = (x % mod + mod) % mod;
    printf("%d", (long long)f[n] * inv % mod);
    return 0;
}

T2:WOJ4804

大模拟。考试的时候写链表写炸了,写成了环形链表,调了半天调不出来。晚上重构了一个deque和vector版就过了。

#include <iostream>
#include <cstdio>
#include <deque>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> q;
deque<int> a[105];
int n, m, l, s, t, cnt, ans[105], b[10005], fa[10005];
int main()
{
    while (scanf("%d%d%d%d%d", &n, &m, &l, &s, &t))
    {
        if (n == -1 && m == -1 && l == -1 && s == -1 && t == -1)
            break;
        q.clear();
        cnt = 0;
        for (int i = 1; i <= n; ++i)
        {
            ans[i] = 0;
            a[i].clear();
            for (int j = 1; j <= l; ++j)
            {
                int k;
                scanf("%d", &k);
                a[i].push_back(k);
                b[++cnt] = k;
            }
        }
        b[++cnt] = s;
        sort(b + 1, b + cnt + 1);
        cnt = unique(b + 1, b + cnt + 1) - b - 1;
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j < a[i].size(); ++j)
                a[i][j] = lower_bound(b + 1, b + cnt + 1, a[i][j]) - b;
        s = lower_bound(b + 1, b + 1 + cnt, s) - b;
        for (int i = 1; i <= cnt; ++i)
            fa[i] = -1;
        for (int i = 1; i <= t; ++i)
        {
            int num = 0;
            for (int j = 1; j <= n; ++j)
                if (!a[j].empty())
                {
                    int k = a[j].front();
                    a[j].pop_front();
                    if (k != s)
                    {
                        if (fa[k] >= 0)
                        {
                            int tmp = fa[k];
                            for (int kk = tmp; kk < q.size(); ++kk)
                            {
                                a[j].push_back(q[kk]);
                                fa[q[kk]] = -1;
                            }
                            a[j].push_back(k);
                            while (q.size() > tmp)
                                q.pop_back();
                        }
                        else
                        {
                            q.push_back(k);
                            fa[k] = q.size() - 1;
                        }
                    }
                    else
                    {
                        if (q.empty())
                            q.push_back(k);
                        else
                        {
                            for (int kk = 0; kk < q.size(); ++kk)
                            {
                                a[j].push_back(q[kk]);
                                fa[q[kk]] = -1;
                            }
                            a[j].push_back(k);
                            q.clear();
                        }
                    }
                    if (!a[j].empty())
                        ++num;
                    else
                        ans[j] = i;
                }
            if (num <= 1)
                break;
        }
        for (int i = 1; i <= n; ++i)
            if (ans[i])
                printf("-%d ", ans[i]);
            else
                printf("%d ", a[i].size());
        putchar('\n');
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j < a[i].size(); ++j)
                printf("%d ", b[a[i][j]]);
            putchar('\n');
        }
    }
    return 0;
}

T3:WOJ4805

被搬到了树上的蒲公英。。。毒瘤数分块,CSP多半不会考这种题(吧?),因此为了节约时间刷没刷完的往届的NOIP题就先咕了(虽然多半永远的咕了)

代码放的std。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fir first
#define sec second

typedef unsigned uint32;
typedef pair<int, int> PII;

namespace io {
    void gi(int &ret) {
        static char ch;
        while (ch = getchar(), !isdigit(ch))
            ;
        ret = ch - '0';
        while (ch = getchar(), isdigit(ch)) {
            ret = ret * 10 + ch - '0';
        }
    }
    
    void print(int ret) {
        static int qu[15], po;
        do {
            qu[++po] = ret % 10;
            ret /= 10;
        } while(ret);
        while (po != 0) {
            putchar(qu[po--] + '0');
        }
    }
}
using io::gi;
using io::print;

const int Max_N = 100005;
const int Max_S = 735;

inline void tension(int &c, int &r, int cur_c, int cur_r) {
    if (c <= cur_c) {
        if (c < cur_c) {
            c = cur_c, r = cur_r;
        } else {
            if (r > cur_r) {
                r = cur_r;
            }
        }
    }
}

int N, Q, type, lastans, col[3][Max_N];
int head[Max_N], adj[Max_N * 2 + 1], nxt[Max_N * 2 + 1], total;

inline void addedge(int u, int v) {
    ++total, adj[total] = v, nxt[total] = head[u], head[u] = total;
}

namespace Tree {
    int euler_clock, fir[Max_N], ST[19][(Max_N << 1) + 1], lg[(Max_N << 1) + 1];
    int dep[Max_N], fa[Max_N], dfn[Max_N], dfs_clock;
    
    void dfs(int u, int f) {		
        dfn[u] = ++dfs_clock;
        ST[0][++euler_clock] = u, fir[u] = euler_clock;
        for (int i = head[u]; i; i = nxt[i]) {
            if (adj[i] != f) {
                dep[ adj[i] ] = dep[u] + 1;
                fa[ adj[i] ] = u;
                dfs(adj[i], u);
                ST[0][++euler_clock] = u;
            }
        }
    }

    inline int get_lca(int u, int v) {
        int l = fir[u], r = fir[v], k;
        if (l > r) { 
            swap(l, r);
        }
        k = lg[r - l + 1];
        return dep[ ST[k][l] ] < dep[ ST[k][r - (1 << k) + 1] ] ? ST[k][l] : ST[k][r - (1 << k) + 1];
    }

    void init() {
        lg[0] = -1;
        for (int i = 1; i <= N * 2 - 1; i++) {
            lg[i] = lg[i >> 1] + 1;
        }
        dfs(1, 0);
        for (int i = 1; i <= 17; i++) {
            for (int j = 1; j + (1 << i) - 1 <= euler_clock; j++) { 
                ST[i][j] = dep[ ST[i - 1][j] ] < dep[ ST[i - 1][j + (1 << (i - 1))] ] ? ST[i - 1][j] : ST[i - 1][j + (1 << (i - 1))];
            }
        }
    }

    bool comp_vt(int x, int y) {
        return dfn[x] < dfn[y];
    }
    
    bool comp_d(int x, int y) {
        return dep[x] > dep[y]; 
    }
}
using Tree::get_lca;
using Tree::comp_vt;
using Tree::comp_d;
using Tree::dep;
using Tree::dfn;
using Tree::fa;

void build_vt(vector<int> &que) {
    static int stk[Max_N], top;
    static vector<int> P;
    sort(que.begin(), que.end(), comp_vt);
    que.resize(unique(que.begin(), que.end()) - que.begin());
    stk[top = 1] = que[0], P.clear(), P.pb(que[0]);
    for (size_t i = 1; i < que.size(); i++) {
        int lca = get_lca(stk[top], que[i]);
        if (lca == stk[top]) {
            stk[++top] = que[i];
        } else {
            while (top > 1 && dep[ stk[top - 1] ] >= dep[lca]) { 
                --top;
            }
            if (stk[top] != lca) { 
                P.pb(lca), stk[top] = lca;
            }
            stk[++top] = que[i];
        }
        P.pb(que[i]);
    }
    que = P;
}

namespace Blocks {
    int id[Max_N], up[Max_N], down[Max_N];
    int mode[Max_S][Max_S], cnt[Max_S][Max_S], lca[Max_S][Max_S], sum[Max_S][Max_N];
    char val[Max_S][Max_N];
    
    vector<int> Key;
    
    int cur[Max_N];
    int ext_c[Max_N], visited[Max_N], stk[Max_N], top = 0;
    
    void predfs(int u, int f) {
        for (int k = 0; k < 3; k++) {
            ++cur[ col[k][u] ];
        }
        if (id[u] != -1) {
            for (int i = 1; i <= N; i++) {
                sum[ id[u] ][i] = cur[i];
            }
        }
        for (int i = head[u]; i; i = nxt[i]) { 
            if (adj[i] != f) {
                predfs(adj[i], u);
            }
        }
        for (int k = 0; k < 3; k++)
            --cur[ col[k][u] ];
    }

    void dfs(int u, int f, int fr, int cur_c, int cur_m) {
        for (int k = 0; k < 3; k++) {
            ++cur[ col[k][u] ];
            tension(cur_c, cur_m, cur[ col[k][u] ], col[k][u]);
        }
        if (id[u] != -1) {
            mode[fr][ id[u] ] = cur_m, cnt[fr][ id[u] ] = cur_c;
        }
        for (int i = head[u]; i; i = nxt[i]) {
            if (adj[i] != f) {
                dfs(adj[i], u, fr, cur_c, cur_m);
            }
        }
        for (int k = 0; k < 3; k++) {
            --cur[ col[k][u] ];
        }
    }

    void get_up(int u, int f, int ff) {
        if (id[u] != -1) {
            ff = u;
        }
        up[u] = ff;
        for (int i = head[u]; i; i = nxt[i]) {
            if (adj[i] != f) {
                get_up(adj[i], u, ff);
            }
        }
    }

    void get_down(int u, int f) {
        down[u] = id[u] == -1 ? -1 : u;
        for (int i = head[u]; i; i = nxt[i])
            if (adj[i] != f) {
                get_down(adj[i], u);
                if (down[u] == -1 && down[ adj[i] ] != -1) {
                    down[u] = down[ adj[i] ];
                }
            }
    }
    
    inline int query(int x, int y, int c) {
        int u = id[x], v = id[y], f = lca[u][v];
        return sum[u][c] + sum[v][c] - 2 * sum[f][c] + val[f][c];
    }
    
    void query(int u, int v) {
        int _lca = get_lca(u, v), cur_r = N + 1, cur_c = 0;
        if (up[u] == up[v]) { 
            while (u != _lca) {
                for (int k = 0; k < 3; k++) { 
                    ++ext_c[ col[k][u] ], stk[++top] = col[k][u];
                }
                u = fa[u];
            }
            while (v != _lca) {
                for (int k = 0; k < 3; k++) {
                    ++ext_c[ col[k][v] ], stk[++top] = col[k][v];
                }
                v = fa[v];
            }
            for (int k = 0; k < 3; k++) {
                ++ext_c[ col[k][_lca] ], stk[++top] = col[k][_lca];
            }
            for (int i = 1; i <= top; i++) {
                if(!visited[ stk[i] ]) {
                    tension(cur_c, cur_r, ext_c[ stk[i] ], stk[i]);
                    visited[ stk[i] ] = true;
                }
            }
        } else {
            if ((dep[ up[u] ] < dep[_lca]) || (dep[ up[v] ] < dep[_lca])) {
                if (dep[ up[v] ] < dep[_lca]) {
                    swap(u, v);
                }
                while (v != up[v]) {
                    for (int k = 0; k < 3; k++) {
                        ++ext_c[ col[k][v] ], stk[++top] = col[k][v];
                    }
                    v = fa[v];
                }
                while (u != _lca) {	
                    for (int k = 0; k < 3; k++) {
                        ++ext_c[ col[k][u] ], stk[++top] = col[k][u];
                    }
                    u = fa[u];
                }
                int p = fa[ down[u] ];
                while (p != u) {
                    for (int k = 0; k < 3; k++) {
                        ++ext_c[ col[k][p] ], stk[++top] = col[k][p];
                    }
                    p = fa[p];
                }
                for (int k = 0; k < 3; k++) {
                    ++ext_c[ col[k][u] ], stk[++top] = col[k][u];
                }
                u = down[u];
            }
            else {
                while (v != up[v]) {
                    for (int k = 0; k < 3; k++) {
                        ++ext_c[ col[k][v] ], stk[++top] = col[k][v];
                    }
                    v = fa[v];
                }
                while (u != up[u]) {
                    for (int k = 0; k < 3; k++) {
                        ++ext_c[ col[k][u] ], stk[++top] = col[k][u];
                    }
                    u = fa[u];
                }
            }
            cur_c = cnt[ id[u] ][ id[v] ], cur_r = mode[ id[u] ][ id[v] ];
            for (int i = 1; i <= top; i++) {
                if (!visited[ stk[i] ]) {
                    tension(cur_c, cur_r, ext_c[ stk[i] ] + query(u, v, stk[i]), stk[i]);
                    visited[ stk[i] ] = true;
                }
            }
        }
        print(cur_c), putchar(' '), print(cur_r), putchar('\n');
        lastans ^= cur_c, lastans ^= cur_r;
        for (int i = 1; i <= top; i++) {
            visited[ stk[i] ] = false;
            ext_c[ stk[i] ] = 0;
        }
        top = 0;
    }
    
    void init() {
        static int P[Max_N], dist[Max_N];
        for (int i = 1; i <= N; i++) {
            P[i] = i, dist[i] = 0;
        }
        sort(P + 1, P + 1 + N, comp_d);
        for (int i = 1; i <= N; i++) {
            for (int j = head[ P[i] ]; j; j = nxt[j]) {
                if (adj[j] != fa[ P[i] ]) {
                    dist[ P[i] ] = max(dist[ P[i] ], dist[ adj[j] ] + 1);
                }
            }
            if (P[i] == 1 || dist[ P[i] ] >= 225) {
                dist[ P[i] ] = 0, Key.pb(P[i]);
            }
        }
        build_vt(Key);
        memset(id, -1, sizeof(id));
        for (size_t i = 0; i < Key.size(); i++) {
            id[ Key[i] ] = i;
            for (int k = 0; k < 3; k++)
                ++val[i][ col[k][ Key[i] ] ];
        }
        for (size_t i = 0; i < Key.size(); i++) {
            for (size_t j = 0; j < Key.size(); j++) {
                lca[i][j] = id[ get_lca(Key[i], Key[j]) ];
            }
        }
        predfs(1, 0);
        for (size_t i = 0; i < Key.size(); i++) {
            dfs(Key[i], 0, i, 0, N + 1);
        }
        get_up(1, 0, -1);
        get_down(1, 0);
    }
}

void __main__() {
    gi(type); 
    gi(N);
    for (int i = 1; i <= N; i++) {
        for (int k = 0; k < 3; k++) {
            gi(col[k][i]);
        }
    }
    for (int u, v, i = 1; i <= N - 1; i++) {
        gi(u), gi(v);
        addedge(u, v), addedge(v, u);
    }
    Tree::init();
    Blocks::init();
    
    gi(Q);
    for (int u, v, i = 1; i <= Q; i++) {
        gi(u), gi(v);
        u ^= lastans * type, v ^= lastans * type;
         Blocks::query(u, v);
    }
}

int main() {
    freopen("mode.in", "r", stdin);
    freopen("mode.out", "w", stdout);
     
    __main__();
    
    return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注