AXXA
B UVA11029 Leading and Trailing 科学记数法 取对数
给定n(2 ≤ n < 2^31)和k(1 ≤ k ≤ 10^7)，输出n^k的前3位和后3位，保证n^k至少6位。
后三位快速幂%1000就行，前三位要用一种特殊的取对数的方法。
先写成科学记数法：n ^ k = a * 10 ^ z， 很显然只要求出a来然后*100就行了。
两边同时取以10为底的对数：k * lg(n) = lg(a) + z
很显然lg(a) < 1，是小数部分，z >= 1，是整数部分。
然后用到double modf(double x,double* iptr)把k*lg(n)分离整数部分和小数部分，再把小数部分带进10^x里 * 100，就能得到前三位了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll fp(ll a,ll b,ll p) {
ll ans = 1;
for(; b; b >>= 1, a = a * a % p) {
if(b & 1)
ans = ans * a % p;
}
return ans;
}
int main() {
ll n,k,p = 9973;
int T;
cin>>T;
for(int i = 1; i <= T; ++i) {
cin>>n>>k;
double d;
printf("Case %d: %d %03d\n",i,(int)(pow(10,modf(k * log10(n),&d)) * 100),fp(n,k,1000));
}
}
|
E HDU1069 Monkey and Banana 记忆化搜索
给n(<40)种箱子的三维，每种的数量无限，宽和高递减的垒箱子，箱子可以旋转，问能垒到的最高高度
因为可以旋转所以一个就有6种情况，然后按照xyz递减排个序，这样搜索时能按箱子序号递增搜索且不是错的，然后随便写写就行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include <bits/stdc++.h>
using namespace std;
int n;
struct box {
int x,y,z;
} b[300];
int tot = 0;
map<int,int> f;
bool cmp(const box& a,const box& b) {
if(a.x == b.x)
if(a.y == b.y)
return a.z > b.z;
else
return a.y > b.y;
else
return a.x > b.x;
}
int dfs(int now) {
if(now > tot)
return 0;
if(f.find(now) != f.end())
return f[now];
int nxt_d = 0;
for(int nxt = now + 1; nxt <= tot; ++nxt) {
if(b[nxt].x >= b[now].x || b[nxt].y >= b[now].y)
continue;
nxt_d = max(nxt_d,dfs(nxt));
}
return f[now] = nxt_d + b[now].z;
}
int main() {
int cnt = 0;
while(~scanf("%d",&n) && n) {
tot = 0;
++cnt;
f.clear();
for(int i = 1; i <= n; ++i) {
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
b[++tot] = (box){x,y,z};
b[++tot] = (box){x,z,y};
b[++tot] = (box){y,x,z};
b[++tot] = (box){y,z,x};
b[++tot] = (box){z,x,y};
b[++tot] = (box){z,y,x};
}
sort(b + 1,b + tot + 1,cmp);
int ans = 0;
for(int i = 1; i <= tot; ++i) {
ans = max(ans,dfs(i));
}
printf("Case %d: maximum height = %d\n",cnt,ans);
}
}
|
G HDU1059 Dividing 多重背包 DP
给定价值1~6的6种物品，数量分别给定。问能否有一种取法取到所有物品总价值的一半。总数量<=20000
常见的多重背包是要二进制拆分的。进阶指南里给了一种巧妙做法：
因为只要求可达性所以可以用一种类似完全背包的做法，但是每种物品数量是有限的，所以开一个数组记录转移而来的状态已经用了多少个该物品，平时能不用就不用，用的时候检查一下数量。这样复杂度就是n^2，详情看代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <bits/stdc++.h>
using namespace std;
int a[10];
bool f[210000];
int used[210000];
int main() {
int cnt = 0;
while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6] && a[1] + a[2] + a[3] + a[4] + a[5] + a[6]) {
++cnt;
printf("Collection #%d:\n",cnt);
int up = (a[1] + a[2] * 2 + a[3] * 3 + a[4] * 4 + a[5] * 5 + a[6] * 6);
if(up % 2) puts("Can't be divided.");
else {
up /= 2;
memset(f,0,sizeof(f));
f[0] = 1;
for(int i = 1; i <= 6; ++i) {
for(int i = 0; i <= up; ++i) used[i] = 0;
for(int j = i; j <= up; ++j) {
if(!f[j] && f[j - i] && used[j - i] < a[i])
f[j] = 1,used[j] = used[j - i] + 1;
}
}
if(f[up]) puts("Can be divided.");
else puts("Can't be divided.");
}
puts("");
}
}
|