19-暑假训练2and3and4

又困又累

HDU5707 DP

给字符串a,b,c,问c是否仅由a,b组成
For example, `adebcf is a combine string of abc and def`.

f[i][j]表示a的前i个和b的前j个能否与c的前i+j个匹配。

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
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
char s[4][2010];
bool f[2010][2010];
int main() {
while(~scanf("%s%s%s",s[0] + 1,s[1] + 1,s[2] + 1)) {
int len[4] = {strlen(s[0] + 1),strlen(s[1] + 1),strlen(s[2] + 1),0};
if(len[0] + len[1] != len[2]) {
puts("No");
continue;
}
memset(f,0,sizeof f);
f[0][0] = 1;//f[0][1] = (s[1][1] == s[2][1]),f[1][0] = (s[0][1] == s[2][1]);
for(int i = 0; i <= len[0]; ++i)
for(int j = 0; j <= len[1]; ++j) {
if(i && s[0][i] == s[2][i + j])
f[i][j] |= f[i - 1][j];
if(j && s[1][j] == s[2][i + j])
f[i][j] |= f[i][j - 1];
}
if(f[len[0]][len[1]])
puts("Yes");
else
puts("No");
}
return 0;
}

ZOJ 2972 DP 背包

背包变形,但是隐含条件是当补充体力大于最大体力时会按照最大体力转移。

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 <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
//T1 T2 T3 F1 F2
int T[120][10],F[120][10];
int f[120][120];
int n,m;
int main() {
int t; scanf("%d",&t);
int ans = 1e9;
while(t--) {
ans = 1e9;
scanf("%d%d",&n,&m);
memset(f,0x3f,sizeof(f));
f[0][m] = 0;
for(int i = 1; i <= n; ++i)
scanf("%d%d%d%d%d",&T[i][1],&T[i][2],&T[i][3],&F[i][1],&F[i][2]);
for(int i = 1; i <= n; ++i) {
// for(int j = m; j >= 0; j--) {
// f[i][j] = min(f[i][j],f[i - 1][j] + T[i][2]);
// }
// for(int j = m - F[i][1]; j >= 0; j--) {
// f[i][j] = min(f[i][j],f[i - 1][j + F[i][1]] + T[i][1]);
// }
// for(int j = F[i][2]; j <= m; ++j) {
// f[i][j] = min(f[i][j],f[i - 1][j - F[i][2]] + T[i][3]);
// }
// for(int j = F[i][2] + 1; j <= m; ++j) {
// f[i][m] = min(f[i][m],f[i - 1][j] + T[i][3]);
// }
for(int j = 0; j <= m; ++j) {
f[i][j] = min(f[i][j],f[i - 1][j] +T[i][2]);
if(j + F[i][1] <= m)
f[i][j] = min(f[i][j],f[i - 1][j + F[i][1]] + T[i][1]);
//if(j >= F[i][1])
//f[i][j - F[i][1]] = min(f[i][j - F[i][1]],f[i - 1][j] + T[i][1]);
if(j >= F[i][2])
f[i][j] = min(f[i][j],f[i - 1][j - F[i][2]] + T[i][3]);
//int k = min(j + F[i][2],m);
//f[i][k] = min(f[i][k],f[i - 1][j] + T[i][3]);
}
for(int j = m - F[i][2] + 1; j <= m; ++j) {
f[i][m] = min(f[i][m],f[i - 1][j] + T[i][3]);
}
}
for(int j = 0; j <= m; ++j)
ans = min(ans,f[n][j]);
printf("%d\n",ans);
}
}

HDU4790

POJ3260 DP 背包 鸽巢原理

给钱和找钱分别是多重和完全背包,因为此题需要选多于该物品价格的钱数(T),所以不能确定背包容量的上界。当然根据鸽巢原理,因为要让找钱的钱币数量最少,所以假设maxv是所有钱币中面值的最大值,那么找的钱币数量不超过maxv。这样上界就是maxT + maxv * maxv

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
using namespace std;
struct pack {
int v,c;
} p[120];
const int maxn = 2e5;
int f[maxn];
const int inf = 1e9;
bool cmp(const pack& a,const pack& b) {
return a.v > b.v;
}
int main() {
int n,m;
cin>>n>>m;
fill(f,f + maxn,inf);
for(int i = 1; i <= n; ++i)
cin>>p[i].v;
for(int i = 1; i <= n; ++i)
cin>>p[i].c;
f[0] = 0;
for(int i = 1; i <= n; ++i) {
for(int k = 1; p[i].c; k*=2) {
int x = min(k,p[i].c);
for(int j = maxn - 1; j >= p[i].v * x; --j) {
f[j] = min(f[j], f[j - p[i].v * x] + x);
}
p[i].c -= x;
}
}
for(int i = 1; i <= n; ++i)
for(int j = maxn - p[i].v - 1; j >= 0; --j)
f[j] = min(f[j],f[j + p[i].v] + 1);
if(f[m] == inf) puts("-1");
else printf("%d\n",f[m]);
}

HDU2476 区间DP

有AB两个字符串,有一个操作可以将A串的某个区间变为同一种字符,
问至少做多少次该操作可以将A串变为B串。

