solved 4/11
2016 Multi-University Training Contest 8
贪心 1001 Ball（BH）
代码：
#include <bits/stdc++.h> const int N = 1000 + 5;
std::pair<int, int> 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 physics（BH）
代码：
#include <bits/stdc++.h>
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 Rikka with Sequence（BH）
代码：（数据加强后TLE）
#include <bits/stdc++.h> typedef long long ll;
const int N = 1e5 + 5; #define lch o << 1
#define rch o << 1 | 1 ll 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 Rikka with Parenthesis II（BH）
代码：
#include <bits/stdc++.h> 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<n; ++i) {
if (str[i] == '(')
l++;
else
r++;
}
return l == r;
} int main() {
//freopen ("1011.txt", "r", stdin);
int T;
scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
scanf ("%s", str); //printf ("%s ", str); if (!check ()) {
puts ("No");
continue;
} int top = 0, error = 0, id = -1;
for (int i=0; i<n; ++i) {
if (str[i] == '(') {
top++;
} else {
if (top == 0) {
error++;
id = i;
break;
}
else
top--;
}
} if (!error) {
puts (top == 0 ? "Yes" : "No");
} else {
str[id] = '(';
top = error = 0;
for (int i=0; i<n; ++i) {
if (str[i] == '(') {
top++;
} else {
if (top == 0) {
error++;
break;
}
top--;
}
}
puts (((!error && top == 2) ? "Yes" : "No"));
}
}
return 0;
}