主要思路
首先,\(n – 1\) 个二元组代表着这颗树形有向图的形状。我们先考虑外向树的情况:子树根的时间戳要早于所有的子节点,所以可以考虑直接用背包的方法进行合并。如果有反向边,那么我们可以考虑进行容斥,枚举反向关系数再乘上一个容斥系数 \(-1\) 即可。
首先,\(n – 1\) 个二元组代表着这颗树形有向图的形状。我们先考虑外向树的情况:子树根的时间戳要早于所有的子节点,所以可以考虑直接用背包的方法进行合并。如果有反向边,那么我们可以考虑进行容斥,枚举反向关系数再乘上一个容斥系数 \(-1\) 即可。
首先,这道题是概率和期望分开算的,进行 DP 时实质上是对概率进行 DP。考虑拆位,设\(dp_b [u]\)为从\(u \to n\)在第\(b\)位为\(1\)的概率,那么显然:
\[ dp_b[u] = \frac{1}{deg[u]}( \sum_{weight(u, v) !\& b} dp_b[v] \sum_{weight(u, v) \& b} (1 – dp_b[v]) ) \]
其中,\((1 – dp_b[v])\)为\(v\)为\(0\)的概率,最后答案消元完就是\(\sum_{i = 1} ans[i] 2^i\)。
今天被各路神仙吊打,顺利 gg。
在考场上我推了个有后效性的 DP,还以为是高斯消元,然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。
首先,对一个概率为\(p\)的事件,它的期望次数是\(\frac{1}{p}\)(参见这里)。然后,考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。
考虑\(dp[1]\)的求法,首先需要两个级别为\(0\)的武器,然后发现无论失败与否都可以保证至少又一个\(0\)级武器,所以我们只需要注意另外一个武器的花费就可以了:
\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]
这道题主要是运用贪心。首先我们可以确定以下几种情况是肯定无解的:
我们发现整个字符串\(s[1 \dots n]\)中,第一个和最后一个字符一定要是 ‘(‘ 和 ‘)’。所以我们只用关心\(s[2 \dots n-1]\)就好。统计需要补充的括号个数:也就是\((n-2)\)减去现已确定的括号个数,分\(remL\)为左括号需要补充的个数、\(remR\)为右括号需要补充的个数。
说实话,这就是我最薄弱的一项,且在比赛中一览无余的暴露出来了。
我们可以把这道题转换一下,可以发现,这个喜悦值毫无关系,第二题的题意即为
给一些物品\(a_i\),每次操作有\(p_i\)的概率可能出现,求要使所有物品出现的期望操作次数。
考虑物品的个数很少,可以进行状压,压缩到\(S\)。对于每一个出现过物品\(i\)的情况,都可以从没有出现过的状态转移过来,即S^(1<<(i - 1))
。对之前的情况乘上一个\(p_i\)即为这一部分的贡献。之后,因为\(\sum_{i} {p_i} \neq 1\),所以存在操作无效的情况,也就是\((1-\sum_{i\in S} p_i)*E_S\)。之后加上操作次数\(1\),式子全貌为:
\[ E_S = (\sum_{i\in S} p_i*E_{S’}) + (1-\sum_{i\in S} p_i)*E_S + 1 \]
移项合并可得:
\[ (\sum_{i\in S} p_i)*E_S = (\sum_{i\in S} p_i*E_{S’}) + 1 \\ E_S = \frac{(\sum_{i\in S} p_i*E_{S’}) + 1}{\sum_{i\in S} p_i} \]
// A.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 21; int n, wi[MAX_N]; long long ans1; double pi[MAX_N], dp[(1 << 20)]; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lf%d", &pi[i], &wi[i]), ans1 += wi[i]; for (int stat = 0; stat < (1 << n); stat++) { double psum = 0, ans = 0; for (int i = 1; i <= n; i++) if (stat & (1 << (i - 1))) { int prestat = stat ^ (1 << (i - 1)); psum += pi[i]; ans += pi[i] * dp[prestat]; } if (psum != 0) dp[stat] = (ans + 1) / psum; } printf("%lld\n%.3lf", ans1, dp[(1 << n) - 1]); return 0; }
啊,我*。
这道题很水,不讲。
/// B.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int MAX_N = 100400, MAX_M = 1e5 + 2000; int head[MAX_N], current, dfn[MAX_N], low[MAX_N], tot, st[MAX_N], hd, aff[MAX_N]; int totp, n, m, tmpx, tmpy, tmpz, ufs[MAX_N], dist[MAX_N]; bool inst[MAX_N]; struct edge { int to, nxt, weight, from; bool operator<(const edge &e) const { return weight > e.weight; } } edges[MAX_M << 1]; int find(int x) { return (ufs[x] == x) ? x : ufs[x] = find(ufs[x]); } void unite(int x, int y) { if (find(x) != find(y)) ufs[find(x)] = find(y); } int addpath(int u, int v, int weight) { edges[current].to = v, edges[current].nxt = head[u]; edges[current].from = u; edges[current].weight = weight, head[u] = current++; return current - 1; } void tarjan(int u) { inst[u] = true, st[++hd] = u; dfn[u] = ++tot, low[u] = dfn[u]; for (int i = head[u]; i != -1; i = edges[i].nxt) if (dfn[edges[i].to] == 0) tarjan(edges[i].to), low[u] = min(low[u], low[edges[i].to]); else if (inst[edges[i].to]) low[u] = min(low[u], dfn[edges[i].to]); if (dfn[u] == low[u]) { int j; totp++; do { j = st[hd], aff[j] = totp; inst[j] = false; } while (st[hd--] != u); } } int main() { while (scanf("%d%d", &n, &m) && n != 0 && m != 0) { memset(dist, 0x3f, sizeof(dist)); memset(st, 0, sizeof(st)), memset(dfn, 0, sizeof(dfn)), hd = 0; for (int i = 1; i <= 2 * n; i++) ufs[i] = i; memset(head, -1, sizeof(head)), memset(aff, 0, sizeof(aff)); totp = n, current = 0, tot = 0; for (int i = 1; i <= m; i++) scanf("%d%d%d", &tmpx, &tmpy, &tmpz), addpath(tmpx + 1, tmpy + 1, tmpz); tarjan(1); for (int i = 1; i <= n; i++) for (int e = head[i]; e != -1; e = edges[e].nxt) if (aff[i] != aff[edges[e].to]) dist[aff[edges[e].to]] = min(dist[aff[edges[e].to]], edges[e].weight); long long ans = 0; for (int i = n + 1; i <= totp; i++) if (aff[1] != i) ans += dist[i]; printf("%lld\n", ans); } return 0; }
这道题来自于 Codeforces,画风十分一至。
首先转换题意,这道题提示了每一个横纵坐标都只会存在一个点,求长为\(len\)且纵坐标最大最小值也为\(len\)的区间个数。我们可以用分治来搞一搞。首先定一个区间\([l,r]\),中点为\(mid\)。我们来探索跨这两个小区间的几种情况。
首先,我们在分类讨论之前设定几个数组:
设\(minl[i]\)为区间\([i,mid]\)的最小值,\(maxl[i]\)为区间\([i,mid]\)的最大值;
设\(minr[i]\)为区间\([mid+1,i]\)的最小值,\(maxr[i]\)为区间\([mid+1,i]\)的最大值。
那么,我们可以讨论跨越的情况:
最值都在左、右同一个区间内
最值分别在两个不同的区间
(i\),可以根据最值之差算出右端点,进行检查并计数。
第二种稍稍麻烦一点:跨区间要考虑最值的两种分布方式,我们以最小值在左侧,最大值在右侧为例,假设有个点符合条件:
\[ maxr[j]-minl[i] = j-i \\ \text{移项得} \\ maxr[j]-j=minl[i]-i \]
可以枚举断点,把计算内容放到桶里去(注意负数,加上数域偏移),然后用两个指针判断合法区间,左端指针减一,右指针加一。
// C.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 50200, NUM_DOMAIN = 6e5; pair<int, int> prs[MAX_N]; int arr[MAX_N], n, maxl[MAX_N], maxr[MAX_N], minl[MAX_N], minr[MAX_N], bucket[2 * NUM_DOMAIN + 1]; long long answer = 0; void dq(int l, int r) { if (l == r) { answer++; return; } int mid = (l + r) >> 1; // preprocessing; minl[mid] = arr[mid], maxl[mid] = arr[mid]; maxr[mid + 1] = arr[mid + 1], minr[mid + 1] = arr[mid + 1]; for (int i = mid - 1; i >= l; i--) minl[i] = min(minl[i + 1], arr[i]), maxl[i] = max(maxl[i + 1], arr[i]); for (int i = mid + 2; i <= r; i++) maxr[i] = max(maxr[i - 1], arr[i]), minr[i] = min(minr[i - 1], arr[i]); // make judges; // at the left: for (int i = mid; i >= l; i--) { int j = i + (maxl[i] - minl[i]); if (j > mid && j <= r && minr[j] > minl[i] && maxr[j] < maxl[i]) answer++; } // at the right; for (int i = mid + 1; i <= r; i++) { int j = i - (maxr[i] - minr[i]); if (j <= mid && j >= l && minl[j] > minr[i] && maxl[j] < maxr[i]) answer++; } // in the middle; // min|max: int ptr1 = mid + 1, ptr2 = mid; for (int i = mid; i >= l; i--) { while (minr[ptr2 + 1] > minl[i] && ptr2 < r) ptr2++, bucket[maxr[ptr2] - ptr2 + NUM_DOMAIN]++; while (maxl[i] > maxr[ptr1]) { bucket[maxr[ptr1] - ptr1 + NUM_DOMAIN]--, ptr1++; if (ptr1 > r) break; } if (ptr1 > r) break; if (ptr1 <= ptr2) answer += bucket[minl[i] - i + NUM_DOMAIN]; } for (int i = mid; i >= l; i--) bucket[minl[i] - i + NUM_DOMAIN] = 0; for (int i = mid + 1; i <= r; i++) bucket[maxr[i] - i + NUM_DOMAIN] = 0; // max|min: ptr1 = mid, ptr2 = mid + 1; for (int i = mid + 1; i <= r; i++) { while (minl[ptr2 - 1] > minr[i] && ptr2 > l) ptr2--, bucket[maxl[ptr2] + ptr2 + NUM_DOMAIN]++; while (maxr[i] > maxl[ptr1]) { bucket[maxl[ptr1] + ptr1 + NUM_DOMAIN]--, ptr1--; if (ptr1 < l) break; } if (ptr1 < l) break; if (ptr2 <= ptr1) answer += bucket[minr[i] + i + NUM_DOMAIN]; } for (int i = mid + 1; i <= r; i++) bucket[minr[i] + i + NUM_DOMAIN] = 0; for (int i = mid; i >= l; i--) bucket[maxl[i] + i + NUM_DOMAIN] = 0; dq(l, mid), dq(mid + 1, r); } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d%d", &prs[i].first, &prs[i].second); for (int i = 1; i <= n; i++) arr[prs[i].first] = prs[i].second; dq(1, n); printf("%lld", answer); return 0; }
这道题挺有趣的,归根结底就是位运算。首先,一个充分的结论就是枚举长度为\(1\)的区间的概率为\(\frac{1}{N^2}\),而长度大于1的概率为\(\frac{2}{N^2}\)。之后,枚举\(int\)的长度\(i \in [0,30]\),把所有数的第\(i\)位组成一个序列进行扫描,之后枚举到第\(j\)个数进行分类讨论。
// CH3801.cpp #include <bits/stdc++.h> using namespace std; const int MAX_N = 1e5 + 200; int n, arr[MAX_N]; double ans1, ans2, ans3; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &arr[i]); for (int k = 0; k < 30; k++) { int last[2], c1 = 0, c2 = 0; last[0] = last[1] = 0; for (int i = 1; i <= n; i++) if ((arr[i] >> k) & 1) { ans1 += (1 << k) * 1.0 / n / n; ans2 += (1 << k) * 1.0 / n / n; ans3 += (1 << k) * 1.0 / n / n; ans1 += (1 << k) * 2.0 / n / n * c1; ans2 += (1 << k) * 2.0 / n / n * (i - 1); ans3 += (1 << k) * 2.0 / n / n * (i - 1 - last[0]); last[1] = i; c1++, swap(c1, c2); } else { ans1 += (1 << k) * 2.0 / n / n * c2; ans2 += (1 << k) * 2.0 / n / n * (last[1]); last[0] = i, c1++; } } printf("%.3lf %.3lf %.3lf", ans1, ans3, ans2); return 0; }