20161114测试总结

#include <stack>
#include <cctype>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
#include <climits>
#include <queue>
#include <string>
#include <ctime>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <map>
using namespace std;
bool iosig;
char ch;
template<class T>
inline void read(T &x) {
    iosig = 0, x = 0;
    do {
        ch = getchar();
        if (ch == '-') iosig = true;
    } while (!isdigit(ch));
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
    if (iosig) x = -x;
}
int n, m, l, r;
int a[1010], b[1010];
int acnt[1010], bcnt[1010];
struct Data {
    int l, r;
} data[1010];
inline void solve() {
    read(n), read(m);
    memset(acnt, 0, sizeof(acnt));
    memset(bcnt, 0, sizeof(bcnt));
    for (register int i = 1; i <= n; i++) read(a[i]), acnt[a[i]]++;
    for (register int i = 1; i <= n; i++) read(b[i]), bcnt[b[i]]++;
    for (register int i = 1; i <= n; i++) {
        if (bcnt[i] > acnt[i]) {
            for (register int i = 0; i < m; i++) read(l), read(r);
            cout << "No\n";
            return;
        }
    }
    for (int i = 0; i < m; i++) {
        read(data[i].l), read(data[i].r);
        if (data[i].l > data[i].r)
            swap(data[i].l, data[i].r);
    }
    for (register int i = 1; i <= n; i++) { 
        bool flag = 0;
        register int pos = find(b + 1, b + n + 1, a[i]) - b;
        
        while (pos != n + 1) {
            l = r = i;
            for (register int j = 0; j < m; j++) {
                if (data[j].l <= l && data[j].r >= r)
                    r = data[j].r, l = data[j].l;
                else if (l <= data[j].l && data[j].r >= r && r >= data[j].l)
                    r = data[j].r;
                else if (data[j].l <= l && r >= data[j].r && data[j].r >= l)
                    l = data[j].l;
                if (l <= pos && r >= pos) {
                    flag = 1;
                    break;
                }
            }
            if (flag) break;
            pos = find(b + pos + 1, b + n + 1, a[i]) - b;
        }
        if (!flag) {
            cout << "No\n";
            return;
        }
    }
    cout << "Yes\n";
}
int main() {
    int t;
    read(t);
    while (t--)
        solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int f[5005][5005], ans;
bool vis[5005];
int n, m, k;
const int mod = 1e9 + 9;
inline void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (register int i = 0; i < m; i++)
        cin >> k, vis[k] = true;
    f[1][1] = 1;
    for (register int i = 2; i <= n; i++) {
        if (vis[i]) {
            k = 0;
            for (register int j = i - 1; j > 0; j--) {
                add(k, f[i - 1][j]);
                f[i][j] = k;
            }
        } else {
             k = 0;
             for (register int j = 1; j <= i; j++) {
                f[i][j] = k;
                add(k, f[i - 1][j]);
             }
        }
    }
    for (register int i = 1; i <= n; i++)
        add(ans, f[n][i]);
    cout << ans;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, n0, n2, l, r, t, t2, i, j, k, ans, mid, m;
int a[1000005], b[1000005];
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 int get() {
    if (n0) {
        --n0;
        return 0;
    }
    if (t > n) {
        ++t2;
        return b[t2 - 1];
    }
    if (t2 > n2) {
        ++t;
        return a[t - 1];
    }
    if (a[t] < b[t2]) {
        ++t;
        return a[t - 1];
    }
    ++t2;
    return b[t2 - 1];
}
inline long long check(int k) {
    long long ans = 0;
    register int now;
    n0 = n2 = 0;
    for (; (n + n0 - 1) % (k - 1);) n0++;
    t = t2 = 1;
    while (true) {
        if (t > n && t2 == n2 && !n0) break;
        now = 0;
        for (i = 1; i <= k; i++) now += get();
        ans += now;
        b[++n2] = now;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    read(n), read(m);
    for (register int i = 1; i <= n; i++)
        read(a[i]);
    sort(a + 1, a + n + 1);
    l = 2, r = n, ans = n;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid) <= m) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}