这次状态比较好，该打的部分分都打了，该打的对拍也都打了。
T1 最小最大和
Problem Description
Alice和Bob在玩一个游戏，每一轮Bob都会给Alice两个整数A和B(1<=A,B<=100)，Alice每一轮必须把目前所有的A序列和B序列中的数一一配对，每个数必须用且只使用一次，要求最大和最小。
Input
第一行一个整数N(1<=N<=100000)，表示比赛的轮数。
接下来N行每行包含两个整数A和B(1<=A,B<=100)，表示Bob这一轮给的两个数。Output
输出N行，每行输出最小的最大和。
Sample Input Copy
输入1： 3 2 8 3 1 1 4 输入2： 3 1 1 2 2 3 3Sample Output Copy
输出1： 10 10 9 输出2： 2 3 4Hint
【样例解释】
样例1中，第一轮的A序列为{2},B序列为{8}，只能是(2,8)，答案为10；
第二轮A序列为{2,3}，B序列{8,1}，可以采用配对(2,8),(1,3)，这样的配对最大的和是10，是最小的配对方案；
第三轮A序列为{2,3,1}，B序列为{8,1,4}可以采用配对(2,1),(3,4),(1,8)，最大的和为9，没有比这更小的配对方案。
【数据范围】
50%的数据N<=200
首先想到一个贪心，A 序列中最大的数与 B 序列中最小的数配对，A 序列中第2大的数与 B 序列中第2小的数配对……以此类推。证明就是反证。
然后因为值域小，所以可以采用桶排的做法。
/**
* @file 最小最大和.cpp
* @tag: #GMOJ#贪心
* @author: ZnPdCo
* @date: 2023-12-31 14:27:51
* @problem: https://gmoj.net/senior/#main/show/1443
**/
#include <cstdio>
#define ll long long
#define N 100000
ll n;
ll x, y;
ll a[110], b[110];
inline ll max(ll k, ll u) {
return k > u ? k : u;
}
int main() {
scanf("%lld", &n);
for(ll i = 1; i <= n; i++) {
scanf("%lld %lld", &x, &y);
a[x]++, b[100-y+1]++;
ll mx = 0;
ll as=0, bs=0;
ll ap=1, bp=1;
while(ap <= 100 || bp <= 100) {
if(a[ap] && b[bp]) mx = max(mx, ap+100-bp+1);
if(as+a[ap] < bs+b[bp]) {
as += a[ap++];
} else if(as+a[ap] > bs+b[bp]) {
bs += b[bp++];
} else {
as += a[ap++];
bs += b[bp++];
}
}
printf("%lld\n", mx);
}
}
T2 回家
Problem Description
Alice住在森林里，森林可以看作是N*M的网格，森林里有怪兽，用‘.’表示空地，‘+’表示怪兽，‘V’表示Alice现在的位置，‘J’表示Alice的家。
Alice可以从当前单元格向上下左右相邻单元格移动，有怪兽的地方也可以走，只不过比较危险，有怪兽的单元格对其他单元格会产生一定的危险系数，假设怪兽位置为(A,B)，它对某单元格(R,C)的危险系数为：|R-A|+|C-B|，危险系数越小越危险，每个单元格的危险系数是所有怪兽对它产生的系数的最小值。
Alice请你帮她找一条最佳路径回家，即使得路径上经过单元格的最小的危险系数最大。Input
输入第一行包含两个整数N和M(1<=N,M<=500)，表示森林的大小。
接下来N行每行包含M个字符：‘.’，‘+’，‘V’，‘J’。
输入只包含一个‘V’和‘J’，而且至少有一个‘+’。Output
输出最佳路径中最小的危险系数。
Sample Input Copy
输入1： 4 4 +... .... .... V..J 输入2： 4 5 ..... .+++. .+.+. V+.J+Sample Output Copy
输出1： 3 输出2： 0
预处理每一行单元格每个点的前面和后面一个怪物可以做到 \(O(n^3)\)，不能过。考虑用 bfs 计算每个单元格的危险系数可以做到 \(O(n^2)\)。
然后跑最短路。
/**
* @file 回家.cpp
* @tag: #GMOJ#最短路#宽搜
* @author: ZnPdCo
* @date: 2023-12-31 14:28:25
* @problem: https://gmoj.net/senior/#main/show/1445
**/
#include <cstdio>
#include <queue>
#include <cstring>
#define ll long long
#define N 510
using namespace std;
const ll dx[4]={0,1,0,-1};
const ll dy[4]={1,0,-1,0};
ll n, m;
char s[N][N];
ll pre[N][N];
ll nxt[N][N];
ll w[N][N];
ll stx, sty, edx, edy;
ll dis[N][N];
ll vis[N][N];
inline ll min(ll x, ll y) {
return x < y ? x : y;
}
inline ll abs(ll x) {
return x < 0 ? -x : x;
}
struct pos {
ll x, y;
pos(ll xx=0, ll yy=0) {x=xx,y=yy;}
friend bool operator <(const pos& x, const pos& y) {
return x.x < y.x;
}
friend bool operator >(const pos& x, const pos& y) {
return x.x > y.x;
}
};
int main() {
scanf("%lld %lld", &n, &m);
for(ll i = 1; i <= n; i++) {
scanf("%s", s[i]+1);
}
// 计算每行每个点上一个和下一个（包括自己）
// 方法炸了，N^3果然还是太大
// 考虑宽搜降到N^2
queue<pos> que;
for(ll i = 1; i <= n; i++) {
for(ll j = 1; j <= m; j++) {
w[i][j] = 1e15;
if(s[i][j] == '+') {
que.push(pos(i, j));
w[i][j] = 0;
}
if(s[i][j] == 'V') {
stx = i, sty = j;
} else if(s[i][j] == 'J') {
edx = i, edy = j;
}
}
}
while(!que.empty()) {
ll x = que.front().x;
ll y = que.front().y;
que.pop();
for(ll i = 0; i < 4; i++) {
ll xx = x+dx[i];
ll yy = y+dy[i];
if(xx > 0 && yy > 0 && xx <= n && yy <= m) {
if(w[xx][yy] > w[x][y]+1) {
w[xx][yy] = w[x][y]+1;
que.push(pos(xx, yy));
}
}
}
}
priority_queue<pair<ll, pos> > q;
for(ll i = 1; i <= n; i++) for(ll j = 1; j <= m; j++) dis[i][j] = -1e15;
dis[stx][sty] = w[stx][sty];
q.push(make_pair(dis[stx][sty], pos(stx, sty)));
while(!q.empty()) {
ll x = q.top().second.x;
ll y = q.top().second.y;
q.pop();
if(vis[x][y]) continue;
vis[x][y] = 1;
for(ll i = 0; i < 4; i++) {
ll xx = x+dx[i];
ll yy = y+dy[i];
if(xx > 0 && yy > 0 && xx <= n && yy <= m) {
if(!vis[xx][yy]) {
if(dis[xx][yy] < min(w[xx][yy], dis[x][y])) {
dis[xx][yy] = min(w[xx][yy], dis[x][y]);
q.push(make_pair(dis[xx][yy], pos(xx, yy)));
}
}
}
}
}
printf("%lld", dis[edx][edy]);
}
T3 开拓
Problem Description
Input
Output
Sample Input Copy
5 50 50 10 1 10 1 20 2 10 2 20 1 30Sample Output Copy
375.00Data Constraint
题目描述有坑，注意钱财可以为负。
如果钱财可以为负就可以跑反向 DP 来避免后效性。设 \(f_i\) 为 \(i\sim n\) 的最大金钱。
设第 \(i\) 位的能力值为 \(1\)，那么发现如果在这里开采资源，第 \(i+1\) 位的能力必须为 \(1-0.01k\)。即：
当然因为初始能力值不为 \(1\) 所以输出答案时可以乘上 \(w\)。
/**
* @file 开拓.cpp
* @tag: #GMOJ#dp#反向dp
* @author: ZnPdCo
* @date: 2023-12-31 14:30:51
* @problem: https://gmoj.net/senior/#main/show/5377
**/
#include <cstdio>
#include <algorithm>
#define ll long long
#define N 100010
using namespace std;
ll n, k, c, w;
ll t[N];
double x[N];
double f[N];
int main() {
freopen("exploit.in", "r", stdin);
freopen("exploit.out", "w", stdout);
scanf("%lld%lld%lld%lld", &n, &k, &c, &w);
for(ll i = 1; i <= n; i++) {
scanf("%lld%lf", &t[i], &x[i]);
}
for(ll i = n; i >= 1; i--) {
if(t[i] == 1) {
f[i] = max(f[i+1], f[i+1]*(1-0.01*k)+x[i]);
} else {
f[i] = max(f[i+1], f[i+1]*(1+0.01*c)-x[i]);
}
}
printf("%.2lf", f[1] * w);
}
T4 删数字
Problem Description
给你一个N 个数组成的序列V，要你删除其中K 个数，M 表示剩下的数字中任意两个数的差值的最大值，m 表示最小差值，要你计算删除K 个数后，M+m的最小值。
Input
第一行包含两个整数N(3<=N<=1,000,000)和K(1<=K<=N-2);
第二行包含N 个空格隔开的数， 表示给定的序列V(-5,000,000<=Vi<=5,000,000)。
Output
输出M+m 的最小值。
Sample Input Copy
输入1： 5 2 -3 -2 3 8 6 输入2： 6 2 -5 8 10 1 13 -1 输入3： 6 3 10 2 8 17 2 17Sample Output Copy
输出1： 7 输出2： 13 输出3： 6Data Constraint
100%的数据
3<=N<=1,000,000，1<=K<=N-2)，-5,000,000<=Vi<=5,000,000
当时打了一个暴力发现最终的一种解序列一定是原序列排序后的一个子串（连续的），证明可反证，然后就可以用单调队列维护区间最小差值就可以过了。
原题数据估计是随机生成的，st表、线段树信仰之后都可以过。
/**
* @file 删数字.cpp
* @tag: #GMOJ#单调队列
* @author: ZnPdCo
* @date: 2023-12-31 14:34:45
* @problem: https://gmoj.net/senior/#main/show/3154
**/
#include <cstdio>
#define ll long long
#define N 1000010
ll a[N], b[N], n, k;
ll c[N]; // i与i-1的差值
ll ans=1e15;
// 我是sb，都排序了还求区间最大值
ll q[N], h=1, t; // 维护区间最小差值
// woc这么卡常？？！
inline ll read() {
ll x = 0;
char c = '.';
ll f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ '0');
c = getchar();
}
return x * f;
}
inline ll min(ll x, ll y) {
return x < y ? x : y;
}
void solve(ll l, ll r) {
if(l == r) return;
ll mid = (l + r) >> 1;
solve(l, mid);
solve(mid + 1, r);
ll pos1 = l, pos2 = mid+1;
for(ll i = l; i <= r; i++) {
if(pos1 > mid) {
b[i] = a[pos2++];
} else if(pos2 > r) {
b[i] = a[pos1++];
} else if(a[pos1] < a[pos2]) {
b[i] = a[pos1++];
} else {
b[i] = a[pos2++];
}
}
for(ll i = l; i <= r; i++) {
a[i] = b[i];
}
}
// 卡这么死干什么
int main() {
n = read(), k = read();
for(ll i = 1; i <= n; i++) {
a[i] = read();
}
solve(1, n);
for(ll i = 2; i <= n; i++) {
c[i] = a[i] - a[i-1];
}
for(ll i = 2; i < n-k; i++) {
// 维护区间最小差值，一个上升单调队列
while(h <= t && c[q[t]] >= c[i]) t--;
q[++t] = i;
}
for(ll i = 1; i <= k+1; i++) { // 左端点
// 左端点 剩下的 自己
ll j = i + n - k - 1;
// 维护区间最小差值，一个上升单调队列
while(h <= t && q[h] <= i) h++; // 因为第i个插值是a(i)-a(i-1)，所以当头为i时也要去掉
while(h <= t && c[q[t]] >= c[j]) t--;
q[++t] = j;
ans = min(ans, a[j] - a[i] + c[q[h]]);
}
printf("%lld", ans);
}