最短路计数

题目描述

给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$。问从顶点 $1$ 开始，到其他每个点的最短路有几条。

输入格式

第一行包含 $2$ 个正整数 $N,M$，为图的顶点数与边数。

接下来 $M$ 行，每行 $2$ 个正整数 $x,y$，表示有一条由顶点 $x$ 连向顶点 $y$ 的边，请注意可能有自环与重边。

输出格式

共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$。

样例

样例输入

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

样例输出

1
1
1
2
4

提示

$1$ 到 $5$ 的最短路有 $4$ 条，分别为 $2$ 条 $1\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$（由于 $4\to 5$ 的边有 $2$ 条）。

• 对于 $20\%$ 的数据，$1\le N\le 100$；
• 对于 $60\%$ 的数据，$1\le N\le 10^3$；
• 对于 $100\%$ 的数据，$1\le N\le 10^6$，$1\le M\le 2\times 10^6$。

思路

无向无权图。可使用bfs遍历，因为路径的权重都为1。
当前图中存在自环，但自环并不影响bfs遍历的最短路。
然后就是重边会对结果造成影响，需要我们考虑。

代码实现

import java.util.*;public class Main{static int MOD = (int)1e5 + 3;public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt(), len = sc.nextInt();List<Integer> list[] = new ArrayList[n+1];// 去环，已经进入过队列的结点，将不再进入队列boolean[] vis = new boolean[n+1];int[] depth = new int[n+1];// 结果。int[] ans = new int[n+1];for(int i = 1; i <= n; i++) list[i] = new ArrayList<>();int x, y;for (int i = 0; i < len; i++) {x = sc.nextInt();y = sc.nextInt();list[x].add(y);list[y].add(x);}Queue<Integer> queue = new ArrayDeque<>();depth[1] = 0;vis[1] = true;ans[1] = 1;queue.offer(1);while(!queue.isEmpty()){int cur = queue.poll();for(int next : list[cur]){if(!vis[next]){vis[next] = true;depth[next] = depth[cur] + 1;queue.offer(next);}// next结点，只有深度为 depth[next]的时候才会更新。// 换句话说就是只有第一次与第一次相同时间到达next时，才会更新值。if(depth[next] == depth[cur] + 1) ans[next] = (ans[next] + ans[cur]) % MOD;}}for(int i = 1; i <= n; i++) System.out.println(ans[i]);sc.close();}
}

中位数

题目描述

给出 $1,2,...,n$ 的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是 $b$。中位数是指把所有元素从小到大排列后，位于中间的数。

输入格式

第一行为两个正整数 $n$ 和 $b$，第二行为 $1,2,...,n$ 的排列。

输出格式

输出一个整数，即中位数为 $b$ 的连续子序列个数。

样例

样例输入

7 4
5 7 2 4 3 1 6

样例输出

4

提示

数据规模与约定

• 对于 $30\%$ 的数据中，满足 $n\le 100$；

• 对于 $60\%$ 的数据中，满足 $n\le 1000$；

• 对于 $100\%$ 的数据中，满足 $n\le 100000,1\le b\le n$。

思路

因为满足需要的区间一定包含b, 所以我们可以先把b在数组中的位置找到。再到基础上拓展区间。
需要b成为区间的中位数，即是需要区间内大于b的数的数量等于区间内小于b的数的数量，我们可以把大于b的数记作1， 小于b的数记为-1。然后只需要左边区间加+右边区间 = 0即为找到一个区间。（还需要特别注意区间长度为奇数也是条件之一）

代码实现

import java.util.*;public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt(), b = sc.nextInt();int[] arr = new int[n+1];for(int i = 1; i <= n; i++) arr[i] = sc.nextInt();int index = query(arr, b);HashMap<Integer, Integer> one = new HashMap<>();HashMap<Integer, Integer> two = new HashMap<>();two.put(0, 1);int val = 0;for(int i = index - 1; i > 0; i--){val += (arr[i] > b ? 1 : -1);if((index - i) % 2 == 1) one.put(val, one.getOrDefault(val, 0) + 1);else two.put(val, two.getOrDefault(val, 0) + 1);}val = 0;long ans = 0;for(int i = index; i <= n; i++){val += (arr[i] == b ? 0 : (arr[i] > b ? 1 : -1));if((i-index) % 2 == 1) ans += one.getOrDefault(-val, 0);else ans += two.getOrDefault(-val, 0);}System.out.println(ans);sc.close();}static int query(int[] arr, int b){for(int i = 1; i < arr.length; i++){if(arr[i] == b) return i; }return -1;}
}