ZOJ Monthly, January 2013

有除了最大的蘑菇题以外的代码。题解因为最近比较忙就……
额,就这样吧……
经检验,下面的代码都可以在ZOJ上AC

ZOJ3676 Edward’s Cola Plan
比较水,看看代码肯定就懂了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 105555;
int n, T;
struct Node {
	int x, y;
 
	Node(){}
 
	Node (int x, int y): x(x), y(y) {}
 
	bool operator < (const Node &oth) const {
		return y - x < oth.y - oth.x;
	}
}a[N];
 
long long sum_x[N];
long long sum_y[N];
 
int main(){
	while (scanf("%d%d", &n, &T) != EOF) {
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &a[i].x, &a[i].y);
		}
		sort(a + 1, a + n + 1);
		sum_x[0] = 0;
		sum_y[0] = 0;
		for (int i = 1; i <= n; i++) {
			sum_x[i] = sum_x[i - 1] + a[i].x;
			sum_y[i] = sum_y[i - 1] + a[i].y;
		}
		for (int i = 0; i < T; i++) {
			int m;
			scanf("%d", &m);
			int index = lower_bound(a + 1, a + n + 1, Node(0, m + 1)) - a;
			if (index > n) {
				cout << sum_x[n] << "\n";
			} else {
				cout << sum_x[index - 1] + sum_y[n] - sum_y[index - 1] - m * (n - index + 1) << "\n";
			}
		}
	}
}

ZOJ3677 Paint Erased
这题本质是涂色点集S和那根线上点集L的交。
而S集合是由若干个可能相交的点集聚成:S = A1 ∪ A2 ∪ A3 ∪ …
很容易想到的是把S割成互不相交的子集,然后分别和L求交,最后答案累加即可。
所以很自然地可以想到矩形切割,但是这里有一个很严重的问题,矩形切割切出来的矩形其实并不是没有交集的,他们在矩形的边缘那条线上会出现重叠。这样子就坑爹了,这里大概还是把边缘拿出来单独离散化处理比较好…总之是有点复杂了
这样子的思路本质是求了S,再求S ∩ L
而相对而言求(A1∩L)∪(A2∩L)∪(A3∩L)∪…则方便得多
这样就只用求出一个矩形在线段上的覆盖部分,然后对若干个线段求并什么的就好了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)

const int MAXN = 1000;
const double eps = 1e-8, PI = atan2(0, -1);
inline double sqr(double x){ return x * x; }
inline bool zero(double x){ return (x > 0 ? x : -x) < eps; }
inline int sgn(double x) { return (x > eps ? 1 : (x + eps < 0 ? -1 : 0)); }
struct point{
    double x, y;
    point(double x, double y):x(x), y(y) {}
    point() {}
    bool operator == (const point & a) const{ return sgn(x - a.x) == 0 && sgn(y - a.y) == 0; }
    bool operator != (const point & a) const{ return sgn(x - a.x) != 0 || sgn(y - a.y) != 0; }
    bool operator < (const point & a) const{ return sgn(x - a.x) < 0 || sgn(x - a.x) == 0 && sgn(y - a.y) < 0; }
    point operator + (const point & a) const{ return point(x + a.x, y + a.y); }
    point operator - (const point & a) const{ return point(x - a.x, y - a.y); }
    point operator * (const double & a) const{ return point(x * a, y * a); }
    point operator / (const double & a) const{ return point(x / a, y / a); }
    double operator * (const point & a) const{ return x * a.y - y * a.x; }//xmult
    double operator ^ (const point & a) const{ return x * a.x + y * a.y; }//dmult
    double length() const{ return sqrt(sqr(x) + sqr(y)); }
    point trunc(double a) const{ return (*this) * (a / length()); }
    point rotate(double ang) const{ point p(sin(ang), cos(ang)); return point((*this) * p, (*this) ^ p); }
    point rotate(const point & a) const{ point p(-a.y, a.x); p = p.trunc(1.0); return point((*this) * p, (*this) ^ p); }
};

struct DB {
	double x;