zzzzzfzzzzz
abcdefedcba
abababababab
cdcdcdcdcdcd

6
7

仅仅考虑A->B确实不好下手,但是只看B的话,相同的两个字符有可能是直接刷过来的,是状态转移考虑因素,但是A也有自己的情况,A的颜色也有可能会影响决策,不能完全看成空白的。比如a的某个字符与b一样,那么就有可能这个不用刷一遍只刷两边的操作会更小。所以先把A完全当作空白的,这样就会比较好操作。

f[l][r]是将空白串变成B的最小代价,然后枚举与l位置的字符相同的位置k,一遍刷过来。

这个转移,一开始我是这样想的:

1
2
if(s2[l] == s2[k])
f[l][r] = min(f[l][r],f[l + 1][k - 1] + f[k + 1][r] + 1);

但是是不对的,因为这样隐含了一个条件:将从l到k的刷写代价单独剥离了出来,但是有可能s[l]或者s[k]在其它区间里被刷写时的操作会更少,所以不行。

1
2
if(s2[l] == s2[k])
f[l][r] = min(f[l][r],f[l + 1][k - 1] + f[k][r]);

这样就行了,这样相当于右边从k->?变成l->k->?,再把剩下的看作空白串刷写。这样其实也相当于扩展了f[k][r]的结果。

同理f[l + 1][k] + f[k + 1][r]也是对的,原理同上,只不过换成了左边。

其实这还牵扯到一个顺序的问题,只要转移时l->k的刷写顺序不与左右两个子过程冲突就行了。

当然全把A看作空白串肯定是不行的,设ans[i]为A的前i个刷成b的代价,那么:

1
2
3
4
5
6
7
8
for(int i = 1; i <= n; ++i) {
if(s1[i] == s2[i])
ans[i] = ans[i - 1];
else {
for(int j = 1; j < i; ++j)
ans[i] = min(ans[i], ans[j] + f[j + 1][i]);
}
}

当相同时肯定不刷最优,否则就枚举将其中某一段看作空白串来刷写的最小操作。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int f[120][120];
int ans[120];
char s1[120],s2[120];
int main() {
while(~scanf("%s%s",s1+1,s2+1)) {
memset(f,0,sizeof(f));
int n = strlen(s1+1);
for(int i = 1; i <= n; ++i)
f[i][i] = 1;
for(int r = 1; r <= n; ++r)
for(int l = r - 1; l; --l) {
f[l][r] = f[l + 1][r] + 1;
for(int k = r; k > l; --k) {
if(s2[l] == s2[k])
f[l][r] = min(f[l][r],f[l + 1][k - 1] + f[k][r]);
}
}
for(int i = 1; i <= n; ++i)
ans[i] = f[1][i];
for(int i = 1; i <= n; ++i) {
if(s1[i] == s2[i])
ans[i] = ans[i - 1];
else {
for(int j = 1; j < i; ++j)
ans[i] = min(ans[i], ans[j] + f[j + 1][i]);
}
}
printf("%d\n",ans[n]);
}
}

HDU1024 DP

在一段序列中选j个互不重叠的子区间,求怎样使得j个区间的和是最大值。

f[i][j]为前i个划分为j组,且一定选i的最大值。i可以和i-1所在的组结合,也可以单独一组:

f[i][j]=max{f[i-1][j],f[1~i-1][j-1]}

当然因为数据太大,所以要压成f[j],然后顺便维护一个maxd为max{f[1~i-1][j-1]}

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int f[maxn];
int lmax[maxn];
int m,n;
const int inf = 2e9;
int a[maxn];
int main() {
while(~scanf("%d%d",&m,&n)) {
for(int i = 1; i <= n; ++i)
scanf("%d",&a[i]);
int ans = -inf;
memset(f,0,sizeof(f));
memset(lmax,0,sizeof(lmax));
int sub;
for(int i = 1; i <= m; ++i) {
sub = -inf;
for(int j = i; j <= n; ++j) {
f[j] = max(f[j - 1], lmax[j - 1]) + a[j];
lmax[j - 1] = sub;
sub = max(sub, f[j]);
}
}
printf("%d\n",sub);
}
}

POJ3696 数论 欧拉定理 欧拉函数


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
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) {
if(!b) return a;
return gcd(b, a%b);
}
ll euler(ll x) {
ll ans = x;
for(ll i = 2; i * i <= x; ++i) {
if(x % i == 0) {
while(x % i == 0) x /= i;
ans = ans/i*(i-1);
}
}
if(x > 1) ans = ans/x*(x-1);
return ans;
}
ll mult(ll a,ll b,ll p) {
ll ans = 0;
for(; b; b>>=1,a = (a + a) % p) {
if(b&1)
ans = (ans + a) % p;
}
return ans;
}
bool check(ll x,ll p) {
ll ans = 1;
ll a = 10;
for(; x; x>>=1,a = mult(a,a,p)) {
if(x&1)
ans = mult(ans,a,p);
}
return ans == 1;
}
int main() {
int cnt = 0;
ll L;
while(~scanf("%lld",&L),L) {
printf("Case %d: ",++cnt);
ll n = 9*L/gcd(9*L,8);
if(gcd(n,10) != 1) {
printf("0\n");
continue;
}
ll phi_n = euler(n);
vector<ll> v;
for(ll i = 1; i * i <= phi_n; ++i) {
if(phi_n % i == 0) {
v.push_back(i);
v.push_back(phi_n / i);
}
}
sort(v.begin(),v.end());
for(int i = 0; i < v.size(); ++i) {
if(check(v[i],n)) {
printf("%lld\n",v[i]);
break;
}
}
}
}

