POJ3252
题意:求区间$[l, r]$内二进制表示中$0$的个数不少于$1$的个数的数字有多少个。
题解:只需分别求出$[1, r]$和$[1, l-1]$内满足要求的数的个数,相减即可。要求$[1, n]$内满足要求的个数,可以从高位到低位枚举$n$的二进制表示,如果某一位是$1$,那么这一位上是$0$的数一定都小于$n$(这一位前面的数和原数相同),因此可以直接暴力求出把这一位变成$0$之后满足要求的数的个数。当然也可以用数位DP的思想预处理。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: int l, r, c[40][40]; void input() { cin >> l >> r; } void init() { for (int i = 0; i < 40; ++ i) c[i][0] = c[i][i] = 1; for (int i = 2; i < 40; ++ i) for (int j = 1; j < i; ++ j) c[i][j] = c[i - 1][j] + c[i - 1][j - 1]; } int get_sum(int t) { int p = t, w = 0, z = 0, nz = 0, ret = 0; bool first = true; while (p) ++ w, p >>= 1; while (~ (-- w)) { if (t & (1 << w)) { for (int i = 1; i <= w; ++ i) { int len = w - i; for (int j = 0; j <= len; ++ j) { if (nz + 1 + j > z + len - j + (first ? 0 : i)) break; ret += c[len][j]; } } ++ nz, first = false; if (z + w >= nz) ++ ret; } else ++ z; } return ret; } void process() { cout << get_sum(r) - get_sum(l - 1) << endl; } public: void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1850
题意:将所有严格上升的字符串按字典序排序后依次编号。求字符串$s$的编号。
题解:令$f_{i, j}$表示以字母$i$开头的长度为$j$的严格上升字符串的个数。根据容斥原理,答案等于长度不大于$s.length()$的严格上升字符串的个数减去长度等于$s.length()$且字典序大于$s$的严格上升字符串的个数。前者可以直接由$f$得到,后者可以用数位DP的思想得到。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: int f[200][12]; string s; void input() { cin >> s; } void init() { for (int i = 'a'; i <= 'z'; ++ i) f[i][1] = 1; for (int i = 2; i <= 11; ++ i) for (int j = 'a'; j < 'z'; ++ j) for (int k = j + 1; k <= 'z'; ++ k) f[j][i] += f[k][i - 1]; } void process() { for (int i = 1; i < s.length(); ++ i) if (s[i] <= s[i - 1]) { cout << 0 << endl; return; } int ans = 0; for (int i = 1; i <= s.length(); ++ i) for (int j = 'a'; j <= 'z'; ++ j) ans += f[j][i]; for (int i = 0; i < s.length(); ++ i) for (int j = s[i] + 1; j <= 'z'; ++ j) ans -= f[j][s.length() - i]; cout << ans << endl; } public: void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1019
题意:定义字符串$s_i$为从$1$到$i$的数字连起来写。求$s_1s_2s_3…$中的第$n$个字符。
题解:先求出第$n$个字符在哪个$s$中,再求出它在$s$的哪个数字中,接着可以暴力出解。可以预处理出$s_i$的长度和$s_1s_2…s_i$的长度。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> typedef long long ll; using namespace std; struct Solver { private: static const int N = 50000; ll n, d[N], f[N], s[N], top, q[N]; void input() { cin >> n; } int get_digit(int t) { int ret = 0; while (t) t /= 10, ++ ret; return ret; } void process() { int rec; for (int i = 1; i <= 50000; ++ i) if (n <= s[i]) { rec = i - 1; break; } n -= s[rec]; for (int i = 1; i <= 50000; ++ i) if (n <= f[i]) { rec = i - 1; break; } n -= f[rec ++], top = 0; while (rec) q[++ top] = rec % 10, rec /= 10; if (n == 1) cout << q[top] << endl; if (n == 2) cout << q[top - 1] << endl; if (n == 3) cout << q[top - 2] << endl; if (n == 4) cout << q[top - 3] << endl; if (n == 5) cout << q[top - 4] << endl; } public: void init() { for (int i = 1; i <= 50000; ++ i) { d[i] = get_digit(i); f[i] = f[i - 1] + d[i]; s[i] = s[i - 1] + f[i]; if (s[i] > 2147483647) break; } } void solve() { input(), process(); } } solver; int main() { ios::sync_with_stdio(false); int T; cin >> T; solver.init(); while (T --) solver.solve(); return 0; }
POJ1942
题意:求${n+m \choose n}$的值,$n, m$和答案均为32位无符号整数。
题解:${n+m \choose n}={(n+m)! \over n!m!}=(m+1) \times (m+2) \div 2 \times (m+3) \div 3 \times … \times (m + n)\div n$。除非$m=0$,否则这个数是按指数级增长的。因此可以直接计算。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: unsigned long long n, m; bool input() { cin >> n >> m; if (! n && ! m) return false; return true; } void process() { if (n > m) swap(n, m); n += m; if (m == 0 || m == n) { cout << 1 << endl; return; } if (m == 1 || m == n - 1) { cout << n << endl; return; } ll ans = (m + 1) * (m + 2) / 2; for (int i = 3; i <= n - m; ++ i) { (ans *= (m + i)) /= i; } cout << ans << endl; } public: bool solve() { if (! input()) return false; process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ2635
题意:给定一个最多$100$位的数字,已知它是由两个质数相乘得到的。问那两个质数中较小的数是否比$l (l \le 10^6)$大。
题解:将$10^6$以内的质数全部筛出来,直接枚举每个质数,高精度取模,判断是否整除。压10位就能AC。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> typedef long long ll; using namespace std; const ll BASE[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000}; struct Prime { private: static const ll N = 1000000; bool vis[N + 1]; public: ll prime[N + 1]; void init() { memset(prime, 0, sizeof prime); memset(vis, false, sizeof vis); for (ll i = 2; i <= N; ++ i) { if (! vis[i]) prime[++ prime[0]] = i; for (ll j = 1; j <= prime[0] && i * prime[j] <= N; ++ j) { vis[i * prime[j]] = true; if (! (i % prime[j])) break; } } } } prime; struct Solver { private: static const ll N = 15; ll l, a[N], b[N]; string k; bool input() { cin >> k >> l; if (k == "0" && ! l) return false; return true; } bool check(ll t) { for (ll i = 0; i <= a[0]; ++ i) b[i] = a[i]; for (ll i = *b; i > 1; -- i) b[i - 1] += b[i] % t * BASE[10]; return ! (b[1] % t); } void init() { ll cnt = 0; a[0] = 1, a[a[0]] = 0; for (ll i = k.length() - 1; ~ i; -- i) { if (cnt == 10) cnt = 0, a[++ a[0]] = 0; a[a[0]] += (k[i] - '0') * BASE[cnt ++]; } for (ll i = 1; i <= prime.prime[0] && prime.prime[i] < l; ++ i) if (check(prime.prime[i])) { cout << "BAD " << prime.prime[i] << endl; return; } cout << "GOOD" << endl; } public: bool solve() { if (! input()) return false; init(); return true; } } solver; int main() { ios::sync_with_stdio(false); prime.init(); while (solver.solve()) ; return 0; }
POJ3292
题意:定义H数为$4n+1 (n \in N)$。H数分为三类:单位($1$),不能由其他非单位H数相乘得到的数(H质数),以及剩下的所有数(H合数)。求给定数以内恰由两个H质数相乘得到的数的个数。
题解:筛出所有H质数,然后暴力枚举任意两个相乘。由于给定数的范围不超过$1000001$,因此相乘不超过这个范围的H质数对比较少。最后求一个前缀和即可。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> typedef long long ll; using namespace std; struct Solver { private: static const int N = 1000001; ll n, top, num[N + 1], tot, prime[N + 1], sum[N + 1]; bool vis[N + 1]; bool input() { cin >> n; return n; } void process() { cout << n << ' ' << sum[n] << endl; } public: void init() { for (int i = 1; (i << 2) + 1 <= N; ++ i) num[++ top] = (i << 2) + 1; for (int i = 1; i <= top; ++ i) if (! vis[num[i]]) { prime[++ tot] = num[i]; for (int j = num[i] << 1; j <= N; j += num[i]) vis[j] = true; } memset(vis, false, sizeof vis); for (int i = 1; i <= tot; ++ i) for (int j = i; j <= tot && prime[i] * prime[j] <= N; ++ j) vis[prime[i] * prime[j]] = true; for (int i = 1; i <= N; ++ i) sum[i] = sum[i - 1] + vis[i]; } bool solve() { if (! input()) return false; process(); return true; } } solver; int main() { ios::sync_with_stdio(false); solver.init(); while (solver.solve()) ; return 0; }
POJ1845
题意:求$A^B$的约数和$S$。
题解:若$n=p_1^{a_1}p_2^{a_2}…p_m^{a_m}$,则$S=(p_1^0+p_1^1+…+p_1^{a_1})(p_2^0+p_2^1+…+p_2^{a_2})…(p_m^0+p_m^1+…+p_m^{a_m})$。将$A$分解质因数,把每个因数的个数乘上$B$,用等比数列求和公式求和,最后累乘得到答案。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> typedef long long ll; using namespace std; struct Solver { private: static const ll MOD = 9901; ll a, b; void input() { cin >> a >> b; } ll power(ll a, ll b) { ll ret = 1; while (b) { if (b & 1) (ret *= a) %= MOD; (a *= a) %= MOD, b >>= 1; } return ret; } ll get_inv(ll t) { return power(t, MOD - 2); } void init() { if (a == 0) { cout << 0 << endl; return; } ll ans = 1, q = (ll) sqrt(a); for (int i = 2; i <= q; ++ i) { if (! (a % i)) { ll tot = 0; while (! (a % i)) ++ tot, a /= i; tot *= b; if (i % MOD == 1) { (ans *= tot + 1) %= MOD; } else { (ans *= (1 - power(i, tot + 1)) * get_inv(1 - i) % MOD) %= MOD; } } } if (a > 1) { ll tot = b; if (a % MOD == 1) (ans *= tot + 1) %= MOD; else (ans *= (1 - power(a, tot + 1)) * get_inv(1 - a) % MOD) %= MOD; } cout << (ans % MOD + MOD) % MOD << endl; } public: void solve() { input(), init(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ2115
题意:有如下程序:
for (variable = A; variable != B; variable += C) statement;
已知$A, B, C$均为$k$位无符号整型。给定$A, B, C, k$,问该循环能执行几次。
题解:由题意得到方程$A+Cx \equiv B \pmod {2^k}$,化简得$Cx \equiv B-A \pmod {2^k}$。这是一个单变元模线性方程。下面来解该方程。
设方程为$ax \equiv b \pmod n$,它等价于$ax-ny=b$。首先求出$d=gcd(a, n)$,如果$d \not \mid b$,则方程无解。否则,方程两边同除以$d$,得到$a’x-n’y=b’$,此时$(a’, n’)=1$,用exgcd求出$a’x-n’y=1$的解$x_0$,$x=x_0 \times b’$即得到原方程的一个解。其他$d-1$个解可以通过这个解加若干次$b’=b/d$得到。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> typedef long long ll; typedef unsigned long long ull; using namespace std; struct Solver { private: ll a, b, c, k, mod; bool input() { cin >> a >> b >> c >> k; return a || b || c || k; } void init() { mod = 1ll << k, b -= a; if (b < 0) b += mod; } ll get_gcd(ll a, ll b, ll &x, ll &y) { if (! b) { x = 1, y = 0; return a; } ll ret = get_gcd(b, a % b, y, x); y -= a / b * x; return ret; } void process() { ll x, y, gcd = get_gcd(c, mod, x, y); ((x %= mod) += mod) %= mod; if (b % gcd) cout << "FOREVER" << endl; else cout << (ull) x * (b / gcd) % (mod / gcd) << endl; } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ3273
题意:有$N$个数排成一行,要将它们分成恰好$M$组,使得每一组数字之和的最大值最小,求这个最小值。
题解:直接二分答案,贪心判断是否可行。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> typedef long long ll; using namespace std; struct Solver { private: static const ll N = 100000; ll n, m, a[N + 1], ma; void input() { cin >> n >> m; for (ll i = 1; i <= n; ++ i) cin >> a[i], ma = max(ma, a[i]); } bool check(ll t) { ll tot = 0, cnt = 1; for (int i = 1; i <= n; ++ i) { tot += a[i]; if (tot > t) tot = a[i], ++ cnt; if (cnt > m) return false; } return cnt <= m; } void process() { ll l = ma, r = ma * 10000; while (l < r) { ll mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } cout << l << endl; } public: void solve() { input(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ3258
题意:在$N$个数中恰好删去$M$个数,使得剩下的数中每两个数之差的最小值最大,求这个最大值。
题解:先将$N$个数排序,接着二分最大值,利用贪心判断是否可行。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> typedef long long ll; using namespace std; struct Solver { private: static const ll N = 50000; ll len, n, m, a[N + 1]; void input() { scanf("%lld%lld%lld", &len, &n, &m); for (ll i = 1; i <= n; ++ i) scanf("%lld", &a[i]); a[++ n] = len; } void init() { sort(a, a + n + 1); } bool check(ll t) { ll last = 0, tot = 0; for (int i = 1; i <= n; ++ i) { if (a[i] - last < t) ++ tot; else last = a[i]; } return tot <= m; } void process() { ll l = 1, r = len + 1; while (l + 1 < r) { ll mid = l + r >> 1; if (check(mid)) l = mid; else r = mid; } printf("%lld\n", l); } public: void solve() { input(), init(), process(); } } solver; int main() { solver.solve(); return 0; }
POJ1905
题意:给定弓形的弧长$l$和弦长$a$,求弧的顶端到弦的距离。
题解:二分答案。可以发现距离越大弧越长。设距离为$x$,圆的半径为$r$,则$(r-x)^2+({a \over 2})^2=r^2$,化简得$r={x^2+({a \over 2})^2 \over 2x}$,接着可以用三角函数计算出弧长,和$l$比较,决定向哪边二分。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> typedef double ld; using namespace std; struct Solver { private: ld a, b, c, l; bool input() { cin >> a >> b >> c; return a >= 0 && b >= 0 && c >= 0; } void init() { l = (1 + b * c) * a; } void process() { ld L = 0.0, M, R = 0.5 * a; while (R - L > 1e-5) { M = (L + R) / 2; ld r = (M * M + a * a / 4) / 2 / M; ld len = 2 * r * asin(a / 2 / r); if (len < l) L = M; else R = M; } cout << setprecision(3) << fixed << M << endl; } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ3122
题意:有$N$块饼和$F$个人,要求每个人分到大小相同的饼,且任意一个人分到的饼都来自同一块饼上,求每个人最多能拿到多大的饼。
题解:二分答案。易知每个人分的饼越大,能分的人就越少。对于每个答案可以直接计算能分多少人。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> typedef double ld; using namespace std; struct Solver { private: static const ld PI = 3.14159265359; static const int N = 10000; int n, f; ld a[N + 1]; void input() { scanf("%d%d", &n, &f), ++ f; for (int i = 1; i <= n; ++ i) scanf("%lf", &a[i]), a[i] *= a[i]; } void process() { ld l = 0, r = 100000000; while (r - l > 1e-7) { ld mid = (l + r) / 2; ld sum = 0; for (int i = 1; i <= n; ++ i) { sum += floor(a[i] / mid); if (sum >= f) break; } if (sum >= f) l = mid; else r = mid; } cout << setprecision(4) << fixed << l * PI << endl; } public: void solve() { input(), process(); } } solver; int main() { int T; scanf("%d", &T); while (T --) solver.solve(); return 0; }
POJ2031
题意:空间中有$N$个球,给定每个球的半径和球心的坐标,求将这些球全部连起来至少需要多长的线。两球相连的条件是两球相交或两球间有连线。
题解:易知两球间所需连线的长度为$len_{i, j}=max(0, dist_{i, j}-r_i-r_j)$。将所有$len_{i, j}$存下来之后做一次最小生成树就可以了。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> typedef double ld; using namespace std; struct Ball { public: ld x, y, z, r; ld get_dist(Ball a) { return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y) + (z - a.z) * (z - a.z)) - r - a.r; } }; struct Line { public: int a, b; ld w; bool operator < (const Line &a) const { return w < a.w; } }; struct UnionFind { private: static const int N = 100; int fa[N + 1]; int get_fa(int t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); } public: void init() { for (int i = 1; i <= N; ++ i) fa[i] = i; } void merge(int a, int b) { fa[get_fa(b)] = get_fa(a); } bool query(int a, int b) { return get_fa(a) == get_fa(b); } }; struct Solver { private: static const int N = 100; int n, top; ld ans; Ball ball[N + 1]; Line line[N * N]; UnionFind union_find; bool input() { cin >> n; if (! n) return false; for (int i = 1; i <= n; ++ i) cin >> ball[i].x >> ball[i].y >> ball[i].z >> ball[i].r; return true; } void init() { top = ans = 0; for (int i = 1; i < n; ++ i) { for (int j = i + 1; j <= n; ++ j) { ld dist = ball[i].get_dist(ball[j]); if (dist < 0) line[++ top] = (Line) {i, j, 0}; else line[++ top] = (Line) {i, j, dist}; } } sort(line + 1, line + top + 1); } void process() { union_find.init(); for (int i = 1; i <= top; ++ i) { if (! union_find.query(line[i].a, line[i].b)) { ans += line[i].w; union_find.merge(line[i].a, line[i].b); } } cout << setprecision(3) << fixed << ans << endl; } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ1039
题意:有一个管道,其竖直截面的宽度恒为$1$。给定上半轨道折线各点的坐标,求从左管口射入一道光所能到达的$x$坐标的最大值。
题解:对于一条不经过上半轨道或下半轨道任何一个点的一条光线,一定存在一条光线分别经过上、下半轨道的至少一个折点,并且不比这条光线的最远距离近。因此可以枚举经过上半轨道的哪个点和下半轨道的哪个点,计算出这条光线能到达的最远距离。可以用叉积来判断线段和直线是否相交。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> typedef double ld; using namespace std; const ld EPS = 1e-8; int cmp(ld t) { if (fabs(t) < EPS) return 0; if (t > 0) return 1; return -1; } struct Point { public: ld x, y; Point(ld a = 0, ld b = 0) : x(a), y(b) {} 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 ld &a) const { return Point(x * a, y * a); } Point operator / (const ld &a) const { return Point(x / a, y / a); } ld operator % (const Point &a) const { return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)); } ld operator * (const Point &a) const { return x * a.y - y * a.x; } ld operator ^ (const Point &a) const { return x * a.x + y * a.y; } }; struct Line { public: Point a, b; Line(Point x = Point(), Point y = Point()) : a(x), b(y) { if (a.x > b.x) swap(a, b); } bool operator | (const Line &x) const { return cmp((b - a) * (x.a - b)) == 1 && cmp((b - a) * (x.b - b)) == -1 || cmp((b - a) * (x.a - b)) == -1 && cmp((b - a) * (x.b - b)) == 1; } Point operator * (const Line &x) const { Point ret = a; ld t = (a - x.a) * (x.a - x.b) / ((a - b) * (x.a - x.b)); return ret + (b - a) * t; } ld ratio() { return (b.y - a.y) / (b.x - a.x); } }; struct Solver { private: static const int N = 20; int n; Point point[N + 1 << 1]; Line line[N + 1 << 1]; bool input() { cin >> n; if (! n) return false; for (int i = 1; i <= n; ++ i) cin >> point[i].x >> point[i].y, point[i + n] = point[i] - Point(0, 1); return true; } void init() { for (int i = 1; i < n; ++ i) { line[(i << 1) - 1] = Line(point[i], point[i + 1]); line[i << 1] = Line(point[i + n], point[i + n + 1]); } } void process() { ld ans = -1e18, far; for (int i = 1; i <= n; ++ i) { for (int j = n + 1; j <= n << 1; ++ j) { if (i + n != j) { Line tmp = Line(point[i], point[j]); if (tmp | Line(point[1], point[1 + n]) || ! cmp((tmp.b - tmp.a) * (point[1] - tmp.b)) || ! cmp((tmp.b - tmp.a) * (point[1 + n] - tmp.b))) { far = point[n].x; for (int k = 1; k <= n - 1 << 1; ++ k) { if (tmp | line[k]) far = min(far, (tmp * line[k]).x); if (! cmp((tmp.b - tmp.a) * (line[k].a - tmp.b))) { if (k & 1) { if (tmp.ratio() > line[k].ratio()) far = min(far, line[k].a.x); } else { if (tmp.ratio() < line[k].ratio()) far = min(far, line[k].a.x); } } } if (far == point[n].x) { cout << "Through all the pipe." << endl; return; } ans = max(ans, far); } } } } cout << setprecision(2) << fixed << ans << endl; } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ1408
题意:在一个$1 \times 1$的正方形的四条边上分别有$n$个点,从左往右依次将上下两条边上的点连接起来,从下往上依次将左右两条边上的点连接起来。求这些线和正方形所围成的$(n+1)^2$个区域中面积最大的区域的面积。
题解:先把所有交点求出来,然后枚举每一个区域,用叉积求出面积。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; struct Point { public: double x, y; Point(double a = 0, double b = 0) : x(a), y(b) {} 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; } double operator ^ (const Point &a) const { return x * a.x + y * a.y; } double operator % (const Point &a) const { return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)); } }; struct Line { public: Point a, b; Line(Point x = Point(), Point y = Point()) : a(x), b(y) {} double operator * (const Line &x) { return abs((b - a) * (x.b - x.a)); } Point operator & (const Line &x) { double t = (a - x.a) * (x.a - x.b) / ((a - b) * (x.a - x.b)); return a + (b - a) * t; } }; struct Solver { private: static const int N = 30; int n; double pos[4][N + 1]; Point inter[N + 2][N + 2]; Line r[N + 2], c[N + 2]; bool input() { cin >> n; if (! n) return false; for (int i = 1; i <= 4; ++ i) for (int j = 1; j <= n; ++ j) cin >> pos[i][j]; return true; } void init() { r[0] = Line(Point(0, 0), Point(1, 0)); for (int i = 1; i <= n; ++ i) r[i] = Line(Point(0, pos[3][i]), Point(1, pos[4][i])); r[n + 1] = Line(Point(0, 1), Point(1, 1)); c[0] = Line(Point(0, 0), Point(0, 1)); for (int i = 1; i <= n; ++ i) c[i] = Line(Point(pos[1][i], 0), Point(pos[2][i], 1)); c[n + 1] = Line(Point(1, 0), Point(1, 1)); for (int i = 0; i <= n + 1; ++ i) for (int j = 0; j <= n + 1; ++ j) inter[i][j] = r[i] & c[j]; } void process() { double ans = 0; for (int i = 0; i <= n; ++ i) for (int j = 0; j <= n; ++ j) ans = max(ans, Line(inter[i][j], inter[i][j + 1]) * Line(inter[i][j + 1], inter[i + 1][j + 1]) + Line(inter[i][j], inter[i + 1][j]) * Line(inter[i + 1][j], inter[i + 1][j + 1])); cout << setprecision(6) << fixed << ans / 2 << endl; } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ1584
题意:按顺/逆时针方向给定一个$n$边形的顶点坐标,判断它是否是凸包,若是,则判断给定的圆是否完全在它内部。
题解:因为已经按顺/逆时针方向给定顶点,因此可以直接枚举每一条边,判断下一个点在它的哪一侧(要注意处理共线的情况)。如果全部同侧则是凸包。要判断圆,得先判断圆心是否在凸包内部。显然,如果圆心在凸包内部,那么它和每条边两个端点所构成夹角的和等于$2 \pi$。接着,计算圆心到每条边的距离,如果到某条边的距离小于圆的半径,则圆不完全在凸包内部。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const double EPS = 1e-6; int cmp(double t) { if (fabs(t) < EPS) return 0; if (t > 0) return 1; return -1; } struct Point { public: double x, y; Point(double a = 0, double b = 0) : x(a), y(b) {} 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; } double operator & (const Point &a) const { return x * a.x + y * a.y; } double operator % (const Point &a) const { return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)); } double operator ^ (const Point &a) const { return acos(( *this & a) / ( *this % Point() * (a % Point()))); } }; struct Line { Point a, b; Line(Point x = Point(), Point y = Point()) : a(x), b(y) {} int operator | (const Point &x) const { return cmp((b - a) * (x - b)); } double operator % (const Point &x) const { return fabs((a - x) * (b - x) / (a % b)); } double operator ^ (const Point &x) const { return (a - x) ^ (b - x); } }; struct Solver { private: static const int N = 100000; int n, dire[N + 1]; double r, sum; Point point[N + 1], circle; Line line[N + 1]; bool input() { cin >> n; if (n < 3) return false; cin >> r >> circle.x >> circle.y; for (int i = 1; i <= n; ++ i) cin >> point[i].x >> point[i].y; for (int i = 1; i < n; ++ i) line[i] = Line(point[i], point[i + 1]); line[n] = Line(point[n], point[1]); return true; } void init() { sum = 0; for (int i = 1; i <= n; ++ i) sum += line[i] ^ circle; for (int i = 1; i < n - 1; ++ i) dire[i] = line[i] | point[i + 2]; dire[n - 1] = line[n - 1] | point[1], dire[n] = line[n] | point[2]; } void process() { bool f1 = false, f2 = false; for (int i = 1; i <= n; ++ i) { if (dire[i] == 1) f1 = true; if (dire[i] == -1) f2 = true; } if (f1 && f2) { cout << "HOLE IS ILL-FORMED" << endl; return; } if (! ~ cmp(sum - 2 * acos(-1))) { cout << "PEG WILL NOT FIT" << endl; return; } for (int i = 1; i <= n; ++ i) { if (! ~ cmp(line[i] % circle - r)) { cout << "PEG WILL NOT FIT" << endl; return; } } cout << "PEG WILL FIT" << endl; } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ1026
题意:给定一个$n$的置换,求一个字符串$s$经过$k$次置换后得到的字符串。
题解:找出置换中的每个循环节,即可直接求出新字符串每一位对应原字符串的哪一位。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 200; int n, a[N + 1], top, num[N + 1][N + 1], belong[N + 1], pos[N + 1]; bool vis[N + 1]; bool input() { cin >> n; if (! n) return false; for (int i = 1; i <= n; ++ i) cin >> a[i]; return true; } void init() { top = 0; memset(num, 0, sizeof num); memset(vis, false, sizeof vis); for (int i = 1; i <= n; ++ i) { if (! vis[i]) { int t = i; ++ top; while (! vis[t]) { vis[t] = true; num[top][++ num[top][0]] = t; belong[t] = top; pos[t] = num[top][0]; t = a[t]; } } } } bool process() { int k; cin >> k; if (! k) return false; string s; getline(cin, s); int len = s.length() - 1; while (len < n) { s += " ", ++ len; } string ans = ""; for (int i = 1; i <= len; ++ i) { int t = belong[i]; ans += s[num[t][(pos[i] - k % num[t][0] + num[t][0] - 1) % num[t][0] + 1]]; } cout << ans << endl; return true; } public: bool solve() { if (! input()) return false; init(); while (process()) ; return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) cout << endl; return 0; }
POJ1054
题意:青蛙经过农田时的痕迹是一条直线。农田里的植物就在这个农田的二维坐标系的整数格点上。如果某只青蛙经过农田,也就是某条直线穿过农田,那么那条直线经过的所有的整数格点上的植物会都会被破坏掉。现在给出所有被破坏的植物的位置,问哪只青蛙破坏的最多。
题解:暴力枚举每两个点所构成的直线,直接计算直线上有几个整点。由于很多点对会重复计算,所以可以剪枝,降低复杂度。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 5000; static const int MOD = 8000009; int r, c, n; bool vis[N + 1][N + 1]; struct Point { int x, y; bool operator < (const Point &a) const { return y == a.y ? x < a.x : y < a.y; } }; Point point[N + 1]; void input() { cin >> r >> c >> n; for (int i = 1; i <= n; ++ i) cin >> point[i].x >> point[i].y, vis[point[i].x][point[i].y] = true; } void init() { sort(point + 1, point + n + 1); int ans = 0; for (int i = 1; i < n; ++ i) { for (int j = i + 1; j <= n; ++ j) { Point s = point[i], t = point[j]; int dx = t.x - s.x, dy = t.y - s.y, tx = t.x + dx, ty = t.y + dy; if (s.x - dx > 0 && s.x - dx <= r && s.y - dy > 0 && s.y - dy <= c) continue; int cnt = 0; while (tx > 0 && tx <= r && ty > 0 && ty <= c) { if (vis[tx][ty]) ++ cnt; else { cnt = 0; break; } tx += dx, ty += dy; } ans = max(ans, cnt); } } if (ans) cout << ans + 2 << endl; else cout << 0 << endl; } public: void solve() { input(), init(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1066
题意:有一个$100 \times 100$的正方形,内部有$n$条线,每条线的两个端点位于正方形两条不同的边上。给定正方形内部的一个点$p$,求它最少穿过多少条线能到达正方形外部。
题解:由于所有线的端点都在正方形的边上,所以从点$p$到正方形边上任意一点穿过线的最少数目就等于从点$p$到那个点的线段穿过线的数目。因此可以直接枚举每条线的端点,计算它和$p$点所构成的线段穿过了多少条线,取最小值加一就是最后答案。要注意$n$等于$0$时答案是$1$。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const double EPS = 1e-6; int cmp(double t) { if (fabs(t) < EPS) return 0; if (t > 0) return 1; return -1; } bool between(double a, double b, double c) { return cmp(a - min(b, c)) == 1 && cmp(max(b, c) - a) == 1; } struct Point { public: double x, y; Point(double a = 0, double b = 0) : x(a), y(b) {} 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; } double operator & (const Point &a) const { return x * a.x + y * a.y; } double operator % (const Point &a) const { return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)); } }; struct Line { public: Point a, b; Line(Point x = Point(), Point y = Point()) : a(x), b(y) {} int operator | (const Line &x) const { return cmp((b - a) * (x.b - x.a)); } Point operator & (const Line &x) const { double t = (a - x.a) * (x.a - x.b) / ((a - b) * (x.a - x.b)); return a + (b - a) * t; } }; struct Solver { private: static const int N = 30; int n; Point point[N + 1 << 1], p; Line line[N + 1]; void input() { cin >> n; for (int i = 1; i <= n; ++ i) { cin >> point[(i << 1) - 1].x >> point[(i << 1) - 1].y >> point[i << 1].x >> point[i << 1].y; line[i] = Line(point[(i << 1) - 1], point[i << 1]); } cin >> p.x >> p.y; } void process() { if (n == 0) { cout << "Number of doors = " << 1 << endl; return; } int ans = 1000; for (int i = 1; i <= n << 1; ++ i) { Line tmp(p, point[i]); int cnt = 0; for (int j = 1; j <= n; ++ j) { if (! (tmp | line[j])) continue; Point inter = tmp & line[j]; if ((between(inter.x, tmp.a.x, tmp.b.x) || between(inter.y, tmp.a.y, tmp.b.y)) && (between(inter.x, line[j].a.x, line[j].b.x) || between(inter.y, line[j].a.y, line[j].b.y))) ++ cnt; } ans = min(ans, cnt); } cout << "Number of doors = " << ans + 1 << endl; } public: void solve() { input(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1095
题意:将二叉树按以下要求标号:①空节点为标号为$0$;②一个节点标号为$1$;③节点少的树比节点多的树的标号小;④节点相同的情况下,左子树标号较小的树标号较小;⑤节点相同且左子树标号相同的情况下,右子树标号较小的树标号较小。按格式输出第$n$棵树的形状。
题解:由$n$个节点构成的二叉树的数量满足卡特兰数。我们可以先求出这棵树由几个节点构成,以及这棵树在节点数和它相同的树中的排名。这样,就可以对左右子树递归处理。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int c[] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190}; struct Solver { private: static const int N = 100000; int n; bool input() { cin >> n; return n; } void process(int t, int node) { if (node == 1) { cout << 'X'; return; } int tmp = t, i; for (i = 0; i < 20; ++ i) { if (tmp <= c[i] * c[node - 1 - i]) break; tmp -= c[i] * c[node - 1 - i]; } if (i) cout << '(', process((tmp - 1) / c[node - 1 - i] + 1, i), cout << ')'; cout << 'X'; if (node - 1 - i) cout << '(', process((tmp - 1) % c[node - 1 - i] + 1, node - 1 - i), cout << ')'; } public: bool solve() { if (! input()) return false; int tmp = n, i; for (i = 1; i < 20; ++ i) { if (tmp <= c[i]) break; tmp -= c[i]; } process(tmp, i), cout << endl; return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ1113
题意:要用尽量短的线将给定的$N$个点围起来,并且线上任意一点到每个点的距离不小于$L$,求线的长度。
题解:用尽量短的线将点围起来,显然是要求凸包。然而还要求到每个点的距离不小于$L$,可以将凸包上的每一条线段沿法线方向向外平移$L$,再用半径为$L$的圆弧将线段连起来。易知所有圆弧加起来刚好是一个圆。因此先求出凸包周长,再加上半径为$L$的圆的周长,就是最后答案。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const double EPS = 1e-6; int cmp(double t) { if (fabs(t) < EPS) return 0; if (t > 0) return 1; return -1; } struct Point { public: double x, y; Point(double a = 0, double b = 0) : x(a), y(b) {} bool operator < (const Point &a) const { return x == a.x ? y < a.y : x < a.x; } Point operator - (const Point &a) const { return Point(x - a.x, y - a.y); } double operator * (const Point &a) const { return x * a.y - y * a.x; } double operator % (const Point &a) const { return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)); } }; struct Line { public: Point a, b; Line(Point x = Point(), Point y = Point()) : a(x), b(y) {} int operator | (const Point &x) const { return cmp((b - a) * (x - b)); } }; struct Solver { private: static const int N = 1000; int n, l, s[N + 1], res[N + 1]; Point point[N + 1]; void input() { cin >> n >> l; for (int i = 1; i <= n; ++ i) cin >> point[i].x >> point[i].y; } void init() { sort(point + 1, point + n + 1); s[1] = 1; for (int i = 2; i <= n; ++ i) if (point[i].x > point[1].x) { s[s[0] = 2] = i; break; } for (int i = s[s[0]] + 1; i <= n; ++ i) { while (s[0] > 1 && (Line(point[s[s[0] - 1]], point[s[s[0]]]) | point[i]) < 1) -- s[0]; if (s[0] == 1 || (Line(point[s[s[0] - 1]], point[s[s[0]]]) | point[i]) > -1) s[++ s[0]] = i; } for (int i = 1; i <= s[0]; ++ i) res[++ res[0]] = s[i]; for (int i = n - 1; i; -- i) if (point[i].x < point[n].x) { s[1] = i + 1, s[s[0] = 2] = i; break; } for (int i = s[s[0]] - 1; i; -- i) { while (s[0] > 1 && (Line(point[s[s[0] - 1]], point[s[s[0]]]) | point[i]) < 1) -- s[0]; if (s[0] == 1 || (Line(point[s[s[0] - 1]], point[s[s[0]]]) | point[i]) > -1) s[++ s[0]] = i; } for (int i = 2; i < s[0]; ++ i) res[++ res[0]] = s[i]; } void process() { double ans = 0; for (int i = 1; i < res[0]; ++ i) ans += point[res[i]] % point[res[i + 1]]; ans += point[res[res[0]]] % point[res[1]]; cout << (int) (ans + 2 * acos(-1) * l + 0.5) << endl; } public: void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1151
题意:给定平面直角坐标系内的$n$个矩形,求它们覆盖的面积。矩形顶点坐标不一定是整数。
题解:先将矩形离散化,接着用扫描线+线段树的方法求矩形面积并——从左往右扫描坐标系,扫到一个矩形的左边界时将它加入线段树,扫到一个矩形的右边界时将它从线段树中删除。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; const int N = 100; double xmap[N + 1 << 1], ymap[N + 1 << 1]; struct Point { int id, nx, ny; double x, y; }; struct Line { int x, y1, y2, val; bool operator < (const Line &a) const { return x == a.x ? val > a.val : x < a.x; } }; bool cmpx(Point a, Point b) { return a.x < b.x; } bool cmpy(Point a, Point b) { return a.y < b.y; } bool cmpi(Point a, Point b) { return a.id < b.id; } struct SegmentTree { private: static const int N = 1000; int tot; struct Node { int l, r, child[2], val; double sum; } node[N]; void build_tree(int root) { node[root].child[0] = node[root].child[1] = node[root].sum = 0; if (node[root].l == node[root].r) return; int mid = node[root].l + node[root].r >> 1; node[++ tot].l = node[root].l, node[tot].r = mid; node[root].child[0] = tot, build_tree(tot); node[++ tot].l = mid + 1, node[tot].r = node[root].r; node[root].child[1] = tot, build_tree(tot); } void update(int root) { if (node[root].l == node[root].r) return; if (node[root].val) node[root].sum = ymap[node[root].r + 1] - ymap[node[root].l]; else node[root].sum = node[node[root].child[0]].sum + node[node[root].child[1]].sum; } void insert_line(int root, int l, int r, int val) { if (node[root].l > r || node[root].r < l) return; if (node[root].l >= l && node[root].r <= r) { node[root].val += val; if (node[root].val) node[root].sum = ymap[node[root].r + 1] - ymap[node[root].l]; else node[root].sum = 0; update(root); return; } insert_line(node[root].child[0], l, r, val); insert_line(node[root].child[1], l, r, val); update(root); } public: void init(int n) { node[node[tot = 1].l = 1].r = n, build_tree(1); } void add(int l, int r, int val) { insert_line(1, l, r - 1, val); } double get() { return node[1].sum; } }; struct Solver { private: static const int N = 100; int n, cas; Point point[N + 1 << 1]; Line line[N + 1 << 1]; SegmentTree tree; bool input() { cin >> n; if (! n) return false; for (int i = 1; i <= n; ++ i) { cin >> point[(i << 1) - 1].x >> point[(i << 1) - 1].y >> point[i << 1].x >> point[i << 1].y; point[(i << 1) - 1].id = (i << 1) - 1, point[i << 1].id = i << 1; } return true; } void init() { sort(point + 1, point + (n << 1) + 1, cmpx); point[1].nx = 1, xmap[1] = point[1].x; for (int i = 2; i <= n << 1; ++ i) { if (point[i].x == point[i - 1].x) point[i].nx = point[i - 1].nx; else point[i].nx = point[i - 1].nx + 1, xmap[point[i].nx] = point[i].x; } sort(point + 1, point + (n << 1) + 1, cmpy); point[1].ny = 1, ymap[1] = point[1].y; for (int i = 2; i <= n << 1; ++ i) { if (point[i].y == point[i - 1].y) point[i].ny = point[i - 1].ny; else point[i].ny = point[i - 1].ny + 1, ymap[point[i].ny] = point[i].y; } sort(point + 1, point + (n << 1) + 1, cmpi); for (int i = 1; i <= n; ++ i) { line[(i << 1) - 1].x = point[(i << 1) - 1].nx; line[(i << 1) - 1].y1 = point[(i << 1) - 1].ny; line[(i << 1) - 1].y2 = point[i << 1].ny; line[(i << 1) - 1].val = 1; line[i << 1].x = point[i << 1].nx; line[i << 1].y1 = point[(i << 1) - 1].ny; line[i << 1].y2 = point[i << 1].ny; line[i << 1].val = -1; } sort(line + 1, line + (n << 1) + 1); tree.init(n << 1); } void process() { int t; double ans = 0; for (int i = 1; i <= n << 1; ++ i) { if (line[i].x == line[1].x) tree.add(line[i].y1, line[i].y2, line[i].val); else { t = i; break; } } while (t <= n << 1) { ans += tree.get() * (xmap[line[t].x] - xmap[line[t - 1].x]); int xx = line[t].x; while (t <= n << 1 && line[t].x == xx) tree.add(line[t].y1, line[t].y2, line[t].val), ++ t; } cout << "Total explored area: " << setprecision(2) << fixed << ans << endl << endl; } public: bool solve() { if (! input()) return false; cout << "Test case #" << ++ cas << endl; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ1166
题意:有$9$个钟,排成三行三列。每个钟只会指向0、3、6、9点。现要求所有钟指向0点,每次只能顺时针旋转一次规定组合的钟:1245、2356、4578、5689、123、789、147、369、24568,求最少需要旋转几次,并输出方案。
题解:可以发现每种组合最多旋转$3$次,因此可以$4^9$枚举每种组合旋转了几次,判断是否满足要求,同时保存答案。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 9; int a[N + 1], b[N + 1], tot, ans[N + 1]; void input() { for (int i = 1; i <= 9; ++ i) cin >> a[i]; } void process() { tot = 1e9; for (int i1 = 0; i1 < 4; ++ i1) for (int i2 = 0; i2 < 4; ++ i2) for (int i3 = 0; i3 < 4; ++ i3) for (int i4 = 0; i4 < 4; ++ i4) for (int i5 = 0; i5 < 4; ++ i5) for (int i6 = 0; i6 < 4; ++ i6) for (int i7 = 0; i7 < 4; ++ i7) for (int i8 = 0; i8 < 4; ++ i8) for (int i9 = 0; i9 < 4; ++ i9) { if (i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 >= tot) continue; for (int i = 1; i <= 9; ++ i) b[i] = a[i]; b[1] += i1 + i2 + i4; b[2] += i1 + i2 + i3 + i5; b[3] += i2 + i3 + i6; b[4] += i1 + i4 + i5 + i7; b[5] += i1 + i3 + i5 + i7 + i9; b[6] += i3 + i5 + i6 + i9; b[7] += i4 + i7 + i8; b[8] += i5 + i7 + i8 + i9; b[9] += i6 + i8 + i9; bool flag = true; for (int i = 1; i <= 9; ++ i) if (b[i] % 4) flag = false; if (flag && i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9 < tot) { tot = i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 + i9; ans[1] = i1, ans[2] = i2, ans[3] = i3, ans[4] = i4, ans[5] = i5; ans[6] = i6, ans[7] = i7, ans[8] = i8, ans[9] = i9; } } for (int i = 1; i <= 9; ++ i) for (int j = 1; j <= ans[i]; ++ j) cout << i << ' '; cout << endl; } public: void solve() { input(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ2127
题意:求两个序列$s_1, s_2$的最长公共上升子序列。
题解:令$f_{i, j}$表示$s_1$的前$i$个数和$s_2$的前$j$个数的最长公共上升子序列长度,并且$s_1$的第$i$个和$s_2$的第$j$个匹配。显然,只有$s_{1, i}=s_{2, j}$时,$f_{i, j}$才有意义。转移方程:$f_{i, j}=max(f_{i’, j’} | i’ \lt i, j’ \lt j, s_{2, j’} \lt s_{2, j}) + 1$。令$g_{j’}=max(f_{i’, j’})$,则转移方程变为:$f_{i, j}=max(g_{j’} | j’ \lt j, s_{2, j’} \lt s_{1, i}) + 1$。这就可以从小到大枚举$i$,再从小到大枚举$j$,同时更新$g$。由于最后要输出序列,所以还需要一个$pre$数组来记录前一项。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 500; int n, m, a[N + 1], b[N + 1], g[N + 1], pre[N + 1][N + 1]; void input() { cin >> n; for (int i = 1; i <= n; ++ i) cin >> a[i]; cin >> m; for (int i = 1; i <= m; ++ i) cin >> b[i]; } void print(int i, int j) { if (! i || ! j) return; while (pre[i][j] == j) -- i; print(i - 1, pre[i][j]); cout << b[j] << ' '; } void process() { for (int i = 1; i <= n; ++ i) { int ma = 0, p = 0; for (int j = 1; j <= m; ++ j) { pre[i][j] = j; if (b[j] < a[i] && g[j] > ma) ma = g[j], p = j; else if (b[j] == a[i] && ma + 1 > g[j]) g[j] = ma + 1, pre[i][j] = p; } } int ans = 0, p = 0; for (int i = 1; i <= m; ++ i) if (g[i] > ans) ans = g[i], p = i; cout << ans << endl; print(n, p), cout << endl; } public: void solve() { input(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1177
题意:给定平面直角坐标系内的$n$个矩形,求它们覆盖区域的周长。
题解:扫描线+线段树,横着一次竖着一次。
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Line { int x, y1, y2, val; bool operator < (const Line &a) const { return x < a.x; } }; struct SegmentTree { private: static const int N = 30000; int tot; struct Node { int l, r, child[2], val, sum; } node[N << 1]; void build_tree(int root) { node[root].child[0] = node[root].child[1] = node[root].val = node[root].sum = 0; if (node[root].l == node[root].r) return; int mid = node[root].l + node[root].r >> 1; node[++ tot].l = node[root].l, node[tot].r = mid; node[root].child[0] = tot, build_tree(tot); node[++ tot].l = mid + 1, node[tot].r = node[root].r; node[root].child[1] = tot, build_tree(tot); } void update(int root) { if (node[root].l == node[root].r) return; if (node[root].val) node[root].sum = node[root].r - node[root].l + 1; else node[root].sum = node[node[root].child[0]].sum + node[node[root].child[1]].sum; } void insert_line(int root, int l, int r, int val) { if (node[root].r < l || node[root].l > r) return; if (node[root].l >= l && node[root].r <= r) { node[root].val += val; if (node[root].val) node[root].sum = node[root].r - node[root].l + 1; else node[root].sum = 0, update(root); return; } insert_line(node[root].child[0], l, r, val); insert_line(node[root].child[1], l, r, val); update(root); } public: void init(int t) { node[node[tot = 1].l = 1].r = t, build_tree(1); } void add(int l, int r, int val) { insert_line(1, l, r - 1, val); } int sum() { return node[1].sum; } }; struct Solver { private: static const int N = 5000; int n; pair<int, int> point[N << 1]; Line line[N << 1]; SegmentTree tree; void input() { cin >> n; for (int i = 1; i <= n; ++ i) { cin >> point[(i << 1) - 1].first >> point[(i << 1) - 1].second; point[(i << 1) - 1].first += 10001, point[(i << 1) - 1].second += 10001; cin >> point[i << 1].first >> point[i << 1].second; point[i << 1].first += 10001, point[i << 1].second += 10001; } } void process() { int ans = 0, last = 0; tree.init(20001); for (int i = 1; i <= n; ++ i) { line[(i << 1) - 1].x = point[(i << 1) - 1].first; line[(i << 1) - 1].y1 = point[(i << 1) - 1].second; line[(i << 1) - 1].y2 = point[i << 1].second; line[(i << 1) - 1].val = 1; line[i << 1].x = point[i << 1].first; line[i << 1].y1 = point[(i << 1) - 1].second; line[i << 1].y2 = point[i << 1].second; line[i << 1].val = -1; } sort(line + 1, line + (n << 1) + 1); for (int i = 1; i <= n << 1; ++ i) { tree.add(line[i].y1, line[i].y2, line[i].val); int sum = tree.sum(); ans += abs(last - sum); last = sum; } last = 0; tree.init(20001); for (int i = 1; i <= n; ++ i) { line[(i << 1) - 1].x = point[(i << 1) - 1].second; line[(i << 1) - 1].y1 = point[(i << 1) - 1].first; line[(i << 1) - 1].y2 = point[i << 1].first; line[(i << 1) - 1].val = 1; line[i << 1].x = point[i << 1].second; line[i << 1].y1 = point[(i << 1) - 1].first; line[i << 1].y2 = point[i << 1].first; line[i << 1].val = -1; } sort(line + 1, line + (n << 1) + 1); for (int i = 1; i <= n << 1; ++ i) { tree.add(line[i].y1, line[i].y2, line[i].val); int sum = tree.sum(); ans += abs(last - sum); last = sum; } cout << ans << endl; } public: void solve() { input(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1191
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; struct Solver { private: static const int N = 8; int n, a[N + 1][N + 1], sum[N + 1][N + 1]; double ans, avg, now, rec[N + 1]; void input() { cin >> n; for (int i = 1; i <= N; ++ i) for (int j = 1; j <= N; ++ j) cin >> a[i][j]; } void init() { ans = 1e9; for (int i = 1; i <= N; ++ i) for (int j = 1; j <= N; ++ j) sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]; avg = 1.0 * sum[N][N] / n; } double get_sum(int i1, int j1, int i2, int j2) { int s = sum[i2][j2] - sum[i1 - 1][j2] - sum[i2][j1 - 1] + sum[i1 - 1][j1 - 1]; return (s - avg) * (s - avg); } void process(int i1, int j1, int i2, int j2, int t) { if (now >= ans) return; if (i2 - i1 + j2 - j1 < n - t + 1) return; if (t == n) { rec[t] = get_sum(i1, j1, i2, j2), now += rec[t], ans = min(ans, now), now -= rec[t]; return; } for (int i = i1; i < i2; ++ i) { rec[t] = get_sum(i1, j1, i, j2), now += rec[t]; process(i + 1, j1, i2, j2, t + 1); now -= rec[t], rec[t] = get_sum(i + 1, j1, i2, j2), now += rec[t]; process(i1, j1, i, j2, t + 1); now -= rec[t]; } for (int j = j1; j < j2; ++ j) { rec[t] = get_sum(i1, j1, i2, j), now += rec[t]; process(i1, j + 1, i2, j2, t + 1); now -= rec[t], rec[t] = get_sum(i1, j + 1, i2, j2), now += rec[t]; process(i1, j1, i2, j, t + 1); now -= rec[t]; } } public: void solve() { input(), init(), process(1, 1, 8, 8, 1); cout << setprecision(3) << fixed << sqrt(ans / n) << endl; } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1195
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct BinaryIndexedTree { private: static const int N = 1024; int a[N + 1][N + 1]; void add_row(int x, int y, int val) { for (int i = y; i <= N; i += i & -i) a[x][i] += val; } int sum_row(int x, int y) { int ret = 0; for (int i = y; i; i -= i & -i) ret += a[x][i]; return ret; } public: void add(int x, int y, int val) { for (int i = x; i <= N; i += i & -i) add_row(i, y, val); } int sum(int x, int y) { int ret = 0; for (int i = x; i; i -= i & -i) ret += sum_row(i, y); return ret; } }; struct Solver { private: static const int N = 1024; int n; BinaryIndexedTree tree; bool process() { int o; cin >> o; if (o == 3) return false; if (! o) cin >> n; if (o == 1) { int x, y, a; cin >> x >> y >> a; ++ x, ++ y; tree.add(x, y, a); } if (o == 2) { int l, b, r, t; cin >> l >> b >> r >> t; ++ l, ++ b, ++ r, ++ t; cout << tree.sum(r, t) - tree.sum(l - 1, t) - tree.sum(r, b - 1) + tree.sum(l - 1, b - 1) << endl; } return true; } public: void solve() { while (process()) ; } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1201
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 50000; int n, nume, h[N + 2], que[N << 4], dist[N + 2]; bool in[N + 2]; struct Edge { int v, c, nxt; } e[N << 2]; void add_edge(int u, int v, int c) { e[++ nume].v = v, e[nume].c = c; e[nume].nxt = h[u], h[u] = nume; } void input() { cin >> n; for (int i = 1; i <= n; ++ i) { int a, b, c; cin >> a >> b >> c; ++ a, ++ b; add_edge(a - 1, b , -c); } for (int i = 1; i <= N + 1; ++ i) { add_edge(i - 1, i, 0); add_edge(i, i - 1, 1); } memset(dist, 0x1f, sizeof dist); } void process() { int s = 0, t = 1; que[1] = 0, dist[0] = 0, in[0] = true; while (s < t) { int u = que[++ s]; in[u] = false; for (int i = h[u]; i; i = e[i].nxt) { if (dist[u] + e[i].c < dist[e[i].v]) { dist[e[i].v] = dist[u] + e[i].c; if (! in[e[i].v]) que[++ t] = e[i].v, in[e[i].v] = true; } } } cout << - dist[N + 1] << endl; } public: void solve() { input(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1222
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 10; int a[N + 1][N + 1], b[N + 1][N + 1], ans[N + 1][N + 1]; void input() { for (int i = 1; i < 6; ++ i) for (int j = 1; j <= 6; ++ j) cin >> a[i][j]; } void modify(int x, int y) { b[x][y] = ! b[x][y]; b[x - 1][y] = ! b[x - 1][y]; b[x][y - 1] = ! b[x][y - 1]; b[x + 1][y] = ! b[x + 1][y]; b[x][y + 1] = ! b[x][y + 1]; } void process() { for (int f = 0; f < 1 << 6; ++ f) { for (int i = 1; i < 6; ++ i) for (int j = 1; j <= 6; ++ j) b[i][j] = a[i][j]; memset(ans, 0, sizeof ans); for (int i = 1; i <= 6; ++ i) { ans[1][i] = f & (1 << (i - 1)); if (ans[1][i]) modify(1, i); } for (int i = 2; i < 6; ++ i) for (int j = 1; j <= 6; ++ j) if (b[i - 1][j]) ans[i][j] = 1, modify(i, j); bool flag = true; for (int i = 1; i <= 6; ++ i) if (b[5][i]) flag = false; if (flag) { for (int i = 1; i < 6; ++ i) { for (int j = 1; j <= 6; ++ j) cout << (ans[i][j] > 0) << ' '; cout << endl; } return; } } } public: void solve() { input(), process(); } } solver; int main() { ios::sync_with_stdio(false); int T; cin >> T; for (int i = 1; i <= T; ++ i) cout << "PUZZLE #" << i << endl, solver.solve(); return 0; }
POJ1286
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: long long n; bool input() { cin >> n; return ~ n; } long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; } long long power(long long a, long long b) { long long ret = 1; while (b) { if (b & 1) ret *= a; a *= a, b >>= 1; } return ret; } void process() { if (! n) { cout << 0 << endl; return; } long long ans = 0; for (int i = 0; i < n; ++ i) ans += power(3, gcd(i, n)); if (n & 1) ans += n * power(3, n + 1 >> 1); else ans += (n >> 1) * power(3, n >> 1) + (n >> 1) * power(3, (n >> 1) + 1); cout << ans / (n << 1) << endl; } public: bool solve() { if (! input()) return false; process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ1691
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Rectangle { int x1, y1, x2, y2, col; }; struct Solver { private: static const int N = 15; int n, ans, nume, h[N + 1], in[N + 1]; bool vis[N + 1]; Rectangle a[N + 1]; struct Edge { int v, nxt; } e[N * N]; void add_edge(int u, int v) { e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume; } void input() { cin >> n; for (int i = 1; i <= n; ++ i) cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2 >> a[i].col; } bool has_inter(int a, int b, int c, int d) { if (a > c) swap(a, c), swap(b, d); return c >= a && c < b; } void init() { ans = 1e9, nume = 0; memset(h, 0, sizeof h); memset(in, 0, sizeof in); memset(vis, false, sizeof vis); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) if (a[i].x2 == a[j].x1 && has_inter(a[i].y1, a[i].y2, a[j].y1, a[j].y2)) add_edge(i, j), ++ in[j]; } void process(int t, int tot, int col, int cnt) { if (tot == n) { ans = min(ans, cnt); return; } vis[t] = true; for (int i = h[t]; i; i = e[i].nxt) -- in[e[i].v]; for (int i = 1; i <= n; ++ i) { if (! vis[i] && ! in[i]) process(i, tot + 1, a[i].col, cnt + (col != a[i].col)); } for (int i = h[t]; i; i = e[i].nxt) ++ in[e[i].v]; vis[t] = false; } public: void solve() { input(), init(); for (int i = 1; i <= n; ++ i) if (! in[i]) process(i, 1, a[i].col, 1); cout << ans << endl; } } solver; int main() { ios::sync_with_stdio(false); int T; cin >> T; while (T --) solver.solve(); return 0; }
POJ1703
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 100000; int n, m, fa[N + 1], dist[N + 1]; void input() { scanf("%d%d", &n, &m); } void init() { for (int i = 1; i <= n; ++ i) fa[i] = i, dist[i] = 0; } int get_fa(int t) { if (t == fa[t]) return t; int ret = get_fa(fa[t]); (dist[t] += dist[fa[t]]) &= 1; return fa[t] = ret; } void process() { int a, b; char c = ' '; while (c != 'A' && c != 'D') scanf("%c", &c); scanf("%d%d", &a, &b); int p = get_fa(a), q = get_fa(b); if (c == 'A') { if (p != q) printf("Not sure yet.\n"); else if (dist[a] != dist[b]) printf("In different gangs.\n"); else printf("In the same gang.\n"); } else fa[p] = q, dist[p] = dist[a] + dist[b] + 1 & 1; } public: void solve() { input(), init(); while (m --) process(); } } solver; int main() { int T; cin >> T; while (T --) solver.solve(); return 0; }
POJ1724
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 100; int k, n, r, nume, ans, h[N + 1]; bool vis[N + 1]; struct Edge { int v, l, t, nxt; } e[N * N + 1]; void add_edge(int u, int v, int l, int t) { e[++ nume].v = v, e[nume].l = l, e[nume].t = t; e[nume].nxt = h[u], h[u] = nume; } void input() { cin >> k >> n >> r; for (int i = 1; i <= r; ++ i) { int u, v, l, t; cin >> u >> v >> l >> t; add_edge(u, v, l, t); } } void init() { ans = 1e9; } void dfs(int u, int l, int t) { if (t < 0 || l >= ans) return; if (u == n) { ans = l; return; } vis[u] = true; for (int i = h[u]; i; i = e[i].nxt) { if (! vis[e[i].v]) dfs(e[i].v, l + e[i].l, t - e[i].t); } vis[u] = false; } public: void solve() { input(), init(), dfs(1, 0, k); cout << ans << endl; } } solver; int main() { solver.solve(); return 0; }
POJ1819
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const double EPS = 1e-6; int cmp(double t) { if (fabs(t) < EPS) return 0; if (t > 0) return 1; return -1; } struct Solver { private: static const int N = 1000; int n, top, sta[N + 1], tot, ans[N + 1]; double r[N + 1], dist[N + 1]; void input() { cin >> n; for (int i = 1; i <= n; ++ i) cin >> r[i]; } void init() { dist[1] = r[1], sta[top = 1] = 1; for (int i = 2; i <= n; ++ i) { dist[i] = r[i]; for (int j = 1; j < i; ++ j) dist[i] = max(dist[i], dist[j] + sqrt((r[i] + r[j]) * (r[i] + r[j]) - (r[i] - r[j]) * (r[i] - r[j]))); if (dist[i] == r[i]) sta[top = 1] = i; else for (int j = 1; j <= top; ++ j) if (! cmp(dist[i] - dist[sta[j]] - sqrt((r[i] + r[sta[j]]) * (r[i] + r[sta[j]]) - (r[i] - r[sta[j]]) * (r[i] - r[sta[j]])))) { sta[top = j + 1] = i; break; } } } void process() { int p = 0; double far = 0; for (int i = 1; i <= n; ++ i) far = max(far, dist[i] + r[i]); for (int i = 1; i <= n; ++ i) if (! cmp(far - dist[i] - r[i])) { p = i; break; } while (sta[top] > p) -- top; int pos = 1; for (int i = 1; i <= n; ++ i) if (i <= p && i == sta[pos]) ++ pos; else ans[++ tot] = i; cout << tot << endl; for (int i = 1; i <= tot; ++ i) cout << ans[i] << endl; } public: void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1870
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 10000; int a, b; pair <int, int> point[N << 1]; bool input() { cin >> a >> b; return a || b; } void process() { int x = point[a].first - point[b].first, y = point[a].second - point[b].second; if (x <= 0 && y >= 0 || x >= 0 && y <= 0) cout << abs(x) + abs(y); else cout << max(abs(x), abs(y)); } public: void init() { point[1] = make_pair(0, 0); int t = 2, cnt = 1; while (t <= 10000) { point[t] = make_pair(point[t - 1].first, point[t - 1].second - 1), ++ t; for (int i = 1; i < cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first - 1, point[t - 1].second - 1); for (int i = 1; i <= cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first - 1, point[t - 1].second); for (int i = 1; i <= cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first, point[t - 1].second + 1); for (int i = 1; i <= cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first + 1, point[t - 1].second + 1); for (int i = 1; i <= cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first + 1, point[t - 1].second); for (int i = 1; i <= cnt; ++ i, ++ t) point[t] = make_pair(point[t - 1].first, point[t - 1].second - 1); ++ cnt; } } bool solve() { if (! input()) return false; cout << "The distance between cells " << a << " and " << b << " is "; process(), cout << "." << endl; return true; } } solver; int main() { ios::sync_with_stdio(false); solver.init(); while (solver.solve()) ; return 0; }
POJ1925
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Point { long long x, y; }; struct Solver { private: static const long long N = 5000; static const long long M = 1000000; long long n, f[M + 1]; Point point[N + 1]; void input() { scanf("%lld", &n); for (int i = 1; i <= n; ++ i) scanf("%lld%lld", &point[i].x, &point[i].y); } void process() { memset(f, 0x1f, sizeof f); f[point[1].x] = 0; for (int i = 2; i <= n; ++ i) { int len = sqrt(point[i].y * point[i].y - (point[i].y - point[1].y) * (point[i].y - point[1].y)); for (int j = max(point[1].x, point[i].x - len); j < point[i].x; ++ j) { int k = min(point[n].x, (point[i].x << 1) - j); f[k] = min(f[k], f[j] + 1); } } if (f[point[n].x] > 5000) printf("-1\n"); else printf("%lld\n", f[point[n].x]); } public: void solve() { input(), process(); } } solver; int main() { int T; scanf("%d", &T); while (T --) solver.solve(); return 0; }
POJ1947
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 150; int n, m, nume, h[N + 1], size[N + 1], f[N + 1][N + 1]; struct Edge { int v, nxt; } e[N << 1]; void add_edge(int u, int v) { e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume; } void input() { cin >> n >> m; for (int i = 1; i < n; ++ i) { int u, v; cin >> u >> v; add_edge(u, v); } } void dfs(int t) { int cnt = 0; size[t] = 1; for (int i = h[t]; i; i = e[i].nxt, ++ cnt) { dfs(e[i].v); size[t] += size[e[i].v]; } f[t][1] = cnt; for (int i = h[t]; i; i = e[i].nxt) { for (int j = size[t]; j; -- j) for (int k = 1; k < j; ++ k) f[t][j] = min(f[t][j], f[t][j - k] + f[e[i].v][k] - 1); } } void init() { memset(f, 0x1f, sizeof f), dfs(1); } void process() { int ans = f[1][m]; for (int i = 2; i <= n; ++ i) ans = min(ans, f[i][m] + 1); cout << ans << endl; } public: void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ1961
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 1000000; int T, n, nxt[N + 1]; string s; bool input() { cin >> n; if (! n) return false; cin >> s; return true; } void init() { nxt[0] = nxt[1] = 0; int k = 0; for (int i = 2; i <= n; ++ i) { for (; k && s[k] != s[i - 1]; k = nxt[k]) ; if (s[k] == s[i - 1]) ++ k; nxt[i] = k; } } void process() { for (int i = 1; i <= n; ++ i) { if (! (i % (i - nxt[i])) && i / (i - nxt[i]) > 1) cout << i << ' ' << i / (i - nxt[i]) << endl; } } public: bool solve() { if (! input()) return false; cout << "Test case #" << ++ T << endl; init(), process(), cout << endl; return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ2029
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 100; int n, w, h, s, t, hor[N + 1][N + 1], ver[N + 1][N + 1]; bool a[N + 1][N + 1]; bool input() { cin >> n; if (! n) return false; cin >> w >> h, memset(a, false, sizeof a); for (int i = 1; i <= n; ++ i) { int x, y; cin >> x >> y, a[y][x] = 1; } cin >> s >> t; return true; } void init() { memset(hor, 0, sizeof hor); memset(ver, 0, sizeof ver); for (int i = 1; i <= h; ++ i) { for (int j = 1; j <= s; ++ j) hor[i][1] += a[i][j]; for (int j = s + 1; j <= w; ++ j) hor[i][j - s + 1] = hor[i][j - s] + a[i][j] - a[i][j - s]; } for (int i = 1; i <= w - s + 1; ++ i) { for (int j = 1; j <= t; ++ j) ver[1][i] += hor[j][i]; for (int j = t + 1; j <= h; ++ j) ver[j - t + 1][i] = ver[j - t][i] + hor[j][i] - hor[j - t][i]; } } void process() { int ans = 0; for (int i = 1; i <= h - t + 1; ++ i) for (int j = 1; j <= w - s + 1; ++ j) ans = max(ans, ver[i][j]); cout << ans << endl; } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ2057
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <iomanip> using namespace std; const int N = 1000; int f[N + 1], size[N + 1]; bool cmp(int a, int b) { return f[a] * size[b] < f[b] * size[a]; } int n, nume, h[N + 1]; int tim, ans, dfn[N + 1]; bool b[N + 1], leaf[N + 1]; struct Edge { int v, nxt; } e[N << 1]; void add_edge(int u, int v) { e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume; e[++ nume].v = u, e[nume].nxt = h[v], h[v] = nume; } bool input() { cin >> n; if (! n) return false; nume = 0, memset(h, 0, sizeof h); for (int i = 1; i <= n; ++ i) { int fa; char c; cin >> fa >> c; if (~ fa) add_edge(fa, i); b[i] = c == 'Y'; } return true; } void init(int t, int fa) { f[t] = 2, size[t] = 0; for (int i = h[t]; i; i = e[i].nxt) if (e[i].v != fa) init(e[i].v, t), f[t] += f[e[i].v], size[t] += size[e[i].v]; if (b[t]) f[t] = 2; if (leaf[t] = ! size[t]) size[t] = 1; } void dfs(int t, int fa) { int arr[10]; memset(arr, 0, sizeof arr); int tmp = ++ tim; dfn[t] = tmp; for (int i = h[t]; i; i = e[i].nxt) if (e[i].v != fa) arr[++ arr[0]] = e[i].v; sort(arr + 1, arr + arr[0] + 1, cmp); for (int i = 1; i <= arr[0]; ++ i) dfs(arr[i], t); if (b[t]) tim = tmp; ++ tim; } void process() { int cnt = 0; tim = -1, ans = 0, dfs(1, 0); for (int i = 1; i <= n; ++ i) cnt += leaf[i], ans += leaf[i] * dfn[i]; cout << setprecision(4) << fixed << 1.0 * ans / cnt << endl; } bool solve() { if (! input()) return false; init(1, 0), process(); return true; } int main() { ios::sync_with_stdio(false); while (solve()) ; return 0; }
POJ2065
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int p; int power(int a, int b) { int ret = 1; a %= p, b %= p - 1; while (b) { if (b & 1) (ret *= a) %= p; (a *= a) %= p, b >>= 1; } return ret; } int get_inv(int t) { return power(t, p - 2); } struct Gauss { static const int N = 100; int n, a[N][N]; void solve() { for (int i = 1; i <= n; ++ i) { if (! a[i][i]) for (int j = i + 1; j <= n; ++ j) if (a[j][i]) { for (int k = i; k <= n + 1; ++ k) swap(a[i][k], a[j][k]); break; } int inv = get_inv(a[i][i]); for (int j = i; j <= n + 1; ++ j) (a[i][j] *= inv) %= p; for (int j = 1; j <= n; ++ j) if (j != i) { int tmp = a[j][i]; for (int k = i; k <= n + 1; ++ k) (((a[j][k] -= a[i][k] * tmp % p) %= p) += p) %= p; } } } }; struct Solver { private: static const int N = 100; int n; string s; Gauss g; void input() { cin >> p >> s, n = s.length(); } void init() { g.n = n; for (int i = 1; i <= n; ++ i) { int tmp = 1; for (int j = 1; j <= n; ++ j) g.a[i][j] = tmp, (tmp *= i) %= p; g.a[i][n + 1] = s[i - 1] - 'a' + 1; if (s[i - 1] == 42) g.a[i][n + 1] = 0; } } void process() { g.solve(); for (int i = 1; i <= n; ++ i) cout << g.a[i][n + 1] << ' '; cout << endl; } public: void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); int T; cin >> T; while (T --) solver.solve(); return 0; }
POJ2186
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 50000; int n, m, nume, tim, h[N + 1], fa[N + 1]; int dfn[N + 1], low[N + 1], sta[N + 1], belong[N + 1]; bool in[N + 1], vis[N + 1]; struct Edge { int v, nxt; } e[N + 1]; void add_edge(int u, int v) { e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume; } int get_fa(int t) { return t == fa[t] ? t : fa[t] = get_fa(fa[t]); } void input() { cin >> n >> m; for (int i = 1; i <= m; ++ i) { int u, v; cin >> u >> v; add_edge(u, v); } } void dfs(int t) { in[sta[++ sta[0]] = t] = true, dfn[t] = low[t] = ++ tim; for (int i = h[t]; i; i = e[i].nxt) { if (in[e[i].v]) low[t] = min(low[t], dfn[e[i].v]); else if (! dfn[e[i].v]) dfs(e[i].v), low[t] = min(low[t], low[e[i].v]); } if (dfn[t] == low[t]) { while (sta[sta[0]] != t) belong[sta[sta[0]]] = t, in[sta[sta[0] --]] = false; belong[sta[sta[0]]] = t, in[sta[sta[0] --]] = false; } } void process() { for (int i = 1; i <= n; ++ i) if (! dfn[i]) dfs(i); for (int i = 1; i <= n; ++ i) fa[i] = i; memset(in, false, sizeof in); for (int i = 1; i <= n; ++ i) for (int j = h[i]; j; j = e[j].nxt) { if (belong[i] == belong[e[j].v]) continue; in[belong[i]] = true; int p = get_fa(belong[i]), q = get_fa(belong[e[j].v]); if (p != q) fa[p] = q; } int t = 0; for (int i = 1; i <= n; ++ i) if (! in[belong[i]] && ! vis[belong[i]]) vis[belong[i]] = true, ++ t; if (t > 1) { cout << 0 << endl; return; } int ans = 0; for (int i = 1; i <= n; ++ i) if (! in[belong[i]]) ++ ans; cout << ans << endl; } public: void solve() { input(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ2195
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 200; int n, m, cnt1, cnt2, dist[N + 1][N + 1]; int match[N + 1], slack[N + 1], flag[2][N + 1]; bool vis[2][N + 1]; pair <int, int> a[N + 1], b[N + 1]; bool input() { cin >> n >> m; cnt1 = cnt2 = 0; if (! n || ! m) return false; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) { char c; cin >> c; if (c == 'H') a[++ cnt1].first = i, a[cnt1].second = j; else if (c == 'm') b[++ cnt2].first = i, b[cnt2].second = j; } return true; } void init() { memset(dist, 0, sizeof dist); for (int i = 1; i <= cnt1; ++ i) for (int j = 1; j <= cnt2; ++ j) dist[i][j] = -abs(a[i].first - b[j].first) - abs(a[i].second - b[j].second); } bool dfs(int t) { vis[0][t] = true; for (int i = 1; i <= cnt2; ++ i) { if (vis[1][i]) continue; int gap = flag[0][t] + flag[1][i] - dist[t][i]; if (! gap) { vis[1][i] = true; if (! ~ match[i] || dfs(match[i])) { match[i] = t; return true; } } else slack[i] = min(slack[i], gap); } return false; } int km() { memset(match, -1, sizeof match); memset(flag[1], 0, sizeof flag[1]); for (int i = 1; i <= cnt1; ++ i) { flag[0][i] = dist[i][1]; for (int j = 2; j <= cnt2; ++ j) flag[0][i] = max(flag[0][i], dist[i][j]); } for (int i = 1; i <= cnt1; ++ i) { memset(slack, 0x1f, sizeof slack); while (true) { memset(vis, false, sizeof vis); if (dfs(i)) break; int d = 1e9; for (int j = 1; j <= cnt2; ++ j) if (! vis[1][j]) d = min(d, slack[j]); for (int j = 1; j <= cnt2; ++ j) { if (vis[0][j]) flag[0][j] -= d; if (vis[1][j]) flag[1][j] += d; else slack[j] -= d; } } } int ret = 0; for (int i = 1; i <= cnt1; ++ i) ret += dist[match[i]][i]; return ret; } void process() { cout << -km() << endl; } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ2352
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct BinaryIndexedTree { private: static const int N = 40000; int n, a[N]; public: void init(int t) { n = t; } void add(int p, int val) { for (; p <= n; p += p & -p) a[p] += val; } int sum(int p) { int ret = 0; for (; p; p -= p & -p) ret += a[p]; return ret; } }; struct Solver { private: static const int N = 15000; int n, ans[N + 1]; pair <int, int> point[N + 1]; BinaryIndexedTree tree; void input() { scanf("%d", &n); for (int i = 1; i <= n; ++ i) scanf("%d%d", &point[i].first, &point[i].second), ++ point[i].first, ++ point[i].second; } void init() { tree.init(32001); sort(point + 1, point + n + 1); } void process() { int pnt = 1; for (int i = 1; i <= 32001; ++ i) for (; pnt <= n && point[pnt].first == i; ++ pnt) { ++ ans[tree.sum(point[pnt].second)]; tree.add(point[pnt].second, 1); } for (int i = 0; i < n; ++ i) printf("%d\n", ans[i]); } public: void solve() { input(), init(), process(); } } solver; int main() { solver.solve(); return 0; }
POJ2406
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 1000000; int n, nxt[N + 1]; string s; bool input() { cin >> s; return s != "."; } void init() { nxt[0] = nxt[1] = 0; int k = 0; n = s.length(); for (int i = 2; i <= n; ++ i) { for (; k && s[k] != s[i - 1]; k = nxt[k]) ; if (s[k] == s[i - 1]) ++ k; nxt[i] = k; } } void process() { if (n % (n - nxt[n])) cout << 1 << endl; else cout << n / (n - nxt[n]) << endl; } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ2409
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: long long n, m, ans; long long power(long long a, long long b) { long long ret = 1; while (b) { if (b & 1) ret *= a; a *= a, b >>= 1; } return ret; } long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; } bool input() { cin >> n >> m; return n && m; } void init() { ans = 0; } void process() { if (m == 1) { cout << n << endl; return; } if (m == 2) { cout << (n * (n - 1) >> 1) + n << endl; return; } for (int i = 0; i < m; ++ i) ans += power(n, gcd(m, i)); if (m & 1) ans += m * power(n, (m + 1 >> 1)); else ans += (m >> 1) * power(n, m >> 1) + (m >> 1) * power(n, (m >> 1) + 1); cout << ans / (m << 1) << endl; } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ2411
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const long long N = 11; int n, m, pool[1 << N]; long long f[N + 2][1 << N]; bool check(int t) { bool flag = false; while (t) { if (t & 1) flag = ! flag; else if (flag) return false; t >>= 1; } return ! flag; } bool input() { cin >> n >> m; if (n > m) swap(n, m); return n && m; } void process() { if (n == 1) { cout << ! (m & 1) << endl; return; } int full = (1 << m) - 1; memset(f, 0, sizeof f); for (int i = 1; i <= pool[0] && pool[i] <= full; ++ i) f[1][pool[i]] = 1; for (int i = 0; i <= full; ++ i) f[2][full - i] = f[1][i]; for (int i = 2; i <= n; ++ i) for (int j = 0; j <= full; ++ j) for (int k = 1; k <= pool[0] && pool[i] <= full; ++ k) if (! (j & pool[k])) f[i + 1][full - (j | pool[k])] += f[i][j]; cout << f[n + 1][0] << endl; } public: void init() { for (long long i = 0; i < 1 << N; ++ i) if (check(i)) pool[++ pool[0]] = i; } bool solve() { if (! input()) return false; process(); return true; } } solver; int main() { ios::sync_with_stdio(false); solver.init(); while (solver.solve()) ; return 0; }
POJ2454
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define random(n) (rand() % n + 1) using namespace std; struct Solver { private: static const int N = 200; int n, r1, r2; pair <int, int> a[N]; void input() { cin >> n; for (int i = 1; i <= n * 3; ++ i) cin >> a[i].first, a[i].second = i; } void init() { sort(a + 1, a + n * 3 + 1); } void process() { int s1 = 0, s2 = 0; for (int i = n + 1; i <= n << 1; ++ i) s1 += a[i].first; for (int i = (n << 1) + 1; i <= n * 3; ++ i) s2 += a[i].first; while (true) { if (s1 > 500 * n && s2 > 500 * n) break; r1 = random(n) + n, r2 = random(n) + (n << 1); s1 += a[r2].first - a[r1].first, s2 += a[r1].first - a[r2].first, swap(a[r1], a[r2]); } for (int i = 1; i <= n * 3; ++ i) cout << a[i].second << endl; } public: void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ2482
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct SegmentTree { private: static const long long N = 50000; long long tot; struct Node { long long l, r, max, tag, child[2]; } node[N]; void push_down(long long root) { if (node[root].l == node[root].r) return; node[node[root].child[0]].max += node[root].tag, node[node[root].child[0]].tag += node[root].tag; node[node[root].child[1]].max += node[root].tag, node[node[root].child[1]].tag += node[root].tag; node[root].tag = 0; } void push_up(long long root) { if (node[root].l == node[root].r) return; node[root].max = max(node[node[root].child[0]].max, node[node[root].child[1]].max); } void build_tree(long long root) { node[root].max = node[root].tag = node[root].child[0] = node[root].child[1] = 0; if (node[root].l == node[root].r) return; long long mid = node[root].l + node[root].r >> 1; node[++ tot].l = node[root].l, node[tot].r = mid; node[root].child[0] = tot, build_tree(tot); node[++ tot].l = mid + 1, node[tot].r = node[root].r; node[root].child[1] = tot, build_tree(tot); } void insert_line(long long root, long long l, long long r, long long val) { if (node[root].r < l || node[root].l > r) return; if (node[root].l >= l && node[root].r <= r) { node[root].max += val, node[root].tag += val; return; } push_down(root); insert_line(node[root].child[0], l, r, val); insert_line(node[root].child[1], l, r, val); push_up(root); } public: void init(long long t) { node[node[tot = 1].l = 1].r = t, build_tree(1); } void add(long long l, long long r, long long val) { insert_line(1, l, r, val); } long long get() { return node[1].max; } }; struct Point { long long ox, oy, x, y, c, id; }; bool cmpx(Point a, Point b) { return a.ox < b.ox; } bool cmpy(Point a, Point b) { return a.oy < b.oy; } bool cmpi(Point a, Point b) { return a.id < b.id; } struct Line { long long x1, x2, y, c; bool operator < (const Line &a) const { return y == a.y ? c > a.c : y < a.y; } }; struct Solver { private: static const long long N = 10000; Point point[N + 1 << 1]; Line line[N + 1 << 1]; SegmentTree tree; void input() { for (long long i = 1; i <= n; ++ i) { cin >> point[i].ox >> point[i].oy >> point[i].c, point[i].id = i; point[i + n].ox = point[i].ox + w - 1, point[i + n].oy = point[i].oy + h - 1; point[i + n].c = -point[i].c, point[i + n].id = i + n; } } void init() { tree.init(n << 1); sort(point + 1, point + (n << 1) + 1, cmpx), point[1].x = 1; for (long long i = 2; i <= n << 1; ++ i) point[i].x = point[i - 1].x + (point[i].ox != point[i - 1].ox); sort(point + 1, point + (n << 1) + 1, cmpy), point[1].y = 1; for (long long i = 2; i <= n << 1; ++ i) point[i].y = point[i - 1].y + (point[i].oy != point[i - 1].oy); sort(point + 1, point + (n << 1) + 1, cmpi); for (long long i = 1; i <= n; ++ i) { line[i].x1 = point[i].x, line[i].x2 = point[i + n].x; line[i].y = point[i].y, line[i].c = point[i].c; line[i + n].x1 = point[i].x, line[i + n].x2 = point[i + n].x; line[i + n].y = point[i + n].y, line[i + n].c = point[i + n].c; } sort(line + 1, line + (n << 1) + 1); } void process() { long long ans = 0, pnt = 1; for (long long i = 1; i <= n << 1; ++ i) { while (line[pnt].y == i && line[pnt].c > 0) tree.add(line[pnt].x1, line[pnt].x2, line[pnt].c), ++ pnt; ans = max(ans, tree.get()); while (line[pnt].y == i && line[pnt].c < 0) tree.add(line[pnt].x1, line[pnt].x2, line[pnt].c), ++ pnt; } cout << ans << endl; } public: long long n, w, h; void solve() { if (w < 2 || h < 2) { cout << 0 << endl; return; } input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); while (cin >> solver.n >> solver.w >> solver.h) solver.solve(); return 0; }
POJ2486
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 100; int nume, h[N + 1], a[N + 1], f[N + 1][N + 2 << 1], g[N + 1][N + 2 << 1]; struct Edge { int v, nxt; } e[N << 1]; void add_edge(int u, int v) { e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume; e[++ nume].v = u, e[nume].nxt = h[v], h[v] = nume; } void input() { nume = 0; memset(h, 0, sizeof h); for (int i = 1; i <= n; ++ i) cin >> a[i]; for (int i = 1; i < n; ++ i) { int u, v; cin >> u >> v, add_edge(u, v); } } void init() { memset(f, 0, sizeof f); memset(g, 0, sizeof g); } void dfs(int t, int fa) { for (int i = 0; i <= k; ++ i) f[t][i] = g[t][i] = a[t]; for (int i = h[t]; i; i = e[i].nxt) if (e[i].v != fa) { dfs(e[i].v, t); for (int j = k; ~ j; -- j) for (int l = 0; l <= j; ++ l) { f[t][j + 2] = max(f[t][j + 2], f[e[i].v][l] + f[t][j - l]); g[t][j + 2] = max(g[t][j + 2], f[e[i].v][l] + g[t][j - l]); g[t][j + 1] = max(g[t][j + 1], g[e[i].v][l] + f[t][j - l]); } } } void process() { dfs(1, 0), cout << g[1][k] << endl; } public: int n, k; void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); while (cin >> solver.n >> solver.k) solver.solve(); return 0; }
POJ2492
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 2000; int T, n, m, fa[N + 1], dist[N + 1]; void input() { scanf("%d%d", &n, &m); } void init() { memset(dist, 0, sizeof dist); for (int i = 1; i <= n; ++ i) fa[i] = i; } int get_fa(int t) { if (t == fa[t]) return t; int ret = get_fa(fa[t]); (dist[t] += dist[fa[t]]) &= 1; return fa[t] = ret; } void process() { bool flag = true; for (int i = 1; i <= m; ++ i) { int a, b; scanf("%d%d", &a, &b); int p = get_fa(a), q = get_fa(b); if (p != q) fa[p] = q, dist[p] = ! (dist[a] + dist[b] & 1); else if (dist[a] == dist[b]) flag = false; } printf("Scenario #%d:\n", ++ T); if (flag) printf("No suspicious bugs found!\n"); else printf("Suspicious bugs found!\n"); printf("\n"); } public: void solve() { input(), init(), process(); } } solver; int main() { int T; scanf("%d", &T); while (T --) solver.solve(); return 0; }
POJ2516
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; struct Solver { private: static const int N = 50; int n, m, k, nume, h[N + 1 << 1], need[N + 1][N + 1], save[N + 1][N + 1]; struct Edge { int v, c, f, nxt; } e[N * N * N]; void add_edge(int u, int v, int c, int f) { e[++ nume].v = v, e[nume].c = c, e[nume].f = f, e[nume].nxt = h[u], h[u] = nume; e[++ nume].v = u, e[nume].c = 0, e[nume].f = -f, e[nume].nxt = h[v], h[v] = nume; } bool input() { cin >> n >> m >> k; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= k; cin >> need[i][j ++]) ; for (int i = 1; i <= m; ++ i) for (int j = 1; j <= k; cin >> save[i][j ++]) ; return n && m && k; } bool vis[N + 1 << 1]; int s, t, ans, dist[N + 1 << 1]; bool spfa(int s, int t) { memset(vis, false, sizeof vis); memset(dist, 0x1f, sizeof dist); dist[t] = 0, vis[t] = true; deque <int> que; que.push_back(t); while (! que.empty()) { int u = que.front(); vis[u] = false, que.pop_front(); for (int i = h[u]; i; i = e[i].nxt) if (e[i ^ 1].c && dist[e[i].v] > dist[u] - e[i].f) { dist[e[i].v] = dist[u] - e[i].f; if (! vis[e[i].v]) { vis[e[i].v] = true; if (! que.empty() && dist[e[i].v] < dist[que.front()]) que.push_front(e[i].v); else que.push_back(e[i].v); } } } return dist[s] < 5e8; } int dfs(int u, int low) { vis[u] = true; if (u == t) return low; int used = 0, a; for (int i = h[u]; i; i = e[i].nxt) if (! vis[e[i].v] && e[i].c && dist[u] - e[i].f == dist[e[i].v]) { a = dfs(e[i].v, min(e[i].c, low - used)); if (a) ans += a * e[i].f, e[i].c -= a, e[i ^ 1].c += a, used += a; if (low == used) break; } return used; } int costflow() { int flow = 0; while (spfa(s, t)) { vis[t] = 1; while (vis[t]) { memset(vis, false, sizeof vis); flow += dfs(s, 1e9); } } return flow; } void process() { int tot = 0; s = 0, t = n + m + 1; bool flag = true; for (int i = 1; i <= k; ++ i) { nume = 1, memset(h, 0, sizeof h); for (int j = 1; j <= n; ++ j) add_edge(0, j, need[j][i], 0); for (int j = 1; j <= m; ++ j) add_edge(j + n, n + m + 1, save[j][i], 0); for (int j = 1; j <= n; ++ j) for (int k = 1; k <= m; ++ k) { int f; cin >> f, add_edge(j, k + n, min(need[j][i], save[k][i]), f); } ans = 0, costflow(), tot += ans; for (int j = h[0]; j; j = e[j].nxt) if (e[j].c) flag = false; } if (flag) cout << tot << endl; else cout << -1 << endl; } public: bool solve() { if (! input()) return false; process(); return true; } } solver; int main() { ios::sync_with_stdio(false); while (solver.solve()) ; return 0; }
POJ2528
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct SegmentTree { private: static const int N = 50000; int tot; struct Node { int l, r, val, child[2]; } node[N]; bool is_leaf(int root) { return node[root].l == node[root].r; } void push_down(int root) { if (is_leaf(root) || ! node[root].val) return; node[node[root].child[0]].val = node[node[root].child[1]].val = node[root].val, node[root].val = 0; } void build_tree(int root) { if (is_leaf(root)) return; int mid = node[root].l + node[root].r >> 1; node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 0, 0, 0 }, build_tree(tot); node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 0, 0, 0 }, build_tree(tot); } void insert_line(int root, int l, int r, int val) { if (node[root].r < l || node[root].l > r) return; if (node[root].l >= l && node[root].r <= r) { node[root].val = val; return; } push_down(root); insert_line(node[root].child[0], l, r, val); insert_line(node[root].child[1], l, r, val); } int get_val(int root, int p) { if (node[root].r < p || node[root].l > p) return 0; return node[root].val ? node[root].val : max(get_val(node[root].child[0], p), get_val(node[root].child[1], p)); } public: void init(int t) { node[node[tot = 1].l = 1].r = t, build_tree(1); } void add(int l, int r, int val) { insert_line(1, l, r, val); } int get(int p) { return get_val(1, p); } }; struct Point { int ox, x, id; }; bool cmpx(Point a, Point b) { return a.ox < b.ox; } bool cmpi(Point a, Point b) { return a.id < b.id; } struct Solver { private: static const int N = 20000; int n; bool disp[N]; Point point[N + 1]; SegmentTree tree; void input() { cin >> n; for (int i = 1; i <= n << 1; cin >> point[i].ox, point[i].id = i ++) ; } void init() { tree.init(n << 1); sort(point + 1, point + (n << 1) + 1, cmpx); for (int i = 1; i <= n << 1; ++ i) point[i].x = point[i - 1].x + (point[i].ox != point[i - 1].ox); sort(point + 1, point + (n << 1) + 1, cmpi); } void process() { for (int i = 1; i <= n; ++ i) tree.add(point[(i << 1) - 1].x, point[i << 1].x, i); memset(disp, 0, sizeof disp); for (int i = 1; i <= n << 1; disp[tree.get(i ++)] = true) ; int ans = 0; for (int i = 1; i <= n; ans += disp[i ++]) ; cout << ans << endl; } public: void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); int T; cin >> T; while (T --) solver.solve(); return 0; }
POJ2750
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct SegmentTree { private: static const int N = 100000; int tot; struct Node { int l, r, sum, lmin, rmin, min, lmax, rmax, max, child[2]; } node[N << 2]; void push_up(int root) { node[root].sum = node[node[root].child[0]].sum + node[node[root].child[1]].sum; node[root].lmin = min(node[node[root].child[0]].lmin, node[node[root].child[0]].sum + node[node[root].child[1]].lmin); node[root].rmin = min(node[node[root].child[1]].rmin, node[node[root].child[1]].sum + node[node[root].child[0]].rmin); node[root].min = min(min(min(node[node[root].child[0]].min, node[node[root].child[1]].min), min(node[root].lmin, node[root].rmin)), node[node[root].child[0]].rmin + node[node[root].child[1]].lmin); node[root].lmax = max(node[node[root].child[0]].lmax, node[node[root].child[0]].sum + node[node[root].child[1]].lmax); node[root].rmax = max(node[node[root].child[1]].rmax, node[node[root].child[1]].sum + node[node[root].child[0]].rmax); node[root].max = max(max(max(node[node[root].child[0]].max, node[node[root].child[1]].max), max(node[root].lmax, node[root].rmax)), node[node[root].child[0]].rmax + node[node[root].child[1]].lmax); } void build_tree(int root) { if (node[root].l == node[root].r) return; int mid = node[root].l + node[root].r >> 1; node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, build_tree(tot); node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, build_tree(tot); } void modify_point(int root, int p, int val) { if (node[root].r < p || node[root].l > p) return; if (node[root].l == node[root].r) { node[root] = (Node) { node[root].l, node[root].r, val, val, val, val, val, val, val, 0, 0 }; return; } modify_point(node[root].child[0], p, val), modify_point(node[root].child[1], p, val), push_up(root); } public: void init(int t) { node[node[tot = 1].l = 1].r = t, build_tree(1); } void edit(int p, int val) { modify_point(1, p, val); } int get_max() { return node[1].max; } int get_min() { return node[1].min; } }; struct Solver { private: static const int N = 100000; int n, sum, cnt, a[N + 1]; SegmentTree tree; void input() { cin >> n; for (int i = 1; i <= n; ++ i) cin >> a[i], sum += a[i], cnt += a[i] < 0; } void init() { tree.init(n); for (int i = 1; i <= n; ++ i) tree.edit(i, a[i]); } void process() { int T; cin >> T; while (T --) { int x, y; cin >> x >> y; sum += y - a[x], cnt += (y < 0) - (a[x] < 0), a[x] = y, tree.edit(x, y); cout << max(bool(cnt) * tree.get_max(), sum - tree.get_min()) << endl; } } public: void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ2777
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct SegmentTree { private: static const int N = 100000; int tot; struct Node { int l, r, val, tag, child[2]; } node[N << 2]; void push_down(int root) { if (node[root].l == node[root].r || ! node[root].tag) return; node[node[root].child[0]].val = node[node[root].child[0]].tag = node[root].tag; node[node[root].child[1]].val = node[node[root].child[1]].tag = node[root].tag; node[root].tag = 0; } void push_up(int root) { if (node[root].l == node[root].r) return; node[root].val = node[node[root].child[0]].val | node[node[root].child[1]].val; } void build_tree(int root) { if (node[root].l == node[root].r) return; int mid = node[root].l + node[root].r >> 1; node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 0, 0, 0, 0 }, build_tree(tot); node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 0, 0, 0, 0 }, build_tree(tot); } void insert_line(int root, int l, int r, int col) { if (node[root].r < l || node[root].l > r) return; if (node[root].l >= l && node[root].r <= r) { node[root].val = node[root].tag = 1 << (col - 1); return; } push_down(root); insert_line(node[root].child[0], l, r, col); insert_line(node[root].child[1], l, r, col); push_up(root); } int query_line(int root, int l, int r) { if (node[root].r < l || node[root].l > r) return 0; if (node[root].l >= l && node[root].r <= r) return node[root].val; push_down(root); int ret = query_line(node[root].child[0], l, r) | query_line(node[root].child[1], l, r); push_up(root); return ret; } public: void init(int t) { node[node[tot = 1].l = 1].r = t, build_tree(1); } void add(int l, int r, int col) { insert_line(1, l, r, col); } int get(int l, int r) { int ret = query_line(1, l, r), cnt = 0; while (ret) cnt += ret & 1, ret >>= 1; return cnt; } }; struct Solver { private: static const int N = 100000; int n, m, a[N + 1]; SegmentTree tree; void input() { int t; cin >> n >> t >> m; } void init() { tree.init(n), tree.add(1, n, 1); } void process() { while (m --) { char c; cin >> c; int x, y, z; cin >> x >> y; if (c == 'C') cin >> z, tree.add(min(x, y), max(x, y), z); else cout << tree.get(min(x, y), max(x, y)) << endl; } } public: void solve() { input(), init(), process(); } } solver; int main() { ios::sync_with_stdio(false); solver.solve(); return 0; }
POJ2828
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; static const int N = 200000; int a[N + 1]; struct SegmentTree { private: int tot; struct Node { int l, r, res, child[2]; } node[N << 2]; void push_up(int root) { if (node[root].l == node[root].r) return; node[root].res = node[node[root].child[0]].res + node[node[root].child[1]].res; } void build_tree(int root) { if (node[root].l == node[root].r) return; int mid = node[root].l + node[root].r >> 1; node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 1, 0, 0 }, build_tree(tot); node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 1, 0, 0 }, build_tree(tot); push_up(root); } void add_point(int root, int rank, int num) { if (rank < 1 || rank > node[root].res) return; if (node[root].l == node[root].r) { a[node[root].l] = num, -- node[root].res; return; } add_point(node[root].child[1], rank - node[node[root].child[0]].res, num); add_point(node[root].child[0], rank, num); push_up(root); } public: void init(int t) { node[node[tot = 1].l = 1].r = t, build_tree(1); } void add(int rank, int num) { add_point(1, rank, num); } }; struct Solver { private: int x[N + 1], y[N + 1]; SegmentTree tree; void init() { tree.init(n); memset(a, 0, sizeof a); } void process() { for (int i = 1; i <= n; ++ i) scanf("%d%d", &x[i], &y[i]), ++ x[i]; for (int i = n; i; -- i) tree.add(x[i], y[i]); for (int i = 1; i <= n; ++ i) printf("%d ", a[i]); printf("\n"); } public: int n; void solve() { init(), process(); } } solver; int main() { while (~ scanf("%d", &solver.n)) solver.solve(); return 0; }
POJ2886
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read_s(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { (x < 0) && (putchar('-'), x = -x); (x > 9) && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write_s(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct SegmentTree { private: static const int N = 500000; int tot; struct Node { int l, r, val, child[2]; } node[N << 2]; void push_up(int root) { if (node[root].l == node[root].r) return; node[root].val = node[node[root].child[0]].val + node[node[root].child[1]].val; } void build_tree(int root) { if (node[root].l == node[root].r) return; int mid = node[root].l + node[root].r >> 1; node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 1, 0, 0 }, build_tree(tot); node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 1, 0, 0 }, build_tree(tot); push_up(root); } int add_point(int root, int rank) { if (rank < 1 || rank > node[root].val) return 0; if (node[root].l == node[root].r) { -- node[root].val; return node[root].l; } int ret = add_point(node[root].child[1], rank - node[node[root].child[0]].val); ret += add_point(node[root].child[0], rank), push_up(root); return ret; } int query_sum(int root, int l, int r) { if (node[root].r < l || node[root].l > r) return 0; if (node[root].l >= l && node[root].r <= r) return node[root].val; return query_sum(node[root].child[0], l, r) + query_sum(node[root].child[1], l, r); } public: void init(int t) { node[node[tot = 1].l = 1].r = t, build_tree(1); } int add(int rank) { return add_point(1, rank); } int get(int l, int r) { return query_sum(1, l, r); } }; struct Solver { private: static const int N = 500000; int a[N + 1]; int prime[N + 1], e[N + 1], num[N + 1]; bool flag[N + 1]; char c[N + 1][20]; SegmentTree tree; void input() { for (int i = 1; i <= n; ++ i) io.read_s(c[i]), io.read(a[i]); } void process() { if (n == 1) { io.write_s(c[1]), putchar(' '), putchar(1), putchar('\n'); return; } tree.init(n); int p = 0, mx = 0; for (int i = 1; i <= n; ++ i) if (num[i] > mx) mx = num[p = i]; tree.add(k); int now = n; while (-- p) { if (a[k] > 0) a[k] = (a[k] - 1) % -- now + 1; else a[k] = (a[k] + 1) % -- now - 1; if (a[k] >= 0) { int j = k + 1; if (j <= n) { int sum = tree.get(j, n); if (a[k] <= sum) k = tree.add(tree.get(1, k) + a[k]); else k = tree.add(a[k] - sum); } else k = tree.add(a[k]); } else { int j = k - 1; if (j) { int sum = tree.get(1, j); if (-a[k] <= sum) k = tree.add(sum + a[k] + 1); else k = tree.add(tree.get(1, n) + sum + a[k] + 1); } else k = tree.add(tree.get(1, n) + a[k] + 1); } } io.write_s(c[k]), putchar(' '), io.write(mx), putchar('\n'); } public: int n, k; void init() { int cnt = 0; num[1] = 1; for (int i = 2; i <= N; ++ i) { if (! flag[i]) { prime[++ cnt] = i; e[i] = 1, num[i] = 2; } for (int j = 1; j <= cnt && i * prime[j] <= N; ++ j) { flag[i * prime[j]] = true; if (i % prime[j]) { num[i * prime[j]] = num[i] << 1, e[i * prime[j]] = 1; } else { num[i * prime[j]] = num[i] / (e[i] + 1) * (e[i] + 2); e[i * prime[j]] = e[i] + 1; break; } } } } void solve() { input(), process(); } } solver; signed main() { solver.init(); while (io.read(solver.n), io.read(solver.k)) solver.solve(); return 0; }
POJ2942
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { (x < 0) && (putchar('-'), x = -x); (x > 9) && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 1000; static const int M = 1000000; int n, m, tim, cnt, nume, h[N + 1], dfn[N + 1], low[N + 1], col[N + 1]; int sta[M + 1]; bool cut[N + 1], vis[N + 1], act[N + 1], a[N + 1][N + 1], con[N + 1][N + 1]; struct Edge { int u, v, nxt; } e[M + 1 << 1]; void add_edge(int u, int v) { e[++ nume].u = u, e[nume].v = v, e[nume].nxt = h[u], h[u] = nume; e[++ nume].u = v, e[nume].v = u, e[nume].nxt = h[v], h[v] = nume; } bool input() { io.read(n), io.read(m); if (! n || ! m) return false; memset(a, 0, sizeof a); for (int i = 1; i <= m; ++ i) { int u, v; io.read(u), io.read(v), a[u][v] = a[v][u] = true; } return true; } void init() { tim = cnt = nume = 0; memset(h, 0, sizeof h), memset(dfn, 0, sizeof dfn); memset(low, 0, sizeof low), memset(cut, 0, sizeof cut); memset(col, 0, sizeof col), memset(con, 0, sizeof con); memset(act, 0, sizeof act); for (int i = 1; i < n; ++ i) for (int j = i + 1; j <= n; ++ j) if (! a[i][j]) add_edge(i, j); } void dfs(int t, int fa) { int child = 0; dfn[t] = low[t] = ++ tim; for (int i = h[t]; i; i = e[i].nxt) if (e[i].v != fa) if (! dfn[e[i].v]) { sta[++ sta[0]] = i, ++ child, dfs(e[i].v, t), low[t] = min(low[t], low[e[i].v]); if (low[e[i].v] >= dfn[t]) { ++ cnt, cut[t] = true; while (true) { int num = sta[sta[0] --]; if (col[e[num].u] != cnt) con[cnt][e[num].u] = true, col[e[num].u] = cnt; if (col[e[num].v] != cnt) con[cnt][e[num].v] = true, col[e[num].v] = cnt; if (e[num].u == t && e[num].v == e[i].v) break; } } } else if (dfn[e[i].v] < dfn[t]) sta[++ sta[0]] = i, low[t] = min(low[t], dfn[e[i].v]); (! fa && child > 1) && (cut[t] = true); } bool color(int t, int cnt) { vis[t] = true; for (int i = h[t]; i; i = e[i].nxt) if (con[cnt][e[i].v]) if (! vis[e[i].v]) { col[e[i].v] = ! col[t]; if (color(e[i].v, cnt)) return true; } else if (col[e[i].v] == col[t]) return true; return false; } void process() { for (int i = 1; i <= n; ++ i) if (! dfn[i]) dfs(i, 0); for (int i = 1; i <= cnt; ++ i) { bool flag = false; memset(vis, 0, sizeof vis), memset(col, 0, sizeof col); for (int j = 1; j <= n; ++ j) (con[i][j] && ! vis[j]) && (flag = flag | color(j, i)); if (flag) for (int j = 1; j <= n; ++ j) act[j] = act[j] | con[i][j]; } int ans = 0; for (int i = 1; i <= n; ++ i) ans += ! act[i]; io.write(ans), putchar('\n'); } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { while (solver.solve()) ; return 0; }
POJ2947
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { (x < 0) && (putchar('-'), x = -x); (x > 9) && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; static const int MOD = 7; int power(int a, int b) { int ret = 1; a %= MOD, b %= MOD - 1; while (b) { if (b & 1) (ret *= a) %= MOD; (a *= a) %= MOD, b >>= 1; } return ret; } int get_inv(int t) { return power(t, MOD - 2); } struct Gauss { static const int N = 300; int n, m, a[N + 1][N + 2]; void init() { n = m = 0, memset(a, 0, sizeof a); } int solve() { for (int i = 1; i <= min(n, m); ++ i) { if (! a[i][i]) { for (int j = i; j <= m; ++ j) if (a[j][i]) { for (int k = i; k <= n + 1; ++ k) swap(a[i][k], a[j][k]); break; } if (! a[i][i]) { for (int j = i; j <= m; ++ j) { bool flag = false; for (int k = i + 1; k <= n; ++ k) flag = flag || a[j][k]; if (! flag && a[j][n + 1]) return -1; } return 1; } } int inv = get_inv(a[i][i]); for (int j = i; j <= n + 1; ++ j) (a[i][j] *= inv) %= MOD; for (int j = 1; j <= m; ++ j) if (j != i) for (int k = n + 1; k >= i; -- k) (a[j][k] += a[i][k] * (MOD - a[j][i])) %= MOD; } if (n > m) return 1; if (m > n) for (int i = n + 1; i <= m; ++ i) if (a[i][n + 1]) return -1; return 0; } }; struct Solver { private: static const int N = 300; int n, m, rank[N + 1], id[N + 1]; bool flag[N + 1]; char a[4], b[4]; Gauss gauss; int get_num(char c[]) { if (c[0] == 'M') return 1; if (c[0] == 'T') if (c[1] == 'U') return 2; else return 4; if (c[0] == 'W') return 3; if (c[0] == 'F') return 5; if (c[0] == 'S') if (c[1] == 'A') return 6; else return 7; } bool input() { io.read(n), io.read(m); if (! n && ! m) return false; gauss.init(), gauss.n = n, gauss.m = m; for (int i = 1; i <= m; ++ i) { int k; io.read(k), io.read(a), io.read(b); gauss.a[i][n + 1] = (get_num(b) - get_num(a) + 1 + MOD) % MOD; for (int j = 1; j <= k; ++ j) { int x; io.read(x), (gauss.a[i][x] += 1) %= MOD; } } for (int i = 1; i <= n; ++ i) rank[i] = i; memset(flag, 0, sizeof flag); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) flag[i] = flag[i] || gauss.a[j][i]; for (int i = 1; i <= n; ++ i) if (! flag[i]) for (int j = i + 1; j <= n; ++ j) if (flag[j]) { for (int k = 1; k <= m; ++ k) swap(gauss.a[k][i], gauss.a[k][j]); swap(flag[i], flag[j]), swap(rank[i], rank[j]); } for (int i = 1; i <= n; ++ i) id[rank[i]] = i; return true; } void process() { int ans = gauss.solve(); if (! ~ ans) io.write((char *) "Inconsistent data."); else if (! ans) for (int i = 1; i <= n; ++ i) io.write(gauss.a[id[i]][n + 1] < 3 ? gauss.a[id[i]][n + 1] + MOD : gauss.a[id[i]][n + 1]), putchar(' '); else io.write((char *) "Multiple solutions."); putchar('\n'); } public: bool solve() { if (! input()) return false; process(); return true; } } solver; int main() { while (solver.solve()) ; return 0; }
POJ2948
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 500; int n, m, a[N + 1][N + 1], b[N + 1][N + 1], f[2][N + 1][N + 1]; bool input() { io.read(n), io.read(m); if (! n || ! m) return false; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) io.read(a[i][j]); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) io.read(b[i][j]); return true; } void init() { memset(f, 0, sizeof f); for (int i = 1; i <= n; ++ i) for (int j = 2; j <= m; ++ j) a[i][j] += a[i][j - 1]; for (int i = 2; i <= n; ++ i) for (int j = 1; j <= m; ++ j) b[i][j] += b[i - 1][j]; } void process() { for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) { f[0][i][j] = max(f[0][i - 1][j], f[1][i - 1][j]) + a[i][j]; f[1][i][j] = max(f[0][i][j - 1], f[1][i][j - 1]) + b[i][j]; } io.write(max(f[0][n][m], f[1][n][m])), putchar('\n'); } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { while (solver.solve()) ; return 0; }
POJ2976
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; static const double EPS = 1e-6; struct Solver { private: static const int N = 1000; int n, k; long long a[N + 1], b[N + 1]; double c[N + 1]; bool input() { io.read(n), io.read(k); if (! n && ! k) return false; for (int i = 1; i <= n; ++ i) io.read(a[i]); for (int i = 1; i <= n; ++ i) io.read(b[i]); return true; } bool check(double t) { double sum = 0; for (int i = 1; i <= n; ++ i) c[i] = t * b[i] - a[i]; sort(c + 1, c + n + 1); for (int i = 1; i <= n - k; ++ i) sum += c[i]; return sum <= 0; } void process() { double l = 0, r = 1; while (r - l > EPS) { double mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid; } io.write((int) (l * 100 + 0.5)), putchar('\n'); } public: bool solve() { if (! input()) return false; process(); return true; } } solver; int main() { while (solver.solve()) ; return 0; }
POJ2983
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 1000; int nume, h[N + 1], dist[N + 1], cnt[N + 1]; int que[N * N]; bool in[N + 1], vis[N + 1]; struct Edge { int v, c, nxt; } e[N * N]; void add_edge(int u, int v, int c) { e[++ nume].v = v, e[nume].c = c, e[nume].nxt = h[u], h[u] = nume; } void input() { char ch; int a, b, c; memset(h, nume = 0, sizeof h); for (int i = 1; i <= m; ++ i) { io.read(ch), io.read(a), io.read(b); if (ch == 'P') io.read(c), add_edge(a, b, c), add_edge(b, a, -c); else add_edge(b, a, -1); } } bool spfa(int x) { int s = 0, t = 1; vis[que[1] = x] = true, dist[x] = 0, in[x] = cnt[x] = 1; while (s < t) { int u = que[++ s]; in[u] = false; for (int i = h[u]; i; i = e[i].nxt) if (dist[e[i].v] > dist[u] + e[i].c) { vis[e[i].v] = true; dist[e[i].v] = dist[u] + e[i].c; if (! in[e[i].v]) { que[++ t] = e[i].v, ++ cnt[e[i].v], in[e[i].v]= true; if (cnt[e[i].v] > 1000) return false; } } } return true; } void process() { memset(cnt, 0, sizeof cnt); memset(vis, 0, sizeof vis); memset(dist, 0x1f, sizeof dist); bool flag = true; for (int i = 1; i <= n; ++ i) if (! vis[i]) flag = flag && spfa(i); if (flag) io.write((char *) "Reliable"); else io.write((char *) "Unreliable"); putchar('\n'); } public: int n, m; void solve() { input(), process(); } } solver; int main() { while (io.read(solver.n), io.read(solver.m)) solver.solve(); return 0; }
POJ3004
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; static const double EPS = 1e-6; static const double PI = acos(-1); int cmp(double t) { if (fabs(t) < EPS) return 0; if (t > 0) return 1; return -1; } struct Point { int x, y; Point(int _x = 0, int _y = 0) : x(_x), y(_y) {} double operator % (const Point &a) const { return sqrt((x - a.x) * (x - a.x) + (y - a.y) * (y - a.y)); } }; struct Line { double a, b; bool operator < (const Line &x) const { return ! cmp(a - x.a) ? cmp(b - x.b) == 1 : cmp(a - x.a) == -1; } }; struct Solver { private: static const int N = 500; int n, d, top, mx; Point point[N + 1]; Line line[N << 2]; void input() { io.read(n), io.read(d); for (int i = 1; i <= n; ++ i) io.read(point[i].x), io.read(point[i].y); } void init() { top = 0; for (int i = 1; i <= n; ++ i) { double dist = point[i] % Point(); if (cmp(dist - d) < 1) continue; double a = asin(point[i].y / dist); point[i].x < 0 && (a = PI - a); double b = asin(d / dist); a < b && (a += PI * 2); line[++ top].a = a - b, line[top].b = a + b; } for (int i = 1; i <= top; ++ i) line[i + top].a = line[i].a + PI * 2, line[i + top].b = line[i].b + PI * 2; sort(line + 1, line + (top << 1) + 1); } void process() { int ret = top; for (int i = 1; i <= top; ++ i) { int ans = 1; double r = line[i].b; for (int j = 1; j < top; ++ j) { ~ cmp(r - line[i + j].b) && (r = line[i + j].b); ! ~ cmp(r - line[i + j].a) && (++ ans, r = line[i + j].b); } ret = min(ret, ans); } io.write(ret), putchar('\n'); } public: void solve() { input(), init(), process(); } } solver; int main() { int T; io.read(T); while (T --) solver.solve(); return 0; }
POJ3034
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Point { int x, y, t; }; struct Solver { private: static const int N = 1000; int n, d, m, f[50][50][50]; bool b[50][50]; Point point[N + 1]; bool input() { io.read(n), io.read(d), io.read(m); if (! n && ! d && ! m) return false; n += 10; for (int i = 1; i <= m; ++ i) io.read(point[i].x), io.read(point[i].y), io.read(point[i].t), point[i].x += 5, point[i].y += 5; return true; } void init() { memset(f, 0, sizeof f); } void process() { int ans = 0; for (int i = 1; i <= 10; ++ i) { memset(b, 0, sizeof b); for (int j = 1; j <= m; ++ j) if (point[j].t == i) b[point[j].x][point[j].y] = true; for (int j = 0; j < n; ++ j) for (int k = 0; k < n; ++ k) { f[i][j][k] = f[i - 1][j][k] + b[j][k]; // 0 1 if (j) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k] + b[j - 1][k] + b[j][k]); if (k) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1] + b[j][k - 1] + b[j][k]); if (j < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k] + b[j + 1][k] + b[j][k]); if (k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + 1] + b[j][k + 1] + b[j][k]); if (d >= 2) { // 0 2 if (j > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k] + b[j - 2][k] + b[j - 1][k] + b[j][k]); if (k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 2] + b[j][k - 2] + b[j][k - 1] + b[j][k]); if (j < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k] + b[j + 2][k] + b[j + 1][k] + b[j][k]); if (k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + 2] + b[j][k + 2] + b[j][k + 1] + b[j][k]); // 1 1 if (j && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 1] + b[j - 1][k - 1] + b[j][k]); if (j && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k + 1] + b[j - 1][k + 1] + b[j][k]); if (j < n - 1 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k - 1] + b[j + 1][k - 1] + b[j][k]); if (j < n - 1 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k + 1] + b[j + 1][k + 1] + b[j][k]); } if (d >= 3) { // 0 3 if (j > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k] + b[j - 3][k] + b[j - 2][k] + b[j - 1][k] + b[j][k]); if (k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 3] + b[j][k - 3] + b[j][k - 2] + b[j][k - 1] + b[j][k]); if (j < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k] + b[j + 3][k] + b[j + 2][k] + b[j + 1][k] + b[j][k]); if (k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + 3] + b[j][k + 3] + b[j][k + 2] + b[j][k + 1] + b[j][k]); // 2 2 if (j > 1 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k - 2] + b[j - 2][k - 2] + b[j - 1][k - 1] + b[j][k]); if (j > 1 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k + 2] + b[j - 2][k + 2] + b[j - 1][k + 1] + b[j][k]); if (j < n - 2 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k - 2] + b[j + 2][k - 2] + b[j + 1][k - 1] + b[j][k]); if (j < n - 2 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k + 2] + b[j + 2][k + 2] + b[j + 1][k + 1] + b[j][k]); // 1 2 if (j && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 2] + b[j - 1][k - 2] + b[j][k]); if (j > 1 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k - 1] + b[j - 2][k - 1] + b[j][k]); if (j && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k + 2] + b[j - 1][k + 2] + b[j][k]); if (j < n - 2 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k - 1] + b[j + 2][k - 1] + b[j][k]); if (j > 1 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k + 1] + b[j - 2][k + 1] + b[j][k]); if (j < n - 1 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k - 2] + b[j + 1][k - 2] + b[j][k]); if (j < n - 2 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k + 1] + b[j + 2][k + 1] + b[j][k]); if (j < n - 1 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k + 2] + b[j + 1][k + 2] + b[j][k]); } if (d >= 4) { // 0 4 if (j > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k] + b[j - 4][k] + b[j - 3][k] + b[j - 2][k] + b[j - 1][k] + b[j][k]); if (k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 4] + b[j][k - 4] + b[j][k - 3] + b[j][k - 2] + b[j][k - 1] + b[j][k]); if (j < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k] + b[j + 4][k] + b[j + 3][k] + b[j + 2][k] + b[j + 1][k] + b[j][k]); if (k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + 4] + b[j][k + 4] + b[j][k + 3] + b[j][k + 2] + b[j][k + 1] + b[j][k]); // 1 3 if (j && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 3] + b[j - 1][k - 3] + b[j][k]); if (j > 2 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k - 1] + b[j - 3][k - 1] + b[j][k]); if (j && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k + 3] + b[j - 1][k + 3] + b[j][k]); if (j < n - 3 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k - 1] + b[j + 3][k - 1] + b[j][k]); if (j > 2 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k + 1] + b[j - 3][k + 1] + b[j][k]); if (j < n - 1 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k - 3] + b[j + 1][k - 3] + b[j][k]); if (j < n - 3 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k + 1] + b[j + 3][k + 1] + b[j][k]); if (j < n - 1 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k + 3] + b[j + 1][k + 3] + b[j][k]); // 2 3 if (j > 2 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k - 2] + b[j - 3][k - 2] + b[j][k]); if (j > 1 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k - 3] + b[j - 2][k - 3] + b[j][k]); if (j > 1 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k + 3] + b[j - 2][k + 3] + b[j][k]); if (j < n - 3 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k - 2] + b[j + 3][k - 2] + b[j][k]); if (j > 2 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k + 2] + b[j - 3][k + 2] + b[j][k]); if (j < n - 2 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k - 3] + b[j + 2][k - 3] + b[j][k]); if (j < n - 3 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k + 2] + b[j + 3][k + 2] + b[j][k]); if (j < n - 2 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k + 3] + b[j + 2][k + 3] + b[j][k]); } if (d >= 5) { // 0 5 if (j > 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 5][k] + b[j - 5][k] + b[j - 4][k] + b[j - 3][k] + b[j - 2][k] + b[j - 1][k] + b[j][k]); if (k > 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 5] + b[j][k - 5] + b[j][k - 4] + b[j][k - 3] + b[j][k - 2] + b[j][k - 1] + b[j][k]); if (j < n - 5) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 5][k] + b[j + 5][k] + b[j + 4][k] + b[j + 3][k] + b[j + 2][k] + b[j + 1][k] + b[j][k]); if (k < n - 5) f[i][j][k] = max(f[i][j][k], f[i - 1][j][k + 5] + b[j][k + 5] + b[j][k + 4] + b[j][k + 3] + b[j][k + 2] + b[j][k + 1] + b[j][k]); // 3 3 if (j > 2 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k - 3] + b[j - 3][k - 3] + b[j - 2][k - 2] + b[j - 1][k - 1] + b[j][k]); if (j > 2 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k + 3] + b[j - 3][k + 3] + b[j - 2][k + 2] + b[j - 1][k + 1] + b[j][k]); if (j < n - 3 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k - 3] + b[j + 3][k - 3] + b[j + 2][k - 2] + b[j + 1][k - 1] + b[j][k]); if (j < n - 3 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k + 3] + b[j + 3][k + 3] + b[j + 2][k + 2] + b[j + 1][k + 1] + b[j][k]); // 1 4 if (j && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 4] + b[j - 1][k - 4] + b[j][k]); if (j > 3 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k - 1] + b[j - 4][k - 1] + b[j][k]); if (j && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k + 4] + b[j - 1][k + 4] + b[j][k]); if (j < n - 4 && k) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k - 1] + b[j + 4][k - 1] + b[j][k]); if (j > 3 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k + 1] + b[j - 4][k + 1] + b[j][k]); if (j < n - 1 && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k - 4] + b[j + 1][k - 4] + b[j][k]); if (j < n - 4 && k < n - 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k + 1] + b[j + 4][k + 1] + b[j][k]); if (j < n - 1 && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 1][k + 4] + b[j + 1][k + 4] + b[j][k]); // 2 4 if (j > 1 && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k - 4] + b[j - 2][k - 4] + b[j - 1][k - 2] + b[j][k]); if (j > 3 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k - 2] + b[j - 4][k - 2] + b[j - 2][k - 1] + b[j][k]); if (j > 1 && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 2][k + 4] + b[j - 2][k + 4] + b[j - 1][k + 2] + b[j][k]); if (j < n - 4 && k > 1) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k - 2] + b[j + 4][k - 2] + b[j + 2][k - 1] + b[j][k]); if (j > 3 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k + 2] + b[j - 4][k + 2] + b[j - 2][k + 1] + b[j][k]); if (j < n - 2 && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k - 4] + b[j + 2][k - 4] + b[j + 1][k - 2] + b[j][k]); if (j < n - 4 && k < n - 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k + 2] + b[j + 4][k + 2] + b[j + 2][k + 1] + b[j][k]); if (j < n - 2 && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 2][k + 4] + b[j + 2][k + 4] + b[j + 1][k + 2] + b[j][k]); // 3 4 if (j > 2 && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k - 4] + b[j - 3][k - 4] + b[j][k]); if (j > 3 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k - 3] + b[j - 4][k - 3] + b[j][k]); if (j > 3 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 4][k + 3] + b[j - 4][k + 3] + b[j][k]); if (j < n - 3 && k > 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k - 4] + b[j + 3][k - 4] + b[j][k]); if (j > 2 && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j - 3][k + 4] + b[j - 3][k + 4] + b[j][k]); if (j < n - 4 && k > 2) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k - 3] + b[j + 4][k - 3] + b[j][k]); if (j < n - 3 && k < n - 4) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 3][k + 4] + b[j + 3][k + 4] + b[j][k]); if (j < n - 4 && k < n - 3) f[i][j][k] = max(f[i][j][k], f[i - 1][j + 4][k + 3] + b[j + 4][k + 3] + b[j][k]); } } } for (int i = 0; i < n; ++ i) for (int j = 0; j < n; ++ j) ans = max(ans, f[10][i][j]); io.write(ans), putchar('\n'); } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { while (solver.solve()) ; return 0; }
POJ3070
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Matrix { int n, m, a[2][2]; Matrix(int _n = 0, int _m = 0) : n(_n), m(_m) { memset(a, 0, sizeof a); } Matrix operator * (const Matrix &t) const { Matrix q(n, t.m); for (int i = 0; i < n; ++ i) for (int j = 0; j < t.m; ++ j) { for (int k = 0; k < m; ++ k) q.a[i][j] += a[i][k] * t.a[k][j]; q.a[i][j] %= 10000; } return q; } Matrix operator ^ (const int &t) const { int b = t; Matrix p(n, n), q(n, n); p.a[0][0] = a[0][0], p.a[0][1] = a[0][1]; p.a[1][0] = a[1][0], p.a[1][1] = a[1][1]; q.a[0][0] = q.a[1][1] = 1; while (b) { if (b & 1) q = q * p; p = p * p, b >>= 1; } return q; } }; struct Solver { private: static const int N = 100000; int n; Matrix a; bool input() { io.read(n); return ~ n; } void process() { if (! n) io.write(0); else if (n < 3) io.write(1); else { a.n = a.m = 2; a.a[0][0] = a.a[0][1] = a.a[1][0] = 1, a.a[1][1] = 0; a = a ^ (n - 2), io.write((a.a[0][0] + a.a[0][1]) % 10000); } putchar('\n'); } public: bool solve() { if (! input()) return false; process(); return true; } } solver; int main() { while (solver.solve()) ; return 0; }
POJ3071
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 7; int n; double a[1 << N][1 << N], f[N][1 << N]; bool input() { scanf("%d", &n); if (! ~ n) return false; for (int i = 0; i < 1 << n; ++ i) for (int j = 0; j < 1 << n; ++ j) scanf("%lf", &a[i][j]); return true; } void init() { memset(f, 0, sizeof f); for (int i = 0; i < 1 << n; ++ i) f[0][i] = a[i][i ^ 1]; } void process() { for (int i = 1; i < n; ++ i) { for (int j = 0; j < 1 << n; ++ j) { int tmp = (j >> i << i) ^ (1 << i); for (int k = 0; k < 1 << i; ++ k) f[i][j] += f[i - 1][j] * f[i - 1][tmp + k] * a[j][tmp + k]; } } double mx(0); int p; for (int i = 0; i < 1 << n; ++ i) if (f[n - 1][i] > mx) mx = f[n - 1][p = i]; printf("%d\n", p + 1); } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { while (solver.solve()) ; return 0; }
POJ3101
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; long long get_gcd(long long a, long long b) { return b ? get_gcd(b, a % b) : a; } struct Fraction { private: long long a, b; public: Fraction(long long _a = 0, long long _b = 1) : a(_a), b(_b) { long long gcd = get_gcd(a, b); a /= gcd, b /= gcd; } Fraction operator + (const Fraction &_a) const { return Fraction(a * _a.b + b * _a.a, b * _a.b); } Fraction operator - (const Fraction &_a) const { return Fraction(a * _a.b - b * _a.a, b * _a.b); } Fraction operator * (const Fraction &_a) const { return Fraction(a * _a.a, b * _a.b); } Fraction operator / (const Fraction &_a) const { return Fraction(a * _a.b, b * _a.a); } int up() { return a; } int down() { return b; } void print() { io.write(a), putchar(' '), io.write(b); } }; struct Solver { private: static const int N = 1000; int n, top, a[N + 1], up[N * N + 1], ans[N * N + 1]; Fraction v[N + 1], t[N + 1]; void input() { io.read(n); for (int i = 1; i <= n; ++ i) io.read(a[i]); } void init() { sort(a + 1, a + n + 1); top = 0; memset(up, 0, sizeof up), memset(ans, 0, sizeof ans); for (int i = 1; i <= n; ++ i) if (a[i] != a[i - 1]) v[++ top] = Fraction(360, a[i]); for (int i = 2; i <= top; ++ i) t[i - 1] = Fraction(180) / (v[i - 1] - v[i]); } void process() { int down = 0; for (int i = 1; i < top; ++ i) { int tmp = t[i].up(); for (int j = 2; j <= 10000; ++ j) if (! (tmp % j)) { int cnt = 0; while (! (tmp % j)) tmp /= j, ++ cnt; up[j] = max(up[j], cnt); if (tmp == 1) break; } if (tmp > 1) up[tmp] = 1; down = get_gcd(down, t[i].down()); } for (int i = 2; i <= 1000000; ++ i) while (up[i] && ! (down % i)) down /= i, -- up[i]; ans[ans[0] = 1] = 1; for (int i = 2; i <= 1000000; ++ i) while (up[i] > 0) { for (int j = 1; j <= ans[0]; ++ j) ans[j] *= i; for (int j = 1; j <= ans[0]; ++ j) ans[j + 1] += ans[j] / 100, ans[j] %= 100; while (ans[ans[0] + 1]) ++ ans[0], ans[ans[0] + 1] += ans[ans[0]] / 100, ans[ans[0]] %= 100; -- up[i]; } for (int i = ans[0]; i; -- i) { int base = 10; while (i < ans[0] && ans[i] < base) putchar('0'), base /= 10; if (i == ans[0] || ans[i]) io.write(ans[i]); } putchar(' '), io.write(down), putchar('\n'); } public: void solve() { input(), init(), process(); } } solver; int main() { solver.solve(); return 0; }
POJ3140
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Graph { private: static const int N = 100000; int nume, h[N + 1]; public: struct Edge { int v, nxt; } e[N + 1 << 1]; void init() { memset(h, nume = 0, sizeof h); } void add_edge(int u, int v) { e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume; e[++ nume].v = u, e[nume].nxt = h[v], h[v] = nume; } Edge begin(int t) { return e[h[t]]; } Edge next(Edge t) { return e[t.nxt]; } }; struct Solver { private: static const int N = 100000; int T, n, m, sum, size[N + 1]; Graph graph; int _abs(int t) { return t > 0 ? t : -t; } bool input() { io.read(n), io.read(m); if (! n && ! m) return false; graph.init(), sum = 0; for (int i = 1; i <= n; ++ i) io.read(size[i]), sum += size[i]; for (int i = 1; i <= m; ++ i) { int u, v; io.read(u), io.read(v); graph.add_edge(u, v); } return true; } void dfs(int t, int fa) { for (Graph::Edge e = graph.begin(t); e.v; e = graph.next(e)) if (e.v != fa) dfs(e.v, t), size[t] += size[e.v]; } void process() { int ans = sum; dfs(1, 0); for (int i = 1; i <= n; ++ i) ans = min(ans, _abs((size[i] << 1) - sum)); io.write((char *) "Case "), io.write(++ T), io.write((char *) ": "), io.write(ans), putchar('\n'); } public: bool solve() { if (! input()) return false; process(); return true; } } solver; signed main() { while (solver.solve()) ; return 0; }
POJ3150
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Matrix { static const int N = 500; int n, m, a[N + 1][N + 1]; Matrix(int _n = 0, int _m = 1) : n(_n), m(_m) { memset(a, 0, sizeof a); } Matrix operator * (const Matrix &x) const { Matrix ret(n, m); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) (ret.a[1][i] += a[1][j] * x.a[j][i]) %= m; for (int i = 2; i <= n; ++ i) for (int j = 1; j <= n; ++ j) ret.a[i][j] = ret.a[i - 1][(j + n - 2) % n + 1]; return ret; } }; struct Solver { private: static const int N = 500; int a[N + 1]; Matrix p, ans; void input() { for (int i = 1; i <= n; ++ i) io.read(a[i]); } void init() { p.n = ans.n = n, p.m = ans.m = m; memset(p.a, 0, sizeof p.a); memset(ans.a, 0, sizeof ans.a); for (int i = 1; i <= n; ++ i) for (int j = -d; j <= d; ++ j) p.a[i][(i + j + n - 1) % n + 1] = 1; for (int i = 1; i <= n; ++ i) ans.a[i][i] = 1; } void process() { while (k) { if (k & 1) ans = ans * p; p = p * p, k >>= 1; } for (int i = 1; i <= n; ++ i) { int sum = 0; for (int j = 1; j <= n; ++ j) (sum += ans.a[i][j] * a[j]) %= m; io.write(sum), putchar(' '); } putchar('\n'); } public: int n, m, d, k; void solve() { input(), init(), process(); } } solver; signed main() { while (io.read(solver.n), io.read(solver.m), io.read(solver.d), io.read(solver.k)) solver.solve(); return 0; }
POJ3227
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; static const double EPS = 1e-6; int cmp(double t) { return fabs(t) < EPS ? 0 : t > 0 ? 1 : -1; } struct Point { double x, y; Point(double _x = 0, double _y = 0) : x(_x), y(_y) {} Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); } Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); } Point operator * (const double &p) const { return Point(x * p, y * p); } double operator * (const Point &p) const { return x * p.y - y * p.x; } double operator % (const Point &p) const { return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y)); } }; struct Line { Point a, b; Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {} Line(double x1, double y1, double x2, double y2) : a(Point(x1, y1)), b(Point(x2, y2)) {} bool operator < (const Line &l) const { return ! ~ cmp(atan2(b.y - a.y, b.x - a.x) - atan2(l.b.y - l.a.y, l.b.x - l.a.x)); } Point operator & (const Line &l) const { double t = (a - l.a) * (l.a - l.b) / ((a - b) * (l.a - l.b)); return a + (b - a) * t; } }; struct Solver { private: static const int N = 1000; int n, h; double ans; Point point[N + 1]; Line now; bool input() { io.read(n), io.read(h); if (! n && ! h) return false; for (int i = 1; i <= n; ++ i) { int x, y; io.read(x), io.read(y), point[i] = Point(x, y); } return true; } void init() { ans = 0, now = Line(0, h, point[1].x, 0); } void process() { for (int i = 1; i < n; ++ i) if (now < Line(Point(0, h), point[i + 1])) { Point tmp = now & Line(point[i], point[i + 1]); if (~ cmp(tmp.x - point[i].x) && ~ cmp(point[i + 1].x - tmp.x)) ans += tmp % point[i + 1], now.b = point[i + 1]; } printf("%.2lf\n", ans); } public: bool solve() { if (! input()) return false; init(), process(); return true; } } solver; int main() { while (solver.solve()) ; return 0; }
POJ3254
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 12; static const int MOD = 100000000; int n, m, tot, a[N + 1], pool[1 << N], f[N + 1][1 << N]; void input() { io.read(n), io.read(m); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) { int t; io.read(t), (a[i] <<= 1) += ! t; } } bool check(int t) { bool flag = false; while (t) { if (t & 1) if (flag) return false; else flag = true; else flag = false; t >>= 1; } return true; } void init() { for (int i = 0; i < 1 << m; ++ i) if (check(i)) pool[++ tot] = i; } void process() { int ans = 0; f[0][1] = 1; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= tot; ++ j) for (int k = 1; k <= tot; ++ k) if (! (pool[k] & a[i]) && ! (pool[k] & pool[j])) (f[i][k] += f[i - 1][j]) %= MOD; for (int i = 1; i <= tot; ++ i) (ans += f[n][i]) %= MOD; io.write(ans), putchar('\n'); } public: void solve() { input(), init(), process(); } } solver; int main() { solver.solve(); return 0; }
POJ3264
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 50000; static const int M = 16; int n, q, a[N + 1], mx[N + 1][16], mn[N + 1][16], num[N + 1]; void input() { io.read(n), io.read(q); for (int i = 1; i <= n; ++ i) io.read(a[i]); } void init() { for (int i = 1; i <= n; ++ i) mx[i][0] = mn[i][0] = a[i]; for (int i = 1; i < 16; ++ i) for (int j = 1; j <= n; ++ j) { mx[j][i] = max(mx[j][i - 1], mx[min(n, j + (1 << i - 1))][i - 1]); mn[j][i] = min(mn[j][i - 1], mn[min(n, j + (1 << i - 1))][i - 1]); } for (int i = 1; 1 << i < n; ++ i) num[1 << i] = 1; for (int i = 2; i <= n; ++ i) num[i] += num[i - 1]; } void process() { int l, r; io.read(l), io.read(r); int len = r - l + 1; io.write(max(mx[l][num[len]], mx[r - (1 << num[len]) + 1][num[len]]) - min(mn[l][num[len]], mn[r - (1 << num[len]) + 1][num[len]])), putchar('\n'); } public: void solve() { input(), init(); while (q --) process(); } } solver; int main() { solver.solve(); return 0; }
POJ3270
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Number { int num, id, rank; }; bool cmpn(Number a, Number b) { return a.num < b.num; } bool cmpi(Number a, Number b) { return a.id < b.id; } struct Solver { private: static const int N = 10000; int n, t, cnt[N + 1], sum[N + 1], mn[N + 1], size[N + 1]; bool vis[N + 1], st[N + 1]; Number a[N + 1]; void input() { io.read(n), t = 1e9; for (int i = 1; i <= n; ++ i) io.read(a[i].num), a[i].id = i, t = min(t, a[i].num); } void init() { sort(a + 1, a + n + 1, cmpn); for (int i = 1; i <= n; ++ i) a[i].rank = i; sort(a + 1, a + n + 1, cmpi); } void dfs(int t) { vis[t] = true, size[t] = 1, sum[t] = mn[t] = a[t].num; if (! vis[a[t].rank]) dfs(a[t].rank), size[t] += size[a[t].rank], sum[t] += sum[a[t].rank], mn[t] = min(mn[t], mn[a[t].rank]); } void process() { int ans = 0; for (int i = 1; i <= n; ++ i) if (! vis[i]) st[i] = true, dfs(i); for (int i = 1; i <= n; ++ i) if (st[i]) ans += min(sum[i] + (size[i] - 2) * mn[i], sum[i] + mn[i] + (size[i] + 1) * t); io.write(ans), putchar('\n'); } public: void solve() { input(), init(), process(); } } solver; signed main() { solver.solve(); return 0; }
POJ3277
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct SegmentTree { private: static const int N = 100000; int tot; struct Node { int l, r, val, child[2]; } node[N << 2]; void build_tree(int root) { if (node[root].l == node[root].r) return; int mid = node[root].l + node[root].r >> 1; node[node[root].child[0] = ++ tot] = (Node) { node[root].l, mid, 0, 0, 0 }, build_tree(tot); node[node[root].child[1] = ++ tot] = (Node) { mid + 1, node[root].r, 0, 0, 0 }, build_tree(tot); } void insert_line(int root, int l, int r, int val) { if (node[root].r < l || node[root].l > r) return; if (node[root].l >= l && node[root].r <= r) { node[root].val = max(node[root].val, val); return; } insert_line(node[root].child[0], l, r, val); insert_line(node[root].child[1], l, r, val); } int query_point(int root, int p) { if (node[root].r < p || node[root].l > p) return 0; if (node[root].l == node[root].r) return node[root].val; return max(node[root].val, max(query_point(node[root].child[0], p), query_point(node[root].child[1], p))); } public: void init(int t) { node[node[tot = 1].l = 1].r = t, build_tree(tot); } void add(int l, int r, int val) { insert_line(1, l, r, val); } int get(int p) { return query_point(1, p); } }; struct Point { int x, id, rank, h; }; bool cmpx(Point a, Point b) { return a.x < b.x; } bool cmpi(Point a, Point b) { return a.id < b.id; } struct Solver { private: static const int N = 100000; int n, mx, xmap[N]; Point point[N]; SegmentTree tree; void input() { io.read(n); for (int i = 1; i <= n; ++ i) { io.read(point[i].x), io.read(point[i + n].x), io.read(point[i].h); point[i].id = i, point[i + n].id = i + n; } } void init() { sort(point + 1, point + (n << 1) + 1, cmpx); for (int i = 1; i <= n << 1; ++ i) point[i].rank = point[i - 1].rank + (point[i].x != point[i - 1].x), xmap[point[i].rank] = point[i].x; mx = point[n << 1].rank; sort(point + 1, point + (n << 1) + 1, cmpi); } void process() { int ans = 0; tree.init(n << 1); for (int i = 1; i <= n; ++ i) tree.add(point[i].rank, point[i + n].rank - 1, point[i].h); for (int i = 1; i < mx; ++ i) ans += tree.get(i) * (xmap[i + 1] - xmap[i]); io.write(ans), putchar('\n'); } public: void solve() { input(), init(), process(); } } solver; signed main() { solver.solve(); return 0; }
POJ3280
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 2000; int n, m, cost[1 << 8][2], f[N + 1][N + 1]; char s[N + 1]; void input() { io.read(n), io.read(m), io.read(s); for (int i = 1; i <= n; ++ i) { char c; io.read(c); int x, y; io.read(x), io.read(y); cost[c][0] = x, cost[c][1] = y; } } void init() { memset(f, 0x1f, sizeof f); for (int i = 1; i <= m; ++ i) for (int j = 1; j <= i; ++ j) f[i][j] = 0; for (int i = 2; i <= m; ++ i) for (int j = 1; j <= m - i + 1; ++ j) { if (s[j - 1] == s[j + i - 2]) f[j][j + i - 1] = f[j + 1][j + i - 2]; else f[j][j + i - 1] = min(f[j][j + i - 2] + min(cost[s[j + i - 2]][0], cost[s[j + i - 2]][1]), f[j + 1][j + i - 1] + min(cost[s[j - 1]][0], cost[s[j - 1]][1])); } } void process() { io.write(f[1][m]), putchar('\n'); } public: void solve() { input(), init(), process(); } } solver; int main() { solver.solve(); return 0; }
POJ3286
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: int n, m; bool input() { io.read(n), io.read(m); return ~ n && ~ m; } int get(int t) { if (t < 0) return 0; int ret = 1 + t / 10, base = 10; for (int i = 1; i <= 10; ++ i, base *= 10) { int q = t / base / 10; if (! q) break; ret += (q - 1) * base + (t / base % 10 ? base : t % base + 1); } return ret; } void process() { io.write(get(m) - get(n - 1)), putchar('\n'); } public: bool solve() { if (! input()) return false; process(); return true; } } solver; signed main() { while (solver.solve()) ; return 0; }
POJ3296
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct Solver { private: static const int N = 100000; int k; double b, w, r, c; bool input() { scanf("%d%lf%lf%lf%lf", &k, &b, &w, &r, &c); return k; } void process() { double ans = w, tmp = 0; if (r > w) { double fi = r - w; b -= fi; if (b <= 0) { printf("0 \n"); return; } b /= k; printf("%d %.2lf ", k, min(b + fi, c - w)); for (int i = 1; i < k; ++ i) printf("%.2lf ", min(b, c - r)); putchar('\n'); } else { double fi = w - r; if ((b + fi) / k > fi) { (b += fi) /= k; printf("%d %.2lf ", k, min(b - fi, c - w)); for (int i = 1; i < k; ++ i) printf("%.2lf ", min(b, c - r)); putchar('\n'); } else { b /= k - 1; printf("%d 0.00 ", k); for (int i = 1; i < k; ++ i) printf("%.2lf ", min(b, c - r)); putchar('\n'); } } } public: bool solve() { if (! input()) return false; process(); return true; } } solver; int main() { while (solver.solve()) ; return 0; }
POJ3301
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Point { double x, y; Point(double _x = 0, double _y = 0) : x(_x), y(_y) {} Point operator ^ (const double &a) const { return Point(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a)); } }; static const double EPS = 1e-8; static const double PI = acos(-1.0); struct Solver { private: static const int N = 30; int n; Point point[N + 1], tmp[N + 1]; void input() { io.read(n); for (int i = 1; i <= n; ++ i) { int x, y; io.read(x), io.read(y), point[i] = Point(x, y); } } double get(double t) { for (int i = 1; i <= n; ++ i) tmp[i] = point[i] ^ t; double mxx = -500, mxy = -500, mnx = 500, mny = 500; for (int i = 1; i <= n; ++ i) { mxx = max(mxx, tmp[i].x), mxy = max(mxy, tmp[i].y); mnx = min(mnx, tmp[i].x), mny = min(mny, tmp[i].y); } return max(mxx - mnx, mxy - mny); } void process() { double l = 0, r = PI; while (r - l > EPS) { double ml = l + (r - l) / 3, mr = r - (r - l) / 3; double vl = get(ml), vr = get(mr); if (vl < vr) r = mr; else l = ml; } printf("%.2lf\n", get(l) * get(l)); } public: void solve() { input(), process(); } } solver; int main() { int T; io.read(T); while (T --) solver.solve(); return 0; }
POJ3308
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; static const double EPS = 1e-8; static const double MAX = 1e4; struct Solver { private: static const int N = 2000; int n, m, l, nume, h[N + 1]; struct Edge { int v, nxt; double c; } e[N << 1]; void add_edge(int u, int v, double c) { e[++ nume].v = v, e[nume].c = c, e[nume].nxt = h[u], h[u] = nume; e[++ nume].v = u, e[nume].c = 0, e[nume].nxt = h[v], h[v] = nume; } void input() { memset(h, 0, sizeof h), nume = 1; io.read(n), io.read(m), io.read(l); for (int i = 1; i <= n; ++ i) { double t; scanf("%lf", &t), add_edge(0, i, log(t)); } for (int i = 1; i <= m; ++ i) { double t; scanf("%lf", &t), add_edge(n + i, n + m + 1, log(t)); } for (int i = 1; i <= l; ++ i) { int u, v; io.read(u), io.read(v), add_edge(u, n + v, MAX); } } int s, t, g[N + 1], que[N + 1], dist[N + 1]; bool bfs() { memset(dist, 0x1f, sizeof dist); int qb = 0, qe = 1; dist[que[1] = s] = 0; while (qb < qe) { int u = que[++ qb]; for (int i = h[u]; i; i = e[i].nxt) if (e[i].c > 0 && dist[e[i].v] > dist[u] + 1) dist[que[++ qe] = e[i].v] = dist[u] + 1; } return dist[t] < 5e8; } double dfs(int u, double low) { if (u == t) return low; double used = 0; for (int i = g[u]; i; i = e[i].nxt) if (e[i].c > 0 && dist[e[i].v] == dist[u] + 1) { double delta = dfs(e[i].v, min(e[i].c, low - used)); if (delta) e[i].c -= delta, e[i ^ 1].c += delta, used += delta; if (e[i].c > 0) g[u] = i; if (low == used) break; } return used; } void process() { s = 0, t = n + m + 1; double flow = 0; while (bfs()) { for (int i = 0; i <= n + m + 1; ++ i) g[i] = h[i]; flow += dfs(s, MAX); } printf("%.4lf\n", exp(flow)); } public: void solve() { input(), process(); } } solver; int main() { int T; io.read(T); while (T --) solver.solve(); return 0; }
POJ3318
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <ctime> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c = '\n'; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; if (! ~ c) return false; c == '-' && (flag = true, c = getchar()); while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c = '\n'; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 500; int a[N + 1][N + 1], b[N + 1][N + 1], c[N + 1][N + 1]; int d[N + 1], e[N + 1], f[N + 1], g[N + 1]; void input() { for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) io.read(a[i][j]); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) io.read(b[i][j]); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) io.read(c[i][j]); } void init() { for (int i = 1; i <= n; ++ i) d[i] = rand() % 100; memset(e, 0, sizeof e), memset(f, 0, sizeof f), memset(g, 0, sizeof g); } void process() { for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) e[i] += d[j] * a[j][i]; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) f[i] += e[j] * b[j][i]; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) g[i] += d[j] * c[j][i]; for (int i = 1; i <= n; ++ i) if (f[i] != g[i]) { io.write((char *) "NO\n"); return; } io.write((char *) "YES\n"); } public: int n; void solve() { input(), init(), process(); } } solver; int main() { srand(time(NULL)); while (io.read(solver.n)) solver.solve(); return 0; }
POJ3321
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct BinaryIndexedTree { private: static const int N = 100000; int a[N + 1]; public: int n; void add(int p, int val) { for (; p <= n; p += p & -p) a[p] += val; } int get(int p) { int ret = 0; for (; p; p -= p & -p) ret += a[p]; return ret; } int sum(int l, int r) { return get(r) - get(l - 1); } }; struct Solver { private: static const int N = 100000; int n, m, nume, tim, h[N + 1], id[N + 1], last[N + 1]; bool has[N + 1]; BinaryIndexedTree tree; struct Edge { int v, nxt; } e[N << 1]; void add_edge(int u, int v) { e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume; e[++ nume].v = u, e[nume].nxt = h[v], h[v] = nume; } void input() { io.read(n); for (int i = 1; i < n; ++ i) { int u, v; io.read(u), io.read(v), add_edge(u, v); } } void dfs(int t, int fa) { id[t] = ++ tim; for (int i = h[t]; i; i = e[i].nxt) if (e[i].v != fa) dfs(e[i].v, t); last[t] = tim; } void process() { dfs(1, 0), io.read(m), tree.n = n, memset(has, 1, sizeof has); for (int i = 1; i <= n; ++ i) tree.add(i, 1); while (m --) { char c; int t; io.read(c), io.read(t); if (c == 'Q') io.write(tree.sum(id[t], last[t])), putchar('\n'); else { if (has[t]) tree.add(id[t], -1); else tree.add(id[t], 1); has[t] = ! has[t]; } } } public: void solve() { input(), process(); } } solver; int main() { solver.solve(); return 0; }
POJ3352
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 1000; int nume, tim, h[N + 1], dfn[N + 1], low[N + 1], sta[N + 1], col[N + 1], in[N + 1]; struct Edge { int v, nxt; } e[N + 1 << 1]; void add_edge(int u, int v) { e[++ nume].v = v, e[nume].nxt = h[u], h[u] = nume; e[++ nume].v = u, e[nume].nxt = h[v], h[v] = nume; } void input() { memset(h, nume = 0, sizeof h); for (int i = 1; i <= r; ++ i) { int u, v; io.read(u), io.read(v), add_edge(u, v); } } void dfs(int t, int fa) { sta[++ sta[0]] = t; dfn[t] = low[t] = ++ tim; for (int i = h[t]; i; i = e[i].nxt) if (e[i].v != fa) if (dfn[e[i].v]) low[t] = min(low[t], dfn[e[i].v]); else { dfs(e[i].v, t), low[t] = min(low[t], low[e[i].v]); if (low[e[i].v] > dfn[t]) { while (sta[sta[0]] != e[i].v) col[sta[sta[0] --]] = e[i].v; col[sta[sta[0] --]] = e[i].v; } } } void process() { tim = 0, memset(dfn, 0, sizeof dfn), dfs(1, 0); while (sta[0]) col[sta[sta[0] -- ]] = 1; memset(in, 0, sizeof in); for (int i = 1; i <= n; ++ i) for (int j = h[i]; j; j = e[j].nxt) if (col[i] < col[e[j].v]) ++ in[col[i]], ++ in[col[e[j].v]]; int ans = 0; for (int i = 1; i <= n; ++ i) ans += in[i] == 1; io.write(ans + 1 >> 1), putchar('\n'); } public: int n, r; void solve() { input(), process(); } } solver; int main() { while (io.read(solver.n), io.read(solver.r)) solver.solve(); return 0; }
POJ3368
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline bool read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return false; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', true); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 100000; int n, q, a[N + 1], b[N + 1], s[N + 1], t[N + 1], cnt[N + 1]; int mx[N + 1][20], lo[N + 1]; bool input() { io.read(n); if (! n) return false; io.read(q); for (int i = 1; i <= n; ++ i) io.read(a[i]); return true; } void init() { b[1] = 1; for (int i = 2; i <= n; ++ i) b[i] = b[i - 1] + (a[i] != a[i - 1]); s[1] = 1, t[b[n]] = n; for (int i = 2; i <= n; ++ i) if (b[i] != b[i - 1]) t[b[i - 1]] = i - 1, s[b[i]] = i; memset(cnt, 0, sizeof cnt), memset(lo, 0, sizeof lo); for (int i = 1; i <= n; ++ i) ++ cnt[b[i]]; for (int i = 1; i <= b[n]; ++ i) mx[i][0] = cnt[i]; for (int i = 1; i < 20; ++ i) for (int j = 1; j <= n; ++ j) mx[j][i] = max(mx[j][i - 1], mx[min(n, j + (1 << i - 1))][i - 1]); for (int i = 1; 1 << i <= b[n]; ++ i) ++ lo[1 << i]; for (int i = 1; i <= b[n]; ++ i) lo[i] += lo[i - 1]; } int query(int l, int r) { if (l > r) return 0; int len = r - l + 1; return max(mx[l][lo[len]], mx[r - (1 << lo[len]) + 1][lo[len]]); } void process() { int l, r; io.read(l), io.read(r); io.write(b[l] < b[r] ? max(max(t[b[l]] - l + 1, r - s[b[r]] + 1), query(b[l] + 1, b[r] - 1)) : r - l + 1), putchar('\n'); } public: bool solve() { if (! input()) return false; init(); while (q --) process(); return true; } } solver; int main() { while (solver.solve()) ; return 0; }
POJ3373
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline int read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 110; static const int K = 10000; int k, base, f[N][K], nxt[N][K], cho[N][K]; void input() { io.read(k); } void init() { memset(f, 0x1f, sizeof f); memset(cho, 0, sizeof cho); memset(nxt, 0, sizeof nxt); } void print(int a, int b) { if (a > len) return; io.write(cho[a][b]), print(a + 1, nxt[a][b]); } void process() { base = 10 % k; for (int i = 0; i < 10; ++ i) if ((i + '0' != c[len - 1]) < f[len][i % k]) f[len][i % k] = i + '0' != c[len - 1], cho[len][i % k] = i; for (int i = len; i > 1; -- i, (base *= 10) %= k) for (int j = i == 2 ? 1 : 0; j < 10; ++ j) for (int l = 0; l < k; ++ l) if (f[i][l] + (j + '0' != c[i - 2]) < f[i - 1][(j * base + l) % k]) { f[i - 1][(j * base + l) % k] = f[i][l] + (j + '0' != c[i - 2]); nxt[i - 1][(j * base + l) % k] = l, cho[i - 1][(j * base + l) % k] = j; } print(1, 0), putchar('\n'); } public: int len; char c[N]; void solve() { input(), init(), process(); } } solver; int main() { while (solver.len = io.read(solver.c)) solver.solve(); return 0; }
POJ3411
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline int read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 15; int n, m, nume, ans, h[N]; int vis[N][1 << N]; struct Edge { int v, c, p, r, nxt; } e[N]; void add_edge(int u, int v, int c, int p, int r) { e[++ nume].v = v, e[nume].c = c; e[nume].p = p, e[nume].r = r; e[nume].nxt = h[u], h[u] = nume; } void input() { io.read(n), io.read(m); for (int i = 1; i <= m; ++ i) { int u, v, c, p, r; io.read(u), io.read(v), io.read(c), io.read(p), io.read(r); add_edge(u, v, c, p ,r); } } void dfs(int t, int status, int cost) { if (vis[t][status] <= cost) return; if (ans <= cost) return; if (t == n) { ans = cost; return; } vis[t][status] = cost; for (int i = h[t]; i; i = e[i].nxt) dfs(e[i].v, status | (1 << e[i].v - 1), cost + (status & (1 << e[i].c - 1) ? e[i].p : e[i].r)); } void process() { memset(vis, 0x1f, sizeof vis), ans = 1e9, dfs(1, 0, 0); if (ans == 1e9) io.write((char *) "impossible\n"); else io.write(ans), putchar('\n'); } public: void solve() { input(), process(); } } solver; int main() { solver.solve(); return 0; }
POJ3422
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline int read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Solver { private: static const int N = 50; static const int M = N * N << 2; static const int K = 10; int n, k, nume, h[M + 1], a[N + 1][N + 1]; struct Edge { int v, c, f, nxt; } e[N << K]; void add_edge(int u, int v, int c, int f) { e[++ nume].v = v, e[nume].c = c, e[nume].f = f; e[nume].nxt = h[u], h[u] = nume; e[++ nume].v = u, e[nume].c = 0, e[nume].f = -f; e[nume].nxt = h[v], h[v] = nume; } void input() { io.read(n), io.read(k); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) io.read(a[i][j]); } int get_id(int x, int y) { return (x - 1) * n + y; } void init() { add_edge(0, nume = 1, k, 0); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) { int id = get_id(i, j); add_edge((id << 1) - 1, id << 1, 1, -a[i][j]); add_edge((id << 1) - 1, id << 1, 10, 0); if (i < n) { int tmp = get_id(i + 1, j); add_edge(id << 1, (tmp << 1) - 1, 10, 0); } if (j < n) { int tmp = get_id(i, j + 1); add_edge(id << 1, (tmp << 1) - 1, 10, 0); } } add_edge(n * n << 1, (n * n << 1) + 1, k, 0); } int s, t, ans, que[M + 1], dist[M + 1]; bool in[M + 1]; bool spfa() { memset(dist, 0x1f, sizeof dist); memset(in, 0, sizeof in); int qb = 0, qe = 1; dist[que[1] = t] = 0, in[t] = true; while (qb != qe) { int u = que[(qb %= M) += 1]; in[u] = false; for (int i = h[u]; i; i = e[i].nxt) if (e[i ^ 1].c && dist[e[i].v] > dist[u] - e[i].f) { dist[e[i].v] = dist[u] - e[i].f; if (! in[e[i].v]) { in[e[i].v] = true; if (qb == qe || dist[que[qb % M + 1]] < dist[e[i].v]) que[(qe %= M) += 1] = e[i].v; else que[qb] = e[i].v, qb = (qb + M - 2) % M + 1; } } } return dist[s] < 5e8; } int dfs(int u, int low) { in[u] = true; if (u == t) return low; int used = 0; for (int i = h[u]; i; i = e[i].nxt) if (! in[e[i].v] && e[i].c && dist[e[i].v] == dist[u] - e[i].f) { int delta = dfs(e[i].v, min(e[i].c, low - used)); if (delta) e[i].c -= delta, e[i ^ 1].c += delta, used += delta, ans += e[i].f * delta; if (low == used) break; } return used; } int costflow() { int flow = 0; while (spfa()) { in[t] = true; while (in[t]) { memset(in, 0, sizeof in); flow += dfs(s, 1e9); } } return flow; } void process() { s = 0, t = (n * n << 1) + 1, ans = 0, costflow(), io.write(-ans), putchar('\n'); } public: void solve() { input(), init(), process(); } } solver; int main() { solver.solve(); return 0; }
POJ3429
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline int read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; struct Fraction { int a, b; int get_gcd(int a, int b) { return b ? get_gcd(b, a % b) : a; } Fraction(int _a = 0, int _b = 1) : a(_a), b(_b) { int gcd = get_gcd(a, b); a /= gcd, b /= gcd; } Fraction operator + (const Fraction &f) const { return Fraction(a * f.b + b * f.a, b * f.b); } Fraction operator - (const Fraction &f) const { return Fraction(a * f.b - b * f.a, b * f.b); } Fraction operator * (const Fraction &f) const { return Fraction(a * f.a, b * f.b); } Fraction operator / (const Fraction &f) const { return Fraction(a * f.b, b * f.a); } }; struct Point { Fraction x, y; Point(Fraction _x = Fraction(), Fraction _y = Fraction()) : x(_x), y(_y) {} Point operator + (const Point &p) const { return Point(x + p.x, y + p.y); } Point operator - (const Point &p) const { return Point(x - p.x, y - p.y); } Point operator * (const Fraction &p) const { return Point(x * p, y * p); } Fraction operator * (const Point &p) const { return x * p.y - y * p.x; } }; struct Line { Point a, b; Line(Point _a = Point(), Point _b = Point()) : a(_a), b(_b) {} Point operator & (const Line &l) const { Fraction t = (a - l.a) * (l.a - l.b) / ((a - b) * (l.a - l.b)); return a + (b - a) * t; } }; struct Solver { private: static const int N = 100; int m; Point point[N << 1]; void input() { for (int i = 1; i <= n; ++ i) { int x, y; io.read(x), io.read(y), point[i] = Point(Fraction(x), Fraction(y)); } io.read(m); } void process() { int ans = 0; for (int i = 1; i <= m; ++ i) { int a, b, c, d; io.read(a), io.read(b), io.read(c), io.read(d); Point tmp = Line(point[a], point[b]) & Line(point[c], point[d]); if (! tmp.x.a && ! tmp.y.a && ! ans) ans = i; point[n + i] = tmp; } io.write(ans), putchar('\n'); } public: int n; void solve() { input(), process(); } } solver; signed main() { while (io.read(solver.n)) solver.solve(); return 0; }
POJ3440
#include <cmath> #include <cctype> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define int long long using namespace std; struct IOManager { template <typename T> inline bool read(T &x) { char c; bool flag = false; x = 0; while (~ c && ! isdigit(c = getchar()) && c != '-') ; c == '-' && (flag = true, c = getchar()); if (! ~ c) return false; while (isdigit(c)) x = (x << 3) + (x << 1) + c - '0', c = getchar(); return (flag && (x = -x), true); } inline bool read(char &c) { c = '\n'; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; return ~ c; } inline int read(char s[]) { char c; int len = 0; while (~ c && ! (isprint(c = getchar()) && c != ' ')) ; if (! ~ c) return 0; while (isprint(c) && c != ' ') s[len ++] = c, c = getchar(); return (s[len] = '\0', len); } template <typename T> inline void write(T x) { x < 0 && (putchar('-'), x = -x); x > 9 && (write(x / 10), true); putchar(x % 10 + '0'); } inline void write(char s[]) { int pos = 0; while (s[pos] != '\0') putchar(s[pos ++]); } } io; static const double PI = acos(-1.0); struct Solver { private: static const int N = 100000; int T, n, m, t, c; double ans[5]; void input() { io.read(n), io.read(m), io.read(t), io.read(c); } void process() { io.write((char *) "Case "), io.write(++ T), io.write((char *) ":\n"); memset(ans, 0, sizeof ans); ans[1] = n * m * (t - c) * (t - c) + (n + m) * (t - c) * c + c * c; ans[2] = (n * (m - 1) + (n - 1) * m) * (t - c) * c + (n + m - 2) * c * c; ans[3] = (n - 1) * (m - 1) * (c * c - c * c * PI / 4); ans[4] = n * m * t * t - ans[1] - ans[2] - ans[3] - ans[4]; for (int i = 1; i <= 4; ++ i) printf("Probability of covering %lld tile%c = %.4lf%%\n", i, i > 1 ? 's' : ' ', ans[i] / n / m / t / t * 100); putchar('\n'); } public: void solve() { input(), process(); } } solver; signed main() { int T; io.read(T); while (T --) solver.solve(); return 0; }