每日一水第45弹(2015 GCJ Round1)

Round 1C:

A:

 有r*c的一个矩阵,现在有一个1*w的条状物放在矩阵内,另一个人开始猜位置,比如猜一个x y,假如这一条恰好覆盖了x y,就要回答他YES,但是另一个人可以作弊,即移动那一条东西,然后说no,只要一直跟前面说的不矛盾即可,假如双方都表现的最优,问最少需要几次才能确定1*w那一条的所有位置。移动的话是不能旋转的,只能平移,可以放到任意位置上 。
B:
 输入第一行三个整数K,L,S,第二行K个大写字母,猴子刚开始有个空串,每次从这K个字母里取出一个字母加到字符串的后面,取S次,这样就得到了一个长度为S的字符串,输入第三行是一个长度为L的字符串target,求S里最多有几个target,和期望有几个target,输出它们的差值
C:
有D种硬币 每种硬币最多只能用C次 求加最少几种硬币 能拼出1~V
A:假设只有一行,
c % w == 0 时,每一行按照w一段选择一次,在每一段的中间选择, 那么最坏情况可以在第c/w次说中,锁定在最后一段
c % w != 0时,第c /w 次猜中一个后,你肯定往两边中的某个方向判断了,这里可以多让你猜错一次。
多行的情况的话其实就是其他r-1行都没有船的情况,每行需要c / w次
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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
int C, D, V;
int a[1000];
int main()
{
        freopen("C-large.in", "r", stdin);
        freopen("out.txt", "w", stdout);
        int t,ca=1;
        scanf("%d", &t);
        while(t--) {
                scanf("%d%d%d", &C,&D,&V);
                for(int i = 0; i < D; i++) {nw
                        scanf("%d", &a[i]);
                }
                std::sort(a, a + D);
                long long now = 0;
                int ret = 0;
                for(int i = 0; i < D; i++) {
                        while(now + 1 < a[i] && now < V) {
                                ret++;
                                now += (now + 1) * C;
                        }
                        if(now < V) {
                                now += 1LL * a[i] * C;
                        }
                }
                while(now < V) {
                        ret++;
                        now += (now + 1) * C;
                }
                printf("Case #%d: %d\n",ca++, ret);
        }
        return 0;
}

 

B:
套了一个ac自动机dp了一发,dp[len][node][cnt] 长度 为len,停留在len节点,出现了cnt次的概率
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
#include <bits/stdc++.h>
const int M = 500;
const int CD = 26;
int ch[M][CD];
int Q[M];
int fail[M];
int val[M];
int sz;
int ID[256];
void Reset() 
{
    sz = 1;
    val[0] = 0;
    fail[0] = 0;
    memset(ch[0],0,sizeof(ch[0]));
    for(int i = 0; i < 26; i++) ID['A'+i] = i;
}
void Insert(char *s) 
{
    int p = 0;
    for(;*s;s++) {
        int c =  ID[*s];
        if(!ch[p][c]) {
            val[sz] = 0;
            memset(ch[sz],0,sizeof(ch[sz]));
            ch[p][c] = sz++;
        }
        p = ch[p][c];
    }
    val[p]++;
}
void Construct() 
{
    int *s = Q, *e = Q;
    for(int i = 0; i < CD; i++) {
        if(ch[0][i]) {
            *e++ = ch[0][i];
            fail[ch[0][i]] = 0;
        }
    }
    while(s!=e) {
        int u = *s ++;
        for(int i = 0; i < CD; i++) {
            int &v = ch[u][i];
            if(v) {
                fail[v] = ch[fail[u]][i];
                *e ++ = v;
                val[v] += val[fail[v]];
            } else {
                v = ch[fail[u]][i];
            }
        }
    }
}
 
//length , node , count of appearance 
double dp[110][M][110];
int f[110][M];
void solve(int len, double p[], int count[])
{
        memset(f, -1, sizeof(f));
        f[0][0] = 0;
        for(int i = 0 ; i <= len; i++) {
                for(int j = 0 ; j < sz; j++) {
                        for(int cnt = 0; cnt <= len; cnt++) {
                                dp[i][j][cnt] = 0.0;
                        }
                }
        }
        /*
        for(int i = 0; i < sz; i++) {
                printf("%d ", val[i]);
        }
        puts("");
        */
        dp[0][0][0] = 1.0;
 
        for(int i = 0; i < len; i++) {
                for(int j = 0; j < sz; j++) {
                      //  printf("f[%d][%d]=%d\n", i, j, f[i][j]);
                        for(int c = 0; c < 26; c++) if(count[c] && f[i][j] != -1){
                                int to = ch[j][c];
                                f[i + 1][to] = std::max(f[i + 1][to], f[i][j] + val[to]);
                        }
                        for(int cnt = 0; cnt <= len; cnt++) {
                                for(int c = 0; c < 26; c++) {
                                        int to = ch[j][c];
                                        dp[i + 1][to][cnt + val[to]] += dp[i][j][cnt] * p[c];
                                }
                        }
                }
        }
        int mx = 0;
        double ret = 0;
        for(int i = 0; i < sz; i++) {
                mx = std::max(mx, f[len][i]);
                for(int cnt = 0; cnt <= len; cnt++) {
                        ret += cnt * dp[len][i][cnt];
                }
        }
       // printf("mx=%d ret=%.10f\n", mx, ret);
        printf("%.10f\n", (double)mx - ret);
}
int main()
{
        freopen("B-large.in", "r", stdin);
        freopen("out.txt", "w", stdout);
        int t, ca = 1;
        scanf("%d", &t);
        while(t--) {
                int K, L, S;
                scanf("%d%d%d", &K, &L, &S);
                char origin[110], target[110];
                int cnt[26];
                memset(cnt, 0, sizeof(cnt));
                scanf("%s", origin);
                for(int i = 0; i < K; i++) {
                        cnt[origin[i] - 'A']++;
                }
                double p[26];
                for(int i = 0; i < 26; i++) {
                        p[i] = (double)cnt[i] / K;
                }
                scanf("%s", target);
                Reset();
                Insert(target);
                Construct();
                printf("Case #%d: ", ca++);
                solve(S, p, cnt);
        }
        return 0;
}

 

 

C:

假如当前能凑成now,那么now+1必须是要选择的,选择了now+1之后可以让连续能凑成的最大值变成now + (now + 1) * c,想想就懂了。所以排序之后依次补充当前最大值+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
32
33
34
35
36
37
38
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
int C, D, V;
int a[1000];
int main()
{
        freopen("C-large.in", "r", stdin);
        freopen("out.txt", "w", stdout);
        int t,ca=1;
        scanf("%d", &t);
        while(t--) {
                scanf("%d%d%d", &C,&D,&V);
                for(int i = 0; i < D; i++) {nw
                        scanf("%d", &a[i]);
                }
                std::sort(a, a + D);
                long long now = 0;
                int ret = 0;
                for(int i = 0; i < D; i++) {
                        while(now + 1 < a[i] && now < V) {
                                ret++;
                                now += (now + 1) * C;
                        }
                        if(now < V) {
                                now += 1LL * a[i] * C;
                        }
                }
                while(now < V) {
                        ret++;
                        now += (now + 1) * C;
                }
                printf("Case #%d: %d\n",ca++, ret);
        }
        return 0;
}

 

每日一水第45弹(2015 GCJ Round1)》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注