HDU5451 Best Solver

不会

HDU5528 Count a * b

不会

POJ2917 数论 唯一分解定理 公式构造

给定n,要求满足条件的1/x + 1/y = 1/n的式子个数,xy正整数,n>=1e9

如果枚举的话,只要枚举一个且x,y范围是[n+1,2*n],设x=n+k,则y=n+n^2/k,所以说,只要求出n^2在1~n范围内的因子个数就行了。当然直接试除法除n^2不现实,可以通过求n的每个质因子的次数,然后*2+1来算。然后+1/2就行了。+1是因为n这个因数只被统计了一次。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll solve(int x) {
ll num = 1;
for(int i = 2; i * i <= x; ++i) {
if(x % i == 0) {
ll c = 0;
while(x % i == 0) x /= i,++c;
num = num * (c * 2 + 1);
}
}
if(x > 1) num *= 3;
return num;
}
int main() {
int n;
int cnt = 0;
scanf("%d",&n);
while (~scanf("%d",&n))
{
int x = (solve(n) + 1) / 2;
printf("Scenario #%d:\n%d\n\n",++cnt,x);
}
}

ZOJ4019 DP 背包 贪心

给定两种物品:系数分别为k1 k2,数量分别为n m,体积各不同。
价值为(k1 or k2)*取该物品后背包剩余容量,问怎样取最大

根据贪心,肯定是先选体积小的再选体积大的。于是分别对两种物品的体积排序。然后肯定是选i个某种物品,肯定是选前i个是最优的。根据这一性质,很容易想到dp[i][j]是选第一种前i个,第二种前j个的最大值,且这一状态能表示出当前背包的剩余体积c - s1[1~i] - s2[1-j],然后就ok了。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll f[2010][2010];
ll s1[2010],s2[2010];
int main() {
int k1,k2,c;
int t; scanf("%d",&t);
int n,m;
while(t--) {
scanf("%d%d%d%d%d",&k1,&k2,&c,&n,&m);
for(int i = 1; i <= n; ++i)
scanf("%lld",s1+i);
for(int i = 1; i <= m; ++i)
scanf("%lld",s2+i);//,s2[i] += s2[i - 1];
sort(s1+1,s1+1+n);
sort(s2+1,s2+1+m);
for(int i = 1; i <= n; ++i)
s1[i] += s1[i - 1];
for(int i = 1; i <= m; ++i)
s2[i] += s2[i - 1];
for(int i = 0; i <= n; ++i)
for(int j = 0; j <= m; ++j)
f[i][j] = 0;
ll ans = 0;
for(int i = 1; i <= n; ++i) {
if(s1[i] > c) break;
f[i][0] = f[i - 1][0] + (c - s1[i]) * k1;
ans = max(ans,f[i][0]);
}
for(int i = 1; i <= m; ++i) {
if(s2[i] > c) break;
f[0][i] = f[0][i - 1] + (c - s2[i]) * k2;
ans = max(ans,f[0][i]);
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j) {
ll x = c - s1[i] - s2[j];
if(x < 0) break;
f[i][j] = max(f[i][j],f[i - 1][j] + x * k1);
f[i][j] = max(f[i][j],f[i][j - 1] + x * k2);
ans = max(ans,f[i][j]);
}
}
printf("%lld\n",ans);
}
}

ZOJ3211 DP 背包 贪心

有n颗树,m(m<=n)天可以砍伐,可以在任意一天开始砍,但是如果在某一天不砍了之后就不能在砍了,
每棵树有a[i],b[i],价值为a[i] + 生长了x天*b[i],问最大价值。

首先贪心的想,肯定m天全砍满,所以一定要砍m棵树,这就是一个01背包。但是这m棵树是有顺序的,所以应该先看这里面b[i]最小的,所以要对b[i]排一遍序。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int f[300][300];
struct tree {
int a,b;
} t[300];
bool cmp(const tree& a,const tree& b) {
return a.b < b.b;
}
int main() {
int T; scanf("%d",&T);
while (T--)
{
memset(f,0,sizeof(f));
int n,m; scanf("%d%d",&n,&m);
for(int i = 1; i <= n; ++i)
scanf("%d",&t[i].a);
for(int i = 1; i <= n; ++i)
scanf("%d",&t[i].b);
sort(t+1,t+n+1,cmp);
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= m; ++j)
f[i][j] = max(f[i - 1][j],f[i - 1][j - 1] + t[i].a + (j - 1) * t[i].b);
}
printf("%d\n",f[n][m]);
}
}

test:

HDU4372

HDU5459

HDU2859