2018/8/21 qbxt测试

期望得分：0？实际得分：0

思路：manacher 会写模板但是不会用 qwq

听了某人的鬼话，直接输出0，然后就gg了

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int N = (int)2e6 + ;

typedef long long ll;

char S[N];

int R[N], lf[N], rt[N];

int n;

void init() {

    scanf("%s", S + ), n = strlen(S + ) <<  | ;

    for (int i = n; i >= ; --i) S[i] = i &  ? '#' : S[i >> ];

}

void manacher() {

    int k = , p = ;

    R[] = , lf[] = ;

    for (int i = ; i <= n; ++i) {

        int j =  * k - i;

        R[i] = min(R[j], p - i + );

        for ( ; i + R[i] <= n && i - R[i] >=  && S[i + R[i]] == S[i - R[i]]; ++R[i]);

        if (i + R[i] -  > p) {

            for (int j = p + ; j <= i + R[i] - ; ++j)

                lf[j] = j - i;

            k = i, p = i + R[i] - ;

        }

    }

    k = n, p = n;

    rt[n] = ;

    for (int i = n - ; i >= ; --i) {

        if (i - R[i] +  < p) {

            for (int j = p - ; j >= i - R[i] + ; --j)

                rt[j] = i - j;

            k = i, p = i - R[i] + ;

        }

    }

    for (int i = ; i <= n; i += ) lf[i] = max(lf[i], lf[i - ]);

    for (int i = n - ; i >= ; i -= ) rt[i] = max(rt[i], rt[i + ]);

    int ans = ;

    for (int i = ; i <= n; i += )

        if (lf[i] + rt[i] > ans)

            ans = lf[i] + rt[i];

    printf("%d\n", ans);

}

int main() {

    freopen("string.in", "r", stdin);

    freopen("string.out", "w", stdout);

    init();

    manacher();

    return ;

}

std

期望得分：20？40？实际得分：20

考场思路：树上两点间的最短路应该要求LCA，那就用树剖求吧只会用树剖 qwq

欸？让着求路径乘积是什么鬼？？线段树？？那就树剖+线段树吧

这个区间怎么合并？？不会这题不会要用倍增LCA吧不会啊咕咕咕~

那就换暴力吧枚举，然后乘起来

嗯。。答案好像不大对啊，这个样例是不是错了啊

20min 后。。。kao，我题目读错了

最后改了改，20分 qwq

正解：

#include<algorithm>

#include<cstdlib>

#include<cstring>

#include<cstdio>

using namespace std;

typedef long long LL;

const int M = ;

const int Mod = 1e9 + ;

LL S, T, G;

int tot, n, m, k, t;

int a[M], sum[M];

int to[M*], net[M*], head[M];

int deep[M], top[M], dad[M], size[M];

inline int read() {

    int x = , f = ;

    char ch = getchar();

    while(ch<'' || ch>'') {

        if(ch == '-') f = -;

        ch = getchar();

    }

    while(ch>='' && ch<='') x = x *  + ch - , ch = getchar();

    return x * f;

}

inline void add(int u, int v) {

    to[++tot] = v; net[tot] = head[u]; head[u] = tot;

    to[++tot] = u; net[tot] = head[v]; head[v] = tot;

}

inline void dfs(int now) {

    size[now] = ;

    deep[now] = deep[dad[now]] + ;

    for(int i = head[now]; i; i = net[i])

        if(dad[now] != to[i]) {

            dad[to[i]] = now;

            dfs(to[i]);

            size[now] += size[to[i]];

        }

}

inline void dfsl(int now) {

    int t = ;

    if(!top[now]) top[now] = now;

    for(int i = head[now]; i; i = net[i])

        if(dad[now] != to[i] && size[to[i]] > size[t])

            t = to[i];

    if(t) {

        top[t] = top[now];

        dfsl(t);

    }

    for(int i = head[now]; i; i = net[i])

        if(dad[now] != to[i] && to[i] != t)

            dfsl(to[i]);

}

inline int lca(int x, int y) {

    while(top[x] != top[y]) {

        if(deep[top[x]] < deep[top[y]])

            swap(x, y);

        x = dad[top[x]];

    }

    return deep[x] > deep[y] ? y : x;

}

inline LL mul(int a, int b) {

    LL res = ;

    while(b) {

        if(b & ) res = (res + a) % Mod;

        a = (a + a) % Mod;

        b >>= ;

    }

    return res;

}

inline LL bl(int tmp) {

    LL ans = ;

    for(int i = ; i <= tmp; i++)

        for(int j = i+; j <= tmp; j++)

            ans = (mul(sum[i], sum[j]) + ans) % Mod;

    return ans;

}

inline void get(int l, int r) {

    if(l == r) return ;

    while(l != r) {

        sum[++t] = a[l];

        l = dad[l];

    }

}

int main() {

    freopen("tree.in","r",stdin);

    freopen("tree.out","w",stdout);

    n = read(), m = read(), k = read();

    for(int i = ; i <= n; i++)

        a[i] = read();

    for(int i = ; i < n; i++) {

        int u, v;

        u = read(), v = read();

        add(u, v);

    }

    dfs();

    dfsl();

    for(int i = ; i <= m; i++) {

        memset(sum, , sizeof sum);

        int u, v;

        t = ;

        u = read(); v = read();

        if(k == ) u ^= S, v ^= S;

        T = lca(u, v);

        get(u, T), get(v, T);

        sum[++t] = a[T];

        G = bl(t);

        printf("%lld\n", G);

        if(k == ) S = G;

    }

    fclose(stdin); fclose(stdout);

    return ;

}

