总结

呃呃（考的最糟糕的一次！！）
0 + 100 + 0 + 0 = 100分
第三题用成了dp，第四题重载运算符写寄了！！！

总之WSSB

T1

这题要我们让 \(s\) 的数量最大化，那我们可以试试贪心，我们让 \(k\) 个为一组来考虑，后面只需要乘上 \(n \div k\)，在考虑一下最后无法分组的几个数，那么如何填这 \(k\) 个数呢？
如果当前的前k天加起来的数加 \(s\) 小于 \(0\)，则这个数选 \(s\)，要不然选 \(d\)，然后就没了（呃呃呃~~所以我说我是个kun~~）

谢谢yabnto大奆佬提供的思路！！！！！！！！！！

code:
时间复杂度：\(O(t \cdot k)\)
空间复杂度：\(O(n)\)

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e4 + 5;

int a[N], t, n, k, s, d; 

void Solve(){
    cin >> n >> k >> s >> d;  
    d *= -1;
    int sum = 0;
    for(int i = 1; i <= k; i++){
        if(sum + s + d * (k - i) < 0){
            a[i] = s;
        }        
        else a[i] = d;
        sum += a[i];
    }  
    sum *= n / k;
    for(int i = 1; i <= n % k; i++){
        sum += a[i];
    }
    if(sum >= 0){
        cout << sum;
    }
    else cout << "Deficit";
    cout << "\n";
}

signed main(){
    cin >> t;
    while(t--){
        Solve();
    } 
    return 0;
}

T2

啊啊啊，就是一个二维前缀和好吧，没啥好说的！！
code:
时间复杂度：\(O(n ^ 2)\)
空间复杂度：\(O(n ^ 2)\)

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e3 + 5;

int n, m, r, c, a[N][N], sum[N][N], ans;

int val(int x, int y, int i, int j){
    return sum[i][j] - sum[i][y - 1] - sum[x - 1][j] + sum[x - 1][y - 1];            
}

signed main(){
    freopen("matrix.in", "r", stdin);
    freopen("matrix.out", "w", stdout);
    cin >> n >> m >> r >> c;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            int x = i - r + 1, y = j - c + 1;
            if(x <= 0 || y <= 0){
                continue;
            }
            ans = max(ans, val(x, y, i, j));
        }
    }
    cout << ans;
    return 0;
}

T3

啊啊啊，我之前用的是 \(dp\)，但是根据 \(Mr.Gengar\) （就是蒹葭）的解释是说 \(dp\) 在这题会陷入局部最优解的循环中（~~虽然我没能听懂~~）

然后我就想到了用二分来逼近 \(m\)，然后对了！！
我们可以考虑一下先用 \(n ^ 2\) 处理出所有 \(p_i + p_j\) 存在 \(b_i\) 中（注意也可以不打，相当于在 \(p_i\) 中加一个为 \(0\) 的元素），然后枚举每一个 \(b_i\) 用二分找到一个 \(b_j\) 使得 \(b_i + b_j \leq m\) 然后取个最大值即可（注意如果 \(b_i > m\) 直接跳过）
code:
时间复杂度：\(O(n ^ 2 \cdot \log^2 n)\)
空间复杂度：\(O(n ^ 2)\)

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e3 + 5;

int n, m, p[N], b[N * N], cnt, ans;

bool cmp(int x, int y){
    return x > y;
}

signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
    }
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= n; j++){
            b[++cnt] = p[i] + p[j];
        }
    } 
    sort(b + 1, b + cnt + 1);
    for(int i = 1; i <= cnt; i++){
        if(b[i] > m){
            continue;
        }
        int tmp = upper_bound(b + 1, b + cnt + 1, m - b[i]) - b - 1;
        if(b[i] + b[tmp] <= m){
            ans = max(ans, b[i] + b[tmp]);
        }
    }
    cout << ans;
    return 0;
}

T4

这题是独立想出来的（~~但是错的很傻逼~~）
我们可以考虑把 \(a_i\) 和 \(b_i\) 都排序，然后从 \([1, 1]\) 输出，没输出一个，就往优先队列里扔一个 \([i + 1, j]\) 和 \([i, j + 1]\)，然后再用一个 \(map\) 来去重即可
code:
时间复杂度：\(O(n \cdot \log n)\)
空间复杂度：\(O(n)\)

#include<bits/stdc++.h> 

using namespace std;

#define int long long

const int N = 1e5 + 5;

int n, a[N], b[N], cnt;

struct node{
    int x, y;
    bool operator < (const node &p) const{
        return a[x] + b[y] > a[p.x] + b[p.y];
    }
}cur;

priority_queue<node> q;
map<pair<int, int>, int> mp;

signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    } 
    for(int i = 1; i <= n; i++){
        cin >> b[i];
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    q.push({1, 1});
    for(int i = 1; cnt < n; i++){
        cur = q.top();
        q.pop();
        if(mp[{cur.x, cur.y}] > 0){
            continue;
        }
        cout << a[cur.x] + b[cur.y] << " ";
        cnt += 1;
        mp[{cur.x, cur.y}] += 1;
        q.push({cur.x + 1, cur.y});
        q.push({cur.x, cur.y + 1});
    } 
    return 0;
}