Codeforces Round #263 (Div. 1) A B C
来源：程序员人生 发布时间：2014-09-29 08:00:01 阅读次数：2191次
Codeforces Round #263 (Div. 1)
A:贪心，排个序，然后从后往前扫一遍，计算后缀和，之后在从左往右扫一遍计算答案
B：树形DP，0表示没有1，1表示有1，0遇到0必然合并，0遇到1也必然合并，1遇到0必然合并，1遇到1，必然切断，按照这样去转移即可
C：树状数组，再利用启发式合并，开一个l，r记录当前被子左右下标，和一个flip表示是否翻转
代码：
A：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 300005;
int n;
ll a[N], sum[N];
int main() {
scanf("%d", &n);ll ans = 0;
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
ans += a[i];
}
sort(a, a + n);
for (int i = n - 1; i >= 0; i--)
sum[i] = a[i] + sum[i + 1];
for (int i = 0; i < n - 1; i++) {
ans += sum[i];
}
printf("%lld
", ans);
//system("pause");
return 0;
}
B：
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstdlib>
using namespace std;
const int N = 100005;
typedef long long ll;
const ll MOD = 1000000007;
int n, node[N];
vector<int> g[N];
ll dp[N][2];
ll pow_mod(ll x, ll k) {
ll ans = 1;
while (k) {
if (k&1) ans = ans * x % MOD;
x = x * x % MOD;
k >>= 1;
}
return ans;
}
ll inv(ll x) {
return pow_mod(x, MOD - 2);
}
void init() {
scanf("%d", &n);
int u;
for (int i = 1; i < n; i++) {
scanf("%d", &u);
g[u].push_back(i);
}
for (int i = 0; i < n; i++)
scanf("%d", &node[i]);
}
void dfs(int u) {
if (g[u].size() == 0) {
dp[u][node[u]] = 1;
return;
}
for (int i = 0; i < g[u].size(); i++)
dfs(g[u][i]);
dp[u][0] = dp[u][1] = 1;
if (node[u]) {
dp[u][0] = 0;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
dp[u][1] = dp[u][1] * (dp[v][0] + dp[v][1]) % MOD;
}
}
else {
ll cnt = 0;
ll mul = 1;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
dp[u][0] = dp[u][0] * (dp[v][0] + dp[v][1]) % MOD;
mul = mul * (dp[v][0] + dp[v][1]) % MOD;
}
dp[u][1] = 0;
for (int i = 0; i < g[u].size(); i++){
int v = g[u][i];
dp[u][1] = (dp[u][1] + mul * inv((dp[v][0] + dp[v][1]) % MOD) % MOD * dp[v][1]) % MOD;
}
}
}
int main() {
init();
dfs(0);
printf("%lld
", dp[0][1] % MOD);
//system("pause");
return 0;
}
C：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lowbit(x) (x&(-x))
const int N = 100005;
int n, q, bit[N];
void add(int x, int v) {
while (x < N) {
bit[x] += v;
x += lowbit(x);
}
}
int get(int x) {
int ans = 0;
while (x) {
ans += bit[x];
x -= lowbit(x);
}
return ans;
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++)
add(i, 1);
int tp, a, b;
int l = 1, r = n, flip = 0;
while (q--) {
scanf("%d%d", &tp, &a);
if (tp == 1) {
int tl = l, tr = r;
if (a <= (r - l + 1) / 2) {
if (flip) {
for (int i = a; i >= 1; i--) {
add(r - 2 * i + 1, get(tr - a + i) - get(tr - a + i - 1));
r--;
}
}
else {
for (int i = a; i >= 1; i--) {
add(l + 2 * i - 1, get(tl + a - i) - get(tl + a - i - 1));
l++;
}
}
} else {
a = r - a - l + 1;
if (!flip) {
for (int i = a; i >= 1; i--) {
add(r - 2 * i + 1, get(tr - a + i) - get(tr - a + i - 1));
r--;
}
}
else {
for (int i = a; i >= 1; i--) {
add(l + 2 * i - 1, get(tl + a - i) - get(tl + a - i - 1));
l++;
}
}
flip ^= 1;
}
}
else {
scanf("%d", &b);
if (flip) {
a = r - a;
b = r - b;
swap(a, b);
} else {
a += l - 1;
b += l - 1;
}
printf("%d
", get(b) - get(a));
}
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
