image-20210626235353301

GG

5780. 删除一个元素使数组严格递增

暴力一下,

枚举每个元素删除后的数据是不是严格递增的, 数据范围是10001000. 平凡才1e61e6没问题的。

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:

bool f(vector<int>& a) {
for(int i=1;i<a.size();i++) {
if(a[i] <= a[i-1]) return false;
}
return true;
}
bool canBeIncreasing(vector<int>& nums) {
int n = nums.size();
vector<int> a;
for(int i = 0;i<n;i++) {
a.clear();
for(int j=0;j<n;j++) {
if(i == j) continue;
a.push_back(nums[j]);
}
if(f(a)) return true;
}

return false;
}
};

5781. 删除一个字符串中所有出现的给定子字符串

开始还想要不要有啥骚操作, 后面觉得暴力没啥问题,然后暴力就过了,,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
string removeOccurrences(string s, string part) {
int lp = part.size();
string ss;
int found;
while((found = s.find(part)) != string::npos) {
ss.clear();
for(int i = 0; i<s.size(); i++) {
if(found <= i && i< found + lp) continue;
ss+=s[i];
}
s=ss;
}
return s;
}
};

5782. 最大子序列交替和

简单dp?吧,

dp[0] 表示以长度为偶数的子序列的最大值。

dp[1] 表示以长度为奇数的子序列的最大值。

遍历每个数字,计算当前这个数字为奇数或者偶数的最大值, 奇数就是dp[0]减去它,偶数就是d[1]加上它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
long long maxAlternatingSum(vector<int>& nums) {
vector<long long> dp(2, 0), dp2(2, 0);
dp[0] = dp2[0] = -1e9;
for(auto a: nums) {
dp2[1] = max(dp[0] - a, dp[1]);
dp2[0] = max(dp[1] + a, dp[0]);

dp = dp2;
}
return max(dp[0], dp2[1]);
}
};

5783. 设计电影租借系统

模拟题

我是用了一个 map[(shop, movie)] = price,其中price的政府表示借出还是没借出。借出为负,没借出为正。

用一个priority_queue<tuple<price,shop,movie >> 的小顶堆维护借出的。

用n个priority_queue<tuple<price,shop>>的小顶堆维护没借出这个电影的商店。

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
class MovieRentingSystem {
public:
map<tuple<int,int>, int> vis; // <shop, movie> 没借出+, 借出-;
priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> jc; // price,shop,movie
priority_queue<tuple<int,int>, vector<tuple<int,int>>, greater<tuple<int,int>>> wj[300005]; // 【movie】 price,shop

MovieRentingSystem(int n, vector<vector<int>>& entries) {
for(auto &entry: entries) {
int shop = entry[0], movie = entry[1], price = entry[2];

vis[tuple(shop, movie)] = price; // 唯一 键
wj[movie].push(tuple(price, shop));
}
}

vector<int> search(int movie) {
vector<int> ans;

vector<tuple<int,int>> tmp;
map<tuple<int,int>, bool> book;

int cnt = 0;
while(cnt < 5 && !wj[movie].empty()) {
auto [price, shop] = wj[movie].top(); wj[movie].pop();
if(vis[tuple(shop, movie)] < 0 || book[tuple(shop, movie)] == true) {
continue;
}
++cnt;
book[tuple(shop, movie)] = true;
tmp.push_back(tuple(price, shop));
ans.push_back(shop);
}

for(auto t: tmp) {
wj[movie].push(t);
}

return ans;
}

void rent(int shop, int movie) {
int price = vis[tuple(shop, movie)]; //这时候一定是 正数
vis[tuple(shop, movie)] = -price;

jc.push(tuple(price, shop, movie));
}

void drop(int shop, int movie) {
int price = vis[tuple(shop, movie)]; //这时候一定是 负数
vis[tuple(shop, movie)] = -price;

wj[movie].push(tuple(-price, shop));
}

vector<vector<int>> report() {
vector<vector<int>> ans;
vector<int> t(2);
map<tuple<int,int>, bool> book;

vector<tuple<int,int,int> > tmp;
int cnt = 0;
while(cnt < 5 && !jc.empty()) {
auto [price, shop, movie] = jc.top(); jc.pop();
if(vis[tuple(shop, movie)] > 0 || book[tuple(shop, movie)] == true) {
continue;
}
++cnt;
tmp.push_back(tuple(price, shop, movie));
book[tuple(shop, movie)] = true;
t[0] = shop, t[1] = movie;
ans.push_back(t);
}
for(auto tt: tmp) {
jc.push(tt);
}

return ans;
}
};

/**
* Your MovieRentingSystem object will be instantiated and called as such:
* MovieRentingSystem* obj = new MovieRentingSystem(n, entries);
* vector<int> param_1 = obj->search(movie);
* obj->rent(shop,movie);
* obj->drop(shop,movie);
* vector<vector<int>> param_4 = obj->report();
*/