—— Summon, Light!
0%

阿里云超级码力在线编程大赛初赛

发表于 更新于 Valine：

写写题解和吐槽。

初赛第1场题解

树木规划

比较简单的贪心算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int treePlanning(vector<int> &trees, int d) {
        int pre=-1e9;
        int res=0;
        for (const auto &x : trees) {
            if (x-pre>=d) {
                pre=x;
            } else {
                res++;
            }
        }
        return res;
    }
};

正三角形拼接

有点麻烦的分类讨论，讨论过的类就不再存在（本题中不需要考虑不能实现）。

  1. 如果某长度至少三次，0刀
  2. 如果某长度两次，且存在比它大的，1刀
  3. 如果某长度一次，且存在是它两倍的，1刀
  4. 如果至少有三根棍子，后两根切出第一根的长度，2刀
  5. 只有两根的情况，看代码（可能有冗余）
  6. 只有一根的情况，必须被3整除才能2刀，其他情况3刀（切出3个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
class Solution {
public:
    int makeEquilateralTriangle(vector<int> &a) {
        map<int,int> cnt;
        int n = a.size();
        sort(begin(a), end(a));
        for (int i=0;i<n;i++) {
            ++cnt[a[i]];
        }
        for (int i=0;i<n;i++) if (i==0 || a[i]!=a[i-1]) {
            if (cnt[a[i]]>=3) {
                return 0;
            }
        }
        for (int i=0;i<n;i++) if (i==0 || a[i]!=a[i-1]) {
            if (cnt[a[i]]==2) {
                if (i+2<n) return 1;
            } else if (cnt[a[i]]==1) {
                if (cnt.count(a[i]*2)) return 1;
            }
        }
        if (n>=3) return 2;
        if (n==2) {
            if (a[1]>a[0]*2) return 2;
            if (a[1]%3==0) return 2;
            if (a[0]%3==0) return 2;
            if (a[0]%2==0) return 2;
            if (a[1]%2==0 && a[0]>=a[1]/2) return 2;
        }
        if (n==1) {
            if (a[0]%3==0) return 2;
        }
        return 3;
    }
};

大楼间穿梭

不是很难的dp，大佬们没有过的原因是题面错了 = =
首先单调队列预处理出每个楼向右是飞到哪个楼。根据数据其实是飞到第一个高度大于等于的，而不是题面里的大于。然后正常dp一下就可以了。

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
class Solution {
public:
    long long shuttleInBuildings(vector<int> &h, int k, int x, int y) {
        using ll = long long;
        int n = h.size();
        deque<int> st;
        vector<int> r(n, -1);
        vector<ll> dp(n, 1LL<<60);
        for (int i=n-1;i>=0;i--) {
            while (!st.empty() && st.front()-i>k) st.pop_front();
            while (!st.empty() && h[st.back()]<h[i]) st.pop_back();
            r[i] = st.empty() ? -1 : st.back();
            st.push_back(i);
        }
        auto getmin = [](ll &x, ll y) {
            if (y<x) x=y;
        };
        dp[0]=0;
        for (int i=0;i<n;i++) {
            if (r[i]!=-1) getmin(dp[r[i]], dp[i]+x);
            if (i+1<n) getmin(dp[i+1], dp[i]+y);
            if (i+2<n) getmin(dp[i+2], dp[i]+y);
        }
        return dp[n-1];
    }
};

对称前后缀

根据题意，容易得到一个朴素的算法，如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    long long suffixQuery(string &s) {
        int n=s.length();
        long long ans=0;
        for (int i=0;i<n;i++) {
            for (int j=n-1;j>=i;j--) {
                int k=0;
                while (i+k<=j && s[i+k]==s[j-k]) ++k;
                ans+=k;
            }
        }
        return ans;
    }
};

当然，这个算法复杂度很高，所以会时间超限。

