2013 成都区域赛现场赛

本文从WordPress迁移而来, 查看全部WordPress迁移文章

hdu 4788 Hard Disk Drive

最简单的题目,实现单位的换算,然后计算一下比率

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

const char str[10] = "BKMGTPEZY";
const double aaa = 1000.0 / 1024.0;

int find(char ch){
for(int i = 0; str[i]; i++)
if(str[i] == ch)
return i;
return -1;
}

int main(){
int T,cas = 0;
scanf("%d",&T);
while(T--){
int n;
char string[10];
scanf("%d%s",&n,string);
int id = find(string[1]);
double res = 1.0;
for(int i = 0; i < id; i++)
res *= aaa;
res = 1.0 - res;
res *= 100;
printf("Case #%d: %.2lf%%\n",++cas,res);
}
return 0;
}

hdu 4786 Fibonacci Tree

题意:给一个无向图,边权只有0,1,1表示白边,0表示黑边,然后要构造一个生成树,使得白边的数目为一个FIB树,也就是生成树的边权和为一个FIB树,问是否可能,只需要输出YES,NO

这题是有个结论是,就是构造最小生成树和最大生成树,如果在这两个权值间(包括这两个权值),存在FIB树,那么一定可以构造出来,这个据说是个定理,但是没找到相关的资料。另外这题注意,可以无法构成一个生成树即图不连通,直接输出NO

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define LIM 100000
#define N 100010
#define M 100010

int n,m,p[N];
int fibs[30],fnum;
struct edge{
int u,v,w;
edge(){}
edge(int _u,int _v,int _w){
u = _u; v = _v; w = _w;
}
}e[M];

void init(){
fibs[0] = 1; fibs[1] = 2; fnum = 2;
for(int i = 2; ; i++){
fibs[i] = fibs[i-1] + fibs[i-2];
if(fibs[i] > LIM){
fnum = i; break;
}
}
}

bool cmp(edge x , edge y){
return x.w < y.w;
}
bool __cmp(edge x , edge y){
return x.w > y.w;
}

int find(int x){
return x == p[x] ? x : p[x] = find(p[x]);
}

int kruskal(){
int res = 0,cnt = 0;
for(int i = 0; i <= n; i++)
p[i] = i;
for(int i = 0 ; i < m; i++){
int u = e[i].u , v = e[i].v , w = e[i].w;
int rtu = find(u);
int rtv = find(v);
if(rtu == rtv) continue;
cnt++; res += w;
p[rtv] = rtu;
}
if(cnt != n-1) return -1;
return res;
}

int main(){
init();
int T,cas = 0;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i = 0 ; i < m; i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
e[i] = edge(u,v,w);
}
sort(e,e+m,cmp);
int Minval = kruskal();
sort(e,e+m,__cmp);
int Maxval = kruskal();
if(Minval == -1 || Maxval == -1){
printf("Case #%d: %s\n",++cas,"No");
continue;
}
bool res = false;
for(int i = 0; i < fnum; i++)
if(fibs[i] >= Minval && fibs[i] <= Maxval){
res = true; break;
}
printf("Case #%d: %s\n",++cas,res ? "Yes" : "No");
}
return 0;
}

hdu 4790 Just Random

题意:给出一个区间[a,b],[c,d],数字p,m,在[a,b]随机选一个数x,另外在[c,d]随机选一个数y,使得(x+y)%p=m,问能选出来的概率。虽然说是概率,其实就是要找到有多少种可能性就行了。公共的选择方案数为tot = (b-a+1) * (d-c+1),如果知道选出合法的方案的个数,除一下就可以

我的方法就是分开来计算,即分类讨论,代码写得有点啰嗦,但是思路还是较好理解的

将[a,b]和[c,d]都按照一个规则,分成三份

[a,b] = [l1,r1] + [n1个p长度的区间] + [l1,r1]

[c,d] = [l2,r2] + [n2个p长度的区间] + [l2,r2]

例如

p = 7

[a,b] = [3,23] = [3,6] + [ [7,13],[14,20] ] + [21,23] (中间有2个长度为p的区间)

[c,d] = [2,30] = [2,6] + [ [7,13],[14,20],[21,27] ] + [28,30] (中间有3个长度为p的区间)

这样分割的依据是,要保证中间一定有完整的长度为p的区间,并且必须从 %p=0 到 %p=p-1, 然后就可以分开计算了

