PDD 0817 笔试 25+25+25+5

第一题, 类似两数之和, 维护一下前面和他互补的数出现的次数

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

typedef long long LL;
const int M = 998244353;


int main() 
{
    int n, m;
    cin >> n >> m;

    vector<LL> a(n + 10, 0);
    unordered_map<LL, vector<LL>> mp;

    LL ans = 0;

    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        LL md = a[i] % m;
        LL tg = m - md;
        tg %= m;
        ans = (ans + mp[tg].size()) % M;
        mp[md].push_back(a[i]);
    }

    cout << ans << endl;
}

第二题 ci * i, 排个序就行

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n;
    long long x;
    cin >> n >> x;
    vector<int> c(n + 10);
    for (int i = 1; i <= n; i ++)
    {
        cin >> c[i];
        c[i] = (n - i + 1) * c[i];
    }
    
    sort(c.begin() + 1, c.begin() + 1 + n);

    for (int i = 1; i <= n; i ++)
    {
        x -= c[i];
        if (x < 0)
        {
            cout << i - 1 << endl;
            return 0;
        }
    }

    cout << n << endl;
}

第三题, 类似昨天东哥的第二题, 滑动窗口

#include <bits/stdc++.h>

#define PII pair<long long, long long>
using namespace std;

typedef long long LL;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    LL n, T;
    cin >> n >> T;
    vector<LL> s(n + 10, 0), d(n + 10, 0);
    for (int i = 1; i <= n; i ++)
        cin >> s[i] >> d[i];

    priority_queue<PII> pq;
    int l = 1, r = 0;
    LL sum = 0;
    LL ans = 1000000000; 

    for (int r = 1; r <= n; r ++)
    {
        sum += s[r];
        pq.push({d[r], r});
        // cout << l << " " << r << endl;
        while (l < r)
        {
            if (sum < T) break;
            ans = min(ans, pq.top().first);
            if (sum == T) break;
            sum -= s[l]; l ++;
            while (pq.top().second < l) pq.pop();
        }
        // cout << pq.top().first << endl;
    }

    cout << ans << endl;
}

第四题只过了 20%, 不会写, 求解答