2019 TCO Round 1B

Posted on Edited on In

Topcoder上有意思的dp题还是多，但是如果能有更多的editor就好了(你要干嘛。。)

题解链接

EllysSki

250的题太简单了。

EllysTeleport

500的题目是我当初面某司的题，就是有可能碰到环路。

2->1->5->6->7->8->5这种情况。

自己过后想了一下，先处理一下这个点是否在环路上，可以记录这个环路的长度。

之后再扫一遍就完了。

就目前处理问题这里完全不会break down一下。智力问题。

当然我这里直接$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
ll val[100005],nxt[100005];
int fa[100005];

class EllysTeleport {
public:
   
    int getMax(int N, int H1, int A, int B, int P, int Q, int M) {
        val[1] = H1;
        repp(i,2,N) {
            val[i] = (val[i-1]*A+B)%M;
        }
        sort(val+1,val+N+1);
        repp(i,1,N) {
            nxt[i] = i-1;
        }
        int ans = 0;
        memset(fa,-1,sizeof(fa));
        repp(i,1,N) {
            int cnt = 0;
            int x = i;
            while(x!=0&&fa[x]!=i) {
                ++cnt;
                fa[x]=i;
                x=nxt[x];
            }
            ans = max(ans,cnt);
        }
        return ans;
    }
}t;

EllysPearls

1000的题意是每个点有个颜色，要求同一个颜色的点都放在一起。问当前这些点需要更改顺序多少次。

题解里说了一般出现15这种，就考虑bitmask dp。然后这个dp其实很经典了。就是[0,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
int n;
vector<int>v;
int dp[55][16][1<<16];
class EllysPearls {
    public:

    int dfs(int ind,int col, int state) {

        if(ind>=n) {
            return 0;
        }
        if(dp[ind][col][state]!=-1) {
            return dp[ind][col][state];
        }
        int ans = 1 + dfs(ind+1,col,state);
        if(v[ind] == col) {
            ans = min(ans, dfs(ind+1,col,state));
        }
        if(!((1<<v[ind]) & state)) {
            ans = min(ans, dfs(ind+1,v[ind],((1<<v[ind])|state)));
        }
        dp[ind][col][state]=ans;
        return ans;
    }

    int getMin(int N, int M, vector <int> pearls) {
        memset(dp,-1,sizeof(dp));
        n = N;
        v = pearls;
        return dfs(0,M+1,0);
    }
}t;

最近这边正好是五一假期，自己没有回家。十分想老爸老妈，想想这些年自己独立做的这些决定。也不知道该说些什么。只希望自己要一直努力下去，真的请一直一直努力下去。

总有一天，要让他们。。。为我骄傲。。。