考场代码

#include <bits/stdc++.h>

using namespace std;

const int N = (int)2e5, mod = (int)1e9 + , inv = (mod + ) >> ;

typedef int arr[N + ];

typedef long long ll;

int n, Q, K, ans, tot, j, k;

arr pt, nt, g, d, ls[], sqs[], f[];

arr a;

struct queue {

    arr v;

    int f, r;

}q;

void link(int x, int y) {

    pt[++tot] = y, nt[tot] = g[x], g[x] = tot;

    pt[++tot] = x, nt[tot] = g[y], g[y] = tot;

}

void bfs() {

    q.v[q.f = q.r = ] = , d[] = ;

    for ( ; q.f <= q.r; ) {

        int x = q.v[q.f++];

        for (int c = ; c <= ; ++c)

            if (d[x] > ( << c)) {

                f[c][x] = f[c - ][f[c - ][x]];

                ls[c][x] = (ls[c - ][x] + ls[c - ][f[c - ][x]]) % mod;

                sqs[c][x] = (sqs[c - ][x] + sqs[c - ][f[c - ][x]]) % mod;

            }

            else break;

        for (int i = g[x]; i; i = nt[i])

            if (!d[pt[i]]) {

                d[pt[i]] = d[x] + ;

                f[][pt[i]] = x, ls[][pt[i]] = a[pt[i]], sqs[][pt[i]] = (ll)a[pt[i]] * (ll)a[pt[i]] % mod;

                q.v[++q.r] = pt[i];

            }

    }

}

int query(int x, int y) {

    if (d[x] > d[y]) swap(x, y);

    int sq = , l = ;

    for (int c = ; c >= ; --c)

        if (d[y] - ( << c) >= d[x])

            (l += ls[c][y]) %= mod, (sq += sqs[c][y]) %= mod, y = f[c][y];

    if (x == y) {

        l = (l + a[y]) % mod, (sq += (ll)a[y] * (ll)a[y] % mod) %= mod;

        l = (ll)l * (ll)l % mod;

        return (ll)(l + mod - sq) * (ll)inv % mod;

    }

    for (int c = ; c >= ; --c)

        if (f[c][x] != f[c][y]) {

            (l += (ls[c][x] + ls[c][y]) % mod) %= mod, (sq += (sqs[c][x] + sqs[c][y]) % mod) %= mod;

            x = f[c][x], y = f[c][y];

        }

    (l += (ls[][x] + ls[][y]) % mod) %= mod, (sq += (sqs[][x] + sqs[][y]) % mod) %= mod;

    y = f[][y];

    (l += a[y]) %= mod, (sq += (ll)a[y] * (ll)a[y] % mod) %= mod;

    l = (ll)l * (ll)l % mod;

    return (ll)(l + mod - sq) * (ll)inv % mod;

}

int main() {

    freopen("tree.in", "r", stdin);

    freopen("tree.out", "w", stdout);

    scanf("%d %d %d", &n, &Q, &K);

    for (int i = ; i <= n; ++i) scanf("%d", a + i);

    for (int i = ; i < n; ++i) {

        scanf("%d %d", &j, &k);

        link(j, k);

    }

    bfs();

    ans = ;

    for ( ; Q--; ) {

        scanf("%d %d", &j, &k);

        if (K) j ^= ans, k ^= ans;

        printf("%d\n", ans = query(j, k));

    }

    return ;

}

std

期望得分：0 实际得分：0

思路：没有思路期望是什么？？不知道

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = ;

typedef int arr[N + ][N + ];

int n, m, k, t, u, v;

arr s, c;

int Sum(int l1, int r1, int l2, int r2) {

    return s[l2][r2] - s[l1 - ][r2] - s[l2][r1 - ] + s[l1 - ][r1 - ];

}

long double Pow(long double x, int y) {

    long double t = x, r = ;

    for ( ; y; y >>= , t = t * t)

        if (y & ) r = r * t;

    return r;

}

int main() {

    freopen("swap.in", "r", stdin);

    freopen("swap.out", "w", stdout);

    scanf("%d%d%d%d\n", &n, &m, &k, &t);

    for (int i = ; i <= n; ++i)

        for (int j = ; j <= m; ++j)

            s[i][j] = c[i][j] = ;

    ll tot = n * m;

    for (int i = ; i <= t; ++i) {

        scanf("%d%d\n", &u, &v);

        s[u][v] = c[u][v] = , --tot;

    }

    for (int i = ; i <= n; ++i)

        for (int j = ; j <= m; ++j)

            s[i][j] += s[i - ][j] + s[i][j - ] - s[i - ][j - ];

    if (!tot) return printf("%.12lf\n", .), ;

    long double exp = tot;

    tot *= tot;

    for (int i = ; i <= n; ++i) {

        for (int j = ; j <= m; ++j) {

            if (c[i][j]) {

                ll cx = Sum(, , i, j), cy = Sum(i, j, n, m), ans = cx * cy;

                cx = Sum(, j, i, m), cy = Sum(i, , n, j);

                ans += cx * cy;

                cx = Sum(, j, i, j), cy = Sum(i, j, n, j);

                ans -= cx * cy;

                cx = Sum(i, , i, j), cy = Sum(i, j, i, m);

                ans -= cx * cy;

                ans = ans * 2LL + 1LL;

                long double e = (long double) - (long double) * (long double)ans / (long double)tot;

                exp += Pow(e, k);

            }

        }

    }

    exp /= (long double);

    printf("%.12Lf\n", exp);

    return ;

}

std

巴特西

2018/8/21 qbxt测试

最新文章

热门文章