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：
#includeB：#include #include #include #include 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;}
#includeC：#include #include #include using namespace std;const int N = 100005;typedef long long ll;const ll MOD = 1000000007;int n, node[N];vector 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;}
#include#include #include 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;}