Algorithms Weekly 5

An Easy problems week

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

  • Codeforces Round #634 (Div. 3)

    standing:

    image-20200419200205067.png
    image-20200419200205067.png

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

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

  • 牛客小白月赛24

    standing:

    image-20200419201023216.png
    image-20200419201023216.png

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

  • Leetcode Weekly 185

    standing(貌似前200有字节内推机会,对于考研狗毫无意义)

    image-20200419201320512.png
    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;
}
};