【Codeforces 788C】The Great Mixing

相关链接

题目传送门:http://codeforces.com/contest/788/problem/C
官方题解:http://codeforces.com/blog/entry/51312

解题报告

假设取$x$个物品的时候原问题有解,且第$i$个物品的编号为$b_i$
那么此时满足这个等式:$\sum\limits_{i=1}^{x}{a_{b_i}}=nx$

这个看起来既不满足单调性,又不能方便地$DP$
但如果我们把$n$给减到$a_i$里去,那么就是$\sum\limits_{i=1}^{x}{a_{b_i}}=0$
这个就好办了,直接搞一个$O(n^2)$的那个$BFS$

这个技巧应用较为广泛,还有一些升级版本
比如这个题:https://oi.qizy.tech/?p=3069

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;
const int M = 2000009;
const int BAS = 1000;

int n,m,tot,dis[N],head[N];
int nxt[M],to[M],_hash[M];
queue<int> que;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read(); m = read();
	for (int i=1;i<=m;i++) _hash[++tot] = read() - n;
	sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=tot;i++) {
		dis[_hash[i] + BAS] = 1;
		que.push(_hash[i] + BAS);
	} 
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=1,t;t=w+_hash[i],i<=tot;i++) {
			if (t < 0 || t > BAS*2 || dis[t]) continue;
			dis[t] = dis[w] + 1; que.push(t);
		}
	}
	cout<<(dis[BAS]?dis[BAS]:-1);
	return 0;
}

【BZOJ 2118】墨墨的等式

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2118
神犇题解:https://blog.sengxian.com/solutions/bzoj-2118

解题报告

先来看一道简单的题目:

给定$a,b,c(a,b,c \le 10^5)$,规定$x,y,z \in \mathbb{N}$
问$ax+by+cz$不能表示出的正整数中,最大的那一个是多少

我们不妨在$\bmod c$的意义下做,这样就可以只考虑$0 \sim c-1$
于是暴力用$a,b$连边,跑一边最短路
这样就可以求出在$\bmod c$的剩余系中,每一个等价类最早出现的位置
于是扫一遍,取一个$\max$就可以了

然后再看看这个题,也就是多连几条边的事吧?

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500009;
const int M = N * 12;
const LL INF = 1e17;

int n,a[N],done[N];
int nxt[M],to[M],cost[M],head[N];
LL dis[N],bmn,bmx,mn=INF;
priority_queue<pair<LL,int> > que;

inline void AddEdge(int u, int v, int c) {
	static int E = 1; cost[++E] = c;
	to[E] = v; nxt[E] = head[u]; head[u] = E;
}

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Dijkstra() {
	for (int i=0;i<mn;i++) dis[i] = INF;
	dis[0] = 0; que.push(make_pair(0, 0));
	while (!que.empty()) {
		int w = que.top().second; que.pop();
		if (done[w]) continue; else done[w] = 1;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	}
}

inline LL cal(LL lim) {
	LL ret = 0, tmp;
	for (int i=0;i<mn;i++) {
		if (lim < dis[i]) continue;
		ret += (lim - dis[i]) / mn + 1;
	}
	return ret;
}

int main() {
	n = read(); cin>>bmn>>bmx;
	for (int i=1;i<=n;i++) {
		a[i] = read();
		if (a[i]) mn = min(mn, (LL)a[i]);
	}
	for (int i=1;i<=n;i++) {
		if (a[i] == mn) continue;
		for (int j=0;j<mn;j++) {
			AddEdge(j, (j+a[i])%mn, a[i]);
		}
	}
	Dijkstra();
	printf("%lld\n",cal(bmx)-cal(bmn-1));
	return 0;
}

【BZOJ 3919】[Baltic2014] portals

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3919
神犇题解:http://www.cnblogs.com/clrs97/p/4668647.html

解题报告

我们自己想一想,这货如果没有Po那就是一个BFS
现在考虑Po的作用,那一定是发射一个Po之后,正常移动是为了走到最近的墙来使用Po
于是我们先预处理出每一个点上下左右每一个方向遇到的第一堵墙
再求出这到这四个点的最近距离$l$

那么如果我们当前在$i$号点,那么我们可以花费$1$的代价走到相邻的四个点
也可以花$l+1$的代价走到上下左右第一个遇到障碍的点
这显然是一个最短路问题,跑一个Dijksta就可以啦!