记原串为$s$，我们可以把$j$看作在逆序串$s’$上的遍历，那么$j$在$s$上取前缀就相当于在$s’$上取后缀，同时$i$也是一个取后缀操作，而$k$则是在计算LCP（最长公共前缀）的长度。
计算两个后缀的LCP长度是一个经典的问题，有许多数据结构可以高效地解决这一问题。我使用了后缀数组，被称为是后缀树的精巧替代品。首先需要把$s$和$s’$用一个特殊字符拼接起来，然后初始化后缀数组，最后枚举$i$和$j$累加答案即可。不过这里会有两个糟糕的边界问题：其一，在朴素算法中可以看到，$j$在$s$上必须大于等于$i$，所以相应地在$s’$上也会有一个枚举的边界；其二，即使设置了枚举的边界，匹配出来的前缀仍有可能超出$i$和$j$的范围，需要限制一下长度。

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
const int MAXN=20000;
int t1[MAXN],t2[MAXN],c[MAXN];

bool cmp(int *r,int a,int b,int l)
{
	return r[a] == r[b] && r[a+l] == r[b+l];
}

void da(int str[],int sa[],int rk[],int height[],int n,int m)
{
	n++;
	int i, j, p, *x = t1, *y = t2;
	for(i = 0; i < m; i++)c[i] = 0;
	for(i = 0; i < n; i++)c[x[i] = str[i]]++;
	for(i = 1; i < m; i++)c[i] += c[i-1];
	for(i = n-1; i >= 0; i--)sa[--c[x[i]]] = i;
	for(j = 1; j <= n; j <<= 1) {
		p = 0;
		for(i = n-j; i < n; i++)y[p++] = i;
		for(i = 0; i < n; i++)if(sa[i] >= j)y[p++] = sa[i] - j;
		for(i = 0; i < m; i++)c[i] = 0;
		for(i = 0; i < n; i++)c[x[y[i]]]++;
		for(i = 1; i < m; i++)c[i] += c[i-1];
		for(i = n-1; i >= 0; i--)sa[--c[x[y[i]]]] = y[i];
		swap(x,y);
		p = 1;
		x[sa[0]] = 0;
		for(i = 1; i < n; i++)
			x[sa[i]] = cmp(y,sa[i-1],sa[i],j)?p-1:p++;
		if(p >= n)break;
		m = p;
	}
	int k = 0;
	n--;
	for(i = 0; i <= n; i++)rk[sa[i]] = i;
	for(i = 0; i < n; i++) {
		if(k)k--;
		j = sa[rk[i]-1];
		while(str[i+k] == str[j+k])k++;
		height[rk[i]] = k;
	}
}

int rk[MAXN],height[MAXN];
int mm[MAXN],best[20][MAXN];

void initRMQ(int n)
{
	mm[0]=-1;
	for(int i=1; i<=n; i++)
		mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
	for(int i=1; i<=n; i++)best[0][i]=i;
	for(int i=1; i<=mm[n]; i++)
		for(int j=1; j+(1<<i)-1<=n; j++) {
			int a=best[i-1][j];
			int b=best[i-1][j+(1<<(i-1))];
			if(height[a]<height[b])best[i][j]=a;
			else best[i][j]=b;
		}
}

int askRMQ(int a,int b)
{
	int t;
	t=mm[b-a+1];
	b-=(1<<t)-1;
	a=best[t][a];
	b=best[t][b];
	return height[a]<height[b]?a:b;
}

int lcp(int a,int b)
{
	a=rk[a];
	b=rk[b];
	if(a>b)swap(a,b);
	return height[askRMQ(a+1,b)];
}

int r[MAXN];
int sa[MAXN];

class Solution {
public:
    long long suffixQuery(string &s) {
        using ll = long long;
        int n = s.length();
        int str[MAXN] = {0};
        for (int i=0;i<n;i++) {
            str[i]=s[i];
        }
        str[n]='#';
        for (int i=0;i<n;i++) {
            str[n+1+i] = s[n-1-i];
        }
        int m=n+n+1;
        da(str, sa, rk, height, m, 128);
        initRMQ(m);
        ll res = 0;
        for (int i=0;i<n;i++) {
            for (int j=n+1;j<m-i;j++) {
                int tmp = lcp(i, j);
                res += min(tmp, m-j-i);
            }
        }
        return res;
    }
};

初赛第2场

其实没有实际写代码，瞎猜一下。

三角魔法

简单的计算几何题，一般用面积法吧。

Update: 好像挺恶心的。

区间异或

搞一个支持RMQ的数据结构，应该就可以过。

五字回文

