Codeforces Round #263 (Div. 1) A B C_html/css_WEB-ITnose

Codeforces Round #263 (Div. 1)

A: Be greedy, sort it, then scan it from back to front, calculate the suffix sum, and then scan it from left to right to calculate the answer

B: Tree DP, 0 means there is no 1, 1 means there is 1, 0 will be merged when it encounters 0, 0 will be merged when it encounters 1, 1 will be merged when it encounters 0, and 1 will be cut off when it encounters 1, follow this way Just transfer

C: tree array, then use heuristic merging, open an l, r to record the left and right subscripts of the current quilt, and a flip to indicate whether to flip

Code:

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\n", 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\n", 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\n", get(b) - get(a));        }    }    return 0;}