Round C APAC Test 2017 题解

发表于 | 分类于 |

Round D都要开始了, Round C还没搞定的我(D题不会搞)…另外300+名次也能拿到面试资格呢, 然而做的人却越来越少了.

Problem A. Monster Path

neta某手游…给个R*C的矩形地图, 上面用.和A标注, 走到A上有P的概率抓到妖怪, 走到.上有Q的概率抓到妖怪. 当在一个位置抓过妖怪, 下次经过就抓不到了, 给定起点坐标Rs和Cs, 需要走一条路线使得走S步获得妖怪数的期望最大, 求这个期望.

因为S最大只有9, 直接乱dfs每条路线就行了. 用数组记录一下当前位置没有抓过怪物的概率, 然后搜的时候每经过一个地点, 可计算出走这里抓到怪物的概率, 然后更新数组里当前位置没有抓过怪物的概率, 继续搜下去, 过程中记录一下概率和就是期望.

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
//省略头文件
using namespace std;
typedef long long ll;
void useFile(string f) {
    freopen((f+".in").c_str(),"r",stdin);
    freopen((f+".out").c_str(),"w",stdout);
}
int r,c,x,y,s;
double p,q;
bool grid[22][22];
double pro[22][22];
int step[4][2] = {0,1,1,0,0,-1,-1,0};
double ans;
void dfs(int x, int y, int st, double cnt) {
    int tx,ty;
    double tp, tmp;
    if(st!=s) {
        tp = grid[x][y]?pro[x][y]*p:pro[x][y]*q;
    } else {
        tp = 0;
    }
    if(!st) {
        ans = max(ans, cnt+tp);
        return;
    }
    for(int i=0;i<4;++i) {
        tx = x + step[i][0];
        ty = y + step[i][1];
        if(tx>=0&&tx<r&&ty>=0&&ty<c) {
            pro[x][y] -= tp;
            dfs(tx, ty, st - 1, cnt+tp);
            pro[x][y] += tp;
        }
    }
}
void gao(){
    scanf("%d%d%d%d%d",&r,&c,&x,&y,&s);
    scanf("%lf%lf",&p,&q);
    char a,b;
    scanf("%c", &b);
    for(int i=0;i<r;++i) {
        for(int j=0;j<c;++j) {
            scanf("%c%c",&a,&b);
            if(a=='A')
                grid[i][j] = 1;
            else
                grid[i][j] = 0;
            pro[i][j] = 1;
        }

    }
    ans = 0;
    dfs(x,y,s,0);
    printf("%.7f\n", ans);
}
int main()
{
    useFile("A-large-practice");
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;++i) {
        printf("Case #%d: ",i);
        gao();
    }
    return 0;
}

Problem B. Safe Squares

为啥我觉得这题比较难, 过的人却最多…
给一个R*C的矩形, 给K个矩形上的点, 求矩形上有多少个正方形不包含这些点中任意一个.

由于R,C,S最大能到3000, 所以需要向O(RC)上靠, 自然会想到动态规划.
如果用dp[i][j]表示前面i*j的矩形中包含的正方形数, 则dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]表示前面i*j矩形中不含当前点grid[i][j]的正方形数量. 为了求得dp[i][j], 还需要加上所有以grid[i][j]为右下角的正方形数量.
因为光枚举i和j复杂度就接近10^7, 因此需要预处理以grid[i][j]为右下角的正方形数量.
以grid[i][j]为右下角的正方形数量等于以grid[i][j]为右下角的最大合法正方形边长(从1开始取, 每个长度都能找到一个合法的正方形), 问题变成了找上方和左方最近的非法点的距离. 这个依然可以用动态规划做.
如果dpDis[i][j]表示以grid[i][j]为右下角的最大合法正方形边长, 则dpDis[i][j]要么被最接近的非法的grid[i-x][j]限制, 要么被最接近的非法的grid[i][j-x]限制, 要么和dpDis[i-1][j-1]受到相同的非法点限制. 我们用left[i][j]表示最接近的左边的非法点距离, top[i][j]表示最接近的上边的非法点距离, 则有:
dpDis[i][j] = min(top[i][j], left[i][j], dpDis[i-1][j-1]).
其中left[i][j]可以很容易根据left[i-1][j]和当前位置点的合法性计算出来, top[i][j]同理.
有了dpDis[i][j]之后我们就可以完成之前的公式:
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + dpDis[i][j].
复杂度O(RC).

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
//省略头文件
using namespace std;
typedef long long ll;
void useFile(string f) {
    freopen((f+".in").c_str(),"r",stdin);
    freopen((f+".out").c_str(),"w",stdout);
}

