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

这个技巧应用较为广泛,还有一些升级版本
比如这个题:http://oi.cyo.ng/?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;
}

【NOIP十连测】[D1T3] Walk

题目传送门:http://oi.cyo.ng/wp-content/uploads/2016/10/noip_test1_statements.pdf

唯一恶心的就是哪些根据val建的边
于是搞一个想分层图一样的玩意儿
然后有的边权为零,于是BFS的时候不往队首扔,往队尾扔即可

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

const int N = 1300000;
const int M = 200000*2+300000+9;

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

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;
}

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

inline void BFS() {
	memset(dis,-1,sizeof(dis));
	dis[1] = 0; que.push_back(1);
	
	while (!que.empty()) {
		int w = que.front(); que.pop_front();
		for (int i=head[w];i;i=nxt[i]) 
			if (w <= n) {
				if (!~dis[to[i]] || dis[to[i]] > dis[w] + 1) dis[to[i]] = dis[w] + 1, que.push_back(to[i]);
			} else {
				if (!~dis[to[i]] || dis[to[i]] > dis[w]) dis[to[i]] = dis[w], que.push_front(to[i]);
			}
		if (w > n) for (int i=0;i<=20;i++) if ((w-n)&(1<<i)) {
			int v = ((w-n)^(1<<i)) + n; if (v <= n) continue;
			if (!~dis[v] || dis[v] > dis[w]) dis[v] = dis[w], que.push_front(v);
		} 
	}
}

int main(){
	freopen("walk.in","r",stdin);
	freopen("walk.out","w",stdout);
	n = read(); m = read();
	for (int i=1,tmp;i<=n;i++) tmp = read(), Add_Edge(i,n+tmp), Add_Edge(n+tmp,i);
	for (int i=1,u,v;i<=m;i++) u = read(), v = read(), Add_Edge(u,v);
	BFS(); for (int i=1;i<=n;i++) printf("%d\n",dis[i]);
	return 0;
}