Google Kickstart 2019 C

Posted on | In

2019 Google Kickstart Round C Solution

A. Wiggle Walk

在一个网格中，给定机器人的起始位置，以及机器人每一步的移动操作，询问机器人结束移动后的最终位置？，不同的是机器人走到一个访问过的格子，会沿运动方向一直走到一个没有访问过的格子。

1 ≤ N,R,C ≤ $5 × 10^4$.

每个点维护下各个方向上第一个没走过的点，因为数组比较大，用map表存一下。

我的想法是更新的时候其实只要把一个方向上连续区域两侧的点更新了就可以了，因为他不可能从中间的点访问这个方向的连续区间。例如(2,2)->(2,5)访问后, 之后是不可能突然在(2,3)这个点访问E/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
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
#include<bits/stdc++.h>
using namespace std;
int t;
int n,r,c,sr,sc;
struct dian{
    int x,y;
    bool operator<(const dian &xx)const
    {
        if(x==xx.x)return y<xx.y;
        return x<xx.x;
    }
    bool operator==(const dian &xx)const
    {
        if(x==xx.x&&y==xx.y)return true;
        return false;
    }
    dian(int r=0,int c=0){x=r;y=c;}
};

dian ans,s;
dian mapp[50001];
dian fin[50001][4];
map<dian,int>boolmap;
int ins[50001];
int dx[5]={0,-1,0,1,0};
int dy[5]={0,0,1,0,-1};

void initupdate(dian from,int i)
{
    for(int j=1;j<=4;j++)
        fin[i][j]=dian{from.x+dx[j],from.y+dy[j]};
}
void update(dian from,dian to,int i)
{
    int fid=boolmap[from];
    int toid=boolmap[to];
    fin[fid][i]=fin[toid][i];
    if((i%2)==0)
        fin[toid][6-i]=fin[fid][6-i];
    if((i%2)==1)
        fin[toid][4-i]=fin[fid][4-i];
}
int main()
{
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        memset(mapp,0,sizeof(mapp));
        boolmap.clear();
        scanf("%d%d%d",&n,&r,&c);
        scanf("%d%d",&sr,&sc);
        string input;
        cin>>input;
        for(int i=0;i<n;i++)
        {
            char temp=input[i];
            if(temp=='N') ins[i]=1;
            if(temp=='E') ins[i]=2;
            if(temp=='S') ins[i]=3;
            if(temp=='W') ins[i]=4;
        }
        int cnt=0;
        dian temp;
        temp.x=sr;temp.y=sc;
        boolmap[temp]=cnt;
        mapp[cnt++]=temp;
        initupdate(temp,cnt-1);
        for(int i=0;i<n;i++)
        {
            ans=fin[boolmap[temp]][ins[i]];
            for(;boolmap.find(ans)!=boolmap.end();)
            {
                int id= boolmap[ans];
                ans=fin[id][ins[i]];
            }
            boolmap[ans]=cnt;
            mapp[cnt++]=ans;
            initupdate(ans,cnt-1);
            update(temp,ans,ins[i]);
            temp=ans;
        }
        printf("Case #%d: %d %d\n",tt,ans.x,ans.y);
    }
    return 0;
}

B. Circuit Board

一个R*C的矩形，第r行第c列的厚度是$V_{r,c}$，求一个面积最大的子矩形，子矩形的每行最大与最小厚度不能超过K。

$0 ≤ K ≤ 10^3$.

orz 不好好刷题的后果。。。就是菜！！

==先说菜鸡做法：时间复杂$O(RC^2)$，首先枚举计算第i行 中第x列到第y列的最大最小厚度；之后枚举子矩形左右两列$O(C^2)$，之后固定两列，扫描每一行寻找满足条件的最长连续行数$O(R)$，总复杂度就是$O(RC^2)$，真的菜。。。

优秀的标准解法，对于每一行用滑动窗口计算每个点可以可以延伸到的最远距离，注意维护滑动窗口的最大最小值。然后枚举每一列作为子矩形的一列，把每一行看作直方图，计算直方图的最大面积，复杂度$O(RC)$

