ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

公园游玩(图论 + 思维)

2022年3月5日 1301点热度 0人点赞 0条评论

题目链接:Problem - I - Codeforces

这道题是我今天参加的选拔赛的最后一题,当时想了好久,总是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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: dfs map 图论 快速幂 思维 贡献
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号