solved 4/11

贪心 1001 （BH）

 

代码：

#include 
     
      const int N = 1000 + 5;std::pair
      
        a[N];int n, m;int main() {    int T;    scanf ("%d", &T);    while (T--) {        scanf ("%d%d", &n, &m);        for (int i=1; i<=n; ++i) {            int c;            scanf ("%d", &c);            a[i] = {0, c};        }        for (int i=1; i<=n; ++i) {            int c;            scanf ("%d", &c);            for (int j=1; j<=n; ++j) {                if (a[j].second == c && !a[j].first) {                    a[j].first = i;                    break;                }            }        }        while (m--) {            int l, r;            scanf ("%d%d", &l, &r);            std::sort (a+l, a+r+1);        }        bool flag = true;        for (int i=1; i<=n; ++i) {            if (a[i].first != i) {                flag = false;                break;            }        }        puts (flag ? "Yes" : "No");    }    return 0;}
      
     

物理+微分方程 1006 （BH）

 

代码：

#include 
     
      int v[100005];int main() {    int T;    scanf ("%d", &T);    while (T--) {        int n, c;        scanf ("%d%d", &n, &c);        for (int i=1; i<=n; ++i) {            int x, d;            scanf ("%d%d%d", v+i, &x, &d);        }        std::sort (v+1, v+1+n);        int m;        scanf ("%d", &m);        while (m--) {            int t, k;            scanf ("%d%d", &t, &k);            printf ("%.3f\n", sqrt ((double) v[k]*v[k] + 2.0*c*t));        }    }    return 0;}
     

线段树+优化 1008 （BH）

 

代码：（数据加强后TLE）

#include 
     
      typedef long long ll;const int N = 1e5 + 5;#define lch o << 1#define rch o << 1 | 1ll sum[N<<2], same[N<<2], add[N<<2];void push_up(int o) {    if (same[lch] == same[rch])        same[o] = same[lch];    else        same[o] = 0;    sum[o] = sum[lch] + sum[rch];}void push_down1(int o, int l, int r) {    add[lch] += add[o];    add[rch] += add[o];    int mid = l + r >> 1;    sum[lch] += add[o] * (mid-l+1);    sum[rch] += add[o] * (r-mid);    if (same[lch])        same[lch] += add[o];    if (same[rch])        same[rch] += add[o];    add[o] = 0;}void push_down2(int o, int l, int r) {    same[lch] = same[rch] = same[o];    int mid = l + r >> 1;    sum[lch] = same[o] * (mid-l+1);    sum[rch] = same[o] * (r-mid);    same[o] = 0;}void build(int o, int l, int r) {    add[o] = 0;    if (l == r) {        scanf ("%I64d", &sum[o]);        same[o] = sum[o];        return ;    }    int mid = l + r >> 1;    build (lch, l, mid);    build (rch, mid+1, r);    push_up (o);}void modify_add(int o, int l, int r, int ql, int qr, int c) {    if (ql <= l && r <= qr) {        sum[o] += (ll) (r - l + 1) * c;        if (same[o])            same[o] += c;        else            add[o] += c;        return ;    }    if (add[o])        push_down1 (o, l, r);    if (same[o])        push_down2 (o, l, r);    int mid = l + r >> 1;    if (ql <= mid)        modify_add (lch, l, mid, ql, qr, c);    if (qr > mid)        modify_add (rch, mid+1, r, ql, qr, c);    push_up (o);}void modify_sqrt(int o, int l, int r, int ql, int qr) {    if (ql <= l && r <= qr && same[o]) {        same[o] = (ll) sqrt ((double) same[o]);        sum[o] = same[o] * (r - l + 1);        add[o] = 0;        return ;    }    if (add[o])        push_down1 (o, l, r);    if (same[o])        push_down2 (o, l, r);    int mid = l + r >> 1;    if (ql <= mid)        modify_sqrt (lch, l, mid, ql, qr);    if (qr > mid)        modify_sqrt (rch, mid+1, r, ql, qr);    push_up (o);}ll query(int o, int l, int r, int ql, int qr) {    if (ql <= l && r <= qr) {        return sum[o];    }    if (add[o])        push_down1 (o, l, r);    if (same[o])        push_down2 (o, l, r);    int mid = l + r >> 1;    ll ret = 0;    if (ql <= mid)        ret += query (lch, l, mid, ql, qr);    if (qr > mid)        ret += query (rch, mid+1, r, ql, qr);    return ret;}int main() {    int T;    scanf ("%d", &T);    while (T--) {        int n, m;        scanf ("%d%d", &n, &m);        build (1, 1, n);        int tp, ql, qr, c;        while (m--) {            scanf ("%d%d%d", &tp, &ql, &qr);            if (tp == 1) {                scanf ("%d", &c);                modify_add (1, 1, n, ql, qr, c);            } else if (tp == 2) {                modify_sqrt (1, 1, n, ql, qr);            } else {                printf ("%I64d\n", query (1, 1, n, ql, qr));            }        }    }    return 0;}
     

构造 1011 （BH）

 

代码：

#include 
     
      const int N = 1e5 + 5;char str[N];int n;bool check() {    if (n & 1)        return false;    if (n == 2) {        if (strcmp (str, ")(") != 0)            return false;    }    int l = 0, r = 0;    for (int i=0; i