【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 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?

【BZOJ 4383】[POI2015] Pustynia

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4383
数据传送门:https://oi.qizy.tech/?attachment_id=1911

题解

这个题暴力差分肯定可以做,就是边太多会爆炸
于是我们考虑先建一个像线段树一样的图
于是原题可以拆成6e5个区间连边
每一个区间又可以拆成log(n)个线段树上的点
于是复杂度就对辣!

代码

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

const int N = 2000000;
const int M = 5000000;
const int INF = 1000000000;

int head[N],to[M],nxt[M],cost[M],val[N],arr[N];
int sol[N],vis[N],in[N],n,m,s,bas,tot;
queue<pair<int,int> > leaf;

inline void Add_Edge(int u, int v, int w) {
	static int T = 0; in[v]++;
	to[++T] = v; nxt[T] = head[u]; 
	head[u] = T; cost[T] = w;
}

inline int read(){
	char c=getchar(); int ret=0,f=1;
	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;
}

void build(int w, int l, int r) {
	bas = max(bas, w);
	if (l < r) {
		int mid = l + r + 1 >> 1;
		Add_Edge(w, w<<1, 0); build(w<<1, l, mid - 1);
		Add_Edge(w, w*2+1, 0); build(w*2+1, mid, r);
	} else {
		leaf.push(make_pair(w,l));
	}
}

bool Get_Ans(int w) {
	sol[w] = true;
	for (int i=head[w];i;i=nxt[i]) {
		if (vis[to[i]] && val[w] - cost[i] < val[to[i]]) {
			return false;
		} else {
			val[to[i]] = min(val[to[i]], val[w] - cost[i]);
			if (--in[to[i]] == 0) {
				if (!Get_Ans(to[i])) {
					return false;
				};
			}
		}
	}
	return true;
}

inline bool solve() {
	for (int i=1;i<=tot;i++) {
		if (!sol[i] && !in[i]) {
			if (!Get_Ans(i)) {
				return false;
			}
		}
	}
	return true;
} 

void insert(int w, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		Add_Edge(tot, w, 0);
	} else {
		int mid = l + r + 1 >> 1;
		if (L < mid) insert(w<<1, l, mid-1, L, R);
		if (R >= mid) insert(w*2+1, mid, r, L, R);
	}
}

int main(){
	n = read(); s = read(); m = read();
	build(1,1,n);
	while (!leaf.empty()) { 
		Add_Edge(leaf.front().first, leaf.front().second + bas, 0);
		leaf.pop(); 
	}
	tot = bas + n;
	fill(val, val+N, INF);
	for (int i=1,p;i<=s;i++) {
		p = read();
		val[p+bas] = read();
		vis[p+bas] = 1;
	}
		
	for (int i=1,l,r,k,last;i<=m;i++) {
		l = read(); r = read(); 
		k = read(); ++tot;
		for (int j=1,tmp;j<=k;j++) {
			arr[j] = tmp = read();
			Add_Edge(bas+tmp, tot, 1);
		}
		arr[0] = l-1; arr[k+1] = r+1;
		for (int j=1;j<=k+1;j++) {
			if (arr[j] - arr[j-1] > 1) {
				insert(1,1,n,arr[j-1]+1,arr[j]-1);
			} 
		}
	}
	if (!solve()) {
		puts("NIE");
	} else {
		for (int i=bas;i<=tot;i++) {
			if (in[i] || val[i] < 1) {
				puts("NIE");
				exit(0);
			}
		}
		
		puts("TAK");
		for (int i=1;i<=n;i++) 
			printf("%d ",val[i+bas]);
	}
	return 0;
}

【Codevs 1817】灾后重建

题目传送门:http://codevs.cn/problem/1817/

这题可以说是Floyd的最终考验吧?
具体来说:做了这题Floyd的原理就完全明白了吧!
详细请参考《算导》P405吧!(难得算导说了一次人话)

#include<iostream>
#include<cstdio>
#include<vector>
#define INF 1000099 
using namespace std;

struct abc{int point,len;};
int n,m;
int t[299]={0};
int f[299][299];
bool yet[299]={0};
vector<abc> path[299];  
bool day[100099]={0};
int pro=0;

void init(){
	for (int i=1;i<=250;i++){
		t[i]=INF;
	}
	for (int i=0;i<=250;i++){
	    for (int j=0;j<=250;j++){
		    f[i][j]=INF;
	    }
	}
    scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
	    scanf("%d",&t[i]); 
	    if (t[i]==0) yet[i]=true;
	}	
	abc hc;
	for (int i=1,a,b,leng;i<=m;i++){
		scanf("%d%d%d",&a,&b,&leng);
		a++;b++;
		f[a][b]=leng;f[b][a]=leng;
		hc.point=b;hc.len=leng;
		path[a].push_back(hc);
		hc.point=a;
		path[b].push_back(hc);
	}
}

void update(int num){
	int end,length;
	for (int k=pro+1;k<=end;k++)
	    yet[k]=true;
	for (int k=pro+1;k<=end;k++){
	    for (int i=1;i<=n;i++){
	    	for (int j=1;j<=n;j++){
	    		f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	    	}
	    }
	}
	pro=end; 
} 

int main(){
	int Q,x,y,ti;
	init();
	cin>>Q;
	for (int i=1;i<=Q;i++){
		scanf("%d%d%d",&x,&y,&ti);
		x++;y++;
		if (!day[ti]) {
		    update(ti);
			day[ti]=1;
		}
		if (f[x][y]<INF && yet[x] && yet[y]) printf("%d\n",f[x][y]);
		else printf("-1\n");
	}
	return 0;
}

为什么去年写的代码这么丑? (╯‵□′)╯︵┻━┻