A. Dead Pixel
网速题（不过我又是补题）
for _ in range(int(input())):
x,y,n,m = map(int,input().split())
n += 1
m += 1
print(max(x*(m-1),x*(y-m),y*(n-1),y*(x-n)))
B. Homecoming
题意：
给一个只包含 A 和 B 的字符串，代表两种站，你可以从位置 (i) 到达位置 (j) 如果 (i,i+1,...,j-1) 都是同一种站，并花费相应的金钱(如果全是A站则花费a元，否则 b 元)。
现给出 (a,b,p) 代表了两种站的花费和你目前的余额
再给出串 (s) ， 问你最小要从哪个站台开始，才能用你的钱到达终点
这道题一开始在疯狂模拟，细节处理的不是很好，还写错了，心态崩了，先放了一放。
直到我看到 (tag) 有一个二分
我为什么老是想不到二分答案
def judge(idx,a,b,p,s):
i = idx - 1
n = len(s)
cost = 0
while i < n:
if s[i] == 'A':
cost += a
else:
cost += b
while i + 1 < n and s[i] == s[i+1]:
i += 1
return True if cost <= p else False
for _ in range(int(input())):
a,b,p = map(int,input().split())
s = input()
n = len(s)
l,r = 1,n
ans = -1
while(l < r):
mid = (l+r)//2
if judge(mid,a,b,p,s):
ans = max(ans,mid)
l = mid + 1
else:
r = mid - 1
print(ans)
C. Restoring Permutation
题意：
You are given a sequence (b_1,b_2,…,b_n). Find the lexicographically minimal permutation (a_1,a_2,…,a_{2n}) such that (bi=min(a_{2i−1},a_{2i})), or determine that it is impossible.
注意：
要是字典序最小
一开始我先排了个序然后贪，这样不能保证字典序最小，直接按顺序贪就可以了。
#include<bits/stdc++.h>
using namespace std;
int T,n;
int B[400];
int vis[300];
map<int,int>P;
int main(){
cin >> T;
while(T--){
cin >> n;
memset(vis,0,sizeof vis);
P.clear();
for(int i = 1;i <= n;i++){
cin >> B[i];
vis[B[i]] = 1;
}
int ok = 1;
for(int i = 1;i <= n;i++){
for(int j = B[i] + 1;j <= 2*n;j++){
if(!vis[j]){
vis[j] = 1;
P[B[i]] = j;
break;
}
}
if(!P[B[i]]){
ok = 0;
break;
}
}
if(!ok){
cout << -1 << endl;
}
else{
for(int i = 1;i <= n;i++){
cout << B[i] << " " << P[B[i]];
if(i == n){
cout<< endl;
}
else{
cout<< " ";
}
}
}
}
}
D. Recommendations
题意：
有 (n) 种刊物，数量为 (a_i) ,数量加一的代价是 (t_i) ，问所有刊物数量不一样的最小代价
思路：
贪心。
要先处理 (t) 最大的
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
struct node {
int a, t;
};
node A[maxn];
map<int, int>vis;
map<int, int>nxt;
int stk[maxn];
int n;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> A[i].a;
}
for (int i = 0; i < n; i++) {
cin >> A[i].t;
}
sort(A, A + n, [](const node& a, const node& b) {
if (a.t == b.t) {
return a.a < b.a;
}
else {
return a.t > b.t;
}
});
long long ans = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
if (!vis[A[i].a]) {
vis[A[i].a] = 1;
}
else {
int now = A[i].a;
while (vis[now]) {
stk[cnt++] = now;
if (!nxt[now]) {
now++;
}
else {
now = nxt[now];
}
}
vis[now] = 1;
stk[cnt++] = now;
ans += 1ll * A[i].t * (now - A[i].a);
for (int i = 0; i < cnt; i++) {
nxt[stk[i]] = now + 1;
}
}
}
cout << ans << endl;
}
这里的 (nxt) 处理的挺巧妙的。