【BZOJ 3482】[COCI2013] hiperprostor

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3482
神犇题解:http://www.cnblogs.com/clrs97/p/4675155.html

解题报告

我们发现一条路径的长度为$ax+b$,是一条直线的形式
那么我们如果求出所有直线的凸包,那么就可以$O(n)$计算答案了

现在考虑如何搞出凸包:

若两条直线的斜率相等,那么纵截距较小的一定优于纵截距较大的
于是我们可以定义状态$f_{i,j}$表示到达$i$点,斜率为$j$,的路径纵截距最小是多少
这个我们可以使用Dijkstra搞出来,之后我们显然可以$O(n)$构造出凸包了

有了凸包后,每一条线段的贡献就是一个等差数列,这个显然可以$O(1)$计算
于是总的时间复杂度就是$O(Qn^2 \log (n^2))$

【BZOJ 4356】[CEOI2014] Wall

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4356
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5196611.html
神犇题解Ⅱ:http://www.cnblogs.com/New-Godess/p/4424149.html

解题报告

bzoj_4356_solution

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int L = 400 + 9;
const int N = L * L * 4;
const int M = N * 4;
const LL INF = 1e17;

int n,m,tot,E,head[N],nxt[M],to[M],cost[M];
int cx[L][L],cy[L][L],intree[L][L];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
bool del[L][L][4],vis[L][L],done[N],bst[L][L][4];
LL dis[N];
priority_queue<pair<LL, int> > que;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void Add_Edge(int u, int v, int c) {
	to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}

inline int id(int x, int y, int t = 0) {
	if (!t) return x + (y - 1) * (n + 1);
	else return (x - 1 + (y - 1) * (n + 1) << 2) + t;
}

inline void Dijkstra(int s) {
	memset(done, 0, sizeof(done));
	fill(dis, dis+N, INF); dis[s] = 0;
	que.push(make_pair(0, s));
	for (int w;!que.empty();) {
		w = que.top().second; que.pop(); 
		if (done[w]) continue;
		done[w] = 1;
		for (int i=head[w];i;i=nxt[i]) {
			if (dis[to[i]] > dis[w] + cost[i]) {
				dis[to[i]] = dis[w] + cost[i];
				que.push(make_pair(-dis[to[i]], to[i]));
			}
		}
	} 
}

bool mark(int x, int y, int f) {
	if (intree[x][y]) return ~intree[x][y]?1:0;
	bool tag = vis[x][y]; 
	for (int w=id(x,y),i=head[w];i;i=nxt[i]) {
		if (dis[w] + cost[i] == dis[to[i]] && to[i] != f) {
			for (int j=1,nx,ny;j<=4;j++) {
				nx = x + dx[j]; ny = y + dy[j];
				if (id(nx, ny) == to[i]) {
					if (mark(nx, ny, w)) {
						bst[x][y][j] = tag = 1;
						bst[nx][ny][j+2>4?j-2:j+2] = 1;
					}
					break;
				}
			}
		}
	}
	intree[x][y] = tag?1:-1;
	return tag;
}

