AWC_0001 Beta 赛时记录
\(\textup{Link.}\)
看到是第一场就来玩一下，挺水的，这边有榜三学长七分钟ak。
兜兜转转，还回去玩了一下其他，最后搞了个一堆罚时，rk500+。
但是咋这么水。
A - Bacteria Growth Experiment
题目都没看，一眼样例输出 \(K + 1\)，\(O(1)\) 过了。
B - Exam Passers
扫一遍，\(O(N)\) 做完了。
C - Discount Coupon
排一遍序，\(O(N \log N)\)，瓶颈在排序。
D - Merchant on the Highway
dp 做，令 \(dp_{i, j}\) 表示上一个选的是 i，花费 \(j\) 的最大收益，背包一遍做完了。
感觉全场最难题，\(O(N^2 \cdot M)\)
$\textup{Code.}$
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 205;
int N, M, K, ans;
int a[MAXN], b[MAXN];
int dp[MAXN][MAXN];
signed main(){cin >> N >> M >> K;for( int i = 1; i <= N; i ++ ){cin >> a[i] >> b[i];}memset( dp, -0x3f, sizeof dp );for( int i = 1; i <= N; i ++ ){if( b[i] <= M ) ans = max( ans, a[i] ), dp[i][b[i]] = a[i];for( int j = max( i - K, 1LL ); j < i; j ++ ){for( int k = 0; k <= M - b[i]; k ++ ){if( dp[j][k] > 0 ){dp[i][k + b[i]] = max( dp[j][k] + a[i], dp[i][k + b[i]] );ans = max( ans, dp[i][k + b[i]] );}}}}cout << ans;return 0;
}
E - Temperature Fluctuation Range
\(set\) 排一下秒了，\(O(N \log N )\)，瓶颈在 \(STL\)。
$\textup{Code.}$
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 5;
int N, K;
int h[MAXN], ans;
multiset<int> st;
signed main(){cin >> N >> K;for( int i = 1; i <= N; i ++ ){cin >> h[i];if( i < K ) st.insert( h[i] );}for( int i = K; i <= N; i ++ ){st.insert( h[i] );auto it1 = st.end();it1 --;auto it2 = st.begin();// cerr << *it1 << " " << *it2 << endl;ans = max( ans, *it1 - *it2 );st.erase( st.find( h[i - K + 1] ) );}cout << ans;return 0;
}