A.圆形赛道上经过次数最多的扇区

解题思路：
模拟。
代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> mostVisited(int n, vector<int>& rounds) {
        int sta = rounds[0]-1;
        int m = rounds.size();
        int a[105],maxv = 1;
        memset(a,0,sizeof(a));
        a[sta]=1;
        int i = 1;
        while(i<m){
            sta = (sta + 1)%n;
            a[sta]++;
            maxv = max(maxv,a[sta]);
            if(sta == rounds[i]-1){
                i++;
            }
        }
        vector<int> ans;
        for(int i=0;i<n;i++){
            if(a[i]==maxv)  ans.push_back(i+1);
        }
        return ans;
    }
};

B.你可以获得的最大硬币数目

解题思路：
从小到大排序，从倒数第二个开始取，每隔一个取一次，直到取到n/3个数，相加即可。
代码展示：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxCoins(vector<int>& piles) {
        sort(piles.begin(),piles.end());
        int n = piles.size();
        int ans=0,num=0;
        for(int j=n-2;num!=n/3;j-=2,num++){
            ans+=piles[j];
        }
        return ans;
    }
};

C.查找大小为 M 的最新分组

解题思路：
并查集。一开始每个字符为一个集合，并且每个集合内 ‘1’ 的元素个数定为0，并用数组或者map记录集合内字符 ‘1’ 个数为i(1 <= i <= n)的集合数。遍历数组，将对应位置字符改为 ‘1’，该集合内 ‘1’ 的元素个数修改为1 。如果左边位置为‘1’，则与左边集合合并，如果右边位置为‘1’，则与右边集合合并，并更新集合内‘1’个数 和 集合内字符 ‘1’ 个数为i(1 <= i <= n)的集合数。
代码展示：

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
class Solution {
public:
    int pre[100005];
    int nu[100005];
    int val[100005];
    map<int,int> q;
    int find(int x){
        int r=x;
        while(r!=pre[r])
        r=pre[r];

        int i=x,j;
        while(pre[i]!=j){
            j=pre[i];
            pre[i]=r;
            i=j;
        }
        return r;
    }
    void join(int x,int y){
        int fx=find(x),fy=find(y);
        if(fx!=fy){
            q[nu[fy]]-=1;
            q[nu[fx]]-=1;
            nu[fy]+=nu[fx];
            pre[fx]=fy;
        }
        q[nu[fy]]+=1;
    }
    int findLatestStep(vector<int>& arr, int m) {
        int ans=-1,n=arr.size();
        for(int i=0;i<n;i++)    pre[i]=i,val[i]=0,nu[i]=0;
        for(int i=0;i<n;i++){
            int x = arr[i]-1;
            val[x]=1;
            nu[x]=1;
            q[1]+=1;
            if(x-1 >= 0 && val[x-1]==1)  join(x-1,x);
            if(x+1 < n && val[x+1]==1)    join(x+1,x);
            if(q[m]>0)  ans=i+1;
        }
        return ans;
    }
};

D.石子游戏 V

解题思路：
区间DP。预处理前缀和。dp[i] [j]表示从i~j这个区间内Alice所能获得的最大分数。枚举k（i <= k < j ),suml为区间i~k的和，sumr为区间k+1~j的和。

  • 如果suml < sumr: dp[i] [j] = max(dp[i] [j],dp[i] [k] + suml)
  • 如果suml > sumr: dp[i] [j] = max(dp[i] [j],dp[k+1] [j] + sumr)
  • 如果suml == sumr: dp[i] [j] = max(dp[i] [j],dp[i] [k] + suml ,dp[k+1] [j] + sumr)

代码展示：

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
#define mmax(a,b)  (((a)>(b))?(a):(b))
class Solution {
public:
    int stoneGameV(vector<int>& stoneValue) {
        int n = stoneValue.size();
        int dp[505][505];
        int sum[505];
        sum[0] = stoneValue[0];
        for(int i=1;i<n;i++)    sum[i] = sum[i-1]+stoneValue[i];
        for(int l=1;l<n;l++){
            for(int i=0;i+l<n;i++){
                int j=i+l;
                dp[i][j]=0;
                for(int k=i;k<j;k++){
                    int suml =  sum[k]-sum[i]+stoneValue[i];
                    int sumr =  sum[j]-sum[k+1]+stoneValue[k+1];
                    if(suml<sumr){
                        dp[i][j] = mmax(dp[i][j],dp[i][k]+suml);
                    }else if(suml>sumr){
                        dp[i][j] = mmax(dp[i][j],dp[k+1][j]+sumr);
                    }else{
                        dp[i][j] = mmax(dp[i][j],dp[i][k]+suml);
                        dp[i][j] = mmax(dp[i][j],dp[k+1][j]+sumr);
                    }
                }
            }
        }
        return dp[0][n-1];
    }
};

做题情况：
AC 四题
排名：202 / 5284
总结反思：
这场周赛总体还可以，做的很快，思路也很清晰。