还有大佬用ST+二分来计算每个点延伸的最远距离，时间复杂度$O(RClog(C))$

标准解法代码之后再说。。。。懒癌晚期

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
#include<bits/stdc++.h>
using namespace std;
int r,c,k;
int v[301][301];
int maxx[301][301][301];
int minx[301][301][301];
int main()
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        scanf("%d%d%d",&r,&c,&k);
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                scanf("%d",&v[i][j]);
        for(int i=1;i<=r;i++)
            for(int x=1;x<=c;x++)
            {
                maxx[i][x][x]=v[i][x];
                minx[i][x][x]=v[i][x];
                for(int y=x+1;y<=c;y++)
                {
                    maxx[i][x][y]=max(maxx[i][x][y-1],v[i][y]);
                    minx[i][x][y]=min(minx[i][x][y-1],v[i][y]);
                }
            }
        int ans=0;
        for(int x=1;x<=c;x++)
        {
            for(int y=x;y<=c;y++)
            {
                int wid=0;
                for(int i=1;i<=r;i++)
                {
                    if(maxx[i][x][y]-minx[i][x][y]>k) wid=0;
                    else wid++;
                    ans=max(ans,wid*(y-x+1));
                }
            }
        }
        printf("Case #%d: %d\n",tt,ans);
    }

}

C. Catch Some

街上有N条狗，第i条狗的位置在$P_i$，每只狗有一种颜色$A_i$。Bundle的家在起点0处，他要观察K只狗。只有Bundle的衣服颜色和狗相同，才能观察，Bundle可以返回家中立即换好衣服。Bundle一秒可以向左或向右移动一格，观察狗或者换衣服不用时间，求观察K只狗最少花费的时间。 $A_i, N\leq 1000$

Hint：观察最后一只狗后，Bundle不用回家！

首先可以发现最优解中相同颜色的狗一定是连续的从家观察到最后，否则一定不是最优解。

并且观察的最后一种颜色因为不用回家所以是单程的，其他颜色是双程的

我们设$dp[i][j][0]$表示前i种颜色的狗观察了j只，且前i种颜色不是最后一种颜色，花费最少时间

$dp[i][j][1]$表示前i种颜色的狗观察了j只，且前i种颜色是最后一种颜色，花费最少时间

$dp[i+1][j][0]=min(dp[i][j-k][0],dp[i][j-k][1])+pos[i+1][k]*2,$

$dp[i+1][j][1]=min(min(dp[i][j-k][0]+pos[i+1][k]),min(dp[i][j-k][1]+2*pos[i+1][k]))$

虽然有3层循环，但是时间复杂度只有$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
#include<bits/stdc++.h>
using namespace std;

int n,k;
int a[1010];
int p[1010];
vector<int> pos[1010];
const int inf=1e9;
int dp[1010][1010][2];
int main()
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        scanf("%d%d",&n,&k);
        for(int i=0;i<n;i++)
            scanf("%d",&p[i]);
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(int i=0;i<=1000;i++)
            pos[i].clear();
        for(int i=0;i<n;i++)
            pos[a[i]].push_back(p[i]);
        for(int i=0;i<1001;i++)
            sort(pos[i].begin(),pos[i].end());
        memset(dp,0x3f,sizeof(dp));
        dp[0][0][0]=0;
        for(int i=1;i<1001;i++)
        {
            for(int j=0;j<=k;j++)
            {
                for(int x=0;x<2;x++)
                {
                    if(dp[i-1][j][x]<inf)
                    {
                        dp[i][j][x]=min(dp[i-1][j][x],dp[i][j][x]);
                        for(int y=1;y+j<=k&&y<=pos[i].size();y++)
                        {
                        dp[i][j+y][x]=min(dp[i][j+y][x],dp[i-1][j][x]+2*pos[i][y-1]);
                        if(x==0)
                        dp[i][j+y][1]=min(dp[i][j+y][1],dp[i-1][j][x]+pos[i][y-1]);
                        }
                    }
                }
            }

        }
        printf("Case #%d: %d\n",tt,dp[1000][k][1]);
    }

}