	DB() {}
	DB(double x):x(x) {}

	bool operator < (const DB &oth) const {
		return oth.x - x > eps;
	}
};


const int N = 2005;
int n, m;
struct Re {
	int t;
	point a, b;
}r[N];

PDD mat[N][N];

vector <point> p;
set <DB> radio[N];
bool mark[N];
vector <double> vec;

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%d%d", &n, &m) == 2) {
		p.clear();
		for (int i = 0; i < n; i++) {
			scanf("%d%lf%lf%lf%lf", &r[i].t, &r[i].a.x, &r[i].a.y, &r[i].b.x, &r[i].b.y);
		}
		for (int i = 0; i < m; i++) {
			double x, y;
			cin >> x >> y;
			p.push_back(point(x, y));
		}
		double ans = 0;
		for (int i = 0; i + 1 < m; i++) {
			radio[i].clear();
			for (int j = 0; j < n; j++) {
				point vec = p[i + 1] - p[i];
				double sr = 0.0, er = 1.0;
				if (r[j].a.x <= p[i].x + eps && p[i].x <= r[j].b.x + eps) {
					checkmax(sr, 0.0);
				} else {
					if (zero(vec.x)) {
						checkmax(sr, 1e20);
					} else {
						checkmax(sr, min((r[j].a.x - p[i].x) / vec.x, (r[j].b.x - p[i].x) / vec.x));
					}
				}
				if (r[j].a.y <= p[i].y + eps && p[i].y <= r[j].b.y + eps) {
					checkmax(sr, 0.0);
				} else {
					if (zero(vec.y)) {
						checkmax(sr, 1e30);
					} else {
						checkmax(sr, min((r[j].a.y - p[i].y) / vec.y, (r[j].b.y - p[i].y) / vec.y));
					}
				}
				if (r[j].a.x <= p[i + 1].x + eps && p[i + 1].x <= r[j].b.x + eps) {
					checkmin(er, 1.0);
				} else {
					if (!zero(vec.x)) {
						checkmin(er, max((r[j].a.x - p[i].x) / vec.x, (r[j].b.x - p[i].x) / vec.x));
					}
				}
				if (r[j].a.y <= p[i + 1].y + eps && p[i + 1].y <= r[j].b.y + eps) {
					checkmin(er, 1.0);
				} else {
					if (!zero(vec.y)) {
						checkmin(er, max((r[j].a.y - p[i].y) / vec.y, (r[j].b.y - p[i].y) / vec.y));
					}
				}
				mat[i][j] = make_pair(sr, er);
//				cout << mat[i][j].first << " " << mat[i][j].second << endl;
//				cout << sr << " " << er << endl;
				if (sr < er) {
					radio[i].insert(sr);
					radio[i].insert(er);
				}
			}
			vec.clear();
			foreach (it, radio[i]) {
				vec.push_back(it->x);
			}
			for (int j = 0; j < vec.size(); j++) mark[j] = 0;
			for (int j = 0; j < n; j++) {
				if (mat[i][j].first >= mat[i][j].second) continue;
				for (int k = (lower_bound(vec.begin(), vec.end(), mat[i][j].first - eps) - vec.begin()); k + 1 < vec.size(); k++) {
					if (vec[k + 1] <= mat[i][j].second + eps) {
						mark[k] = r[j].t;
					}
				}
			}
			for (int j = 0; j + 1 < vec.size(); j++) {
				if (mark[j]) ans += (vec[j + 1] - vec[j]) * (p[i + 1] - p[i]).length();
			}
		}
		cout << fixed << setprecision(2) << ans << "\n";
	}
	return 0;
}

ZOJ3678 The Toy of Flandre Scarlet
考虑三个相邻的数x, y, z。那么作以下操作
x + 1, y + 1, z
x + 1, y, z – 1
于是可以发现,考虑两个点(a, b, c), (d, e, f)。
如果a + b + c和d + e + f的奇偶性相同,那么这两个点之间值是可以互相传递的。
那么可以考虑把所有的值都转到相邻的两个格子中,如果他们相等,那么就可以消完,否则消不完。

