Algorithms Weekly 5

Posted on | Post modified:

An Easy problems week

本周参加了三场比赛，Codeforces Round #634 (Div. 3)，牛客小白月赛，和本周的力扣周赛。

  • Codeforces Round #634 (Div. 3)

    standing:

    image-20200419200205067.png

div3场还是稍微简单一些，但是中间被D卡了，然后先跑去写了E1&E2，不过cf的机子是真的快，我E2代码的复杂度大概是$2e9$，但是$1.4s$就跑完了。回头看过D突然发现这是个简单题，题目大意就是一个$99$的数独，每个位置的数字都在$[1,9]$之内，你最多可以改变$9$个位置的数字，即变成另一个$[1,9]$内的数字，**使得每行，每列，每个33的子数独都存在相同元素**，给出一种改变方法。

思路就是改变$(0,0),(1,3),(2,6),(3,1),(4,4),(5,7),(6,2),(7,5),(8,8)$这九个位置即可。

  • 牛客小白月赛24

    standing:

    image-20200419201023216.png

貌似并没有很精妙的题目，都是板子&套路题。

  • Leetcode Weekly 185

    standing（貌似前200有字节内推机会，对于考研狗毫无意义）

    image-20200419201320512.png

这次的T3还是很有意思的。

T3题面：

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 “croak” ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

注意：要想发出蛙鸣 “croak”，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。

如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。

我的解法是类似于括号匹配的方式，设置四个变量代表当前$c,r,o,a$的数目，假设当前字母是$r$，那么$c$的个数就要减去$1$，当遇到$k$的时候就算是匹配完了一只青蛙了，此时更新最大值，最大值为$max(ans,nc+nr+no+na+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
class Solution {
public:
    int minNumberOfFrogs(string s) {
        int bc=0,br=0,bo=0,ba=0,bk=0;
        int maxx=0;
        for(char c:s){
            if(c=='c') ++bc;
            if(c=='r'){
                if(bc==0) return -1;
                --bc;
                ++br;
            }
            if(c=='o'){
                if(br==0) return -1;
                --br;
                ++bo;
            }
            if(c=='a'){
                if(bo==0) return -1;
                --bo;
                ++ba;
            }
            if(c=='k'){
                if(ba==0) return -1;
                --ba;
                maxx=max(maxx,ba+bo+br+bc+1);
            }
        }
        if(bc||br||bo||ba) return -1;
        return maxx;
    }
};

T4是一个很简单的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
27
28
29
30
class Solution {
public:
    const int mod = 1e9+7;
    long long dp[60][101][60];//截止到a[i] 最大值为j cost为k的方案数
    int numOfArrays(int n, int m, int k) {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=m;i++) dp[1][i][1]=1;
        for(int i=2;i<=n;i++){
            for(int now=1;now<=m;now++){
                for(int last=1;last<=m;last++){
                    for(int k=1;k<=n;k++){
                        if(now>last){
                            dp[i][now][k+1]+=dp[i-1][last][k];
                            dp[i][now][k+1]%=mod;
                        }else{
                            dp[i][last][k]+=dp[i-1][last][k];
                            dp[i][last][k]%=mod;
                        }
                    }
                }
            }
        }
        long long ans=0;
        for(int i=1;i<=m;i++){
            ans+=dp[n][i][k];
            ans%=mod;
        }
        return ans;
    }
};