因为只需要考虑长度为5的串，直接枚举中心位置判断即可。
（似乎比第二题简单啊）

小栖的金字塔

题面又错了……不过至少改正了 = =

考虑从(2,2)到(5,5)最短路是三次↘，一次↘可以替换为↙加→。也就是说=(↘↘↘全排列)+(↘↘↙→全排列)+(↘↙→↙→全排列)+(↙→↙→↙→全排列)。
应该可以有一个递推形式，那么$O(n-k)$就可以搞定。

Update: 是超级卡特兰数。

初赛第3场题解

最大公倍数

分类讨论，看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    long long greatestcommonmultiple(int a, int b) {
        if (b&1) {
            return 1LL*b*(b-1)*(b-2);
        }
        if (b-a==2) {
            return 1LL*b*(b-1)*(b-2)/2;
        }
        if (b%3==0) {
            return 1LL*(b-1)*(b-3)*(b-2);
        } else {
            return 1LL*(b-1)*(b-3)*b;
        }
    }
};

房屋染色

题目不太好懂，样例也SB。
其实题意就是相邻房子颜色必须不一样，但是可以造一条有长度上限的步行街（这些房子颜色必须一样）。

用$dp(i,0/1,k)$表示到第$i$个房子涂了第$k$种颜色，以及当前有没有造过步行街，那么容易得到状态转移。这里用了multiset优化取最小值的操作，不优化可能也行吧。

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
class Solution {
public:
    int paintHouseIII(vector<vector<int>> &costs, int t) {
        int N = costs.size();
        int K = costs[0].size();
        int ccc[K][N] = {0};
        for (int k=0;k<K;k++) {
            for (int i=1;i<=N;i++) {
                ccc[k][i]=ccc[k][i-1]+costs[i-1][k];
            }
        }
        
        auto getmin = [](int &x, int y) {
            if (y<x) x=y;
        };
        int inf = 1<<29;
        int dp[N+1][2][K];
        for (int i=0;i<=N;i++) {
            for (int k=0;k<K;k++) {
                if (i==0) dp[i][0][k]=0, dp[i][1][k]=inf;
                else dp[i][0][k]=dp[i][1][k]=inf;
            }
        }
        for (int i=1;i<=N;i++) {
            multiset<int> ms;
            for (int k=0;k<K;k++) {
                ms.insert(dp[i-1][0][k]);
            }
            for (int k=0;k<K;k++) {
                ms.erase(ms.find(dp[i-1][0][k]));
                getmin(dp[i][0][k], *ms.begin()+costs[i-1][k]);
                ms.insert(dp[i-1][0][k]);
            }
            ms.clear();
            for (int k=0;k<K;k++) {
                ms.insert(dp[i-1][1][k]);
            }
            for (int k=0;k<K;k++) {
                ms.erase(ms.find(dp[i-1][1][k]));
                getmin(dp[i][1][k], *ms.begin()+costs[i-1][k]);
                ms.insert(dp[i-1][1][k]);
            }
            for (int len=2;len<=t;len++) {
                if (len>i) break;
                ms.clear();
                for (int k=0;k<K;k++) {
                    ms.insert(dp[i-len][0][k]);
                }
                for (int k=0;k<K;k++) {
                    ms.erase(ms.find(dp[i-len][0][k]));
                    getmin(dp[i][1][k], *ms.begin()+(ccc[k][i]-ccc[k][i-len]));
                    ms.insert(dp[i-len][0][k]);
                }
            }
        }
        int ans = inf;
        for (int k=0;k<K;k++) {
            getmin(ans, dp[N][0][k]);
            getmin(ans, dp[N][1][k]);
        }
        return ans;
    }
};

字符串游戏

首先容易发现，跟字母的顺序没有关系。
瞎想瞎写了好久，才发现就是个 Anti-Nim，抄个代码就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool stringGame(string &s) {
        map<char,int> mp;
        for (const auto &c : s) {
            ++mp[c];
        }
        int cnt=0;
        int ans=0;
        for (const auto &p : mp) {
            if (p.second>1) cnt++;
            ans^=p.second;
        }
        if (ans) {
            return cnt;
        } else {
            return !cnt;
        }
    }
};

完美字符串