#include <cstdio>

const int N = 5;
int L, W, H;
int a[N][N][N];
int pos[N][N][N];
int main() {
	while (scanf("%d%d%d", &L, &W, &H) != EOF) {
		int cnt = 0;
		int sum = 0;
		for (int i = 0; i < L; i++) {
			for (int j = 0; j < W; j++) {
				for (int k = 0; k < H; k++) {
					scanf("%d", &a[i][j][k]);
					pos[i][j][k] = ++cnt;
					if ((i + j + k) & 1) {
						sum += a[i][j][k];
					} else {
						sum -= a[i][j][k];
					}
				}
			}
		}
		if (sum == 0) {
			puts("Yes");
		} else {
			puts("No");
		}
}
}


ZOJ3679 One Touch Drawing
预处理以后蘑菇爆搜就可以了。注意可能出现一直疯狂传送的情况……这时候要判断一下。

	#include <cstdio>
	#include <cstring>
	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <set>
	#include <map>
	#include <cmath>
	#include <sstream>
	#include <iomanip>
	#include <cassert>
	using namespace std;
	template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
	template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
	typedef pair <int,int> PII;
	typedef pair <double,double> PDD;
	#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
	const int N = 105;
	int n, m, w;
	struct edge {
	   int x, y, t, d, z;
	   edge(){}
	   edge(int x, int y, int t, int d, int z):x(x), y(y), t(t), d(d), z(z) {}
	};
	vector <edge> E;
	int cnt[N], sum;
	int transTo[N];
	int f[N][N];
	void dfs(int x) {
	   if (sum == 0) {
		  throw 1;
	   }
	   if (f[x][x]) {
		  return;
	   }
	   cnt[x]++;
	   for (int i = 0; i < m; i++) {
		  if (E[i].z == x) {
			 swap(E[i].x, E[i].y);
		  }
	   }
	   if (transTo[x] != -1) {
		  dfs(transTo[x]);
	   } else {
		  for (int i = 0; i < m; i++) {
			 if (E[i].t && E[i].x == x) {
				sum--;
				E[i].t--;
				dfs(E[i].y);
				E[i].t++;
				sum++;
			 } else if (E[i].t && E[i].y == x && !E[i].d) {
				sum--;
				E[i].t--;
				dfs(E[i].x);
				E[i].t++;
				sum++;
			 }
		  }
	   }
	   cnt[x]--;
	   for (int i = 0; i < m; i++) {
		  if (E[i].z == x) {
			 swap(E[i].x, E[i].y);
		  }
	   }
	}
	int main(){
	   while (scanf("%d%d%d", &n, &m, &w) != EOF) {
		  E.clear();
		  memset(cnt, 0, sizeof(cnt));
		  memset(transTo, 0xFF, sizeof(transTo));
		  memset(f, 0, sizeof(f));
		  sum = 0;
		  for (int i = 0; i < m; i++) {
			 int x, y, t, d, z;
			 scanf("%d%d%d%d%d", &x, &y, &t, &d, &z);
			 E.push_back(edge(x, y, t, d, z));
			 sum += t;
		  }
		  for (int i = 0; i < w; i++) {
			 int s1, s2;
			 scanf("%d%d", &s1, &s2);
			 assert(transTo[s1] == -1);
			 transTo[s1] = s2;
			 f[s1][s2] = 1;
		  }
		  for (int k = 0; k < n; k++) {
			 for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
				   f[i][j] |= f[i][k] & f[k][j];
				}
			 }
		  }
		  try {
			 for (int i = 0; i < n; i++) {
				dfs(i);
			 }
		  } catch (...) {
			 puts("Yes");
			 continue;
		  }
		  puts("No");
	   }
	}


ZOJ3680 E – Cup 1
蘑菇+爆搜……

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <vector>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 505;
int n;
vector <pair < int, pair <int,int> > > E[N];
map <string, int> ref;
string name[N];
int _rank[N];
map <string, int> rank;
 
struct Node {
	int point;
	int js;
	int jq;
	int id;
 