bool grid[3010][3010];
ll dp[3010][3010];
ll rbcnt[3010][3010];
ll lt[3010][3010][2];
int r,c,k;
void gao(){
    int x,y;
    scanf("%d%d%d",&r,&c,&k);
    memset(grid,0,sizeof(grid));
    memset(dp,0,sizeof(dp));
    memset(rbcnt,0,sizeof(rbcnt));
    memset(lt,0,sizeof(lt));
    for(int i=0;i<k;++i) {
        scanf("%d%d",&x,&y);
        grid[x+1][y+1] = 1;
    }
    for(int i=1;i<=r;++i) {
        for(int j=1;j<=c;++j) {
            lt[i][j][0] = grid[i][j]?0:lt[i-1][j][0]+1;
            lt[i][j][1] = grid[i][j]?0:lt[i][j-1][1]+1;
            rbcnt[i][j] = grid[i][j]?0:min(rbcnt[i-1][j-1]+1, min(lt[i][j][0],lt[i][j][1]));
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + rbcnt[i][j];
        }
    }
    printf("%lld\n", dp[r][c]);
}
int main()
{
    useFile("B-large-practice");
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;++i) {
        printf("Case #%d: ",i);
        gao();
    }
    return 0;
}

另一种计算dpDis[i][j]的方法是通过二分.
用数字1表示非法点, 0表示合法点, 预处理数组sum[i][j]表示矩形中1的个数.
有了sum[i][j]数组, 可以得到其中任意正方形中1的个数. 如要得到以grid[i][j]为右下角, 边长为L的正方形内1的个数, 可以用sum[i][j] - sum[i-l][j] - sum[i][j-l] + sum[i-l][j-l]求得, 然后通过二分, 查找使得1个数为0的最大边长L, 就是dpDis[i][j]的值.

Problem C. Evaluation

给N个形如a=f(b,c)的字符串, 表示变量a的值依赖b和c的值. b=g()这样的字符串表示给b一个基本值. N不超过1000, 左侧变量只会在左侧出现一次, 右侧函数内变量数不超过10. 现在可以任意安排顺序, 问这些字符串能否使得每个变量都能够求得值(是否合法).

直接把每个变量名拿出来(想念js正则), 依赖关系用单向边连起来, 构成图. 如a依赖b和c,则用c和b指向a. 然后我们根据入度关系, 用拓扑序进行更新, 从有值的点向依赖他的点更新, 最后看看是否有入度不为0的点(依赖成环)或者没有定值的点(如没有定义基本值). 复杂度为O(N)(点数不会超过11*N, 边数也不会超过10*N).

看代码的时候需要注意的是, 我代码里面本意是用val[]表示是否能求出值, 但实际上只要其依赖的变量中有一个能求出值, 其val[]就会变成true. 其需要入度计数cnt[]辅助, 当val[]为true且入度为0时才保证其依赖的数都已经有值了.

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
//省略头文件
using namespace std;
typedef long long ll;
void useFile(string f) {
    freopen((f+".in").c_str(),"r",stdin);
    freopen((f+".out").c_str(),"w",stdout);
}
int n;
bool val[10010];
int cnt[10010];
vector<int> nxt[10010];

