Codeforces Round #576 (Div. 2)

英语场，手速场。

题目链接：http://codeforces.com/contest/1199

---

A：

O(n)扫一遍，对于每个a[i]，往前扫x个往后扫y个完事。

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int maxn = 1e5 + 10;
int n, x, y, a[maxn];

int main() {
    scanf("%d%d%d", &n, &x, &y);
    rep1(i, 1, n) scanf("%d", &a[i]);
    rep1(i, 1, n) {
        int flag1 = 1, flag2 = 1;
        for (int j = i - 1; j >= 1 && j >= i - x; j--)
            if (a[j] < a[i]) {
                flag1 = 0; break;
            }
        for (int j = i + 1; j <= n && j <= i + y; j++)
            if (a[j] < a[i]) {
                flag2 = 0; break;
            }
        if (flag1 && flag2) {
            printf("%d
", i);
            return 0;
        }
    }
    return 0;
}

B：

给定H和L，求解r^2-(r-H)^2=L^2，并输出r-H。

小学数学。

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

int H, L;

int main() {
    scanf("%d%d", &H, &L);
    double h = H, l = L;
    printf("%.6f
", (l * l + h * h) / 2.0 / h - h);
    return 0;
}

C：

题意巨恶心的一题。

给定一个数组，定义数组大小为数组元素个数*数组所含数字种类数。给定一个压缩算法，该压缩算法选择一个区间[l,r]，然后逐个检查数组元素是否在区间内。若<l，则使之变为l;若>r，则使之变为r。

题目给定n(数组长度)和b，问在执行该压缩算法后，最少变几个元素，使得数组大小<=8*b。

一开始没认真思考压缩算法的作用，盲目贪心导致wa11。贪心显然是错的，不能保证压缩后的数组所有元素都在区间内。

用一个vector<pair<int,int>>来记录数字和出现次数。尺取维护当前区间元素个数。对于给定的b，显然有k=8*b/n，K=pow(2,k)。这样就确定了算法结束后最终剩余多少种数字。O(n)判一遍完事。

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

int n, I, k, K = 1, total = 0, ans;
map<int, int>cnt;
vector<pair<int, int>>v;

int main() {
    scanf("%d%d", &n, &I); k = (I << 3) / n;
    rep1(i, 1, k) {
        K <<= 1;
        if (K > n) break;
    }
    for (int i = 0, a; i < n; i++) {
        scanf("%d", &a);
        cnt[a]++;
    }
    for (auto i : cnt) v.pb(i);
    for (int i = 0; i < min(K, (int)v.size()); i++)
        total += v[i].second;
    ans = total;
    for (int i = K; i < (int)v.size(); i++)
        total = total + v[i].second - v[i - K].second, ans = max(ans, total);
    printf("%d
", n - ans);
    return 0;
}

D：

给定一个数组和q次操作，操作分为两类：1、把数组某个元素修改为给定值val；2、检查整个数组，若某元素小于给定值val，变为val。输出q次操作之后的数组。

一眼线段树。单点修改很简单，区间修改就上lazy tag。

/* basic header */
#include <bits/stdc++.h>
/* define */
#define ll long long
#define dou double
#define pb emplace_back
#define mp make_pair
#define sot(a,b) sort(a+1,a+1+b)
#define rep1(i,a,b) for(int i=a;i<=b;++i)
#define rep0(i,a,b) for(int i=a;i<b;++i)
#define eps 1e-8
#define int_inf 0x3f3f3f3f
#define ll_inf 0x7f7f7f7f7f7f7f7f
#define lson (curpos<<1)
#define rson (curpos<<1|1)
/* namespace */
using namespace std;
/* header end */

const int maxn = 2e5 + 10;
int n, m, a[maxn], ans[maxn];
struct SegmentTree {
    struct Node {
        int val, add;
    } mem[maxn << 2];
    SegmentTree() {}

    void build(int *a, int curpos, int curl, int curr) {
        if (curl == curr) {
            mem[curpos].val = a[curl];
            mem[curpos].add = 0;
            return;
        }
        int mid = curl + curr >> 1;
        build(a, lson, curl, mid); build(a, rson, mid + 1, curr);
    }

    void update(int curpos, int pos, int curl, int curr, int val) {
        if (curl == curr) {
            mem[curpos].val = val;
            mem[curpos].add = 0;
            return;
        }
        int mid = curl + curr >> 1;
        mem[lson].add = max(mem[curpos].add, mem[lson].add);
        mem[rson].add = max(mem[curpos].add, mem[rson].add);
        mem[curpos].add = 0;
        if (pos <= mid) update(lson, pos, curl, mid, val);
        else update(rson, pos, mid + 1, curr, val);
    }

    void maintain(int curpos, int curl, int curr) {
        if (curl == curr) {
            ans[curl] = max(mem[curpos].val, mem[curpos].add);
            return;
        }
        mem[lson].add = max(mem[lson].add, mem[curpos].add);
        mem[rson].add = max(mem[rson].add, mem[curpos].add);
        int mid = curl + curr >> 1;
        maintain(lson, curl, mid); maintain(rson, mid + 1, curr);
    }
} st;

int main() {
    scanf("%d", &n);
    rep1(i, 1, n) scanf("%d", &a[i]);
    st.build(a, 1, 1, n);
    scanf("%d", &m);
    while (m--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int pos, val; scanf("%d%d", &pos, &val);
            st.update(1, pos, 1, n, val);
        } else {
            int val; scanf("%d", &val);
            st.mem[1].add = max(st.mem[1].add, val);
        }
    }
    st.maintain(1, 1, n);
    rep1(i, 1, n) printf("%d ", ans[i]);
    return 0;
}