U
p
d
Upd
Upd：
2022.11.28
2022.11.28
2022.11.28 完成
八中OJ链接
我们还是先观察数据范围：
1
≤
n
,
m
≤
500
1 \leq n,m \leq 500
1≤n,m≤500,那么就只能用广度优先搜索了。
个人认为这道题出得不好，因为按照目前的最优解，时间复杂度应该为
O
(
n
2
m
2
)
O(n^2m^2)
O(n2m2) 的，应该是过不掉的，但为什么在
150
m
s
150ms
150ms 内就过掉了呢？原因有二：一是数据太水，仅有一组极限数据并且 ‘#’ 符号少得可怜。二是如果每一次
b
f
s
bfs
bfs 不用
O
(
n
m
)
O(nm)
O(nm) 的时间初始化，其实真正的时间复杂度是远远小于
O
(
n
2
m
2
)
O(n^2m^2)
O(n2m2) 的。
我们先来想一想最暴力的做法，枚举两个城市，再用
O
(
n
m
)
O(nm)
O(nm) 求其最短距离，这样做是
O
(
n
3
m
3
)
O(n^3m^3)
O(n3m3) 的，绝对会原地起飞。
现在，来说说这道题的正确做法——染色法，即将每个城市用
d
f
s
dfs
dfs 染色后去求解。如果每个城市只有一个 #，那么，这个问题就是一个很裸的
B
F
S
BFS
BFS 问题。但是，现在的问题就是，要如何
做，才能够求得一片城市与另一片城市的最短距离？其实，每一次
b
f
s
bfs
bfs 最坏会遍历整个地图，并且我们只是求其最小距离，所以，我们可以将某一个城市内的所有 # 全都作为我们搜索的起点，然后计算从这些起点当中，走到另一个 # 的最短距离是多少（
B
F
S
BFS
BFS），因为我们只需要找到最小距离，并不需要知道究竟是哪个城市到了另外哪个城市，因此，我们在跑
B
F
S
BFS
BFS 之前，找到当前我们找的这个城市有哪些 #，将同一个城市内的所有#都
p
u
s
h
push
push 进我们的队列当中，然后，再跑一个
B
F
S
BFS
BFS，找到这个城市能走到的离它最近的城市的距离，最后取最小的那个答案即可。
A
C
AC
AC
C
o
d
e
:
Code:
Code:
#includeusing namespace std;
const int N = 5e2 + 5, INF = 0x3f3f3f3f;
const int zx[4] = {-1, 0, 1, 0}, zy[4] = {0, 1, 0, -1};
int n, m, ans = INF;
char c[N][N];
bool vis[N][N];
struct node {int x, y, step;
};
queueq;
bool in(int x, int y) {return x >= 1 && x<= n && y >= 1 && y<= m;
}
void dfs(int x, int y) {c[x][y] = 'A';
q.push((node){x, y, 0});
for(int i = 0;i< 4;i++) {int dx = x + zx[i], dy = y + zy[i];
if(in(dx, dy) && c[dx][dy] == '#') dfs(dx, dy);
}
}
void bfs() {for (int i = 1;i<= n;i++)
for (int j = 1;j<= m;j++)
vis[i][j] = 0;
while(!q.empty()) {node p = q.front();
q.pop();
if(c[p.x][p.y] == '#') { while(!q.empty()) q.pop();
ans = min(ans, p.step);
return ;
}
for(int i = 0;i< 4; ++i) { int dx = p.x + zx[i], dy = p.y + zy[i];
if(in(dx, dy) && !vis[dx][dy] && c[dx][dy] != 'A') { vis[dx][dy] = 1;
q.push((node){dx, dy, p.step + 1});
}
}
}
}
int main() {scanf("%d%d", &n, &m);
for(int i = 1;i<= n;i++) scanf("%s", c[i] + 1);
for(int i = 1;i<= n;i++)
for(int j = 1;j<= m;j++)
if(c[i][j] == '#') { dfs(i, j);
bfs();
}
printf("%d", ans);
return 0;
}
U
p
d
Upd
Upd：
2022.11.26
2022.11.26
2022.11.26 完成
洛谷链接 八中OJ链接
看到数据范围
1
0
10
≤
L
≤
R
≤
1
0
11
10^{10} \leq L \leq R \leq 10^{11}
1010≤L≤R≤1011 并且是统计
[
L
,
R
]
[L,R]
[L,R] 内有满足条件的号码数量，很容易想到数位
D
P
DP
DP。
其实，数位
D
P
DP
DP 也是一个很模板化的东西。对其总结如下：
dfs(数的最后若干位,各种限制条件,当前第几位)
if 最后一位
return 各种限制条件下的返回值
局部变量 ct = 当前位的数字
局部变量 sum = 0;
for i = 0 to ct - 1
sum += 当前位取i时一定无无限制的合法状态数
sum += 当前位取i时满足当前限制的合法状态数
根据ct更新限制条件 不再满足则 return sum
return sum + dfs(当前位后的若干位,更新后的限制条件,下一位)
slv(当前数)
if (只有一位) return 对应的贡献
局部变量 ct;
for ct = 可能最高位 to 1
if 当前位有数字 break
局部变量 nw = 当前位数字
局部变量 sum = 0
for i = 1 to nw - 1
sum += 当前位取i后合法情况任意取的贡献
for i = 1 to ct-1
for j = 1 to 9
sum += 第i位取j后合法情况任意取的贡献
sum += dfs(去掉第一位后的若干位,限制条件,第二位)
return sum
main
预处理当前位取i的各种条件各种限制的贡献
读入 L R
--L
输出 slv(R)-slv(L)
return 0而在这道题中，我们就可以很容易的套模板，定义六维的
D
P
DP
DP 去记忆化
d
f
s
dfs
dfs,即
d
p
[
第
i
位
]
[
填
j
]
[
目
前
连
续
L
]
[
是
否
有
4
]
[
是
否
有
8
]
[
是
否
有
至
少
3
位
连
续
数
字
]
dp[第i位][填j][目前连续L][是否有4][是否有8][是否有至少3位连续数字]
dp[第i位][填j][目前连续L][是否有4][是否有8][是否有至少3位连续数字]。
然后按照板子按部就班的做便能
A
C
AC
AC.
A
C
AC
AC
C
o
d
e
Code
Code:
#includeusing namespace std;
#define int long long
const int N = 20;
int x, y, num[N], dp[N][N][N][2][2][2];
int dfs(int pos, int pre1, int pre2, bool limit, bool zero, bool e, bool f, bool ok) {if (e && f) return 0;
if (!pos) return ok;
if (!limit && !zero && dp[pos][pre1][pre2][e][f][ok]) return dp[pos][pre1][pre2][e][f][ok];
int mxd = limit ? num[pos] : 9;
int ans = 0;
for (int i = 0; i<= mxd;i++)
ans += dfs(pos - 1, (zero && !i) ? -1 : i, zero ? -1 : pre1, limit && i == mxd, zero && !i, e || i == 8, f || i == 4, ok || ((!zero && i == pre1 && i == pre2)));
if (!limit && !zero) dp[pos][pre1][pre2][e][f][ok] = ans;
return ans;
}
int solve(int x) {int len = 0;
while (x) num[++len] = x % 10, x /= 10;
return dfs(len, -1, -1, 1, 1, 0, 0, 0);
}
signed main() {scanf("%lld%lld", &x, &y);
printf("%lld", solve(y) - solve(x - 1));
return 0;
}
U
p
d
Upd
Upd：
2022.11.26
2022.11.26
2022.11.26 完成
洛谷链接
解题思路：由数据范围
1
≤
x
≤
1
0
9
1 \leq x \leq 10^9
1≤x≤109 可得，这是一道思维题。
思维题，其实无非分为以下四种：拼凑、归纳、分类、数论。
而这一题，题中没有复杂的数学公式，便可以从拼凑角度出发。
随便列举出一些数字：
122
=
111
∗
1
+
11
∗
1
122 = 111 * 1 + 11 * 1
122=111∗1+11∗1,
233
−
111
∗
2
+
11
∗
1
233 - 111 * 2 + 11 * 1
233−111∗2+11∗1
发现，似乎三位数可以由
11
11
11 和
111
111
111 拼凑，那么更高位数字呢？。
我们又可以发现：
11
−
>
11
11 ->11
11−>11
111
−
>
111
111 ->111
111−>111
1111
−
>
11
×
100
+
11
1111 ->11 \times 100 + 11
1111−>11×100+11
11111
−
>
11
×
1000
+
111
11111 ->11 \times 1000 + 111
11111−>11×1000+111
111111
−
>
1111
×
10
+
11
−
>
11
×
1000
+
1111
111111 ->1111 \times 10 + 11 ->11 \times 1000 + 1111
111111−>1111×10+11−>11×1000+1111
又因为
111
=
11
×
10
+
1
111 = 11 \times 10 + 1
111=11×10+1
所以
11
x
+
111
y
=
11
（
x
+
10
y
）
+
1
11x + 111y = 11（x + 10y）+1
11x+111y=11（x+10y）+1
此时，我们就可以求解出
x
、
y
x、y
x、y 的值。
我们还可以发现这些数的一个美好特征：永远可以将一个非常大的数字消到三位数以下，也就说我们可以分段打表（有人
A
C
AC
AC 过）求出
x
%
11
×
111
x \% 11 \times 111
x%11×111 后判断是否小于
x
x
x 即可。
A
C
AC
AC
C
o
d
e
Code
Code:
#includeusing namespace std;
#define int long long
int T, x;
signed main() {scanf("%lld", &T);
while(T--) {scanf("%lld", &x);
if (x % 11 * 111<= x) puts("YES");
else puts("NO");
}
return 0;
}
//num = 11 * x + 111 * y
//num = 11 * (x + 10 * y) + y
U
p
d
Upd
Upd：
2022.11.26
2022.11.26
2022.11.26 完成
八中OJ链接 洛谷链接
可以观察数据范围
1
≤
a
i
≤
20
1 \leq a_i \leq 20
1≤ai≤20,可以用状压
D
P
DP
DP 求解。
细看题目，便发现有这样一个性质：如果交换相邻的两数，其他所有数字的相对位置是不变的。（其实，也可以根据逆序对的一个引理得出：将一个序列排序最少交换相邻元素的次数等于该序列的逆序对数。）
推论：在交换的时候我们就可以分开考虑每一种数字。
例如:
1
1
1
1
1
1
3
3
3
2
2
2
4
4
4 中,我们发现交换下标为
1
1
1 和
2
2
2 的数字，其实序列并没有改变，而颜色只有
20
20
20 种,也就是相邻的同种颜色不考虑交换。
于是，我们可以来状压颜色的种类。
D
P
DP
DP 的定义如下：定义
d
p
i
dp_i
dpi 表示表示已选的数的状态集合（注意，每选择一个数，意味着给其赋一个比之前选的数都大，比之后选的数都小的权值），集合中的数权值逆序对的最小值。
理解一下：若有一个序列
1
1
1
2
2
2
1
1
1
3
3
3,
d
p
[
3
]
=
d
p
[
(
011
)
2
]
dp[3] = dp[(011)_2]
dp[3]=dp[(011)2] (已经选择了
1
1
1 和
2
2
2 两种数)
=
1
=1
=1.为什么呢？因为既然是求权值逆序对，即我们可以将它同种类数字赋上同一个值，求其值逆序对的最小值。在这里，我们将
1
1
1 赋值为
1
1
1,
2
2
2 赋值为
2
2
2,便会有一个逆序对，就是最小值。
接着，我们来考虑一下转移方程吧。
d
p
i
dp_i
dpi 应该怎么转移呢？
当我们在更新状态
i
i
i 时，
i
i
i 以前
d
p
dp
dp 值应该是有的，那么，我们可以枚举颜色的种类，假设没有这个种类的数字的
d
p
dp
dp 值加上
v
a
l
val
val (
v
a
l
val
val 就是逆序对个数)，即
d
p
i
=
m
i
n
(
d
p
i
,
d
p
j
+
v
a
l
)
dp_i = min(dp_i,dp_j+val)
dpi=min(dpi,dpj+val)
而这个
v
a
l
val
val 的值需要用两重循环去枚举，会
T
T
T！怎么办？可以用一个数组预处理。用
c
x
y
c_{xy}
cxy 表示数列中满足
i
＜
j
i ＜ j
i＜j 且
a
i
=
x
a_i = x
ai=x,
a
j
=
y
a_j = y
aj=y 的
(
i
,
j
)
(i,j)
(i,j) 对数。
这样，这道状压
D
P
DP
DP 的题目就可以被解决了，最坏时间复杂度为
O
（
4
∗
1
0
5
×
20
+
2
20
×
2
0
2
）
O（4*10^5 \times 20 + 2^{20} \times 20^2）
O（4∗105×20+220×202） 运算次数约为
4
∗
1
0
7
4*10^7
4∗107,时限
4
s
e
c
4 sec
4sec，可以通过。
但是，注意一点，初始化
D
P
DP
DP 时候，不能只初始化到
1
<
<
m
a
x
n
1<< maxn
1<
#includeusing namespace std;
#define int long long
const int N = 4e5 + 5, M = 25, INF = 0x3f3f3f3f;
int n, maxx, maxn, a[N], cnt[M], c[M][M], dp[(1<< 20) + 5];
signed main() {scanf("%lld", &n);
for (int i = 1;i<= n;i++) scanf("%lld", &a[i]), a[i]--;
maxx = *max_element(a + 1, a + n + 1) + 1, maxn = (1<< maxx) - 1;
for (int i = 1;i<= n;i++) {cnt[a[i]]++;
for (int j = 0;j<= maxx;j++) c[j][a[i]] += cnt[j];
}
for (int i = 1;i<= maxn;i++) dp[i] = INF;
for (int i = 1;i<= maxn;i++)
for (int j = 0;j< maxx;j++)
if (i & (1<< j)) { int val = 0, pre = i - (1<< j);
for (int k = 0;k< maxx;k++) if (pre & (1<< k)) val += c[j][k];
dp[i] = min(dp[i], dp[pre] + val);
}
printf("%lld", dp[maxn]);
return 0;
} A C AC AC C o d e Code Code
#includeusing namespace std;
#define int long long
const int N = 4e5 + 5, M = 25, INF = 0x3f3f3f3f;
int n, maxx, maxn, a[N], cnt[M], c[M][M], dp[(1<< 20) + 5];
signed main() {scanf("%lld", &n);
for (int i = 1;i<= n;i++) scanf("%lld", &a[i]), a[i]--;
maxx = *max_element(a + 1, a + n + 1) + 1, maxn = (1<< maxx) - 1;
for (int i = 1;i<= n;i++) {cnt[a[i]]++;
for (int j = 0;j<= maxx;j++) c[j][a[i]] += cnt[j];
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int i = 1;i<= maxn;i++)
for (int j = 0;j< maxx;j++)
if (i & (1<< j)) { int val = 0, pre = min(i - (1<< j), maxn + 1);
for (int k = 0;k< maxx;k++) if (pre & (1<< k)) val += c[j][k];
dp[i] = min(dp[i], dp[pre] + val);
}
printf("%lld", dp[maxn]);
return 0;
}
U
p
d
Upd
Upd：
2022.11.26
2022.11.26
2022.11.26 完成
八中OJ链接 洛谷链接
首先，我们要知道
1
−
n
1-n
1−n 的最短路的距离是多少。于是我们可以跑一遍
d
i
j
k
s
t
r
a
dijkstra
dijkstra 来
O
(
n
l
o
g
n
)
O(n log n)
O(nlogn) 求最短距离。
然后我们可以发现
0
≤
k
≤
50
0 \leq k \leq 50
0≤k≤50 ，于是我们可以在
k
k
k 上面做一个
D
P
DP
DP。
不难定义出
d
p
u
d
dp_{ud}
dpud 表示路程为区间
[
d
i
s
u
,
d
i
s
u
+
d
]
[dis_u, dis_u+d]
[disu,disu+d] 以内的方案数（
d
i
s
u
dis_u
disu 表示到
u
u
u 的最短路)
于是我们可以在每种询问时暴力枚举
k
k
k ，每次用
d
f
s
dfs
dfs 记忆化的方式来计算
d
p
n
i
dp_{ni}
dpni 的值，答案即为
d
p
n
i
dp_{ni}
dpni 之和。
那么
d
f
s
dfs
dfs 应该怎么写呢？
对于每一个
d
f
s
dfs
dfs ，我们可以枚举起点（可以反向建图，将终点作为起点）能到达的点，我们就可以由
d
f
s
(
u
,
l
)
dfs(u,l)
dfs(u,l) 转到
d
f
s
(
v
,
d
i
s
[
u
]
+
l
−
d
i
s
[
v
]
−
e
d
g
e
2
[
i
]
.
l
e
n
)
dfs(v,dis[u]+l-dis[v]-edge2[i].len)
dfs(v,dis[u]+l−dis[v]−edge2[i].len)了。
边界便为当
i
≤
−
1
i \leq -1
i≤−1 或
i
≠
k
+
1
i \neq k + 1
i=k+1时，返回
0
0
0;
但是，数据中有明显的指示，有
0
0
0 边！所以我们可以用一个
f
l
a
g
flag
flag 数组来标记。
最后，我们可以将这个
d
f
s
dfs
dfs 记忆化，每个点和边在一个
d
f
s
dfs
dfs 最多只会遍历一次，所以时间复杂度为
O
(
n
O(n
O(n
l
o
g
(
n
+
m
)
+
k
(
n
+
m
)
)
log(n+m)+k(n+m))
log(n+m)+k(n+m))。
A
C
AC
AC
C
o
d
e
1
Code1
Code1:
#includeusing namespace std;
const int N = 2e5 + 1, M = 51;
struct node{int val, dis;
friend bool operator< (node x, node y) {return x.dis >y.dis;}
};
priority_queueq;
struct Edge{int to, next, len;
}edge[N<< 1], edge2[N<< 1];
int T, n, m, K, P, num, num2, head[N], head2[N], dis[N], vis[N], flag[N][M], dp[N][M];
void add(int x, int y, int z) {edge[++num] = (Edge){y, head[x], z}, head[x] = num; }
void adds(int x, int y, int z) {edge2[++num2] = (Edge){y, head2[x], z}, head2[x] = num2; }
void Dijkstra() {for (int i = 1; i<= n; ++i) vis[i] = 0, dis[i] = 1e9; dis[1] = 0;
q.push((node){1, 0});
while (!q.empty()){node tmp = q.top(); q.pop();
int u = tmp.val, l = tmp.dis;
if (vis[u]) continue;
vis[u] = 1;
for (int i = head[u]; i; i = edge[i].next){ int v = edge[i].to;
if (dis[v] >dis[u] + edge[i].len){ dis[v] = dis[u] + edge[i].len;
if (!vis[v]) q.push((node){v, dis[v]});
}
}
}
}
int dfs(int u, int l) {if (l< 0 || l >K) return 0;
if (flag[u][l]) return -1;
if (dp[u][l] != -1) return dp[u][l];
flag[u][l] = 1;
int sum = 0;
for (int i = head2[u]; i; i = edge2[i].next){int v = edge2[i].to;
int tmp = dfs(v, dis[u] + l - dis[v] - edge2[i].len);
if (tmp == -1) return -1;
(sum += tmp) %= P;
}
if (u == 1 && !l) ++sum;
dp[u][l] = sum, flag[u][l] = 0;
return sum;
}
int main() {scanf("%d", &T);
while (T--) {num = num2 = 0;
memset(head, 0, sizeof(head));
memset(head2, 0, sizeof(head2));
scanf("%d%d%d%d", &n, &m, &K, &P);
for (int i = 1, x, y, z;i<= m;i++) { scanf("%d%d%d", &x, &y, &z);
add(x, y, z), adds(y, x, z);
}
Dijkstra();
memset(dp, 255, sizeof(dp));
memset(flag, 0, sizeof(flag));
int ans = 0, flag = 0;
for (int i = 0; i<= K;i++) { int tmp = dfs(n, i);
if (tmp == -1){flag = 1; break;}
ans = (ans + tmp) % P;
}
if (!flag) printf("%d\n", ans);
else puts("-1");
}
return 0;
} 下面便是用
T
o
p
S
o
r
t
TopSort
TopSort 的做法，复杂度相同(别人的)（其实是
d
f
s
dfs
dfs 的作用）。
另外，
S
t
r
u
c
t
Struct
Struct 的封装也很好。
A
C
AC
AC
C
o
d
e
2
Code2
Code2:
#includeconst int N = 1e5 + 10, M = 2e5 + 10, Nt = 131072, inf = 0x3f3f3f3f;
int ri() {char c = getchar(); int x = 0, f = 1; for(;c< '0' || c >'9'; c = getchar()) if(c == '-') f = -1;
for(;c >= '0' && c<= '9'; c = getchar()) x = (x<< 1) + (x<< 3) - '0' + c; return x * f;
}
int n, q[N], d[N], rk[N], f[N], g[N], *D, id[N], T[Nt<< 1], dp[51][N], K, P;
struct Edge {int nx[M], pr[N], to[M], w[M], tp;
void add(int u, int v, int W) {to[++tp] = v; nx[tp] = pr[u]; pr[u] = tp; w[tp] = W;}
void adds(int u, int v, int w) {add(u, v, w); add(v, u, w);}
void Pre() {for(int i = 1;i<= n; ++i) pr[i] = 0; tp = 0;}
}G, R;
int min(int a, int b) {return D[a]< D[b] ? a : b;}
bool cmp(int a, int b) {return f[a] == f[b] ? rk[a]< rk[b] : f[a]< f[b];}
void Up(int i, int v) {for(T[i += Nt] = v;i >>= 1;) T[i] = min(T[i<< 1], T[i<< 1 | 1]);}
void Dij(const Edge &G, int st) {for(int i = 0;i<= n; ++i) D[i] = inf;
D[st] = 0; Up(st, st);
for(;D[T[1]] != inf;) {int u = T[1]; Up(u, 0);
for(int i = G.pr[u], v, w; i; i = G.nx[i])
if(D[v = G.to[i]] >(w = D[u] + G.w[i]))
D[v] = w, Up(v, v);
}
}
bool Topsort() {int L = 1, R = 0;
for(int i = 1;i<= n; ++i)
if(!d[i])
q[++R] = i;
for(int u = q[L];L<= R; u = q[++L])
for(int i = G.pr[u]; i; i = G.nx[i])
if(!G.w[i] && !--d[G.to[i]])
q[++R] = G.to[i];
for(int i = 1;i<= R; ++i)
rk[q[i]] = i;
for(int i = 1;i<= n; ++i)
if(d[i] && f[i] + g[i]<= f[n] + K)
return false;
for(int i = 1;i<= n; ++i)
id[i] = i;
std::sort(id + 1, id + n + 1, cmp);
return true;
}
void Inc(int &a, int b) {a += b; if(a >= P) a -= P;}
void Dp() {memset(dp, 0, sizeof(dp));
dp[0][id[1]] = 1;
for(int k = 0;k<= K; ++k)
for(int x = 1, u = id[1];x<= n; u = id[++x])
for(int i = G.pr[u], w, v; i; i = G.nx[i])
if((w = f[u] + k + G.w[i] - f[v = G.to[i]])<= K)
Inc(dp[w][v], dp[k][u]);
}
int main() {for(int C = ri();C--;) {n = ri(); int m = ri(); K = ri(), P = ri();
G.Pre(); R.Pre();
for(int i = 1;i<= n; ++i)
d[i] = rk[i] = 0;
for(int u, v, w;m--;)
u = ri(), v = ri(), w = ri(),
G.add(u, v, w), R.add(v, u, w), d[v] += !w;
D = f; Dij(G, 1);
D = g; Dij(R, n);
if(!Topsort()) { puts("-1"); continue;
}
Dp();
int r = 0;
for(int i = 0;i<= K; ++i) Inc(r, dp[i][n]);
printf("%d\n", r);
}
return 0;
}
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