int main() {
	m = read(); n = read();
	del[1][1][2] = del[1][1][4] = 1;
	for (int j=1;j<=m;j++) {
		for (int i=1;i<=n;i++) {
			if (read()) {
				vis[i][j] = 1;
				del[i][j][4] = 1;
				del[i+1][j][3] = 1;
				del[i][j+1][1] = 1;
				del[i+1][j+1][2] = 1;
			}
		}
	}
	for (int j=1,tmp;j<=m;j++) {
		for (int i=1;i<=n+1;i++) {
			cy[i][j] = tmp = read();
			Add_Edge(id(i, j), id(i, j+1), tmp);
		}
	}
	for (int j=1,tmp;j<=m+1;j++) {
		for (int i=1;i<=n;i++) {
			cx[i][j] = tmp = read();
			Add_Edge(id(i, j), id(i+1, j), tmp);
		}
	}
	Dijkstra(id(1,1));  
	mark(1, 1, id(1, 1));  
	E = 0; memset(head,0,sizeof(head));
	for (int j=1;j<=m+1;j++) {
		for (int i=1;i<=n+1;i++) {
			if (!del[i][j][1]) {
				if (!del[i][j][4] && !bst[i][j][1]) Add_Edge(id(i, j, 1), id(i, j, 4), 0);
				if (i <= n && !del[i+1][j][2]) Add_Edge(id(i, j, 1), id(i+1, j, 2), cx[i][j]);
			}
			if (!del[i][j][2]) {
				if (!del[i][j][1] && !bst[i][j][4]) Add_Edge(id(i, j, 2), id(i, j, 1), 0);
				if (!del[i][j][3] && !bst[i][j][3]) Add_Edge(id(i, j, 2), id(i, j, 3), 0);
			}
			if (!del[i][j][3]) {
				if (!del[i][j][4] && !bst[i][j][2]) Add_Edge(id(i, j, 3), id(i, j, 4), 0);
				if (j <= m && !del[i][j+1][2]) Add_Edge(id(i, j, 3), id(i, j+1, 2), cy[i][j]);
			}
			if (!del[i][j][4]) {
				if (i <= n && !del[i+1][j][3]) Add_Edge(id(i, j, 4), id(i+1, j, 3), cx[i][j]);
				if (j <= m && !del[i][j+1][1]) Add_Edge(id(i, j, 4), id(i, j+1, 1), cy[i][j]);
			}
		}
	}
	Dijkstra(id(1,1,3));
	printf("%lld\n",dis[id(1,1,1)]);
	return 0;
}

【BZOJ 4144】[AMPPZ2014] Petrol

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4144
神犇题解:http://www.cnblogs.com/Tunix/p/4593049.html

解题报告

随便想一想,这题似乎除了有加油站的点之外,其他点似乎完全可以不用考虑?
再仔细想一想的话,我们似乎只要求出任意两个有加油站的点的最短路,然后再做一个MST就可以了!

现在的问题就是如何求出任意两点的最短路了
我们考虑放宽一点条件,求出一些最短路径的集合 $\{ e \}$ ,使其能够凑出任意两点的最短路
现在考虑两点之间最短路的性质:

定义$blg(x)$表示离$x$最近的关键点
那么对于 $a \to b$ 最短路上,一定是前一部分$blg(x)=a$,后一部分$blg(x)=b$
于是我们就可以通过枚举原图中的一条边$(x_1,x_2)$并且判断$blg(x_1)$是否等于$blg(x_2)$来找到所有中途不经过加油站的最短路

如何证明呢?考虑反证法:如果中途有一个点$blg(y)=c$那么先从$a \to b \to c$一定不比$a \to b$劣
这是因为如果我们走到y点后绕道到c点去加油,回来的时候油量一定不少于从a点到y点的油量

这样我们就可以找到一个边集 $\{ \varepsilon \}$使得 $\{ e\} \subset \{ \varepsilon \}$
于是我们把$\{ \varepsilon \}$拿出来,做一个最小生成树,然后查询的时候,在树上倍增一下就可以啦!

【BZOJ 4456】[ZJOI2016] 旅行者

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4456
神犇题解:http://blog.csdn.net/neither_nor/article/details/51733997

解题报告

将询问离线后考虑分治
不停地将区间尽量划分成正方形
考虑每一个块内的询问:

1. 最优路径经过中轴线

那么我们枚举中轴线上的每一个点
跑一遍到块内所有点的最短路
然后用这个东西来更新答案

2. 最优路径不经过中轴线

那么我们递归处理

于是我们就在 $O(n\sqrt n {\log ^2}n)$ 的时间复杂度内解决这个问题了
然而复杂度可以被证明到少个 $log$ 参见:http://blog.csdn.net/neither_nor/article/details/51733997

【BZOJ 4152】[AMPPZ2014] The Captain

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4152
神犇题解:http://blog.csdn.net/qq_34731703/article/details/52724766

解题报告

因为横着的边和竖着的边相互独立
于是分开考虑,先考虑横着的边:

直接连是 $ O({n^2})$
但因为 $ dis(i,j) = dis(i,k) + dis(k,j)(i < k < j)$ 所以只连相邻的点就可以啦!

竖着的边也同理
这样的话,边数和点数都是 $ O(n)$ 级别的
于是就可以上正常的最短路辣!
另外,据说这题卡SPFA?