首页 > 其他分享 >【21 ZR联赛集训 day10】身经百战

【21 ZR联赛集训 day10】身经百战

时间:2024-09-27 14:27:36浏览次数:10  
标签:ch 21 int sum day10 vec que ZR dis

【21 ZR联赛集训 day10】身经百战

显然每个怪物是独立的。

我们考虑对操作建带权边,答案就是求最短路。

但是点数太多,于是我们可以对怪物血量和所有 \(a_i,b_i\) 离散化一下,因为我们只需要考虑这些点,注意 \(1\) 也要离散化,因为我们需要考虑 \(1\)。

一个小优化,如果 \(a_i>b_i\) 且 \(c_i\ge a_i-b_i\) 这条 \((a_i,b_i,c_i)\) 的边没必要加,因为直接操作一一个一个减不会更差。此外自环(\(a_i=b_i\))也是没必要的,重边取最小那条(不过太麻烦了,没必要)。

我们从 \(1\) 开始沿逆向边做最短路,时间复杂度 \(O(m\log m)\)。

Code

#include<bits/stdc++.h>
#define pf printf
#define sf scanf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define isdigit(x) (x>='0'&&x<='9')
//#define int ll
using namespace std;
typedef long long ll;
const int N=1e6+7,M=1e5+5;
template <typename T>
void read(T &sum){
	sum=0;
	T fl=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) (ch=='-')&&(fl=-1);
	for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+ch-'0';
	sum=sum*fl;
}
template <typename T>
void write(T x){
	static int st[36];
	int top=0;
	if(x<0) putchar('-'),x=-x;
	do{
		st[top++]=x%10,x/=10;
	}while(x);
	while(top) putchar(st[--top]+'0');
}
template <typename T>
void write(T x,char ch){
	write(x);
	putchar(ch);
}

int head[N<<1],cnt;
struct edge{
	int to,val,ne;
}e[N<<2];
void addedge(int u,int v,int w){
	swap(u,v);
//	pf("(%d %d %d)\n",u,v,w);
	e[++cnt]={v,w,head[u]};head[u]=cnt;
}

int n,m;
int v[N];
int a[M],b[M],c[M];
int vec[N<<1];
int len;
int ans[N];

int dis[N<<1],vi[N<<1];
struct qst{
	int x,d;
	bool operator <(const qst b)const{
		return (d!=b.d?d>b.d:x>b.x);
	}
};
void getdis(int rt){
	memset(vi,0,sizeof(vi));
	priority_queue<qst> que;
	dis[rt]=0;
	que.push({rt,0});
	while(!que.empty()){
		qst k=que.top();
		que.pop();
		int u=k.x,d=k.d;
		if(vi[u]) continue;
		vi[u]=1;
//		pf("u: %d\n",u);
		for(int i=head[u];i;i=e[i].ne){
			int v=e[i].to,w=e[i].val;
			if(d+w<dis[v]){
				dis[v]=d+w;
//				pf("v: %d,%d\n",v,dis[v]);
				que.push({v,dis[v]});
			}
		}
	}
}
ll sum;

signed main(){
	read(n),read(m);
	rep(i,1,n){
		read(v[i]);
		vec[++vec[0]]=v[i];
	}
	rep(i,1,m){
		read(a[i]),read(b[i]),read(c[i]);
		vec[++vec[0]]=a[i],vec[++vec[0]]=b[i];
	}
	vec[++vec[0]]=1;
	sort(vec+1,vec+vec[0]+1);
	len=unique(vec+1,vec+vec[0]+1)-vec-1;
	rep(i,2,len) {
//		pf("%d ",vec[i]);
		addedge(i,i-1,vec[i]-vec[i-1]);
	}
//	pf("\n");
	rep(i,1,n){
		int x=lower_bound(vec+1,vec+len+1,v[i])-vec;
		ans[i]=x;
	}
	rep(i,1,m){
		if((c[i]>=a[i]-b[i]&&a[i]>b[i])||a[i]==b[i]) continue;
		int u=lower_bound(vec+1,vec+len+1,a[i])-vec,
		v=lower_bound(vec+1,vec+len+1,b[i])-vec;
		addedge(u,v,c[i]);
	}
	memset(dis,0x7f,sizeof(dis));
	getdis(lower_bound(vec+1,vec+len+1,1)-vec);
	rep(i,1,n){
//		pf("%d\n",dis[ans[i]]);
		sum+=dis[ans[i]];
	}
	write(sum);
}

