2022/11/21-27 训练小记
CF1761 D. Carry Bit
赛时感觉很不可做，对着题解想明白的qwq
下文起用 \(a_i,b_i\) 表示其二进制表示下的第 \(i\) 位（1-indexed）。
人类智慧地想到记 \(c_i\) 表示第 \(i\) 位向第 \(i + 1\) 位进位的值（1-indexed，\(i \in [1,n]\)），且 \(c_0 = 0\)。
这样一来，由 \(c_i\) 其实是可以直接确定 \((a_i,b_i)\) 的。具体来讲可以分以下四类：
-
\(c_i = 0, c_{i - 1} = 0\)，则 \((a_i,b_i) = (0,0),(0,1),(1,0)\)
-
\(c_i = 0, c_{i - 1} = 1\)，则 \((a_i,b_i) = (0,0)\)
-
\(c_i = 1, c_{i - 1} = 0\)，则 \((a_i,b_i) = (1,1)\)
-
\(c_i = 1, c_{i - 1} = 1\)，则 \((a_i,b_i) = (0,1),(1,0),(1,1)\)
因此当 \(c_i = c_{i - 1}\) 时，\((a_i,b_i)\) 有 \(3\) 种可能；当 \(c_i \neq c_{i - 1}\) 时，\((a_i,b_i)\) 只有 \(1\) 种可能。
枚举一个 \(q\) 表示 \(c\) 中满足 \(c_i \neq c_{i - 1}(i \in [1,n])\) 的 \(i\) 的总数，则对于这样的 \(c\)，我们有 \(3^{n - q}\) 种 \((a,b)\)。
下面的问题是，如何计算满足 \(c_i \neq c_{i - 1}\) 的总数为 \(q\)，且最终 \(f(a,b) = k\) 的 \(c\) 的方案数。
首先考虑 \(q\) 的限制带来了什么。观察到 \(c\) 一定是由若干个 \(1\) 与若干个 \(0\) 交替组成的（e.g. \(c = \{0, 1, 1, 0, 1, 1, 0, 0\}\)）。而每一段极长的 \(0\) 与极长的 \(1\) 的交汇处都会有一处 \(c_i \neq c_{i - 1}\)，不难得到 \(c\) 中会有 \(\lceil {\frac{q + 1}{2}}\rceil\) 段极长的 \(0\) 与 \(\lfloor {\frac{q + 1}{2}}\rfloor\) 段极长的 \(1\)。（将 \(c_0\) 一并考虑）
至于 \(k\) 的限制，经过推导得到当 \(c\) 中恰好有 \(k\) 个 \(1\) 与 \(n - k + 1\) 个 \(0\)（将 \(c_0\) 一并考虑）时满足 \(k\) 的限制。
这样一来就成了一个典型的组合数学问题了。
我们考虑将 \(k\) 个 \(1\) 划分为 \(\lfloor {\frac{q + 1}{2}}\rfloor\) 段，将 \(n - k + 1\) 个 \(0\) 划分为 \(\lceil {\frac{q + 1}{2}}\rceil\) 段，两者交替排列，其方案数之积即为此时合法的 \(c\) 的数量。故最终有：
\[Ans = \sum \limits_{q = 0} ^ {n} {3 ^ {n - q} \cdot \binom{k - 1}{\lfloor {\frac{q + 1}{2}}\rfloor - 1} \cdot \binom{n - k}{\lceil {\frac{q + 1}{2}}\rceil - 1}} \]\(\texttt{Main Code}\)
i64 pp[N], fac[N];
void sieve(){
pp[0] = 1LL; for(int i = 1; i < N; ++i) pp[i] = pp[i - 1] * 3 % mod;
fac[0] = 1LL; for(int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % mod;
}
inline i64 ksm(i64 a, i64 b, i64 p){
i64 ret = 1;
while(b){
if(b & 1) ret = ret * a % p;
b >>= 1; a = a * a % mod;
}
return ret;
}
inline i64 inv(int x){return ksm(x, mod - 2, mod);}
inline i64 binom(int x, int y){
if(y > x) return 0;
if(y == -1) return (x == -1);
return inv(fac[y]) * inv(fac[x - y]) % mod * fac[x] % mod;
}
void solve(){
int n, k; cin >> n >> k;
i64 ans = 0;
for(int q = 0; q <= n; ++q){
ans += pp[n - q] * binom(k - 1, (q + 1) / 2 - 1) % mod * binom(n - k, q / 2);
ans %= mod;
}
cout << ans << '\n';
}
T291501 祝大家
憨憨题直接计算，显然是 \(\mathcal{O}(\log n)\) 量级的。
i64 n, k;
inline i64 calc(i64 x){
if(x <= k) return 1;
return ((x + 1) / 2 + k - 1) / k;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> k;
i64 cur = n, c = 1, ans = 0;
while(cur > 0){
ans += c * calc(cur);
cur -= ((cur + 1) / 2 + k - 1) / k * k;
c <<= 1;
}
cout << ans;
}
P5651 基础最短路练习题
保证 \(G\) 中不存在简单环使得边权异或和不为 \(0\)
考虑两点间不同的最短路要么部分重合，要么部分成环，重合时异或和自然为 \(0\)，不重合时由于上述限制异或和也为 \(0\)。推广一下这个结论就知道，本题中两点间最短路的异或和一定相等，即所有路径等价。所以求一棵生成树，然后 \(\mathcal{O}(n)-\mathcal{O}(1)\) 处理即可。
P1144 最短路计数
有很多最短路性质问题都会考虑对松弛操作做处理，本题是一个很典的例子。在松弛操作中加入如下代码即可：
if(dis[u] + 1 < dis[e[i].v]){
dis[e[i].v] = dis[u] + 1;
ans[e[i].v] = ans[u];
pq.push((node){dis[e[i].v], e[i].v});
}else if(dis[u] + 1 == dis[e[i].v]){
ans[e[i].v] += ans[u]; if(ans[e[i].v] >= mod) ans[e[i].v] -= mod;
pq.push((node){dis[e[i].v], e[i].v});
}
P2149 [SDOI2009] Elaxia的路线
图论好题（虽然只有蓝），值得细研究。
\(\texttt{Description}\)
给定带权无向图和两对点 \((x_1,y_1),(x_2,y_2)\)，求两对点间最短路的最长公共距离。
（即对于所有的 \(x_1 \to y_1\) 的最短路的边集与 \(x_2 \to y_2\) 的最短路的边集的交集，求这个交集的最大边权和）。
解 1
符号约定：记 \(dis_{u,v}\) 表示无向图上 \(u \to v\) 的最短路径长，\(w_{(u,v)}\) 表示边 \((u,v)\) 的边权，最短路集指所有最短路中被包括的有向边组成的有向边集。
引理 1 一条有向边 \((u,v)\) 位于 \(x \to y\) 的某条最短路上的充分必要条件是 \(dis_{x,u} + w_{(u,v)} + dis_{v,y} = dis_{x,y}\)。
证明 利用最短路的子路径也是最短路这一性质，考虑若 \((u,v)\) 位于 \(x \to y\) 的任一最短路上，则 \(x \to u, v \to y\) 的部分同样是最短路；反过来，取 \(x \to u, v \to y\) 的最短路径长 \(dis_{x,u},dis_{v,y}\)，若 \(dis_{x,u} + w_{(u,v)} + dis_{v,y} = dis_{x,y}\)，则有向边 \((u,v)\) 一定在一条 \(x \to u \to v \to y\) 的最短路上。
引理 2 对于无向图上任意一条无向边 \((u,v)\)，其所对应的两条有向边至多有 \(1\) 条属于 \(x \to y\) 的最短路集。
证明 考虑依据边权大小建立模型：其中 \(1,4\) 点为路径起止端点，\(a,b\) 为非负整数，边 \((2,3)\) 的边权为 \(z(z \geq 1)\)，\(1 \to 2, 1 \to 3, 2 \to 4, 3 \to 4\) 的最短路径长均被标注在图中。
对于这种情况，有 \(2\) 条可能的经过边 \((2,3)\) 或 \((3,2)\) 的路径：
- \(1 \to 3 \to 2 \to 4\)，即绿色路径，记该路径为①
- \(1 \to 2 \to 3 \to 4\)，即黄色路径，记该路径为②
那么，有向边 \((2,3)\) 与 \((3,2)\) 同时存在于 \(1 \to 4\) 的最短路集中的充分必要条件是 \(2x + a + z = 2y + b + z \leq x + y\)。
解得 \(x \leq y - a - z, y \leq x - b - z\)。另一方面，由于 \(a,b \geq 0, z \geq 1\)，所以 \(x,y\) 是恒无解的，所以这个关系式恒不成立，即有向边 \((2,3)\) 与 \((3,2)\) 不可能同时存在于 \(1 \to 4\) 的最短路集中。
与上述讨论类似，最终仍可通过无解反证。证毕。
又由于图的边权均正整数，故最终形成的最短路集不可能出现环，因此，最短路集一定是一个DAG
引理 3 最长公共部分一定是一条链。
证明 由于最短路的子路径也是最短路，所以一段公共部分上成环的部分一定可以转化为一条长度相等的链。证毕。
综上所述，我们可以求出 \(x_1 \to y_1, x_2 \to y_2\) 对应的 DAG，对这两个 DAG 求最长链即可。这个过程可以对 DAG 进行一次拓扑实现，状态转移显然，$Ans_v = max{Ans_u + w_{(u,v)}} $。
大体思路是这样，但还有不少细节需要注意：（记 \(x_1 \to y_1, x_2 \to y_2\) 对应的 DAG 分别为 \(D_1, D_2\)）
-
建立新图时，需要遍历每一条有向边 \((u,v)\)，若 \((u,v)\) 存在于 \(D_1\) 中，则考虑 \((u,v)\) 或 \((v,u)\) 是否存在于 \(D_2\) 中，若存在则向一个新图中加入有向边 \((u,v)\)。（由引理 2 可知这样建图 \((u,v)\) 和 \((v,u)\) 至多一者会加入新图）
-
按照上述规则建图，则对新图进行拓扑时 \(Ans_{y_2}\) 的值不能转移到别的 \(Ans_v\) 上去，即状态转移严谨来讲是这样的：
原因在于，由于我们建立的新图中路径的方向与 \(D_1\) 一致，所以新图中可能存在一条穿过 \(y_2\) 的链。但是最短路到 \(y_2\) 就为止了，不可能再增广到链的异侧。为了避免这个情况，因此有 \(Ans_{y_2}\) 不能加到别的 \(Ans_v\) 上去。
给出一份可以解释为什么不能直接转移的样例，其中 \(2 \to 8, 8 \to 4, 4 \to 5\) 均为新图中存在的边，\(y_2 = 8\)。
至此这道题就做完了。给出完整代码：
\(\texttt{Main Code 1}\)
#include <bits/stdc++.h>
using namespace std;
const int N = 1500 + 5, M = 3e5 + 5;
struct edge{
int v, nxt, w;
}e1[M << 1], e2[M << 1];
int head1[N], tot1, head2[N], tot2, deg[N];
inline void add1(int u, int v, int w){
e1[++tot1].nxt = head1[u];
head1[u] = tot1;
e1[tot1].v = v;
e1[tot1].w = w;
}
inline void add2(int u, int v, int w){
e2[++tot2].nxt = head2[u];
head2[u] = tot2;
e2[tot2].v = v;
e2[tot2].w = w;
++deg[v];
}
struct node{
int val, u;
bool operator < (const node &x) const {return val > x.val;}
};
priority_queue<node> pq;
bool vis[N];
int dis[4][N];
void dijkstra(int id, int s){
memset(dis[id], 0x3f, sizeof(dis[id]));
memset(vis, 0, sizeof(vis));
dis[id][s] = 0;
pq.push((node){0, s});
while(!pq.empty()){
int u = pq.top().u; pq.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i = head1[u]; i; i = e1[i].nxt){
if(dis[id][u] + e1[i].w < dis[id][e1[i].v]){
dis[id][e1[i].v] = dis[id][u] + e1[i].w;
pq.push((node){dis[id][e1[i].v], e1[i].v});
}
}
}
}
int ans[N];
int x_1, y_1, x_2, y_2;
queue<int> S;
void topo(int n){
for(int i = 1; i <= n; ++i) if(!deg[i]) S.push(i);
while(!S.empty()){
int u = S.front(); S.pop();
for(int i = head2[u]; i; i = e2[i].nxt){
ans[e2[i].v] = max(ans[e2[i].v], ((u == y_2)? 0 : ans[u]) + e2[i].w);
if(--deg[e2[i].v] == 0) S.push(e2[i].v);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n, m; cin >> n >> m;
cin >> x_1 >> y_1 >> x_2 >> y_2;
int u, v, w;
for(int i = 1; i <= m; ++i){
cin >> u >> v >> w;
add1(u, v, w); add1(v, u, w);
}
dijkstra(0, x_1); dijkstra(1, y_1); dijkstra(2, x_2); dijkstra(3, y_2);
for(int i = 1; i <= n; ++i){
for(int j = head1[i]; j; j = e1[j].nxt){
if(dis[0][i] + e1[j].w + dis[1][e1[j].v] == dis[0][y_1]){
if(dis[2][i] + e1[j].w + dis[3][e1[j].v] == dis[2][y_2] ||
dis[3][i] + e1[j].w + dis[2][e1[j].v] == dis[2][y_2])
add2(i, e1[j].v, e1[j].w);
}
}
}
topo(n);
cout << *max_element(ans + 1, ans + n + 1);
}
解 2
参考 @djq 与 @caeious 的思路
建新图时其实还有一种方法：分类讨论地求一下只保留在两 DAG 中同向出现的边时的最长链，和只保留在两 DAG 中反向出现的边时的最长链。这样一来 dp 过程中就不必对 \(Ans_{y_2}\) 进行特殊转移了。非常巧妙。
解 3
推广一下解 1 中的引理 2，可以得出推论：最短路算法最终形成的最短路集必然是一个 DAG。
因此，建图时除了运用解 1 中的引理 1，还有一种办法是在 \(dijkstra\) 的松弛操作中记录前驱。即向松弛部分加入如下片段：
if (dis[e.to] >= e.w + dis[now.to]){
if (dis[e.to] > e.w + dis[now.to]){
pre[e.to].clear();
dis[e.to] = e.w + dis[now.to];
que.push({e.to, dis[e.to]});
}
pre[e.to].push_back({now.to, e.w});
}
这样一来就可以得到 \(dijkstra\) 后形成的 DAG 了。但是这个 DAG 并不是我们最终想要的最短路集，因此考虑将所有的边反向后对该图进行一次 dfs，标记所有遍历到的边，这样便得到了最短路集。
标签：27,21,int,短路,Ans,i64,ans,2022.11,dis From： https://www.cnblogs.com/chroneZ/p/16926073.html