比赛链接：
https://vjudge.net/contest/507736
B – Boss Rush
题意：
有 /(n/) 个技能，第 /(i/) 个技能使用完后的 /(t_i/) 时间内不能使用其他技能，该技能会在 /(len_i/) 的时间中，每秒造成 /(d[i][j]/) 点伤害 /((1 <= j <= len_i)/)，boss 有 /(H/) 滴血，问最短多少时间能杀死 boss。
思路：
先二分时间，然后通过记忆化搜索 + 状态压缩判断指定时间内是否能造成相对应的伤害。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 20, M = 1e5 + 10, K = 3e5 + 10;
LL n, H, t[N], len[N], d[N][M], pre[N][M], dp[K];
bool check(LL x){
for (int i = 0; i < (1 << n); i ++ ){
dp[i] = -1;
}
function<LL(LL)> dfs = [&](LL state){
if ( ~ dp[state]) return dp[state];
LL ans = 0, sumt = 0;
for (int i = 0; i < n; i ++ ){
if (state >> i & 1){
sumt += t[i + 1]; //已经使用的技能的冷却时间
}
}
if (sumt > x) return dp[state] = 0;
for (int i = 0; i < n; i ++ ){
if ( ! (state >> i & 1)){ //使用新的技能
ans = max(ans, pre[i + 1][min(len[i + 1], x - sumt)] + dfs(state | (1 << i)));
}
}
return dp[state] = ans;
};
return dfs(0) >= H;
}
void solve(){
cin >> n >> H;
LL mx = 0;
for (int i = 1; i <= n; i ++ ){
cin >> t[i] >> len[i];
mx += t[i] + len[i];
for (int j = 1; j <= len[i]; j ++ )
cin >> d[i][j];
for (int j = 1; j <= len[i]; j ++ )
pre[i][j] = pre[i][j - 1] + d[i][j];
}
LL L = 0, R = mx + 1;
while(L < R){
LL mid = (L + R) >> 1;
if (check(mid)){
R = mid;
}
else{
L = mid + 1;
}
}
if (L > mx) cout << "-1/n";
else cout << L - 1 << "/n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL T = 1;
cin >> T;
while(T -- ){
solve();
}
return 0;
}
C – Cyber Language
题意：
给定一行句子，输出每个单词的首字母的大写。
思路：
签到，按题意操作。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
char s[100];
void solve(){
gets(s);
for (int i = 0; i < strlen(s); i ++ )
if (i == 0 || s[i - 1] == ' ')
cout << (char)(s[i] - 'a' + 'A');
cout << "/n";
}
int main(){
LL T = 1;
cin >> T;
getchar(); //把换行读取了
while(T -- ){
solve();
}
return 0;
}
I – Package Delivery
题意：
快递站有 /(n/) 个包裹，每个包裹从第 /(l/) 天存放到第 /(r/) 天，每次去快递站可以拿 /(k/) 个包裹，问最少去快递站几次能拿到所有包裹。
思路：
对于第 /(i/) 个快递，它的时间为 /(l_i/) 到 /(r_i/)。
按照贪心的策略，肯定拿 /(r_i/) 最小的那个快递，再从所有 /(l_j <= r_i <= r_j/) 的快递中选 /(r_j/) 最小的 /(k/) 个拿走。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
void solve(){
LL n, k;
cin >> n >> k;
vector < pair<LL, pair<LL, LL> > > st(n);
vector < pair<LL, LL> > ed(n);
for (int i = 0; i < n; i ++ ){
cin >> st[i].first >> ed[i].first;
st[i].second = {ed[i].first, i};
ed[i].second = i;
}
sort(st.begin(), st.end());
sort(ed.begin(), ed.end());
priority_queue < pair<LL, LL>, vector< pair<LL, LL> >, greater< pair<LL, LL> > > q;
vector <bool> used(n, false);
LL ans = 0;
for (int i = 0, j = 0; i < n; i ++ ){
if (used[ed[i].second]) continue;
while(j < n && st[j].first <= ed[i].first){
q.push(st[j].second);
j ++ ;
}
ans ++ ;
for (int t = 0; t < k; t ++ ){
if (q.empty()) break;
used[q.top().second] = true;
q.pop();
}
}
cout << ans << "/n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL T = 1;
cin >> T;
while(T -- ){
solve();
}
return 0;
}
K – Taxi
题意：
有 /(n/) 个小镇，第 /(i/) 个小镇的位置为 /(（x_i，y_i）/)，费用为 /(w_i/)，对于一个点 /(（x^{‘}, y^{‘}）/)，它到第 /(i/) 个小镇的费用为 /(min(w_i, /lvert x^{‘} – x_i /rvert + /lvert y^{‘} – y_i /rvert)/)，现有 q 次询问，每次告诉一个点 /(（x^{‘}, y^{‘}）/)，问小镇到这个点的费用最大为多少？。
思路：
/(max(/lvert x^{‘} – x_i /rvert, /lvert y^{‘} – y_i /rvert)/)
= /(max(max(x^{‘} – x_i, – x^{‘} + x_i), max(y^{‘} – y_i, – y^{‘} + y_i))/)
= max{/((x^{‘} + y^{‘}) + (- x_i – y_i), (x^{‘} – y^{‘}) + (- x_i + y_i), (- x^{‘} + y^{‘}) + (x_i – y_i), (- x^{‘} – y^{‘}) + (x_i + y_i)/)}
所以只需要预处理出所有城镇坐标的四个属性，就可以通过 O(1) 的方法计算曼哈顿距离的答案。
而 /(w/) 则没办法，所以对 /(w/) 进行排序，使其单调，那么就可以通过二分取选择 /(w/)。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const LL N = 1e5 + 10, INF = 1e18;
struct node{
LL x, y, w;
bool operator < (const node & x) const{
return w < x.w;
}
}point[N];
LL a[N], b[N], c[N], d[N], ans;
void solve(){
LL n, q;
cin >> n >> q;
for (int i = 1; i <= n; i ++ )
cin >> point[i].x >> point[i].y >> point[i].w;
sort(point + 1, point + n + 1);
a[n + 1] = b[n + 1] = c[n + 1] = d[n + 1] = -INF;
for (int i = n; i >= 1; i -- ){
a[i] = max(a[i + 1], point[i].x + point[i].y);
b[i] = max(b[i + 1], point[i].x - point[i].y);
c[i] = max(c[i + 1], - point[i].x + point[i].y);
d[i] = max(d[i + 1], - point[i].x - point[i].y);
}
while(q -- ){
LL x, y;
cin >> x >> y;
ans = 0;
LL L = 1, R = n;
function <bool(LL)> check = [&](LL k){
LL mx = a[k] - x - y;
mx = max(mx, b[k] - x + y);
mx = max(mx, c[k] + x - y);
mx = max(mx, d[k] + x + y);
ans = max(ans, min(point[k].w, mx));
return point[k].w < mx;
};
while(L < R){
LL mid = (L + R) >> 1;
if (check(mid)){
L = mid + 1;
}
else{
R = mid;
}
}
check(L);
cout << ans << "/n";
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL T = 1;
cin >> T;
while(T -- ){
solve();
}
return 0;
}
L – Two Permutations
题意：
给定两个序列 /(p/) 和 /(q/)，每次重构从其中一个序列中取出首位元素，然后加入序列 /(r/) 的后面，直到两个序列所有元素被取完结束，现在给定序列 /(s/)，问有多少种取法可以让 /(r = s/)。
思路：
因为每次只从 /(p/) 或者 /(q/) 中取出元素，所以可以定义 /(dp[i][0]/) 表示 /(r/) 序列的第 /(i/) 位是从 /(p/) 序列中取出来的方案数，/(dp[i][1]/) 表示 /(r/) 序列的第 /(i/) 位是从 /(q/) 序列中取出来的方案数。
如果该元素本来就是从本序列中取出，即 /(s[i – 1]/) 和 /(s[i]/) 是从同一个序列中取出的，那么它们位置的坐标差为 1。
如果是从不同序列中取出的，因为之前总共取了 /(i/) 个元素，那么两个序列中的位置之和一定等于 /(i/)。
所以在动态规划之前，先记录两个序列中每个元素的位置即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int mod = 998244353;
void solve(){
LL n;
cin >> n;
vector <LL> p(n + 1), q(n + 1), id1(n + 1), id2(n + 1), s(2 * n + 1);
for (int i = 1; i <= n; i ++ ){
cin >> p[i];
id1[p[i]] = i;
}
for (int i = 1; i <= n; i ++ ){
cin >> q[i];
id2[q[i]] = i;
}
for (int i = 1; i <= 2 * n; i ++ )
cin >> s[i];
vector < vector<LL> > dp(2 * n + 1, vector<LL>(2));
dp[0][0] = 1;
LL ans = 0;
for (int i = 1; i <= 2 * n; i ++ ){
LL pre = s[i - 1], now = s[i];
if (id1[now] == id1[pre] + 1) dp[i][0] = (dp[i][0] + dp[i - 1][0]) % mod;
if (id1[now] + id2[pre] == i) dp[i][0] = (dp[i][0] + dp[i - 1][1]) % mod;
if (id2[now] == id2[pre] + 1) dp[i][1] = (dp[i][1] + dp[i - 1][1]) % mod;
if (id2[now] + id1[pre] == i) dp[i][1] = (dp[i][1] + dp[i - 1][0]) % mod;
}
cout << (dp[2 * n][0] + dp[2 * n][1]) % mod << "/n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL T = 1;
cin >> T;
while(T -- ){
solve();
}
return 0;
}
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/278817.html