【2017】 CSP - S 题解
T1
如果 $a,b$ 均是正整数且互质,那么由 $ax+by,x≥0,y≥0$ 不能凑出的最大数是 $ab−a−b$。
证明:$a, b$ 有一个为 $1$ 时,易知为 $0$,
$a$ 的线性表示(按题目要求),有$2a, 3a, 4a…$,
$b$ 的线性表示(按题目要求),有$2b, 3b, 4b…$,
它们可以组合,$a + b, a + 2b…2a + b,…$,由于 $gcd(a, b) == 1$,
所以它们的线性表示第一次重复在 $ab / gcd(a, b) == ab$,
由于 $a \equiv 1 (mod b)$ 且 $b \equiv 1 (mod a)$,
有 $2a mod b == 2 …$,在 $ab$ 之前余数出现 $1~b-1$ 这些数各一次。
当到了第二轮,$a(x-b) - yb$中,可以线性表示 $1~b-1$,且 $y < b$。
所以当大于$ab$时,可以构造$y$使得出现所有大于$ab$的数。
易得,可以构造出 $ab - a$ 和 $ab - b$,因为 $a!=1,b!=1$ 时,线性表示出这些余数,
可以有线性表示 $y <= a-1$ 另一个是 $x <= b-1$,恰好符合,所以大于的也都可以表示。
将增加改成减少就可以表示出 $ab - a - b + 1$ 及以上的所有数,
而 $ab - a - b$ 因为此时没有余数为 $0$ 的线性表示,哪个存在仅当 $y == a$ 或者也是 $x == b$,
所以它不能被表示,所以最大的不能被表示的整数是 $ab - a - b$。
#include<bits/stdc++.h>
using namespace std;
long long a,b;
int main(){
scanf("%lld%lld",&a,&b);
printf("%lld", a*b-a-b);
}
T3
怎么才能快速求出从某个点出发消耗一定冗余的最短路呢?
根据三角逆不等式,我们可以找到想到的起点和终点,找一条不在最短路径上的点去更新。
我们也可以通过这个思路由最短路推导冗余路,也就是在最短路的边上舒展。
发散思考结束,开始解题,本题的难点是对冗余 $K$ 的处理。
面对这一类状态空间过大的问题,最好的解决方式就是将其缩小。
所以 路径长 $<= d + K$ 可以转化成 $= {d, d + 1, d + 2, …, d + K}$
现在的问题就是如何处理 $= {d + c}$ 时满足要求的路径条数了。
这里会用记忆化搜索的方式解决。
1、解决顺序与方式
这里采用的方式是 逆推求满足性,
即先确定从起点到终点所用的冗余,再根据不同的出边转换,用反向 $Dijkstra$,快速求出出边会产生的冗余,
从而计算此后节点会产生的冗余。
注意此方法有 两个边界
【1】到达终点、没有冗余
【2】当前冗余已大于起点到终点的冗余、此后无论如何都不满足(可行性剪枝)
2、记忆化搜索 在状态相等时可以使用,如结点相同、冗余相同则方案数也相同
3. 标记数组判零环
因为 $0$ 环不会增加冗余,所以同一个冗余重复搜到了同一个结点,就代表有 $0$ 环。
但需要注意的是,即使没有 $0$ 环,也可能会有两条同冗余路径交到同一结点,这种情况怎么避免呢?
注意 $DFS$ 一条道走到黑的性质,如果在同一条链上重复搜到则是零环造成,反之则不是。
所以我们要在搜完了这条链之后解除标记。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 400010, S = 51;
typedef pair<int, int> PII;
int T;
int n, m, K, P;
int ans;
int h[N], f[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N][S];
bool st[N], vis[N][S], flag = false;
void init()
{
flag = false;
idx = 0, ans = 0;
memset(f, -1, sizeof f);
memset(h, -1, sizeof h);
memset(cnt, -1, sizeof cnt);
memset(st, false, sizeof st);
}
void add(int h[], int a, int b, int c)
{
w[idx] = c, e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra() // 反向 Dijkstra, 便于后面算冗余
{
priority_queue<PII, vector<PII>, greater<PII> > heap;
memset(dist, 0x3f, sizeof dist);
dist[n] = 0;
heap.push({0, n});
while (heap.size())
{
PII t = heap.top();
heap.pop();
int ver = t.second;
if (st[ver]) continue;
st[ver] = true;
for (int i = f[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
}
// 从 u 走到 n, 消耗了 s 个冗余单位的方案数
int dfs(int u, int s)
{
// 搜索的过程中,如果一个点两次进入我们的最短路,那么显然就是 0 环.
if (vis[u][s]) // 重复搜到了这个点且冗余未发生变化
{
flag = true; // 也就是出现了 0 环
return 0;
}
if (cnt[u][s] != -1) return cnt[u][s]; // 记忆化搜索,
vis[u][s] = true;
int &Cnt = cnt[u][s] = 0; // 方案数
for (int i = h[u]; i != -1; i = ne[i])
if (!flag) { // 没有发现零环的话
int v = e[i];
// min(n -> v) + u -> v - min(n -> u) = u -> v 的冗余
// u -> n 原冗余 - u -> v 的冗余 = v -> n 的冗余
int k = s - (dist[v] + w[i] - dist[u]);
if (0 <= k && k <= K) Cnt = (Cnt + dfs(v, k)) % P; // 计算方案数
}
if (flag) return 0;
vis[u][s] = false;
if (u == n && s == 0) Cnt = 1;
return Cnt;
}
int main()
{
scanf("%d", &T);
while (T -- )
{
init();
scanf("%d %d %d %d", &n, &m, &K, &P);
while (m -- )
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
add(h, a, b, c), add(f, b, a, c);
}
dijkstra();
for (int i = 0; i <= K; i ++ ) // 计算每一类冗余产生的方案数
if (!flag) // 没有 0 环
{
memset(vis, false, sizeof vis); // 初始化
ans = (ans + dfs(1, i)) % P; // 累计
}
if (flag) ans = -1; // 方案无数
printf("%d\n", ans);
}
return 0;
}
T5
将连接的层数作为阶段,一个阶段仅有上一个阶段转移,
#include <bits/stdc++.h>
using namespace std;
const int N = 15, M = 1 << 15, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int ne[M];
int f[M][N];
int get_cost(int cur, int pre)
{
if ((ne[pre] & cur) != cur) return -1; // 首先要满足可以拓展
int remain = pre ^ cur;
int cost = 0;
for (int i = 0; i < n; i ++ )
{
if (remain >> i & 1)
{
int t = INF;
for (int j = 0; j < n; j ++ )
if (pre >> j & 1)
t = min(t, g[j][i]);
cost += t;
}
}
return cost;
}
int main()
{
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
for (int i = 0; i <= n; i ++ ) g[i][i] = 0;
for (int i = 1; i <= m; i ++ )
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
u --, v --;
g[u][v] = g[v][u] = min(g[u][v], w);
}
for (int st = 1; st < 1 << n; st ++ ) // 处理合法转移
for (int i = 0; i < n; i ++ )
if (st >> i & 1)
{
for (int j = 0; j < n; j ++ )
if (g[i][j] != INF)
{
ne[st] |= 1 << j; // 维护有边相连的点
}
}
memset(f, 0x3f, sizeof f);
for (int i = 0; i < n; i ++ ) f[1 << i][0] = 0; // 起点
for (int i = 1, cost; i < 1 << n; i ++ )
for (int j = (i-1)&i; j; j = (j-1)&i)
if (~(cost = get_cost(i, j)))
{
for (int k = 1; k < n; k ++ )
{
f[i][k] = min(f[i][k], f[j][k-1] + cost * k);
}
}
int res = INF;
for (int k = 0; k < n; k ++ )
res = min(res, f[(1 << n) - 1][k]); // 目标状态找最优解
printf("%d", res);
}