[l1,r1] 和 [l2,r2] 的方案数

[l1,r1] 和 [n2个p长度的区间] 的方案数

[l1,r1] 和 [l2,r2] 的方案数

[n1个p长度的区间] 和 [l2,r2] 的方案数

[n1个p长度的区间] 和 [n2个p长度的区间] 的方案数

[n1个p长度的区间] 和 [l2,r2] 的方案数

[l1,r1] 和 [l2,r2] 的方案数

[l1,r1] 和 [n2个p长度的区间] 的方案数

[l1,r1] 和 [l2,r2] 的方案数

全部加起来就是总方案数

计算的方法其实不难,不过有点繁琐,想清楚就行了,主要是利用一下模的一些性质

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

LL A,B,C,D,P,M;
LL l1,r1,__l1,__r1 , l2,r2,__l2,__r2, n1,n2;
LL ANS;

void init(LL &L1,LL &R1, LL &__L1,LL &__R1, LL &N1 , LL L , LL R){
if(L % P == 0){
L1 = R1 = -1LL;
N1 = (R-L+1)/P;
}
else{
L1 = L;
LL temp = L % P;
temp = L + (P-temp-1);
R1 = ( temp <= R ? temp : R );
N1 = (R - R1)/P;
}
if(R % P == P-1){
__L1 = __R1 = -1LL;
N1 = (R-L+1)/P;
}
else{
__R1 = R;
LL temp = R % P;
temp = R - temp;
__L1 = (temp >= L ? temp : L);
}
if(__L1 == L1 && __R1 == R1){
__L1 = __R1 = -1LL;
}
}

LL work(LL a,LL b,LL c,LL d){
LL l,r,mid = M , res = 0;
a %= P; b %= P; c %= P; d %= P;
if(b <= mid){
l = M-a; r = M-b; swap(l,r);
l = max(l,c);
r = min(r,d);
if(r >= l) res += (r-l+1);
}
else if(a > mid){
l = M-a+P; r = M-b+P; swap(l,r);
l = max(l,c);
r = min(r,d);
if(r >= l) res += (r-l+1);
}
else{
l = M-a; r = 0; swap(l,r);
l = max(l,c);
r = min(r,d);
if(r >= l) res += (r-l+1);
l = P-1; r = M-b+P; swap(l,r);
l = max(l,c);
r = min(r,d);
if(r >= l) res += (r-l+1);
}
return res;
}

void solve(){
ANS = 0LL;
if(l1 != -1LL){
if(l2 != -1LL)
ANS += work(l1 , r1 , l2 , r2);
if(n2 != 0LL)
ANS += (r1-l1+1) * n2;
if(__l2 != -1LL)
ANS += work(l1 , r1 , __l2 , __r2);

}
if(n1 != 0LL){
if(l2 != -1LL)
ANS += n1 * work(0LL , P-1 , l2 , r2);
if(n2 != 0LL)
ANS += (n1*n2) * P;
if(__l2 != -1LL)
ANS += n1 * work(0LL , P-1 , __l2 , __r2);
}
if(__l1 != -1LL){
if(l2 != -1LL)
ANS += work(__l1 , __r1 , l2 , r2);
if(n2 != 0LL)
ANS += n2 * work(__l1 , __r1 , 0LL , P-1);
if(__l2 != -1LL)
ANS += work(__l1 , __r1 , __l2 , __r2);
}
}



LL gcd(LL p , LL q){
return q == 0LL ? p : gcd(q , p%q);
}

int main(){
int T,cas = 0;
scanf("%d",&T);
while(T--){
scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&A,&B,&C,&D,&P,&M);
init(l1,r1,__l1,__r1,n1,A,B);
init(l2,r2,__l2,__r2,n2,C,D);
//printf("[%I64d , %I64d] , [%I64d , %I64d] %I64d\n",l1,r1,__l1,__r1,n1);
//printf("[%I64d , %I64d] , [%I64d , %I64d] %I64d\n",l2,r2,__l2,__r2,n2);
solve();
LL TOT = (B-A+1)*(D-C+1);
if(ANS == 0LL){
printf("Case #%d: %I64d/%I64d\n",++cas,0LL,1LL);
continue;
}
LL G = gcd(ANS,TOT);
printf("Case #%d: %I64d/%I64d\n",++cas,ANS/G,TOT/G);
}
return 0;
}

