NOIP第四阶段总结

模拟测试46

阶段排名

最后一场比赛了，成绩还是一如既往的烂，不过心态感觉好多了

A 中间值 (Unaccepted)

人家都nlogn我是nlognlog1e9，T成70了

Show Code

B 最小值 (Unaccepted)

Show Code

C Race (Unaccepted)

暴力

Show Code

D Magic (Unaccepted)

Show Code

晚间小测10

阶段排名 8

A 跳跃

数据范围n最大40，显然折半搜，只不过k范围4e10看成了1e4就没开longlong，考完三个人调了半时才发现

Show Code

#include <cstdio>
#include <algorithm>

typedef long long ll;
const int N = 50, M = 1.1e6;
int n, n2, na, nb, bh[N], m, h[N], s[N], t[N];
ll ans, k;
struct Node {
    int h; ll s;
    bool operator < (const Node &b) const {
        return s < b.s;
    }
}a[M], b[M];

int Find(const int *a, int x) {
    int l = 1, r = a[0], mid;
    for (; l < r; a[mid=l+r>>1] >= x ? r = mid : l = mid + 1);
    return l;
}

void Dfs(int x, ll sum) {
    if (x > n2) return;
    if (sum >= k) ans++;
    if (x) a[++na] = (Node) {h[x], sum};
    for (int i = x + 1; i <= n; ++i)
        if (h[i] >= h[x]) Dfs(i, sum + s[i]);
}

void Dfs(int x, ll sum, int hi) {
    if (x > n) return;
    if (sum >= k) ans++;
    b[++nb] = (Node) {hi, sum};
    for (int i = x + 1; i <= n; ++i)
        if (h[i] >= h[x]) Dfs(i, sum + s[i], hi);
}

void Add(int x) {
    for (; x; x -= x & -x) t[x]++;
}

int Ask(int x, int s = 0) {
    for (; x <= bh[0]; x += x & -x) s += t[x];
    return s;
}

