这道题是我今天参加的选拔赛的最后一题,当时想了好久,总是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; }
Comments NOTHING