题解 - Gemini Boy - ACM之路~
2012 Asia Chengdu Regional Contest
A题(HDU 4464)：无意义的题。。就贴个代码吧。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 10010;
int n, cas;
char ch[maxn];
int main() {
cas = 0;
while (~scanf("%d", &n)) {
int ans = 0;
for (int i = 0; i < n; i++) {
scanf("%s", ch);
int len = strlen(ch);
int sum = 0;
for (int i = 0; i < len; i++) {
sum += (int)ch[i];
}
if (ans < sum)
ans = sum;
}
printf("Case %d: %d\n", ++cas, ans);
}
return 0;
}
B题(HDU 4465)：这题是道求期望的题，还算比较简单。公式很容易得到：
但是因为组合数比较大，不能直接算。为了保证精度，可以先求log，然后再用乘方，算回来。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int n, cas = 0;
double p;
int main() {
while (~scanf("%d %lf", &n, &p)) {
printf("Case %d: ", ++cas);
double q = 1 - p;
if (fabs(p) < 1e-10 || fabs(q)<1e-10) {
printf("%.6lf\n", 1.0 * n);
continue;
}
double tmp = (n + 1) * log(p);
double tem = (n + 1) * log(q);
double ans = 0, t = 0, tt = 0, ttt = 0;
for (int i = n + 1; i <= n + n; i++) {
tt = t + tmp + (i-1-n) * log(q) + log(1.0+n+n-i);
ttt = t + tem + (i-1-n) * log(p) + log(1.0+n+n-i);
ans += exp(tt) + exp(ttt);
t += log(1.0*i) - log(1.0*i-n);
}
printf("%.6lf\n", ans);
}
return 0;
}
HDU 4699: Editor
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4699
题意就是模拟打字，要求支持以下操作：
- I x：在当前光标后面插入x
- D：删除光标前面一个字符
- L：光标向左移动一步
- R：光标向右移动一步
- Q k：插入前k个数字中子段和最大是多少。
这题可以用splay维护，比较简单的办法是用双向链表，维护一个ans数组，记录前i个ss数字中子段和最大是多少。对于L，R，D，I操作的时候记得更新ans数组就行了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
#include <list>
using namespace std;
const int maxn = 1001010;
const int inf = 0x3f3f3f3f;
struct ListNode {
ListNode *next;
ListNode *pre;
int key, sum;
};
ListNode nodes[maxn*2];
ListNode *p;
int C, id, ans[maxn];
int n, x;
char op[100];
void add(int key) {
ListNode *q = &nodes[C++];
q->sum = p->sum + key;
q->key = key;
q->pre = p;
q->next = p->next;
if (q->next != 0)
q->next->pre = q;
p->next = q;
p = p->next;
id++;
ans[id] = max(p->sum, ans[id-1]);
}
void del() {
if (p->pre == 0)
return ;
id--;
ListNode *q = &nodes[C++];
q = p->next;
p = p->pre;
if (q != 0)
q->pre = p;
p->next = q;
}
void left() {
if (p->pre == 0)
return ;
id--;
p = p->pre;
}
void right() {
if (p->next == 0)
return ;
int tmp = p->sum;
id++;
p = p->next;
p->sum = tmp + p->key;
ans[id] = max(p->sum, ans[id-1]);
}
void init() {
for (int i = 0; i < maxn; i++)
ans[i] = -inf;
C = 1; id = 0;
p = &nodes[0];
p->pre = 0;
p->next = 0;
p->sum = 0;
p->key = 0;
}
void work() {
for (int i = 0; i < n; i++) {
scanf("%s", op);
if (op[0] == 'I') {
scanf("%d", &x);
add(x);
} else if (op[0] == 'D') {
del();
} else if (op[0] == 'L') {
left();
} else if (op[0] == 'R') {
right();
} else {
scanf("%d", &x);
printf("%d\n", ans[x]);
}
}
}
int main() {
while (scanf("%d", &n) != EOF) {
init();
work();
}
return 0;
}
HDU 4705: Y
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4705
题意就是给一棵树，然后问不在一条链上的三个点有多少种。
树形DP，直接求不好求，先求其补集。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#pragma comment(linker, "/STACK:16777216")
const int maxn = 100100;
vector<int> son[maxn];
int f[maxn], x, y;
long long n, ans;
void clear() {
for (int i = 0; i < maxn; i++)
son[i].clear();
memset(f, 0, sizeof(f));
ans = 0;
}
void dfs(int u, int fa) {
long long tmp = 0;
f[u] = 1;
for (int i = 0; i < son[u].size(); i++) {
int v = son[u][i];
if (v == fa)
continue;
dfs(v, u);
f[u] += f[v];
ans += tmp * f[v];
tmp += f[v];
}
ans += tmp * (n - f[u]);
}
void init() {
clear();
for (int i = 1; i < n; i++) {
cin >> x >> y;
son[x].push_back(y);
son[y].push_back(x);
}
}
void work() {
dfs(1, -1);
long long res = n * (n-1) * (n-2) / 6;
cout << res - ans << endl;
}
int main() {
while (cin >> n) {
init();
work();
}
return 0;
}
BZOJ 2752: [HAOI2012]高速公路(road) (线段树)
链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2752
概率背景的题，不过稍微想想，稍微推一推，就能得到公式。然后注意到只要用线段树维护3个sum就行了，sum1 费用和， sum2 下标乘以费用的和 sum3下标的平方乘以费用的和
PS：。。。在写线段树的时候被一个傻逼问题bug住了好久，，调了好久。好吧 我就是煞笔
2版线段树的代码。
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100100;
long long sumo[maxn], sump[maxn];
struct SegNode {
int left, right;
long long sum1, sum2, sum3;
long long add;
int mid() {
return (left + right) >> 1;
}
long long size() {
return (right - left + 1);
}
};
struct SegmentTree {
SegNode tree[maxn*5];
void pushUp(int idx) {
tree[idx].sum1 = tree[idx<<1].sum1 + tree[idx<<1|1].sum1;
tree[idx].sum2 = tree[idx<<1].sum2 + tree[idx<<1|1].sum2;
tree[idx].sum3 = tree[idx<<1].sum3 + tree[idx<<1|1].sum3;
}
void pushDown(int idx) {
if (tree[idx].add) {
long long add = tree[idx].add;
int right1 = tree[idx<<1].right;
int left1 = tree[idx<<1].left;
int right2 = tree[idx<<1|1].right;
int left2 = tree[idx<<1|1].left;
tree[idx].add = 0;
tree[idx<<1].sum1 += tree[idx<<1].size() * add;
tree[idx<<1|1].sum1 += tree[idx<<1|1].size() * add;
tree[idx<<1].sum2 += (sumo[right1] - sumo[left1-1]) * add;
tree[idx<<1|1].sum2 += (sumo[right2] - sumo[left2-1]) * add;
tree[idx<<1].sum3 += (sump[right1] - sump[left1-1]) * add;
tree[idx<<1|1].sum3 += (sump[right2] - sump[left2-1]) * add;
tree[idx<<1].add += add;
tree[idx<<1|1].add += add;
}
}
void build(int left, int right, int idx) {
tree[idx].left = left;
tree[idx].right = right;
tree[idx].sum1 = 0;
tree[idx].sum2 = 0;
tree[idx].sum3 = 0;
tree[idx].add = 0;
if (left == right)
return ;
int mid = tree[idx].mid();
build(left, mid, idx<<1);
build(mid+1, right, idx<<1|1);
}
void update(int left, int right, int idx, long long value) {
if (tree[idx].left == left && tree[idx].right == right) {
tree[idx].add += value;
tree[idx].sum1 += tree[idx].size() * value;
tree[idx].sum2 += (sumo[right] - sumo[left-1]) * value;
tree[idx].sum3 += (sump[right] - sump[left-1]) * value;
return ;
}
pushDown(idx);
int mid = tree[idx].mid();
if (right <= mid)
update(left, right, idx<<1, value);
else if (left > mid)
update(left, right, idx<<1|1, value);
else {
update(left, mid, idx<<1, value);
update(mid+1, right, idx<<1|1, value);
}
pushUp(idx);
}
long long query(int left, int right, int idx, int L, int R) {
if (tree[idx].left == left && tree[idx].right == right) {
//printf("%d %d %d\n", idx, left, right);
return (R + L - 1) * tree[idx].sum2 - tree[idx].sum3 -
((long long)L * R - R) * tree[idx].sum1;
}
pushDown(idx);
int mid = tree[idx].mid();
if (right <= mid)
return query(left, right, idx<<1, L, R);
else if (left > mid)
return query(left, right, idx<<1|1, L, R);
else {
return (query(left, mid, idx<<1, L, R) + query(mid+1, right, idx<<1|1, L, R));
}
}
};
SegmentTree tree;
int N, M;
long long gcd(long long a, long long b) {
return b ? gcd(b, a % b) : a;
}
void init() {
memset(sumo, 0, sizeof(sumo));
memset(sump, 0, sizeof(sump));
for (int i = 1; i < maxn; i++)
sumo[i] = sumo[i-1] + i;
for (int i = 1; i < maxn; i++)
sump[i] = sump[i-1] + (long long)i * i;
scanf("%d %d", &N, &M);
tree.build(1, N, 1);
}
void work() {
char op[19];
for (int i = 0; i < M; i++) {
scanf("%s", op);
if (op[0] == 'C') {
int x, y;
long long z;
scanf("%d %d %lld", &x, &y, &z);
tree.update(x, y-1, 1, z);
} else {
int x, y;
scanf("%d %d", &x, &y);
long long tmp = tree.query(x, y, 1, x, y);
long long tem = (long long)(y - x + 1) * (y - x) / 2;
long long ans = gcd(tmp, tem);
printf("%lld/%lld\n", tmp / ans, tem / ans);
}
}
}
int main() {
init();
work();
return 0;
}
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100100;
long long sumo[maxn], sump[maxn];
struct SegNode {
int left, right;
long long sum1, sum2, sum3;
long long add;
};
struct SegmentTree {
SegNode tree[maxn*5];
void pushUp(int idx) {
tree[idx].sum1 = tree[idx<<1].sum1 + tree[idx<<1|1].sum1;
tree[idx].sum2 = tree[idx<<1].sum2 + tree[idx<<1|1].sum2;
tree[idx].sum3 = tree[idx<<1].sum3 + tree[idx<<1|1].sum3;
}
void pushDown(int idx, int left, int right) {
if (tree[idx].add) {
long long add = tree[idx].add;
tree[idx].add = 0;
tree[idx].sum1 += (right - left + 1) * add;
tree[idx].sum2 += (sumo[right] - sumo[left-1]) * add;
tree[idx].sum3 += (sump[right] - sump[left-1]) * add;
if (left == right) return ;
tree[idx<<1].add += add;
tree[idx<<1|1].add += add;
}
}
void update(int L, int R, int left, int right, int idx, long long value) {
pushDown(idx, L, R);
if (L >= left && R <= right) {
tree[idx].add += value;
return ;
}
int mid = (L + R) >> 1;
if (left <= mid)
update(L, mid, left, right, idx<<1, value);
if (right >= mid+1)
update(mid+1, R, left, right, idx<<1|1, value);
pushDown(idx<<1, L, mid);
pushDown(idx<<1|1, mid+1, R);
pushUp(idx);
}
long long query(int L, int R, int left, int right, int idx) {
pushDown(idx, L, R);
if (L >= left && R <= right) {
printf("%d %d %d\n", idx, left, right);
return (right + left - 1) * tree[idx].sum2 - tree[idx].sum3 -
((long long)left * right - right) * tree[idx].sum1;
}
int mid = (L + R) >> 1;
long long ans = 0;
if (left <= mid)
ans += query(L, mid, left, right, idx<<1);
if (right >= mid + 1)
ans += query(mid+1, R, left, right, idx<<1|1);
return ans;
}
};
SegmentTree tree;
int N, M;
long long gcd(long long a, long long b) {
return b ? gcd(b, a % b) : a;
}
void init() {
memset(sumo, 0, sizeof(sumo));
memset(sump, 0, sizeof(sump));
for (int i = 1; i < maxn; i++)
sumo[i] = sumo[i-1] + i;
for (int i = 1; i < maxn; i++)
sump[i] = sump[i-1] + (long long)i * i;
scanf("%d %d", &N, &M);
}
void work() {
char op[19];
for (int i = 0; i < M; i++) {
scanf("%s", op);
if (op[0] == 'C') {
int x, y;
long long z;
scanf("%d %d %lld", &x, &y, &z);
tree.update(1, N, x, y-1, 1, z);
} else {
int x, y;
scanf("%d %d", &x, &y);
long long tmp = tree.query(1, N, x, y, 1);
long long tem = (long long)(y - x + 1) * (y - x) / 2;
long long ans = gcd(tmp, tem);
printf("%lld/%lld\n\n", tmp / ans, tem / ans);
}
}
}
int main() {
init();
work();
return 0;
}
BZOJ 3251: 树上三角形
链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3251
题意就是给一棵树，点权，然后查询一条链上是否有3个点的点权能组成一个三角形。
注意到三角形任意2边之和大于第三边，然后最坏的情况类似于斐波那契数列，大约4 50左右的时候，就会超int。所以当链的长度大于45的时候，返回true，否则就暴力判断是否可行。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 101110;
int N, Q;
vector<int> next[maxn];
long long val[maxn];
int par[maxn], dep[maxn];
void dfs(int u) {
for (int i = 0; i < next[u].size(); i++) {
int v = next[u][i];
//if (dep[v]) continue;
dep[v] = dep[u] + 1;
dfs(v);
}
}
bool check(int x, int y) {
int cnt = 0;
long long num[55];
for ( ; dep[x] > dep[y]; x = par[x]) {
num[cnt++] = val[x];
if (cnt > 45) return true;
}
for ( ; x != y; x = par[x], y = par[y]) {
num[cnt++] = val[x];
num[cnt++] = val[y];
if (cnt > 45) return true;
}
num[cnt++] = val[y];
if (cnt < 3)
return false;
sort(num, num + cnt);
for (int i = 0; i + 2 < cnt; i++) {
if (num[i] + num[i+1] > num[i+2])
return true;
}
return false;
}
void init() {
for (int i = 0; i < maxn; i++) {
next[i].clear();
dep[i] = 0;
val[i] = 0;
par[i] = 0;
}
par[1] = -1;
scanf("%d %d", &N, &Q);
for (int i = 1; i <= N; i++)
scanf("%d", &val[i]);
for (int i = 1; i < N; i++) {
int x, y;
scanf("%d %d", &x, &y);
par[y] = x;
next[x].push_back(y);
}
dep[1] = 1;
dfs(1);
}
void work() {
for (int i = 0; i < Q; i++) {
int opt, x, y;
scanf("%d %d %d", &opt, &x, &y);
if (opt == 1)
val[x] = y;
else {
if (dep[x] < dep[y])
swap(x, y);
if (x == y || x == par[y] || y == par[x]) {
puts("N");
continue;
}
if (check(x, y) == true)
puts("Y");
else puts("N");
}
}
}
int main() {
init();
work();
return 0;
}