20161110测试总结

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
char s[MAXN];
pair<char, int> a[MAXN];
int n, m;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    n = strlen(s);
    for (int i = 0; i < n; i++)
        a[i] = make_pair(s[i], i);
    sort(a, a + n);
    for (register int i = 1, p = a[0].second; i <= n; i++, p = a[p].second)
        cout << (char)a[p].first;
    return 0;
}

#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 155;
const int mod = 51123987;
inline void add(int &a, const int b) {
    a = (a + b) % mod;
}
int n, m, limit;
int f[2][MAXN][MAXN][MAXN], pos;
char s[MAXN];
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
#endif
    static int next[MAXN][3];
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> s + 1;
    transform(s + 1, s + n + 1, s + 1, [](char a) -> int {return a - 'a';});
    for (int i = 1, j = 1; i <= n; i = j) {
        for (; j <= n && s[i] == s[j]; j++);
        s[++m] = s[i];
    }
    for (int i = 0; i < 3; i++)
        next[m + 1][i] = m + 1;
    for (int i = m; i >= 0; i--) {
        for (int j = 0; j < 3; j++)
            next[i][j] = next[i + 1][j];
        if (i > 0) next[i][s[i]] = i;
    }
    limit = (n + 2) / 3;
    int ans = 0;
    f[0][0][0][0] = 1;
    for (int a = 0; a <= n && a <= limit; a++) {
        for (int b = 0; a + b <= n && b <= limit; b++) {
            for (int c = 0; a + b + c <= n && c <= limit; c++) {
                for (int i = 0; i <= m; i++) {
                    if (a + b + c == n) {
                        if (abs(a - b) <= 1 && abs(b - c) <= 1 && abs(a - c) <= 1) {
                            add(ans, f[pos][b][c][i]);
                        }
                    } else {
                        add(f[pos ^ 1][b][c][next[i][0]], f[pos][b][c][i]);
                        add(f[pos][b + 1][c][next[i][1]], f[pos][b][c][i]);
                        add(f[pos][b][c + 1][next[i][2]], f[pos][b][c][i]);
                    }
                    f[pos][b][c][i] = 0;
                }
            }
        }
        pos ^= 1;
    }
    cout << ans;
    return 0;
}

#pragma GCC diagnostic error "-std=c++11"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
const int LOGN = 19;
vector<int> edge[MAXN];
int father[MAXN][LOGN], size[MAXN];
long long f[MAXN][LOGN], ans, logn;
char ch;
inline void read(int &x) {
    x = 0;
    do ch = getchar(); while (!isdigit(ch));
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
}
inline void dfs1(int u = 1) {
    for (register int i = 1; i < logn; i++)
        father[u][i] = father[father[u][i - 1]][i - 1];
    size[u] = 1;
    for (auto i : edge[u])
        if (i != father[u][0])
            father[i][0] = u, dfs1(i), size[u] += size[i];
}
inline void dfs2(int u = 1) {
    for (auto i : edge[u])
        if (i != father[u][0])
            dfs2(i);
    register long long sum = 1;
    for (register int i = 0; i < logn; i++) sum += f[u][i];
    register int t = u;
    for (register int i = 0; i < logn; i++)
        sum -= f[u][i], ans -= sum * size[t], t = father[t][i], ans += sum * size[t], f[father[u][i]][i] += sum;
}
inline void addEdge(int u, int v) {
    edge[u].push_back(v);
    edge[v].push_back(u);
}
int n;
int main() {
    read(n);
    logn = ceil(log2(n));
    for (register int i = 1, u, v; i < n; i++)
        read(u), read(v), addEdge(u, v);
    father[1][0] = 1;
    dfs1(), dfs2();
    cout << ans;
    return 0;
}