	bool operator < (const Node &oth) const {
		if (point != oth.point) return point > oth.point;
		if (js != oth.js) return js > oth.js;
		return jq > oth.jq;
	}
 
	bool operator == (const Node &oth) const {
		return point == oth.point && js == oth.js && jq == oth.jq;
	}
 
}a[N];
int m;
int v[N];
 
bool cmp(Node A, Node B) {
	if (A.js != B.js) return A.js > B.js;
	if (A.jq != B.jq) return A.jq > B.jq;
	return _rank[A.id] < _rank[B.id];
}
 
void calc() {
		for (int i = 1; i <= n; i++) {
			a[i].point = a[i].js = a[i].jq = 0;
			foreach (it, E[a[i].id]) {
				a[i].jq += it->second.first;
				a[i].js += it->second.first - it->second.second;
				if (it->second.first > it->second.second) {
					a[i].point += 3;
				} else if (it->second.first == it->second.second) {
					a[i].point++;
				}
			}
		}
}
 
void gao(int l, int r) {
	if (l == r) return;
	m++;
	for (int i = l; i <= r; i++) {
		v[a[i].id] = m;
	}
	for (int i = l; i <= r; i++) {
		a[i].point = a[i].js = a[i].jq = 0;
		foreach (it, E[a[i].id]) {
			if (v[it->first] == m) {
				a[i].jq += it->second.first;
				a[i].js += it->second.first - it->second.second;
				if (it->second.first > it->second.second) {
					a[i].point += 3;
				} else if (it->second.first == it->second.second) {
					a[i].point++;
				}
			}
		}
	}
	sort(a + l, a + r + 1);
	vector <Node> buf;
	vector <PII> need;
	for (int i = l; i <= r; i++) {
		if (buf.empty() || a[i] == buf[0]) {
			buf.push_back(a[i]);
		} else {
			need.push_back(PII(i - buf.size(), i - 1));
			buf.clear();
			buf.push_back(a[i]);
		}
	}
	need.push_back(PII(r + 1 - buf.size(), r));
	if (need.size() == 1) {
		for (int i = l; i <= r; i++) {
			a[i].point = a[i].js = a[i].jq = 0;
			foreach (it, E[a[i].id]) {
				a[i].jq += it->second.first;
				a[i].js += it->second.first - it->second.second;
				if (it->second.first > it->second.second) {
					a[i].point += 3;
				} else if (it->second.first == it->second.second) {
					a[i].point++;
				}
			}
		}
		sort(a + l, a + r + 1, cmp);
	} else {
		foreach(it, need) {
			gao(it->first, it->second);
		}
	}
}
 
int main(){
	int Tc = 0;
	while (scanf("%d", &n) != EOF) {
		if (Tc) puts("");
		Tc++;
		ref.clear();
		rank.clear();
		char buf[1000];
		for (int i=1;i<=n;i++) E[i].clear();
		for (int i = 0; i < n*(n-1)/2;i++) {
			scanf("%s",buf);
			string team_a(buf);
			int x,y;
			scanf("%d:%d", &x, &y);
//			cout << x << " " << y << endl;
			scanf("%s",buf);
			string team_b(buf);
			if (!ref.count(team_a)) {
				ref[team_a] = ref.size();
//				cout << team_a << " " << ref[team_a] << endl;
				name[ref.size()] = team_a;
			}
			if (!ref.count(team_b)) {
				ref[team_b] = ref.size();
//				cout << team_b << " " << ref[team_b] << endl;
				name[ref.size()] = team_b;
			}
			E[ref[team_a]].push_back( make_pair(ref[team_b], make_pair(x, y) ) );
			E[ref[team_b]].push_back( make_pair(ref[team_a], make_pair(y, x) ) );
		}
		int m;
		scanf("%d",&m);
		for (int i = 0; i < m; i++) {
			scanf("%s",buf);
			rank[string(buf)] = i;
		}
		for (int i = 1; i <= n; i++) {
			a[i].id = i;
			_rank[i] = rank[name[i]];
		}
		m = 0;
		memset(v,0,sizeof(v));
		calc();
		sort(a + 1, a + n + 1);
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			if (!cnt || a[i].point == a[i - 1].point) {
				cnt++;
			} else {
				gao(i - cnt, i - 1);
				cnt = 1;
			}
		}
		gao(n + 1 - cnt, n);
		for (int i=1;i<=n;i++) {
			cout << name[a[i].id] << endl;
		}
	}
}