void gao(){
    scanf("%d",&n);
    int l = 0;
    map<string, int> ma;
    string str;
    memset(val,0,sizeof(val));
    memset(cnt,0,sizeof(cnt));
    for(int i=0;i<10010;++i) {
        nxt[i].clear();
    }
    for(int i=0;i<n;++i) {
        cin>>str;
        string tmp;
        int lf;
        int j=0;
        for(;str[j]!='=';++j) {
            tmp.push_back(str[j]);
        }
        if(!ma[tmp]) {
            lf = ++l;
            ma[tmp] = l;
        } else {
            lf = ma[tmp];
        }
        while(str[j]!='(')
            ++j;
        while(str[j]!=')') {
            ++j;
            tmp.clear();
            while(str[j]!=','&&str[j]!=')') {
                tmp.push_back(str[j]);
                ++j;
            }
            if(tmp.length()==0) {
                val[lf] = 1;
            } else {
                if(!ma[tmp]) {
                    ma[tmp] = ++l;
                }
                nxt[ma[tmp]].push_back(lf);
                ++cnt[lf];
            }
        }
    }

    queue<int> qu;
    for(int i=1;i<=l;++i) {
        if(val[i]&&!cnt[i]) {
            qu.push(i);
        }
    }
    while(!qu.empty()) {
        int x = qu.front();
        qu.pop();
        for(int i=0;i<nxt[x].size();++i) {
            int y = nxt[x][i];
            --cnt[y];
            val[y] = 1;
            if(!cnt[y])
                qu.push(y);
        }
    }
    bool ans = true;
    for(int i=1;i<=l;++i) {
        if(cnt[i]||!val[i]) {
            ans = false;
            break;
        }
    }
    if(ans)
        printf("GOOD\n");
    else
        printf("BAD\n");

}
int main()
{
    useFile("C-large-practice");
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;++i) {
        printf("Case #%d: ",i);
        gao();
    }
    return 0;
}

Problem D. Soldiers

彻底不会..看了份代码才想明白. 想到了就是SB题, 可惜智商不够..
给N个士兵, 每个有一个攻击力A[i]和防御力D[i], Alice和Bob轮流选且Alice先选, 每次选择的士兵攻击力或者防御力必须大于所有已经被选中的士兵, 直到不能选. 两人都身经百战, 见得多了, 问Alice是否能够比Bob多选一个士兵.

Alice多选一个士兵等价于先手走最后一步.
假设攻击力最高是x, 防御力最高是y, 可知当选择的士兵里有攻击力为x和防御力为y的士兵时就不能再选了.
如果有一个士兵的攻击力为x防御力为y, 则直接选他, 先手必胜.
如果没有这样的士兵, 则只有攻击力为x且防御力小于y的士兵和防御力为y且攻击力小于x. 对于这两类士兵, 每类至少有一个士兵, 先选到其中一个的人必败, 因为后手可以选另一类的任意一个使得先手无法再继续选择. 因此要避免先选A[i] = x且D[i] < y和A[i] < x且D[i] = y的士兵.
要避免这样的选择, 即要在A[i] < x且D[i] < y的士兵集合中走最后一步, 就形成了子问题.
整体复杂度O(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
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
//省略头文件
using namespace std;
typedef long long ll;
void useFile(string f) {
    freopen((f+".in").c_str(),"r",stdin);
    freopen((f+".out").c_str(),"w",stdout);
}
int a[4010],d[4010],n;
bool dfs() {
    if(n == 0) {
        return 0;
    }
    int x = 0,y = 0;
    for(int i=0;i<n;++i) {
        x = max(x, a[i]);
        y = max(y, d[i]);
    }
    int l = 0;
    for(int i=0;i<n;++i) {
        if(a[i]!=x&&d[i]!=y) {
            a[l] = a[i];
            d[l] = d[i];
            ++l;
            continue;
        }
        if(a[i]==x&&d[i]==y)
            return 1;
    }
    n = l;
    return dfs();
}
void gao(){
    scanf("%d",&n);
    for(int i=0;i<n;++i) {
        used[i] = 0;
        scanf("%d%d",&a[i],&d[i]);
    }
    if(dfs()) {
        printf("YES\n");
        return;
    }
    printf("NO\n");
    return;
}
int main()
{
    useFile("D-large-practice");
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;++i) {
        printf("Case #%d: ",i);
        gao();
    }
    return 0;
}