感覺開學之後
最近比較少刷題
分數就卡在1900左右了
感覺沒有特別來練習的話有點難進步
不過每天都有寫的話
至少不太會退步
0.0
Q1 能放多少箱子
思路
暴力
沒什麼特別的
```cpp
class Solution {
public:
int maxContainers(int n, int w, int maxWeight)
{
int res = 0;
int now = 0;
while(now+w <= maxWeight && res < n*n)
{
res ++;
now += w;
}
return res;
}
};
```
Q2
有k個相同的數字的話就可以連在一起
請問有幾團連在一起的
思路
union find + 一個用水桶來判斷相同數字的函式
最後看有幾團就好
```cpp
class UnionFind {
vector<int> par, cnt;
public:
UnionFind(int n): par(n, -1), cnt(n, 1) { }
int find(int a) {
if(par[a] == -1) return a;
return par[a] = find(par[a]);
}
bool un(int a, int b) {
int pa = find(a);
int pb = find(b);
if(pa == pb) return 0;
if(cnt[pa] < cnt[pb]) swap(pa, pb);
cnt[pa] += cnt[pb];
par[pb] = pa;
return 1;
}
};
class Solution {
public:
int intersect(vector<int>& a,vector<int>& b)
{
int re = 0;
for(int i = 0 ; i < 101 ; i ++)
{
if(a[i] >0 && b[i] > 0)re++;
}
return re;
}
int numberOfComponents(vector<vector<int>>& properties, int k)
{
int n = properties.size();
UnionFind uf(n);
vector<vector<int>> paper(n, vector<int>(101, 0));
for(int i = 0 ; i < n ; i ++)
{
for(int j : properties[i])
{
paper[i][j]++;
}
}
for(int i = 0 ; i < n ; i ++)
{
for(int j = i+1 ; j < n ; j ++)
{
if(intersect(paper[i] , paper[j]) >= k)
{
// cout << intersect(properties[i] , properties[j]) << endl;
uf.un(i,j);
}
}
}
unordered_set<int> fgo;
for(int i = 0 ; i < n ; i ++)
{
fgo.insert({uf.find(i)});
}
return fgo.size();
}
};
```
Q3
一群巫師輪流釀藥水
時間是mana*skill
然後藥水一定要連著釀
思路
因為要每種藥水都看開始釀造的最好時機
所以用dp來慢慢推或比較方便
看每次釀藥水最快能開始釀的時候
要看的時間就是上一種藥水釀好後
下一個人能開始釀的時間
0.0
```cpp
class Solution {
public:
long long minTime(vector<int>& skill, vector<int>& mana)
{
int n = skill.size();
int m = mana.size();
vector<vector<long long>> paper( m , vector<long long>(n,0) ) ;
paper[0][0] = skill[0]*mana[0];
for(int i = 1 ; i < n ; i ++)
{
paper[0][i] = skill[i]*mana[0] + paper[0][i-1];
}
for(int i = 1 ; i < m ; i ++)
{
vector<long long> now(n);
now[0] = skill[0]*mana[i] + paper[i-1][0];
for(int p = 1 ; p < n ; p ++)
{
now[p] = skill[p]*mana[i] + now[p-1];
}
long long shift = 0;
for(int s = 0 ; s < n-1 ; s ++)
{
shift = max(shift , paper[i-1][s+1] - now[s]);
}
for(int x = 0 ; x < n ; x ++)
{
paper[i][x] = now[x] + shift;
}
}
// for(int i = 0 ; i < m ; i ++)
// {
// for(int j = 0 ; j < n ; j ++)
// {
// cout << paper[i][j] << " " ;
// }
// cout << endl;
// }
return paper[m-1][n-1];
}
};
// 1 5 2 4
// 5 5 30 40 60
// 1 1 5 7 4
// 29 35 53
// 4
// 2
```