标签:ch,21,int,sum,day10,vec,que,ZR,dis
From: https://www.cnblogs.com/liyixin0514/p/18435621

相关文章

  • 【21 ZR联赛集训 day10】不知道高到哪里去了
    【21ZR联赛集训day10】不知道高到哪里去了二分答案。设敌人的速度是\(1\),二分我的速度\(v\),我可以从\(C\)走到\(T\)当对于每个我到达的点\(u\),敌人无法比我先到达,即敌人到达\(u\)最短用时比我大。先求敌人到每个结点的最短路,然后对于二分的一个\(v\),从\(C\)开始搜......
  • 【21 ZR联赛集训 day18】聚会
    【21ZR联赛集训day18】聚会给出一个由小的编号连向大的编号的DAG,有\(q\)次询问,每次给出\(t\)和若\(s\)个点,表示除这些点之外其他点到\(t\)的最大距离。问距离最远的那个结点编号。\(1\len\le10^5,1\lem\le2\times10^5,\sums\le10^5\)。根号分治。对每个点......
  • 【21 ZR联赛集训 day18】游戏
    【21ZR联赛集训day18】游戏给定长度为\(n\)的序列\(A,B\),每个数形如\(\frac{2^{p_1}3^{p_2}5^{p_3}7^{p_4}11^{p_5}13^{p_6}}{2^{p_7}3^{p_8}5^{p_9}7^{p_{10}}11^{p_{11}}13^{p_{12}}}\)。可以进行若干次操作,每次操作选定\(i(2\lei\len-1),(a_{i-1},a_i,a_{i+1})\gets......
  • 【2021提高组十连测day7】a
    【2021提高组十连测day7】a题意:求每个点和其他所有点曼哈顿距离的平方之和。形式化地,求\(\sum_{j=1}^{n}(|x_i-x_j|+|y_i-y_j|)^2(1\lei\len)\)。对于每个点,我们把其他点分成四部分:左上、左下、右上、右下。四个部分可以通过旋转整个坐标系来解决。因此这里讲如何处理左上......
  • 【21 ZR联赛集训 day10】跑得比谁都快
    【21ZR联赛集训day10】跑得比谁都快\(O(nq)\)做法显然,不讲。如果我们把所有红绿灯的位置\(mod(g+r)\),放到数据结构里,就可以\(O(\logn)\)的时间内找到第一个红灯的位置。然后我们预处理每个红绿灯红灯结束的时刻开始,走到终点要用的时间\(f_i\),DP倒序求解。对于每个询......
  • 【20联赛集训day10】玩游戏
    【20联赛集训day10】玩游戏给一个长度为\(n\)的序列,\(|a_i|\le10^{13}\)。给出一个\(k\)问从\(k\)出发不断向两端拓展,满足任何时刻的区间和\(\le0\),问能否拓展到区间\((1,n]\)。考虑贪心,分别维护\(k\)左边和右边的区间,维护一个指针。每次贪心地向一边走,走到能走到......
  • 【20zr提高组十连测day10】心
    【20zr提高组十连测day10】心首先不同的操作序列一定在某个时刻使数组内容不同,因此我们只需要统计合法的操作序列数量。一个合法的最终数组形如若干个\(1,M\),而且\(1,M\)之间可能有若干个\(x\),长度为\(n+1\)。造成这个数组的操作序列必须满足所有操作\(1,M\)按顺序排列,......
  • 【20zr提高组十连测day10】信
    【20zr提高组十连测day10】信给定\(n,m\),\(n,m\le10^5\),给定分别长度为\(n-1,m,n,m-1\)的单调不减的序列\(A,B,C,D\),然后形如该图建边:考虑到序列是递增的,对于除最左上角以外的每个点,每个点一定要选和自己相连的一条边才能形成一棵树。那么选择左边或上边一定是更优的,而且......
  • 【20联赛集训day10】排列
    【20联赛集训day10】排列一个长度为\(n\)的排列,每次操作删除所有存在相邻的数字比它更大的数字,问执行\(k\)次操作后剩下恰好一个数的排列方案数。首先因为每次删除至少删一半的数字,所以最多删\(\log\)次。对于一个排列,我们可以发现把序列按最大值劈开,左右两边互不干扰,成......
  • [SWPUCTF 2021 新生赛]easy_md5
    分析一下代码, name不等于password,namd,md5值和password,md5值相等。get传参name,post传参password。$name!=$password&&md5($name)==md5($password)属于MD5绕过中的php==弱类型绕过有两个办法,第一个办法就是importrequests#网站的URLurl="http://node7.a......