贪心，对于01相间的子串的操作次数不会优于只考虑全0子串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int perfectString(string &s, int k) {
        int now=0;
        int ans=0;
        for (const auto &c : s) {
            if (c=='0') ++now;
            else {
                ans+=(now+k-1)/k;
                now=0;
            }
        }
        return ans+(now+k-1)/k;
    }
};

初赛第4场题解

十字绣

经典游戏 Nonogram，比赛的时候完全没时间搞。

NP完全问题，搜索剪枝即可。
手玩了一下发现有很多很好的启发式策略，但是很难写成代码……
最后搞了个很暴力的dfs套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
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
int mp[30][30];

class Solution {
private:
    int N, M;
    vector<vector<int>> rhint, chint;
    bool succ;
    bool col_strict_check(int c) {
        vector<int> blk;
        int cnt=0;
        for (int i=0;i<N;i++) {
            if (mp[i][c]==1) {
                ++cnt;
            } else {
                if (cnt) blk.push_back(cnt);
                cnt=0;
            }
        }
        if (cnt) blk.push_back(cnt);
        if (blk.size()==chint[c].size()) {
            for (int i=0;i<blk.size();i++) {
                if (blk[i]!=chint[c][i]) {
                    return false;
                }
            }
            return true;
        } else {
            return false;
        }
    }
    bool col_check(int r, int c) {
        vector<int> blk;
        int cnt=0;
        for (int i=0;i<r;i++) {
            if (mp[i][c]==1) {
                ++cnt;
            } else {
                if (cnt) blk.push_back(cnt);
                cnt=0;
            }
        }
        if (cnt) blk.push_back(cnt);
        if (blk.size()>chint[c].size()) {
            return false;
        }
        if (blk.size()+(N-r+!cnt)/2 < chint[c].size()) {
            return false;
        }
        for (int i=0;i<blk.size()-!!cnt;i++) {
            if (blk[i]!=chint[c][i]) {
                return false;
            }
        }
        if (cnt && cnt>chint[c][blk.size()-1]) {
            return false;
        }
        return true;
    }
    vector<int> rpos[30];
    void row_search(int R, int dep, int lst) {
        if (dep==rhint[R].size()) {
            for (int j=0;j<M;j++) mp[R][j]=0;
            for (int i=0;i<dep;i++) {
                for (int j=rpos[R][i];j<rpos[R][i]+rhint[R][i];j++) {
                    mp[R][j]=1;
                }
            }
            dfs(R+1);
            return;
        }
        int tmp=lst;
        for (int i=dep;i<rhint[R].size();i++) {
            tmp+=rhint[R][i]+1;
        }
        if (--tmp>M) return;
        if (tmp==M) {
            tmp=lst;
            for (int i=dep;i<rhint[R].size();i++) {
                rpos[R].push_back(tmp);
                tmp+=rhint[R][i]+1;
            }
            row_search(R, rhint[R].size(), M);
            if (succ) return;
            for (int i=dep;i<rhint[R].size();i++) {
                rpos[R].pop_back();
            }
            return;
        }
        for (int i=lst;i+rhint[R][dep]<=M;i++) {
            rpos[R].push_back(i);
            row_search(R, dep+1, i+rhint[R][dep]+1);
            if (succ) return;
            rpos[R].pop_back();
        }
    }
    void dfs(int dep) {
        if (dep==rhint.size()) {
            for (int i=0;i<M;i++) {
                if (col_strict_check(i)==false) {
                    return;
                }
            }
            succ=true;
            return;
        }
        if (dep) {
            for (int i=0;i<M;i++) {
                if (col_check(dep, i)==false) {
                    return;
                }
            }
        }
        rpos[dep].clear();
        row_search(dep, 0, 0);
        if (succ) return;
    }
public:
    vector<string> crossStitch(vector<vector<int>> &rowInfo, vector<vector<int>> &colInfo) {
        rhint = rowInfo;
        chint = colInfo;
        N = rhint.size();
        M = chint.size();
        succ = false;
        dfs(0);
        vector<string> res;
        for (int i=0;i<N;i++) {
            string r;
            for (int j=0;j<M;j++) {
                if (mp[i][j]==1) r+='*';
                else r+='.';
            }
            res.push_back(r);
        }
        return res;
    }
};

闰年