hdu 4784 Dinner Coming Soon

很麻烦的题意,也导致了解题很麻烦

  1. 有n个城市,m条有向边,城市从1到n标号,出发地为1,目的地为n;而边,是有时间和金钱花费的
  2. 一个有k个平行世界,从0到k-1表示
  3. 每次到达一个城市,可以买一袋盐,卖一袋盐,什么都不做(只能3选1)
  4. 每个城市的盐的价格可能不同,另外,同一个城市在不同的平行世界里的盐的价格也可能不同,所以可能通过买进和卖出,利用差价能挣钱
  5. 每次进行一个时空转移,能从kth世界转移到(kth+1)%k世界,但是还是在同一个城市,每次转移一个世界,要花费1分钟,注意,要到达1和n城市,只能在0平行世界到达
  6. 一旦到达目的地n,就要结束,不能再走回去
  7. 有总的时间限制T,限制携带盐的数量B(一开始身上盐的数量为0),一开始携带的金钱
  8. 在时间限制内,去到n城市,并且令到身上的钱最多

题意如此纠结,这个问题也没有什么特殊的性质,那就暴力搞,也就是搜索了

一开始设置的状态有问题TLE,后来改回来,用优先队列,才做对

这题,有一点,导致了可以使用优先队列,就是无论怎么操作,时间都是增加的(即使不花费金钱但一定花费时间),所以我们以时间来进行扩展,一直向下搜索,设置一个优先队列,让时间最早的(剩余时间最多的)先出队,然后扩展更新

设置状态

  • u 城市编号
  • kth 所在的平行时间
  • time 剩余多少时间
  • num 身上现在带有多少盐

这是队列元素要记录的信息,另外用一个dp数组来记录金钱

dp[u][kth][time][num]表示在这种状态下获得的最大金钱

另外这题的操作包括了时空转移,移动,买,卖,写得时候可以把移动类的操作和买卖类的操作合并,不要分开,否则会出错

例如从当期点移动到另一个点后,就马上考虑到底是买,卖还是什么都不做,如果不是的话,先将一个状态入队了,下次出队的时候再考虑是买还是卖,会导致在一个地方多次的买卖

所以更新只有6种

  1. 时空转移后什么都不做
  2. 时空转以后买
  3. 时空转移后卖
  4. 移动后什么都不做
  5. 移动后买
  6. 移动后卖

另外注意题意:到达n点后无论如何就结束了,不能再走,所以在BFS过程中,如果出队的元素,它的u=n,那么不能用这个元素进行扩展,所以甚至可以控制不把这样的元素放进队列,不过出队时直接丢弃会更好些

为了避免重复搜索状态,设置标记inq[u][kth][time][num],不要把相同的状态丢进队列

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define NN 110
#define NM 210
#define NB 5
#define NK 6
#define NR 100010
#define NT 210

struct edge{
int v,ct,cr;
edge(){}
edge(int _v,int _ct,int _cr){
v = _v; ct = _ct; cr = _cr;
}
};
vector<edge>e[NN];
struct elem{
int u; //城市
int kth; //时空
int time; //剩余时间
int num; //盐的数目
elem(){}
elem(int _u,int _kth,int _time,int _num){
u = _u; kth = _kth; time = _time; num = _num;
}
bool operator<(const elem &temp)const{
return time < temp.time;
}
};
priority_queue<elem>que;
int n,nm,nb,nk,nr,nt,p[NK][NN];
int dp[NN][NK][NT][NB]; //dp[u][kth][time][num]
bool inq[NN][NK][NT][NB];

