2023.01.31
周赛87
4798. 打怪兽
https://www.acwing.com/problem/content/4801/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// 二分答案: 答案具有二分性质
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// n * n * log(n)
int n, m; cin >> n >> m;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
int L = 1, R = n + 1;
while(L < R) { //log(R - L)
int mid = (L + R) >> 1;
// O(n)
vector<int> b;
for(int i = 0; i < mid; i++) b.push_back(a[i]);
sort(b.begin(), b.end(), greater<int>());
ll sum = 0;
for(int i = 0; i < b.size(); i += 2) sum += b[i];
if(sum <= m) L = mid + 1;
else R = mid;
}
cout << L - 1;
// 找到的是第一个 1
// 0 0 0 0 0 1 1 1 1 1
// 找到的是最后一个 0
/*
int L = 0, R = n;
while(L < R) {
int mid = (L + R + 1) / 2;
if(sum <= m) L = mid;
else R = mid - 1;
}
*/
return 0;
}
4799. 最远距离
https://www.acwing.com/problem/content/4802/
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
vector<int> edge[N];
int ans = 0;
int bfs(int st) { //start
vector<int> vis(N);
queue<int> q;
q.push(st);
vis[st] = 1;
int ret = 0;
while(q.size()) {
int x = q.front(); q.pop();
ret = x;
for(int y : edge[x]) {
if(!vis[y]) {
q.push(y);
vis[y] = vis[x] + 1;
ans = max(ans, vis[y]);
}
}
}
return ret;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
edge[x].push_back(y);
edge[y].push_back(x);
}
bfs(bfs(1));
cout << ans - 1;
return 0;
}
周赛88
4800. 下一个
https://www.acwing.com/problem/content/4803/
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int x; cin >> x;
x ++;
while(1) {
int f = 0;
vector<int> vis(10);
for(int i = x; i; i /= 10) {
int a = i % 10;
vis[a] ++;
if(vis[a] >= 2) f = 1;
}
if(f) x ++;
else break;
}
cout << x;
return 0;
}
4801. 强连通图
https://www.acwing.com/problem/content/4804/
#include <bits/stdc++.h>
using namespace std;
int n, m;
string s, t;
int cnt_2;
int st[22][22];
void dfs(int x, int y) {
if(x < 0 || y < 0 || x >= n || y >= m || st[x][y] == 1) return ;
st[x][y] = 1;
cnt_2 ++;
if(s[x] == '>') dfs(x, y + 1);
else dfs(x, y - 1);
if(t[y] == 'v') dfs(x + 1, y);
else dfs(x - 1, y);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m >> s >> t;
int cnt = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++) {
cnt_2 = 0;
memset(st, 0, sizeof st);
dfs(i, j);
if(cnt_2 == n * m) cnt ++;
}
if(cnt == n * m) cout << "YES";
else cout << "NO";
return 0;
}
4802. 金明的假期
https://www.acwing.com/problem/content/4805/
#include <bits/stdc++.h>
using namespace std;
/*
0: 0...0000
1: 0...0001
2: 0...0010
3: 0...0011
(x & 1) = 0 or 1
(x & 2) = 0 or 2
& | ^
*/
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n; cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i++) cin >> a[i];
vector<vector<int>> dp(n + 1, vector<int>(3));//0:a, 1:b, 2:c
for(int i = 1; i <= n; i++) {
dp[i][0] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
if(a[i - 1] & 1) dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + 1;
if(a[i - 1] & 2) dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + 1;
}
cout << n - max({dp[n][0], dp[n][1], dp[n][2]});
return 0;
}