又是分类讨论（通过率9%），看代码。

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
class Solution {
public:
    /**
     * @param inputQueries: input Queries, means [[m1, d1, m2, d2, x], [m1, d1, m2, d2, x],...]
     * @return: guess whether y1 is leep year
     */
    string guessYear(vector<vector<int>> &inputQueries) {
        string res;
        int mdays[]={0,31,28,31,30,31,30,31,31,30,31,30,31};
        for (const auto &ve : inputQueries) {
            if (ve[0]==2 && ve[1]==29) {
                res.push_back('R');
                continue;
            }
            bool samey=false;
            if (ve[2]>ve[0] || ve[2]==ve[0] && ve[3]>=ve[1]) {
                samey=true;
            }
            if (ve[2]==2 && ve[3]==29) {
                if (samey) {
                    res.push_back('R');
                } else {
                    res.push_back('P');
                }
                continue;
            }
            if (samey && ve[2]<=2) {
                res.push_back('?');
                continue;
            }
            if (samey && ve[0]>2) {
                res.push_back('?');
                continue;
            }
            int a=ve[0];
            int dd=0;
            while (a!=ve[2]) {
                dd+=mdays[a];
                if (++a>12) {
                    a=1;
                }
            }
            dd+=ve[3]-ve[1];
            if (dd<0) dd+=365;
            if (samey) {
                if (dd==ve[4]) {
                    res.push_back('P');
                } else {
                    res.push_back('R');
                }
            } else {
                if (dd==ve[4]) {
                    if (ve[0]>2) {
                        res.push_back('?');
                    } else {
                        res.push_back('P');
                    }
                } else {
                    if (ve[2]>2) {
                        res.push_back('P');
                    } else {
                        res.push_back('R');
                    }
                }
            }
        }
        return res;
    }
};

from start to end

暴力。

感兴趣的可以学一下"字符串最小表示"。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool judge(string &s1, string &s2) {
        int n=s1.length();
        int m=s2.length();
        if (n!=m) return false;
        for (int i=0;i<m;i++) {
            // cout<<s2<<endl;
            if (s1==s2) return true;
            s2=s2.substr(1,m-1)+s2[0];
        }
        return false;
    }
};

抽奖

长得就有单调性，二分答案，然后暴力算期望次数。
需要注意$aa$和$i$相乘之前就得判断有没有超过$1.0$，否则期望次数算出来会偏大很多。

（这题右键题面某个$a$选择Show Math As -> TeX commands有惊喜……）

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
const double eps=1e-6;

class Solution {
private:
    double calc(double a,int b,double cc) {
        double s=1.0;
        double cnt=0.0;
        for (int i=1;i<b;i++) {
            cnt+=i*a*s;
            s*=(1.0-a);
        }
        double aa=a+cc;
        bool ter=false;
        for (int i=b;!ter;i++) {
            if (aa-1.0>=eps) {
                aa=1.0;
                ter=true;
            }
            cnt+=s*aa*i;
            s*=(1.0-aa);
            aa+=cc;
        }
        return cnt;
    }
public:
    double lotteryDraw(int b, int c, int p) {
        double cc=c/100.0;
        double pp=p/100.0;
        double C=100.0/p;
        double l=0.0, r=1.0;
        double res=-1.0;
        while (r-l>eps) {
            double a0=(l+r)*0.5;
            double n0=calc(a0,b,cc);
            if (n0-C>=eps) {
                l=a0;
            } else {
                r=a0;
                res=a0;
            }
        }
        return res*100.0;
    }
};

吐槽

主要吐槽在线编辑器，完全不可用啊！

  1. 竟然连高亮都没有！不知道他们自己有没有体验过
  2. 把题目显示在代码框的右边？既不符合逻辑也没听说过，可能就是为了显得特别
  3. 我做第一题的时候发现根本改不了input，然后就再也没用了
  4. 字体大小也不能调节，看得我眼睛都要瞎了

排行榜显然也没认真做，

  1. 每页只能显示5个人，而且不能跳页，只有上一页下一页
  2. 没有自己的排名（问了一下客服，可以去"个人中心"里面看）
  3. 没有在任何地方说明“总用时”是如何计算的

我们阿里云办的比赛真是太好了！👍👍

咖啡，亦我所需也