ZOJ3681 E – Cup 2

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const long long INF = 1LL * 1000000000 * 1000000000;
int n, m;
long long F[40];

long long tr(long long x) {
	return x / 2 + 1;
}

void init() {
	for (int i = 0; i <= 4; i++) {
		F[i] = tr(1 << i);
	}
	for (int i = 5;i<=35;i++) {
		F[i] = INF;
		for (int j=0;j<i;j++) {
			checkmin(F[i], F[i - j] * tr(1LL << j));
		}
	}
}

int gao(int n) {
	int j;
	for (int i=0;;i++) {
		if (n == (1 << i)) {
			j=i;
			break;
		}
	}
	return F[j];
}

int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
//	freopen("out", "w", stdout);
	init();
	while (scanf("%d%d", &n, &m) != EOF) {
//		n = _n;
		long long ans = 1;
		while (n % 2 == 0) {
			n/=2;
			ans*=2;
		}
		ans = gao(ans);
		for (int i=3;i*i<=n;i++) {
			while (n % i == 0) {
				n /= i;
				ans = ans * (i / 2 + 1);
			}
		}
		if (n != 1) {
			ans = ans * (n / 2 + 1);
		}
		puts(ans > m ? "No" : "Yes");
		printf("%lld\n", ans);
	}
}