bool can_buy(int money,int cost,int v,int num){
if(money < cost) return false; //不够钱买
if(v == 1 || v == n) return false; //1和n不能买东西
if(num == nb) return false; //盐的数量已经达到上限不能买
return true;
}
bool can_sell(int u,int num){
if(u == 1 || u == n || num == 0) return false;
return true;
}
bool can_cross(int u,int time){
if(u == 1 || u == n || time == 0) return false;
return true;
}
bool can_move(int u,int kth,int time,int money){
if(kth != 0 && (u == 1 || u == n)) return false; //不是0时空不能去1和n城市
if(time < 0 || money < 0) return false; //不够时间,不够金钱去到v城市
return true;

}
int BFS(){
cl(dp,-1); cl(inq,false);
while(!que.empty()) que.pop();
que.push(elem(1,0,nt,0)); //1号点,0时空,开始时间,盐数0
dp[1][0][nt][0] = nr; //最开始的状态
inq[1][0][nt][0] = true;
while(!que.empty()){
elem now = que.top();
que.pop();
int u = now.u , kth = now.kth , time = now.time , num = now.num;
inq[u][kth][time][num] = false;
//printf("%d %d %d %d %d\n",u,kth,time,num,dp[u][kth][time][num]);
if(u == n) continue; //去到终点就已经结束了,所以终点的状态要跳过,不能用它来更新

//时空转移
if(can_cross(u,time)){
int __kth = (kth+1)%nk;
//转移后什么都不做
if(dp[u][__kth][time-1][num] < dp[u][kth][time][num]){
dp[u][__kth][time-1][num] = dp[u][kth][time][num];
if(!inq[u][__kth][time-1][num]){
que.push(elem(u,__kth,time-1,num));
inq[u][__kth][time-1][num] = true;
}
}
//转移后买一袋盐
if(can_buy(dp[u][kth][time][num],p[__kth][u],u,num)){
if(dp[u][__kth][time-1][num+1] < dp[u][kth][time][num] - p[__kth][u]){
dp[u][__kth][time-1][num+1] = dp[u][kth][time][num] - p[__kth][u];
if(!inq[u][__kth][time-1][num+1]){
que.push(elem(u,__kth,time-1,num+1));
inq[u][__kth][time-1][num+1] = true;
}
}
}
//转移后卖一袋盐
if(can_sell(u,num)){
if(dp[u][__kth][time-1][num-1] < dp[u][kth][time][num] + p[__kth][u]){
dp[u][__kth][time-1][num-1] = dp[u][kth][time][num] + p[__kth][u];
if(!inq[u][__kth][time-1][num-1]){
que.push(elem(u,__kth,time-1,num-1));
inq[u][__kth][time-1][num-1] = true;
}
}
}
}

//移动
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i].v , ct = e[u][i].ct , cr = e[u][i].cr;
if(can_move(v,kth,time-ct,dp[u][kth][time][num]-cr)){
//移动后什么都不做
if(dp[v][kth][time-ct][num] < dp[u][kth][time][num] - cr){
dp[v][kth][time-ct][num] = dp[u][kth][time][num] - cr;
if(!inq[v][kth][time-ct][num]){
que.push(elem(v,kth,time-ct,num));
inq[v][kth][time-ct][num] = true;
}
}
//移动后买一袋盐
if(can_buy(dp[u][kth][time][num],p[kth][v],v,num)){
if(dp[v][kth][time-ct][num+1] < dp[u][kth][time][num] - cr - p[kth][v]){
dp[v][kth][time-ct][num+1] = dp[u][kth][time][num] - cr - p[kth][v];
if(!inq[v][kth][time-ct][num+1]){
que.push(elem(v,kth,time-ct,num+1));
inq[v][kth][time-ct][num+1] = true;
}
}
}
//移动后卖一袋盐
if(can_sell(v,num)){
if(dp[v][kth][time-ct][num-1] < dp[u][kth][time][num] - cr + p[kth][v]){
dp[v][kth][time-ct][num-1] = dp[u][kth][time][num] - cr + p[kth][v];
if(!inq[v][kth][time-ct][num-1]){
que.push(elem(v,kth,time-ct,num-1));
inq[v][kth][time-ct][num-1] = true;
}
}
}
}
}
}
int res = -1;
for(int time = 0; time <= nt; time++)
for(int num = 0; num <= nb; num++)
res = max(res , dp[n][0][time][num]);
return res;
}

int main(){
int T,cas = 0;
scanf("%d",&T);
while(T--){
scanf("%d%d%d%d%d%d",&n,&nm,&nb,&nk,&nr,&nt);
for(int i = 1; i <= n; i++)
e[i].clear();
for(int kth = 0; kth < nk; kth++)
for(int u = 1; u <= n; u++)
scanf("%d",&p[kth][u]);
for(int i = 0; i < nm; i++){
int u,v,ct,cr;
scanf("%d%d%d%d",&u,&v,&ct,&cr);
e[u].pb(edge(v,ct,cr));
}
int res = BFS();
printf("Case #%d:",++cas);
if(res == -1) puts(" Forever Alone");
else printf(" %d\n",res);
}
return 0;
}