//今天debuff加满了，贪心用dp，dp用贪心，简单题做错。难
//题猜不到

C

//就是一个替换，我tm还想成dp了
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
    int n,m;
    cin>>n>>m;
    vector<ll> a(n+2);
    vector<ll> b(n+2);
    vector<ll> bb(n+2);
    ll sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        bb[i]+=bb[i-1]+b[i];
    }
    for(int i=n+1;i>m;i--){
        sum+=min(a[i],b[i]);
    }
    ll res=a[m];
    for(int i=1;i<m;i++){
        res=min(res,a[i]+bb[m]-bb[i]);
    }
    cout<<sum+res<<"\n";
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    };
}

C

//简简单单的双映射，但是存在一个问题就是建议用find，因为数字可以是0，避免
//查找的时候产生值为0的对
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
    int n;
    cin >> n;
    vector<ll> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int m;
    cin >> m;
    while (m--) {
        string s;
        cin >> s;
        int size = s.size();
        if (size != n) {
            cout << "NO\n";
            continue;
        }
        map<char, ll> mp;
        map<ll, char> ma;
        bool b = false;

        for (int i = 0; i < n; i++) {
            char si = s[i];
            ll ai = arr[i];
            if (mp.find(si) != mp.end() && mp[si] != ai) {
                cout << "NO\n";
                b = true;
                break;
            }
            if (ma.find(ai) != ma.end() && ma[ai] != si) {
                cout << "NO\n";
                b = true;
                break;
            }
            mp[si] = ai;
            ma[ai] = si;
        }
      if(!b) 
            cout << "YES\n";
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

E

//如果二分可以搜索到原来的x，那么不用交换。如果搜索不///到，直接和这个二分结果交换就行，反正原来那个位置二分//不会经过
//还有一点就是向下取符号长这样子；还有就是题意要先搞清//楚干嘛
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

void solve(){
    int n,x;
    cin>>n>>x;
    vector<int> arr(n+1);
    int p = -1;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        if(arr[i]==x) p=i;
    }

    int l=1,r=n+1;
    while(r-l>1){
        int mid=(l+r)/2;
        if(arr[mid]<=x){
            l=mid;
        }else{
            r=mid;
        }
    }

    if(arr[l]==x){
        cout<<"0\n";
    } else {
        cout<<"1\n"<<p<<" "<<l<<"\n";
    }
}

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

    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

F

//一念贪心一念dp，补药一路走到黑，看数据范围，
//这题要主dp，辅贪心
//放在最后，想锻炼举反例的可以试一下；
//由于状态比较多，每个矩形我们可以选完后会有收益和代价
//就变成了背包问题。同时由于每个矩形怎么选也有收益，那么我们可以贪心的把他划分成子物品
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<ll, ll> pii;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<pii>> v(n + 1); // 存储每个矩形的(点数, 操作数)
    vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, (ll)1e15)); // 初始化dp数组，所有值为无穷大
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;

        priority_queue<pii, vector<pii>, greater<pii>> que;
        que.push({min(l, r), max(l, r)});

        ll sum = 0;      // 当前点数
        ll daijia = 0;   // 当前操作数

        // 处理队列中的元素，生成(v[i]中的点数和对应的操作数)
        while (!que.empty()) {
            pii t = que.top();
            que.pop();
            sum++;
            daijia += t.x;


            t.y--;
            ll a = min(t.x, (ll)t.y);
            ll b = max(t.x, (ll)t.y);
            if(a==0) sum++;
             v[i].emplace_back(make_pair(sum, daijia));
            if (a != 0) {
                que.push({a, b});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
            for (int j = 0; j <=m; j++) {
                dp[i][j]=min(dp[i][j],dp[i-1][j]);
                for (auto &[vv, w] : v[i]) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][max(0ll,j- vv)] + w);

            }
        }
    }

    // 输出结果
    if (dp[n][m] == (ll)1e15) {
        cout << "-1\n";
    } else {
        cout << dp[n][m] << "\n";
    }
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}



先上错误代码记录n小时的坚持
大体上我是这样子的，对（长加宽）经行升序排序，然后只要sum+（行加列）<k;就不断的加进去。最后再对剩余的矩形维护每次取出来的边是最短的，然后sum++去逼近这个k
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void solve() {
    int n, k;
    cin >> n >> k;

    int cnt = 0;
    priority_queue<pii, vector<pii>, greater<pii>> que; 
    int l, r;
    vector<pii> temp; 
    int ss=0;
    for (int i = 0; i < n; i++) {
        cin >> l >> r;
        temp.push_back({min(l, r), max(l, r)});
    }
    sort(temp.begin(),temp.end(),[](pii a,pii b){
        int sum_a = a.first + a.second;
        int sum_b = b.first + b.second;
        if (sum_a == sum_b) {
            if(a.first * a.second==b.first * b.second){
            if (a.first == b.first) {
                 return a.second > b.second;
               }
                 return a.first > b.first;
            }
             return sum_a < sum_b;}
             return a.first * a.second<b.first * b.second;
        }
    );
    int j=0;
    for(j=0;j<(int)temp.size()&&ss<k;j++){
        if(ss+temp[j].first+temp[j].second>=k) break;
        //cout<<"oooo\n";
        ss+=temp[j].first+temp[j].second;
        cnt+=temp[j].first*temp[j].second;
        //que.push({temp[i].first,temp[i].second});
    }
    if(ss<k&&j==n){
        cout<<-1<<"\n";
        return;
    }
    if(ss==k){
        cout<<cnt<<"\n";
        return;
    }
    for(j;j<n;j++){
        //cout<<temp[j].first<<" "<<temp[j].second<<"\n";
        que.push({temp[j].first,temp[j].second});
    }

    int sum = ss;
    //int biaoji=0;
    //cout<<que.size();
    while (!que.empty() && sum < k) {
        pii zu = que.top();
        que.pop();
        int mmin = zu.first;
        int mmax = zu.second;
        sum++;
        cnt += mmin;
        mmax--;
        l=min(mmin,mmax);
        r=max(mmin,mmax);
        if(l==0){
            sum++;
        }
        if(l>0){
            que.push({l,r});
        }

    }
    if (sum < k) {
        cout << -1 << "\n";
    } else {
        cout << cnt << "\n";
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

错在代价的计算和收益并不是线性