比赛传送门:Dashboard - Codeforces Round #822 (Div. 2) - Codeforces
A. Select Three Sticks
枚举所有点,选择一个点作为基准,计算所有点与基准的差的绝对值,取最小的三个相加,再从所有结果中取小就可以了。时间复杂度\(O(t*n^2*logn)\)
B. Bright, Nice, Brilliant
这个构造太简单就不说了。
C. Removing Smallest Multiples
从1到N枚举所有数字x,再枚举这个数字x的所有倍数,如果遇到了要保留的数字(s[i] == ‘1’),那么就break,因为这个要保留的数字是x的最小倍数,无法被删除,后面也就无法删除了。类似于埃氏筛法。
调和级数\(\sum_{1}^{n}1 / i =ln(n) + y\),复杂度为\(O(t* n * logn)\)。
D. Slime Escape
先假定要从K到0,如果是要到N + 1只需要将序列反过来从N - K + 1到0即可。
我们把K右侧的点作为“补给站”,但是要求sum要大于等于一个阈值才能获取这个补给,然后一直往左边走,看看能不能走到终点、
反转数组改变起点再算一次。
这是一个很重要的思维,左右横跳的题可以转化为“补给站”。
代码 / Code
#include <bits/stdc++.h> #define fi first #define se second #define int long long using namespace std; const int maxn = 2e5 + 9, inf = 8e18; int a[maxn], N, K; bool go(int k) { vector<pair<int, int> > v;//补给站数组 for(int i = k + 1, sum = 0, mi = 0;i <= N; ++ i)//mi是过程中的代价,要减去mi依然非负才可以加上sum { sum += a[i], mi = min(mi, sum); if(sum > 0)v.push_back({mi, sum}), mi = sum = 0; } for(int i = k - 1, j = 0, sum = a[k];i >= 1; -- i)//sum是过程中的值 { while(j < v.size() && sum + v[j].fi >= 0)sum += v[j ++].second; sum += a[i]; if(sum < 0)return false;//如果中途出现负数就停 } return true; } void solve() { cin >> N >> K; for(int i = 1;i <= N; ++ i)cin >> a[i]; bool ans1 = go(K); reverse(a + 1,a + 1 + N); bool ans2 = go(N - K + 1); cout << ((ans1 || ans2) ? "YES" : "NO") << '\n'; } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int _;cin >> _; while(_ --)solve(); return 0; }
文章评论