https://ac.nowcoder.com/acm/contest/3003
题解 https://ac.nowcoder.com/discuss/364961?type=101&order=0&pos=9&page=3
C. 算概率
题意:每道题有正确率,问恰好作对K道题的概率。
dp
dp[i][j] 表示到第 i 题,做对了 j 题的概率。
dp[i][j]=dp[i−1][j−1]⋅a[i]+dp[i−1][j]⋅(1−a[i])
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| #include<bits/stdc++.h> using namespace std; #define ll long long typedef pair<ll, ll> pii; const int maxn = 2e5 + 10; const int INF = 0x3f3f3f3f; const ll mod = 1e9 + 7; int n; ll a[3000], dp[3000][3000]; int main() { cin >> n; for (int i = 1; i <= n; i++)cin >> a[i]; dp[1][1] = a[1]; dp[1][0] = mod + 1 - a[1]; for (int i = 2; i <= n; i++) { dp[i][0] = dp[i - 1][0] * (mod + 1 - a[i]) % mod; for (int j = 1; j <= i; j++) { dp[i][j] = (dp[i - 1][j - 1] * a[i] % mod + dp[i - 1][j] * (mod + 1 - a[i]) % mod) % mod; } } for (int i = 0; i <= n; i++)printf("%lld%s", dp[n][i], i == n ? "\n" : " "); return 0; }
|
E. 做计数
题意:问有多少正整数 (i,j,k) 满足 i+j=k 且 i⋅j≤n
等式变为 i+j+2ij 为正整数,所以 i⋅j 为小于 n 的完全平方数,可以直接枚举,再枚举这个完全平方数的因子,得到数对 (i,j) 的个数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| #include<bits/stdc++.h> using namespace std; #define ll long long typedef pair<ll, ll> pii; const int maxn = 2e5 + 10; const int INF = 0x3f3f3f3f; const ll mod = 1e9 + 7; ll n, ans; int main() { cin >> n; for (ll i = 1; i*i <= n; i++) { for (ll j = 1; j*j <= i * i; j++) { if (i*i%j == 0)ans += 2; } ans--; } cout << ans << endl; return 0; }
|
F. 拿物品
题意:有一些物品,每个物品有 a,b 值,牛牛拿某个物品得到它的a值,牛可乐拿某个物品得到它的b值,两人都想自己的值比对方大的量多,问最终每人拿了那些物品。
假设最终两人值为 W1,W2,两人交换一件物品后牛牛更赚,则 W1′=W1−a1+a2,W2′=W2+b1−b2,W1′−W2′=W1−W2+(a2+b2)−(a1+b1)>W1−W2,所以 a2+b2>a1+b1 ,则说明a+b更大的物品更赚,所以按a+b排序,再间隔分配。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #include<bits/stdc++.h> using namespace std; #define ll long long typedef pair<ll, ll> pii; const int maxn = 2e5 + 10; const int INF = 0x3f3f3f3f; const ll mod = 1e9 + 7; int n; ll a[maxn], b[maxn]; int c[maxn]; bool cmp(int i, int j) { return a[i] + b[i] > a[j] + b[j]; } int main() { cin >> n; for (int i = 1; i <= n; i++)scanf("%lld", &a[i]); for (int i = 1; i <= n; i++)scanf("%lld", &b[i]), c[i] = i; sort(c + 1, c + n + 1, cmp); for (int i = 1; i <= n; i += 2)printf("%s%d", i == 1 ? "" : " ", c[i]); puts(""); for (int i = 2; i <= n; i += 2)printf("%s%d", i == 2 ? "" : " ", c[i]); puts(""); return 0; }
|
H. 施魔法
题意:牛可乐有 n 个元素( 编号 1…n ),第 i 个元素的能量值为 ai。
牛可乐可以选择至少 k 个元素来施放一次魔法,魔法消耗的魔力是这些元素能量值的极差。形式化地,若所用元素编号集合为 S,则消耗的魔力为 $ \max_{i\in S}{a_i}-\min_{i\in S}{a_i}$。牛可乐要求每个元素必须被使用恰好一次。牛可乐想知道他最少需要多少魔力才能用完所有元素,请你告诉他。
dp优化
dp[i] 表示到第 i 个物品,最少魔力。
则 dp[i]=maxi−j+1≥k{dp[j]}
再不断记录前面的dp值以优化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| #include<bits/stdc++.h> using namespace std; #define ll long long const int INF = 0x3f3f3f3f; const int maxn = 3e5 + 10; int n, k; ll a[maxn], dp[maxn]; int main() { cin >> n >> k; for (int i = 1; i <= n; i++)scanf("%lld", &a[i]); sort(a + 1, a + n + 1); memset(dp, 0x3f, sizeof(dp)); dp[k] = a[k] - a[1]; ll mn = 0 - a[1]; for (int i = k + 1; i <= n; i++) { dp[i] = mn + a[i]; mn = min(mn, dp[i - k + 1] - a[i - k + 2]); } cout << dp[n] << endl; return 0; }
|
I. 建通道
题意:有几个点,每个点有点权,两点连边的消耗为两点的点权异或值的最低位1,即 lowbit(vi⊕vj) ,问使得所有点联通的最小消耗。
显然不能直接求生成树。
从最低位开始找,若存在两个点在某一位异或为1,则必定一个1,一个0,其它点若该位为1,则连为0的那个,否则连为1的那个,每条边的花费都是最小值,总的花费也是最小。
而若有两点权值相同,则连边消耗为0,可以不计算。则读入时只读入不重复的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| #include<bits/stdc++.h> using namespace std; #define ll long long ll n, a[100], p, cnt, x; map<ll, int>mp; int main() { cin >> n; for (int i = 1; i <= n; i++) { scanf("%lld", &x); if (mp[x])continue; mp[x] = 1; cnt++; for (int j = 0; j <= 30; j++)if (x&(1ll << j))a[j]++; } for (p = 0; p <= 30 && !(a[p] && a[p] < n); p++); cout << 1ll * (1ll << p)*(cnt - 1) << endl; return 0; }
|
J. 求函数
题意: 牛可乐有 m 次操作,每次操作为以下二者其一:
• 1,i,k,b 将 fi(x) 修改为 fi(x)=k×x+b。
• 2,l,r 求 (fr1(⋯(fl+1(fl(1)))⋯))。
对求值操作输出答案。
线段树
把式子化简得到
ans=i=l∏rki+i=l∑rbi⋅j=i+1∏rkj
可以用线段树维护 ∏i=lrki 和 ∑i=lrbi⋅∏j=i+1rkj。
第一棵线段树很容易更新,考虑第二棵。
合并前 ∑i=l1r1bi⋅∏j=i+1r1kj 和 ∑i=l2r2bi⋅∏j=i+1r2kj,且 l2=r1+1。
合并后为 ∑i=l1r2bi⋅∏j=i+1r2kj
对比发现合并方式为
(i=l1∑r1bi⋅j=i+1∏r1kj)⋅i=l2∏r2ki+(i=l2∑r2bi⋅j=i+1∏r2kj)
∏i=l2r2ki 刚好是同一个节点的在另一棵树里的右节点,总的合并复杂度仍是 O(logn)
求答案时把两棵线段树的值加起来即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
| #include<bits/stdc++.h> using namespace std; #define ll long long typedef pair<ll, ll> pii; const int maxn = 2e5 + 10; const int INF = 0x3f3f3f3f; const ll mod = 1e9 + 7; int n, m; ll k[maxn], b[maxn]; #define mid ((l+r)>>1) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 ll t1[maxn << 2], t2[maxn << 2]; void pushup(int rt) { t1[rt] = t1[rt << 1] * t1[rt << 1 | 1] % mod; t2[rt] = (t2[rt << 1] * t1[rt << 1 | 1] % mod + t2[rt << 1 | 1]) % mod; } void build(int l, int r, int rt) { if (l == r) { t1[rt] = k[l]; t2[rt] = b[l]; return; } build(lson); build(rson); pushup(rt); } void update(int l, int r, int rt, int q, ll K, ll B) { if (l == r) { t1[rt] = K; t2[rt] = B; return; } if (q <= mid)update(lson, q, K, B); else update(rson, q, K, B); pushup(rt); } pii query(int l, int r, int rt, int ql, int qr) { if (ql <= l && qr >= r)return pii(t1[rt], t2[rt]); if (qr <= mid)return query(lson, ql, qr); else if (ql > mid)return query(rson, ql, qr); else { pii res1 = query(lson, ql, qr), res2 = query(rson, ql, qr); return pii(res1.first*res2.first%mod, (res1.second*res2.first%mod + res2.second) % mod); } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++)scanf("%lld", &k[i]); for (int i = 1; i <= n; i++)scanf("%lld", &b[i]); build(1, n, 1); while (m--) { int op; scanf("%d", &op); if (op == 1) { int i; ll K, B; scanf("%d%lld%lld", &i, &K, &B); update(1, n, 1, i, K, B); } else { int l, r; scanf("%d%d", &l, &r); pii ans = query(1, n, 1, l, r); printf("%lld\n", (ans.first + ans.second) % mod); } } return 0; }
|