20161102测试总结

#include <bits/stdc++.h>
using namespace std;
int a[110], t, n;
int f[110];
inline int solve() {
    register int mid = (n >> 1) + 1, ans = 0;
    f[mid] = a[n];
    for (int i = mid - 1; i >= 1; i -= 2) f[i] = a[mid - i];
    for (int i = mid - 2; i >= 1; i -= 2) f[i] = a[n - (mid - i - 1)];
    for (int i = mid + 1; i <= n; i += 2) f[i] = a[i - mid + 1];
    for (int i = mid + 2; i <= n; i += 2) f[i] = a[n - (i - mid)];
    for (int i = 2; i <= n; i++) ans += abs(f[i] - f[i - 1]);
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    for (int i = 1; i <= t; i++) {
        cin >> n;
        for (int j = 1; j <= n; j++) cin >> a[j];
        sort(a + 1, a + n + 1);
        int ans = solve();
        reverse(a + 1, a + n + 1);
        cout << "Case " << i << ": " << max(ans, solve()) << "\n";
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
bool iosig;
inline char read() {
    if (ioh == iot) {
        iot = (ioh = buf) + fread(buf, 1, iol, stdin);
        if (ioh == iot) return -1;
    }
    return *ioh++;
}
template<class T>
inline bool read(T& x) {
    iosig = false;
    for (ioc = read(); !isdigit(ioc); ioc = read()) {
        if (ioc == -1) return false;
        if (ioc == '-') iosig = true;
    }
    x = 0;
    while (ioc == '0') ioc = read();
    for (; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
    ioh--;
    if (iosig) x = -x;
    return true;
}
int r, c, a, b;
int mp[MAXN][MAXN];
inline bool check(int mid) {
    static int buf[MAXN], sum[MAXN];
    memset(sum, 0, sizeof(sum));
    int x = 0, y = 0, prei = 0, prej = 0;
    for (int i = 1; i <= r; i++) {
        y = prej = 0;
        memset(buf, 0, sizeof(buf));
        for (int j = 1; j <= c; j++)
            buf[j] = buf[j - 1] + mp[i][j];
        for (int j = 1; j <= c; j++)
            sum[j] += buf[j];
        for (int j = 1; j <= c; j++)
            if (sum[j] - sum[prej] >= mid)
                prej = j, y++;
        if (y >= b)
            prei = i, x++, memset(sum, 0, sizeof(sum));
    }
    return x >= a;
}
int main() {
    read(r), read(c), read(a), read(b);
    int range = 0;
    for (int i = 1; i <= r; i++)
        for (int j = 1; j <= c; j++)
            read(mp[i][j]), range += mp[i][j];

    int l = 0, r = range + 1;
    while (l < r - 1) {
        register int mid = l + r >> 1;
        if (check(mid)) l = mid;
        else r = mid;
    }
    cout << l;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int iol = 1024 * 1024;
char buf[iol], *ioh, *iot, ioc;
bool iosig;
inline char read() {
    if (ioh == iot) {
        iot = (ioh = buf) + fread(buf, 1, iol, stdin);
        if (ioh == iot) return -1;
    }
    return *ioh++;
}
template<class T>
inline bool read(T& x) {
    iosig = false;
    for (ioc = read(); !isdigit(ioc); ioc = read()) {
        if (ioc == -1) return false;
        if (ioc == '-') iosig = true;
    }
    x = 0;
    while (ioc == '0') ioc = read();
    for (; isdigit(ioc); ioc = read())
        x = (x << 1) + (x << 3) + (ioc ^ '0');
    ioh--;
    if (iosig) x = -x;
    return true;
}
const int MAXN = 100010;
int n, tot;
int father[MAXN], son[MAXN * 20][2], pre[MAXN * 20], dis[MAXN];
struct Node {
    int v, w;
    Node() {}
    Node(int v, int w) : v(v), w(w) {}
};
std::vector<Node> edge[MAXN];
inline void addEdge(int u, int v, int w) {
    edge[u].push_back(Node(v, w));
    edge[v].push_back(Node(u, w));
}
inline void bfs(int u = 1) {
    queue<int> q;
    q.push(u);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < edge[x].size(); i++) {
            Node *now = &edge[x][i];
            if (now->v != father[x]) {
                father[now->v] = x;
                dis[now->v] = dis[x] ^ now->w;
                q.push(now->v);
            }
        }
    }
}
int main() {
    /*max{w}*/
    int maxw = 0;
    read(n);
    for (int i = 0, u, v, w; i < n; i++)
        read(u), read(v), read(w), addEdge(u, v, w), maxw = max(maxw, w);
    bfs();
    /*Math.log2(maxw)*/
    int log = log2(maxw);
    /*build*/
    for (int i = 1, tmp; i <= n; i++) {
        tmp = 0;
        for (int j = log, x; j >= 0; j--) {
            /*000000->_1_->000000*/
            x = (dis[i] & (1 << j)) ? 1 : 0;
            if (!son[tmp][x]) son[tmp][x] = ++tot;
            tmp = son[tmp][x];
        }
        pre[tmp] = i;
    }
    int ans = 0;
    /*digit calculate*/
    for (int i = 1, tmp; i <= n; i++) {
        tmp = 0;
        for (int j = log, x; j >= 0; j--) {
            x = (dis[i] & (1 << j)) ? 1 : 0;
            if (son[tmp][!x]) tmp = son[tmp][!x];
            else tmp = son[tmp][x];
        }
        ans = max(ans, dis[i] ^ dis[pre[tmp]]);
    }
    cout << ans;
    return 0;
}