| 數學 | 組合數學 | POJ3252,poj1850,poj1019,poj1942 |
| 數論 | poj2635, poj3292,poj1845,poj2115 | |
| 計算方法（二分） | poj3273,poj3258,poj1905,poj3122 |
?
?
?
?
?
?
?
??
???
???
??????????
??????????????
???????????????????
?????????????????????????????????
組合數學
poj 3252
題意：如果一個數是round number，則它的二進制表示中，0的個數大于等于1的個數。現在給一段數據范圍[start, end]。求這一段數中round number的個數.(1 <= start < end <= 2,000,000,000)
思路：暴力肯定會掛掉。因為是二進制表示，所以可以把結果“湊”出來。
比如數據a用二進制表示有5位，那么1到4位中的round number是可以求出來的。結果為getNum(end) - getNum(start - 1);
一、如求4位二進制表示的數中round number的個數。第一位肯定是1。后邊還有三位，不是0就是1。設后三位中有x 個0則共有的情況數為 C(3, x)。因為要滿足（0的個數） >= （1的個數）。所以這里x可以取2，3；
二、還剩下五位二進制的情況。比如數據 11010.我們可以從左向右第2位開始。如果遇到1。則將其當成0，然后后邊幾位任意取，求符合條件的情況數。也就是說11010改成10xxx。實現方法是統計前邊有多少個0和1.然后可以知道后邊不確定的部分還至少需要多少個0才可以滿足條件。
?
ps:2,000,000,000二進制共有31位。本菜開了一個20的數組，然后wa了一下午！-_-! 本菜一下午的心血，代碼無任何參考！
渣代碼
?
View Code #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 50;
int aug[N][N];
int bit[N];
int s, e;
int C(int n, int m) { //dp求組合數,c[n][m] = c[n-1][m] + c[n-1][m-1];
if(n == 0 || m == 0 || n == 1 || m == n) return 1;
if(aug[n][m]) return aug[n][m];
aug[n - 1][m] = C(n - 1, m);
aug[n - 1][m - 1] = C(n - 1, m - 1);
return aug[n - 1][m] + aug[n - 1][m - 1];
}
int solve(int n) {
int ans, bt, t;
int i, j, x;
memset(bit, 0, sizeof(bit));
ans = 1; bt = 0; t = n;
while(t) {bit[++bt] = (t&1); t >>= 1;} //bt表示n共有多少位,bit[]記錄n的二進制表示
for(i = 2; i < bt; ++i) { //統計[1,bt)位中所有的情況數
t = i - 1;
if(t&1) {
for(j = t/2 + 1; j <= t; ++j)
ans += C(t, j);
} else {
for(j = (t + 1)/2 + 1; j <= t; ++j) {
ans += C(t, j);
}
}
}
int a = 1, b = 0; //a表示當前取到的數中1的個數，b表示當前取到的數中0的個數
for(i = bt - 1; i > 0; --i) { //統計二進制有bt位時的情況數
if(bit[i]) {
t = i - 1; //t表示后邊可以自由組合的位數
x = t + a - b - 1; //設x為后邊至少需要的0的個數，x + b + 1 = t - x + a，x = (t + a - b - 1)/2
if(x < 0) x = 0; //x可能為負，影響最后結果。本菜在這里wa了一次！
if(x&1) x = (x + 1)/2; //奇偶性不同會有區別，自己在紙上畫畫
else x /= 2;
for(j = x; j <= t; ++j) {
ans += C(t, j);
}
++a;
} else ++b;
}
if(b >= a) ans++; //判斷n是不是round number
return ans;
}
int main() {
freopen("data.in", "r", stdin);
memset(aug, 0, sizeof(aug));
while(~scanf("%d%d", &s, &e)) {
printf("%d\n", solve(e) - solve(s - 1));
}
return 0;
}
poj 1850 (31/03)
??? 昨天晚上回去神神叨叨的想了一路，回宿舍寫了半天沒寫出來。今天上午上課時才想起來怎么寫。
思路: 先取給出序列的長度n。小于n的長度的序列排列方式共有sum(C(26, i)) (1 <= i < n)。等于n長度的序列。確定兩個相鄰的字符中間可以有取到多少個字符。然后從剩下可取的字符中選字符補上。
比如序列： adgi，長度n = 4. ans += C(26, 1) + C(26, 2) + C(26, 3).
a 和d中間可以放bc。如果放b，后邊兩位還有C(24, 2)中選擇，如果是c，后邊還有C(23, 2)種選擇。
dg，gi同理。注意，第一個字符a處理有些特殊，因為不用考慮前邊有什么，所以直接從1到s[0] - 'a' 就行。
渣代碼：
View Code #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N = 100;
int aug[N][N];
char s[N];
int C(int n, int m) {
if(n == 0 || m == 0 || n == 1 || n == m) return 1;
if(aug[n][m]) return aug[n][m];
aug[n - 1][m] = C(n - 1, m);
aug[n - 1][m - 1] = C(n - 1, m - 1);
return aug[n - 1][m] + aug[n - 1][m - 1];
}
int main() {
//freopen("data.in", "r", stdin);
int n, i, j, ans;
int x, y, flag;
while(~scanf("%s", s)) {
n = strlen(s);
ans = flag = 0;
for(i = 1; i < n && !flag; ++i) {
if(s[i] < s[i - 1]) flag = 1;
}
if(flag) {puts("0"); continue;}
for(i = 1; i < n; ++i) {
ans += C(26, i);
}
for(i = 0; i < n; ++i) {
i ? x = s[i - 1] - 'a' + 1 : x = 0;
y = s[i] - 'a' + 1;
for(j = x + 1; j < y; ++j) {
ans += C(26 - j, n - i - 1);
}
}
printf("%d\n", ans + 1);
}
return 0;
}
POJ 1019
感覺數學題搞起來不是那么輕松，雖然這是道水題。。。
思路：先把1到X共有幾位數存起來，用n連續減掉為整的數X所占的位數。 余下的數從1開始湊，直到大于n。然后去掉多出n的部分然后取最后一位(% 10)。
ps：貌似說的我都有點看不懂。。。看代碼吧
View Code #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 40000;
int s[N];
int bit(int x) {
int k = 0;
while(x) {
x /= 10;
++k;
}
return k;
}
void init() {
int i;
s[0] = 0;
for(i = 1; i < N; ++i) {
s[i] = s[i - 1] + bit(i);
}
}
int main() {
//freopen("data.in", "r", stdin);
int n, t, i, l, ans;
init();
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
i = 0;
while(n >= s[i]) { //去掉整的位
n -= s[i];
i++;
}
if(!n) {printf("%d\n", (i - 1)%10); continue;}
l = 0;
for(i = 1; l < n; ++i) { //湊出第n位的數i是多少。
l += bit(i);
}
--i;
ans = i/((int)pow(double(10), l - n)); //去掉多余的位
printf("%d\n", ans % 10);
}
return 0;
}
POJ 1942
《組合數學》(Richard A.Brualdi 機械工業出版社) 8.5 格路徑和Schr?der 數
注意求C(n + m, min(n, m))。否則會tle
??
數論???????????????????????????????
?POJ 2635
?????? 題意：給一個數key，它是兩個素數的乘積，然后求較小的那個素數是否小于L，如果是，輸出。
?思路: 10^6以內的素數打表，把key換成1000進制，枚舉素數進行大整數取模。 如果出現滿足條件的則輸出。
第一次打表打錯了，我又搓了！
View Code #include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <cmath>
using namespace std;
const int N = 1000;
const int MAX = 1000010;
int num[N];
int prim[MAX];
bool f[MAX];
int tol, num_s;
char s[N];
void init() {
int i, j, k;
tol = 0;
memset(f, true, sizeof(f));
k = 1;
for(i = 2; i < MAX; ++i) {
if(i*i >= MAX) break;
for(j = i*i; j < MAX; j += i) {
f[j] = false;
}
}
for(i = 2; i < MAX; ++i) {
if(f[i]) prim[tol++] = i;
}
}
int mod(int x) {
int i, res = 0;
for(i = num_s - 1; i >= 0; --i) {
res = (res*1000 + num[i]) % x;
}
return res;
}
void deal() {
int i, k, len;
len = strlen(s);
memset(num, 0, sizeof(num));
num_s = 0;
for(i = len - 1; i >= 0; i -= 3) {
for(k = max(0, i - 2); k <= i; ++k) {
num[num_s] = num[num_s]*10 + s[k] - '0';
}
++num_s;
}
}
int main() {
//freopen("data.in", "r", stdin);
int l, i;
bool flag;
init();
while(~scanf("%s%d", s, &l)) {
if(!l) break;
deal();
flag = false;
for(i = 0; i < tol && prim[i] < l && !flag; ++i) {
if(mod(prim[i]) == 0) {
printf("BAD %d\n", prim[i]);
flag = true;
}
}
if(!flag) puts("GOOD");
}
return 0;
}
POJ 3292
主要是打表，既然打表就打徹底，否則TLE。。。H-primes的表，然后退出H-simi-primes的表。最后O(1)輸出。
?
View Code #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1000002;
int prime[N];
bool vis[N];
int tol;
void init() {
memset(vis, true, sizeof(vis));
int i, j;
for(i = 5; i < N; i += 4) {
if(i*i > N) break;
if(!vis[i]) continue;
for(j = i*i; j < N; j += i) {
vis[j] = false;
}
}
tol = 0;
for(i = 1; i < N; i += 4) {
if(vis[i]) prime[tol++] = i;
}
int t;
memset(vis, false, sizeof(vis));
for(i = 1; i < tol; ++i) {
if(prime[i]*prime[i] > N) break;
for(j = i; j < tol; ++j) {
t = prime[i] * prime[j];
if(t > N) break;
vis[t] = true;
}
}
memset(prime, 0, sizeof(prime));
for(i = 1; i < N; ++i) {
prime[i] = prime[i - 1];
if(vis[i]) prime[i]++;
}
}
int main() {
//freopen("data.in", "r", stdin);
init();
int n;
while(scanf("%d", &n), n) {
printf("%d %d\n", n, prime[n]);
}
return 0;
}
POJ 1845
忘算了一種情況，wa了一晚上！-_-!
對A分解質因子，A = a1^x1 + a2^x2 + ... + an^xn
則A的所有因子之和為 sum(A) = {1+ a1 + a1^2 + .. a1^x1}*{1 + a2 + a2^2 + ... + a1^x2}* ... * {1 + an + an^2 + an^3 + ... + an^xn}?? //怎么證明的，不知道！找了半天反例沒找出來
A^B即為 A^B = a1^(x1*B) + a2^(x2*B) + ... an ^ (xn*B);
求一次1+ a1 + a1^2 + .. a1^x1可以用二分的思想 + 快速冪取模
如果x1為奇數 則 (a1^(x1/2) + 1)* (1 + a1 + ... + a1^(x1/2));
如果x1為偶數 則 (a1^(x1 - 1/2) + 1)* (1 + a1 + ... + a1^(x1 - 1/2)) + a1^x1;
?
View Code #include <iostream>
#include <cstring>
#include <cstdio>
#define mod(x) x%9901
using namespace std;
typedef long long ll;
const int MAXN = 8000;
int prime[MAXN], tol;
bool vis[MAXN];
void init() {
int i, j;
tol = 0;
memset(vis, false, sizeof(vis));
for(i = 2; i < MAXN; ++i) {
for(j = i*i; j < MAXN; j += i) {
vis[j] = true;
}
}
for(i = 2; i < MAXN; ++i) {
if(!vis[i]) prime[tol++] = i;
}
}
ll exp_mod(ll a, ll b) {
ll res = 1;
a = mod(a);
while(b) {
if(b&1) {
res = mod(res * a);
}
a = mod(a * a);
b >>= 1;
}
return res;
}
ll sum(ll a, ll b) {
if(b == 0) return 1;
if(b&1) return mod((exp_mod(a, b/2 + 1) + 1) * sum(a, b/2));
return mod(mod((exp_mod(a, (b-1)/2 + 1) + 1) * sum(a, (b-1)/2)) + mod(exp_mod(a, b)));
}
int main() {
//freopen("data.in", "r", stdin);
int i, a, b;
ll ans, x;
init();
while(~scanf("%d%d", &a, &b)) {
ans = 1;
for(i = 0; i < tol && prime[i] <= a; ++i) {
x = 0;
while(a % prime[i] == 0) {
x ++;
a /= prime[i];
}
if(!x) continue;
ans = mod(ans * sum(prime[i], x*b));
}
if(a > 1) ans = mod(ans * sum(a, b));
printf("%lld\n", ans);
}
return 0;
}
? POJ 2115
???? 題目的意思是求 a + c*x = b(mod n) , 可以轉換成c*x = (b - a) (mod n)。經典的模線性方程
cx + ny = d; d為c，n的最大公約數。
如果b%d ！= 0 輸出 FOREVER
因為d = cx + ny;
? d%n = cx%n;
又因為 b | d
b%n = d*(b/d)%n = cx(b/d)%n;
所以方程b % n = cx0%n的一個解為x0 = x*(b/d)%n（題目要求余數）。
因為n | d，所以所求的余數每d個一次循環，為了保證x0不為負數。ans = (x0 + n/d)%(n/d);
ps:《算法導論》上有各種證明，這題要用long long， 并且long long(1) << k;
?
View Code #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll exp_gcd(ll a, ll b, ll& x, ll& y) {
if(b == 0) {
x = 1; y = 0;
return a;
}
ll p = exp_gcd(b, a%b, x, y);
ll tmp = x;
x = y; y = tmp - (a/b)*y;
return p;
}
void mod_equ(ll a, ll b, ll n) {
ll x, y;
ll d = exp_gcd(a, n, x, y);
if(b%d != 0) {puts("FOREVER"); return ;}
x = x*(b/d)%n;
n = n/d;
if(n < 0) n = -n;
printf("%lld\n", (x%n + n)%n);
}
int main() {
//freopen("data.in", "r", stdin);
ll a, b, c;
int k;
while(~scanf("%lld%lld%lld%d", &a, &b, &c, &k)) {
if(!a && !b && !c && !k) break;
mod_equ(c, b - a, ll(1) << k);
}
return 0;
}
?
計算方法（二分）
POJ 3273
剛想寫dp，一看數據范圍，直接無語了。看到discuss里有人說用二分，不得不佩服二分的強大。Orz
以sum(day[i])為上界R，max(day[i])為下屆L，得到一個mid。算出mid為限制時共分成了多少塊(m)，如果if( m < M ) R = mid - 1; else L = mid + 1; 詳見代碼 ??????????????????????????
View Code // 110+ ms 1Y ^^
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int inf = ~0u>>2;
const int MAXN = 100007;
int a[MAXN], N, M;
int num(int mid) {
int s = 0, m = 0, i;
for(i = 0; i < N; ++i) {
if(s + a[i] <= mid) {
s += a[i];
} else {
s = a[i]; m ++;
}
}
return m;
}
int main() {
//freopen("data.in", "r", stdin);
int md, sum, i;
while(~scanf("%d%d", &N, &M)) {
sum = 0; md = - inf;
for(i = 0; i < N; ++i) {
scanf("%d", &a[i]);
md = max(md, a[i]);
sum += a[i];
}
int l = md, r = sum, mid;
while(l < r) {
mid = (l + r) >> 1;
if(num(mid) < M) r = mid - 1;
else l = mid + 1;
}
printf("%d\n", l);
}
return 0;
}
POJ 1905
公式很容易推出來，可是我把公式寫復雜了。最后把精度都搞砸了。。。T_T
設要求的高度為x。弧的半徑為r
(r - x)^2 + (l/2)^2 = r^2;
r = (x^2 + (l/2)^2)/(2*x);
r-x，跟r 所夾的角度為o = asin((l/2)/r);
以x求出的弧長為L0 = 2*o*r; L0與L‘比較，如果小于則增大x，如果大于則減小x。（二分枚舉x的值）
?
View Code #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const double eps = 1e-8;
double len, L;
int cmp(double x) {
if(x > eps) return 1;
else if(x < -eps) return -1;
return 0;
}
double cal(double x) {
double r = ((len/2)*(len/2) + x*x)/(2*x);
double O = asin(len/(2*r));
double L0 = 2*O*r;
if(cmp(L0 - L) >= 0) return 1;
else return 0;
}
int main() {
//freopen("data.in", "r", stdin);
double n, c;
while(~scanf("%lf%lf%lf", &len, &n, &c)) {
if(cmp(len) < 0 && cmp(n) < 0 && cmp(c) < 0) break;
L = (1 + n * c) * len;
double l = 0, r = len, mid, t;
while(cmp(r - l) > 0) {
mid = (l + r)/2;
t = cal(mid);
if(t == 1) r = mid;
else l = mid;
}
printf("%.3lf\n", l);
}
return 0;
}
POJ 3122
題意：已知有N個pie，要分成F + 1份，每份的體積相同（每份必須是完整的，不能是幾個小塊湊起來的）。現在求每份pie可取的最大體積。
思路：求出平均體積avg，所求的體積v就肯定在(0， avg] 區間內，二分枚舉 v的值，判斷以v體積分的話可以分到的快數n，讓n與F + 1比較。調整L，R的值。
ps: eps = 1e-8會tle，1e-6就好。
View Code #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN = 10007;
const double pi = acos(-1.0);
const double eps = 1e-6;
double v[MAXN];
int cmp(double x) {
if(x > eps) return 1;
else if(x < -eps) return -1;
else return 0;
}
int main() {
//freopen("data.in", "r", stdin);
int N, F, n, i, T;
double mid, l, r, t, rad;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &N, &F);
l = 0; r = 0; ++F;
for(i = 0; i < N; ++i) {
scanf("%lf", &rad);
v[i] = pi*rad*rad;
r += v[i];
}
r = r/F;
while(cmp(r - l) > 0) {
mid = (l + r) / 2;
for(n = 0, i = 0; i < N; ++i) {
t = v[i];
while(cmp(t - mid) >= 0) {++n; t -= mid;}
}
if(n < F) r = mid;
else l = mid;
}
printf("%.4f\n", l);
}
return 0;
}
?
????????????????????????????????????????????????????
????????????????????????????????????????????????
????????????????????????????????????????????????
??????????????????????????????????????????????????????
)
)