ZOJ3682 E – Cup 3

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
template <class T> void checkmin(T &t,T x){if (x < t) t = x;}
template <class T> void checkmax(T &t,T x){if (x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
#define foreach(it,v) for (__typeof((v).begin()) it = (v).begin();it != (v).end();it++)
const int N = 105555;
const int Mod = 1000000007;
int s1, s2;
int n;
int a[N];
int sum[N];
int F[2][N];
int *pf, *f;
 
int main(){
#ifdef cwj
	freopen("in", "r", stdin);
#endif
	while (scanf("%d%d", &s1, &s2) != EOF) {
		scanf("%d", &n);
		sum[0] = 0;
		for (int i=1;i<=n;i++) {
			scanf("%d",&a[i]);
			sum[i] = sum[i - 1] + a[i];
		}
		if (s1 > s2) swap(s1, s2);
		memset(F, 0, sizeof(F));
		F[0][0] = 1;
		pf = F[0];
		f = F[1];
		int Max = 0;
		for (int i=1;i<=n;i++) {
			int newMax = min(Max + a[i], s1);
			for (int j=0;j<=newMax;j++) f[j] = 0;
			for (int j=0;j<=Max;j++) {
				if (pf[j]) {
					if (j + a[i] <= s1) {
						f[j + a[i]] += pf[j];
						if (f[j + a[i]] >= Mod) f[j + a[i]] -= Mod;
					}
					if (!(a[i] & 1) && j + a[i] / 2 <= s1 && sum[i - 1] - j + a[i] / 2 <= s2) {
						f[j + a[i] / 2] += pf[j];
						if (f[j + a[i] / 2] >= Mod) f[j + a[i] / 2] -= Mod;
					}
					if (sum[i - 1] - j + a[i] <= s2) {
						f[j] += pf[j];
						if (f[j] >= Mod) f[j] -= Mod;
					}
				}
			}
			Max = newMax;
			swap(pf, f);
		}
		printf("%d\n", pf[s1]);
	}
 }


ZOJ3683 Simple Language

蘑菇题……慢慢磨就可以,不想磨了……= =b


ZOJ3684 Destroy

二分答案+树形dp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=10005;
int n,e,Center;
struct edge{int x,y,c,w;edge *next;}g[N*2],*ls[N];

void addedge(int x,int y,int c,int w){
	g[++e].x=x; g[e].y=y; g[e].c=c; g[e].w=w; g[e].next=ls[x]; ls[x]=&g[e];
}

void checkmax(int &t,int x){
	if (x>t) t=x;
}

namespace Gao1{
	int v[N],Min;
	int F[N][2];
	int From[N];
	int who[N][2];
	
	void update(int p,int key,int pos){
		if (F[p][0]==-1) { F[p][0]=key; who[p][0]=pos; }
		else if (key>F[p][0]){
			F[p][1]=F[p][0];
			who[p][1]=who[p][0];
			F[p][0]=key;
			who[p][0]=pos;
		}
		else if (key>F[p][1]){
			F[p][1]=key;
			who[p][1]=pos;
		}
	}
	
	void dfs(int p){
		v[p]=1;
		bool son=false;
		for (edge *t=ls[p];t;t=t->next)
			if (!v[t->y]){
				son=true;
				dfs(t->y);
				update(p,F[t->y][0]+t->c,t->y);
			}
		if (!son){
			F[p][0]=0;
			who[p][0]=p;
		}
	}
	
	void select(int p,int fa,int faw){
		From[p]=0;
		if (fa){
			From[p]=From[fa]+faw;
			if (who[fa][0]==p){
				if (F[fa][1]!=-1)
					checkmax(From[p],F[fa][1]+faw);
			}
			else{
				if (F[fa][0]!=-1)
					checkmax(From[p],F[fa][0]+faw);
			}
		}
		int now=max(F[p][0],F[p][1]);
		checkmax(now,From[p]);
		if (now<Min){
			Min=now;
			Center=p;
		}
		for (edge *t=ls[p];t;t=t->next)
			if (t->y!=fa)
				select(t->y,p,t->c);
	}

	void Find_Center(){
		memset(v,0,sizeof(v));
		memset(who,0,sizeof(who));
		memset(From,0,sizeof(From));
		for (int i=1;i<=n;i++) F[i][0]=F[i][1]=-1;
		dfs(1);
		Min=0x7FFFFFFF;
		select(1,0,0);
	}
}

namespace Gao2{
	int du[N];
	int v[N];
	int Limit;
	
	void dfs(int p){
		v[p]=1;
		for (edge *t=ls[p];t;t=t->next)
			if (!v[t->y] && t->w>Limit)
				dfs(t->y);
	}
	
	bool check(int mid){
		Limit=mid;
		memset(v,0,sizeof(v));
		dfs(Center);
		for (int i=1;i<=n;i++)
			if (du[i]==2 && v[i]) return false;
		return true;
	}

	void gao(){
		int l=0,r=100000000;
		memset(du,0,sizeof(du));
		for (int i=1;i<=e;i++){
			du[g[i].x]++;
			du[g[i].y]++;
		}
		while (l<r){
			int mid=(l+r)/2;
			if (check(mid)) r=mid;
			           else l=mid+1;
		}
		cout << l << endl;
	}
}

int main(){
	while (cin >> n){
		e=0;
		memset(ls,0,sizeof(ls));
		for (int i=1;i<n;i++){
			int x,y,c,w;
			scanf("%d%d%d%d",&x,&y,&c,&w);
			addedge(x,y,c,w);
			addedge(y,x,c,w);
		}
		Gao1::Find_Center();
		Gao2::gao();
	}
}

ZOJ3685 Cube

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int N = 10005;
const int M = 1 << 20;
int n;
char s[N];
int sum[M];
bool used[N];

#define abs(x) ((x) < 0 ? -(x) : (x))

int main() {
	for (int i = 0; i < M; i++) {
		sum[i] = 0;
		for (int j = 0; j < 20; j++) {
			if (i & 1 << j) {
				sum[i] += (j + 1) * (j + 1) * (j + 1);
			}
		}
	}
	while (scanf("%d", &n) == 1) {
		long long now = 0;
		int rest = n > 20 ? 20 : n;
		for (int i = n; i > rest; i--) {
			if (now > 0) {
				now -= (long long)(i) * i * i;
				used[i] = 0;
			} else {
				now += (long long)(i) * i * i;
				used[i] = 1;
			}
		}
		long long ans = 1LL << 50;
		int all = 0;
		int best_mask = -1;
		for (int i = 1; i <= rest; i++) all += i * i * i;
		for (int mask = 0; mask < 1 << rest; mask++) {
			long long tmp = abs(now + sum[mask] * 2 - all);
			if (tmp < ans) {
				ans = tmp;
				best_mask = mask;
			}
		}
		for (int i = 1; i <= rest; i++) used[i] = !!(best_mask & 1 << (i - 1));
		for (int i = n; i; i--) putchar(used[i] ? '+' : '-');
		puts("");
	}
}

SRM 567

Rating += 52

250
这个题写得圡爆了
因为bitset没有重载<弄了好久,最后直接重写了……搞得只剩100分多一点 太圡了。 本质是找<=n的数里面,分解素因子以后,指数奇偶性mask和自己相同的数的个数。 做法是把指数为奇的那些素数乘起来,然后得到一个最小的指数奇偶性mask和自己相同的数值。然后它可以乘的数就是一些完全平方数了。这个先把完全平方数存在一个vector里面然后lower_bound一下算数目就可以了。 500 先统计出每个字母的数目,如果想字典序最小,一定是aaabbbccc这样把相同的字母排在一起的形式。然后和另外的字符串比较的过程中,肯定都是先比a的数目,相等的话再比b的数目,如此下去…… 于是每次选一个X的拥有数目是最大之一的字母。如果此时,X是唯一一个最大的,那么就符合了,否则继续。 比赛的时候cha得不够果断啊,要不然起手就能cha两个500

int num[55][26];
int used[26];

vector  getWinningStrings(vector  S) {
	vector  ans;
	memset(num, 0, sizeof(num));
	int n = S.size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < S[i].size(); j++)
			num[i][S[i][j] - 'a']++;
	}
	for (int i = 0; i < n; i++) {
		bool flag = 0;
		memset(used, 0, sizeof(used));
		vector  vec;
		for (int j = 0; j < n; j++) if (j != i) vec.push_back(j);
		while (!flag) {
			bool found = 0;
			for (int j = 0; j < 26; j++) {
				if (!used[j]) {
					int Max = -1;
					foreach (it, vec)
						if (num[*it][j] > Max) Max = num[*it][j];
					if (Max < num[i][j]) {
						flag = 1;
						found = 1;
						break;
					}
					if (Max == num[i][j]) {
						found = 1;
						used[j] = 1;
						vector  tmp_vec;
						foreach (it, vec) {
							if (num[*it][j] == Max) tmp_vec.push_back(*it);
						}
						vec = tmp_vec;
						break;
					}
				}
			}
			if (!found) break;
		}
		if (flag) ans.push_back(i);
	}
	return ans;
}

1000
从后往前搜索,每次对后面的决策有影响的就是那些山的轮廓线……要注意这个轮廓线高度只可能+1 -1或者不变……所以可以用一个初始高度h0加上一个50位的三进制数表示。
然后用map记忆化搜索就好了。
……至于轮廓线数目为什么很少,我也不是很清楚-.-,但是感觉已经把本质相同的状态都合并了,也没有什么再可以利用的信息的,所以不这么做大概也没法做了。
值得一提的是,似乎用map < vector , int >这样的记忆化方法也可以过……真是好像敢写就敢过……
推荐[[iwi]]的代码
还有练习房里WJMZBMR的无节操hash压状态版本……

World Final Training 6——2012 Petr Mitrichev Contest 10

上次做完忘了贴了……存着以后好找
传送门
Board

没什么好说的,就是智商被碾压了。rank 3好像还不错,但人家这是单挑比赛好不好T_T
D这种构造题就是死活想不出555
F题和上年GCJ的某题有相似之处,但是birthday hack也死活hack不出来,也不会搞了。
膜拜一下总是随便虐场的WJMZBMR……
复习去了。