这道题是我今天参加的选拔赛的最后一题，当时想了好久，总是TLE。后面看了学长的代码才看懂，还是经历的太少了。
题目大意
在公园里有N的点，有M条边，每条边有边权Wi（0 ~ 9），有一个长度为K的路线，必须按照路线一个点一个点地走，每个点可以走多次。
权值和为将权值从左往右排列得到的数字。
求所有方案的权值和的平均值。
思路
常规想法是将边存下来，然后dfs搜索求出答案。
这里一反常态，不用vector建图，不用dfs，不用dp，就是要思维，需要看懂题目意思。
因为数据较大，所以使用二维map来存图。
这里有个小tips，建立二维map时，以下两种声明方式各有利弊，map套map的时间复杂度会达到O(logN * logN)虽然不大，但是有可能会卡这个。如果用数组来存，可以O(logN)查询，但是数据范围有限制，如果范围特别大就存不了。
map<int, map<int, int> > mp;//方法1，牺牲查询速度，获得更离散的空间
map<int, int> mp[maxn];//方法2，查询速度快，但是不能开太大我们用两个二维map，分别存路线上两个点之间的权值和以及边的数量，以此求出这些边对答案的贡献（平均值）。如果中间出现了数量为0的边，说明没边，断开了。
这里还用到了逆元和快速幂，具体可以自己查一下，比较简单。
本题重点在于将多条边合并成一条，以极低的复杂度完成。
代码
/*Copyright (C) Eriktse 2022*/
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#include <vector>
#include <utility>
#include <bitset>
#define fi first
#define se second
#define gc getchar
#define pr printf
#define sc scanf
#define pb push_back
#define int long long
//用%lld输出long long类型数据
using namespace std;
inline int readInt()
{
int s = 0,w = 1;char c = gc();
while(c < '0' || c > '9'){if(c == '-')w = -1;c = gc();}
while('0' <= c && c <= '9'){s = s * 10 + c - '0',c = gc();}
return s * w;
}
/*-------全局变量-------*/
const int p = 998244853, maxn = 3e5 + 10;
int N, M, K;
struct Node{int u, v, w;}node[maxn];
int a[maxn];
map<int, int> mp[maxn];
map<int, int> mp2[maxn];
/*-------自定义函数------*/
inline qmi(int a,int b)
{
int res = 1;
while(b)
{
if(b & 1)res = (res * a) % p;
a = (a * a) % p, b >>= 1;
}
return res;
}
inline int inv(int x){return qmi(x, p - 2);}
signed main()
{
N = readInt(), M = readInt(), K = readInt();
for(int i = 1;i <= M; ++ i)
{
int x = readInt(), y = readInt(), w = readInt();
mp[x][y] ++;mp2[x][y] += w;
mp[y][x] ++;mp2[y][x] += w;
}
for(int i = 1;i <= K; ++ i)a[i] = readInt();
int ans = 0;
for(int i = 1;i < K; ++ i)
{
int x = a[i], y = a[i + 1];
if(mp[x][y] == 0)//断开了
{
pr("Stupid Msacywy!\n");
return 0;
}
ans = (ans + (qmi(10, K - i - 1) * mp2[x][y] % p) * inv(mp[x][y] % p)) % p;
}
pr("%lld\n",ans % p);
return 0;
}
文章评论