int main() {
    freopen("san.in", "r", stdin);
    freopen("san.out", "w", stdout);
    scanf("%d%lld", &n, &k); n2 = n >> 1;
    for (int i = 1; i <= n; ++i)
        scanf("%d%d", &h[i], &s[i]), bh[i] = h[i];
    std::sort(bh + 1, bh + n + 1);
    bh[0] = std::unique(bh + 1, bh + n + 1) - bh - 1;
    for (int i = 1; i <= n; ++i)
        h[i] = Find(bh, h[i]);
    Dfs(0, 0);
    for (int i = n2 + 1; i <= n; ++i)
        Dfs(i, s[i], h[i]);
    std::sort(a + 1, a + na + 1);
    std::sort(b + 1, b + nb + 1);
    for (int i = 1, j = nb; i <= na; ++i) {
        for (; j >= 1 && a[i].s + b[j].s >= k; --j) 
            Add(b[j].h);
        ans += Ask(a[i].h);
    }
    printf("%lld
", ans);
    return 0;
}

B 床单 (Unaccepted)

打个暴力数组都开不下差评

Show Code

模拟赛45

阶段排名 7

A bins

考场上写了个n^2log的写法60分
正解就是维护出前k个和接下来k个的桶数组，这个每次左面的删去a[k]，右面的加上a[k],删去a[k2]和a[k2-1]（从大到小枚举k）
判断的时候就是要保证左面的从大小为j开始的后缀和都大于右面从大小为j+1开始的后缀和就是可以装进去

Show Code

#include <cstdio>
#include <cstring>

const int N = 2e4 + 5;

int read(int x = 0, int f = 1, char c = getchar()) {
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') f = -1;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return x * f;
}

int n, m, a[N], b1[1005], b2[1005];

int main() {
    freopen("bins.in", "r", stdin);
    freopen("bins.out", "w", stdout);
    m = read(); n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read(); 
        if (i > (n >> 1)) b2[a[i]]++;
        else b1[a[i]]++;
    }
    if (n & 1) b2[a[n]]--;
    for (int i = n / 2; i >= 0; --i) {
        int s1 = 0, s2 = 0, g = 1;
        for (int j = m; j >= 1 && g; --j) {
            s1 += b1[j];
            if (s1 > s2) g = 0;
            s2 += b2[j];
        }
        if (g) return printf("%d
", i), 0;
        b1[a[i]]--; b2[a[i]]++; b2[a[i*2]]--; b2[a[i*2-1]]--;
    }
}

B inversions

考场上把这个题A了，真是挺涨信心
考虑归并排序求逆序对，每次反转之后将这一层及以下的数反过来，对上面没有影响
所以归并排序的时候记录下来这一层逆序对数和倒过来后的逆序对数就好了

Show Code

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long ll;
typedef unsigned long long ull;
const int N = 1.1e6;

int n, m, maxn, n2, a[N], q[N], b[N];
ll s[25], cnt[25], ans, sum;
ull k1, k2;

ull Rand() {
    ull k3 = k1, k4 = k2; k1 = k4;
    k3 ^= (k3 << 23);
    k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
    return k2 + k4;
}

void Solve(int l, int r, int k) {
    if (l == r) return;
    int mid = l + r >> 1;
    Solve(l, mid, k - 1); Solve(mid + 1, r, k - 1);
    if (l == 1 && r == n2) {
        l = 1;
    }
    for (int tot = 0, i = l, j = mid + 1; i <= mid + 1; ++i) {
        for (; j <= r && (a[j] < a[i] || i == mid + 1); ++j) b[++tot] = a[j];
        if (i <= mid) cnt[k] += j - mid - 1, sum += j - mid - 1, b[++tot] = a[i];
    }
    for (int i = l, j = mid + 1, tot = 0; i <= mid; ++i) {
        for (; j <= r && a[j] <= a[i]; ++j) tot = j == mid + 1 || a[j] != a[j-1] ? 1 : tot + 1;
        if (a[i] == a[j-1]) s[k] -= tot;
    }
    memcpy(a + l, b + 1, 4 * (r - l + 1));
}

int main () {
    freopen("inversions.in", "r", stdin);
    freopen("inversions.out", "w", stdout);
    scanf("%d%d%d%llu%llu", &n, &m, &maxn, &k1, &k2);
    n2 = 1 << n;
    for (int i = 1; i <= n2; i++) 
        a[i] = Rand() % maxn + 1;
    for (int i = 1; i <= m; i++) 
        q[i] = Rand() % (n + 1);
    s[n] = (1ll << n - 1) * (1ll << n - 1);
    for (int i = n - 1; i >= 1; --i)
        s[i] = s[i+1] / 2;
    Solve(1, n2, n);
    for (int i = 1; i <= m; ++i) {
        for (int j = 0; j <= q[i]; ++j)
            sum -= cnt[j], cnt[j] = s[j] - cnt[j], sum += cnt[j];
        ans = ans ^ (sum * i);
    }
    printf("%lld
", ans);
    return 0;
}

C candies

考虑新加一袋糖果后的构成肯定可以变为原来的2倍多1（所以第一问找删去这袋糖果后构成最多的那袋），这袋糖果比之前的总和大就可以了，但是让求最小的，写了个(nm)^2的，然后就挂了
前面半部分没什么问题，主要是后面复杂度不对，考虑一个Q不和法是应为有两种构造相减等于Q了，那就bool背包看看一个Q可不可以被构造出来就好了
代码里的那个指针真的巨好用！！！，直接右移

Show Code

#include <cstdio>

const int N = 105, M = 1e9 + 7;

int read(int x = 0, int f = 1, char c = getchar()) {
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') f = -1;
    for (; c >='0' && c <='9'; c = getchar())
        x = x * 10 + c - '0';
    return x * f;
}

int n, m, mx, x, y, a[N], f[N*7000], cnt, g[N*7000];
bool dp[N*14000], *v = dp + 7005;

int main() {
    freopen("candies.in", "r", stdin);
    freopen("candies.out", "w", stdout);
    n = read(); f[0] = 1;
    for (int i = 1; i <= n; ++i) {
        a[i] = read(); m += a[i];
        for (int j = m; j >= a[i]; --j)
            if (f[j-a[i]]) cnt += !f[j], (f[j] += f[j-a[i]]) %= M;
    }
    for (int i = 1; i <= n; ++i) {
        int ans = cnt;
        for (int j = 0; j <= m; ++j)
            if (f[j]) g[j] = (f[j] - (j >= a[i] ? g[j-a[i]] : 0) + M) % M, ans -= !g[j];
        if (ans > mx) mx = ans, x = i;
    }
    v[0] = 1; m = 0;
    for (int i = 1; i <= n; ++i) {
        if (i == x) continue;
        for (int j = m; j >= -m; --j)
            v[j+a[i]] |= v[j];
        for (int j = -m; j <= m; ++j)
            v[j-a[i]] |= v[j];
        m += a[i];
    }
    for (int i = 1; i <= m + 1; ++i)
        if (!v[i]) return printf("%d %d
", a[x], i), 0;
}

D sheep (Unaccepted)

折磨难写的题还捆绑测试，果断放弃

Show Code