首页 > 代码库 > Codeforces Round #263 (Div. 1) A B C
Codeforces Round #263 (Div. 1) A B C
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\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; }
Codeforces Round #263 (Div. 1) A B C
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。