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