Codeforces Round #683 (Div. 2, by Meet IT)

A.
让所有的都到sum即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        cout << n << endl;
        for(int i=1; i<=n; i++){
            cout << i << " ";
        } 
        cout <<'\n';
    }
}

B.
如果相邻的两个都是负号，那么可以抵消，如果负号相邻的是正数，那么负号可以转移，从而最后如果剩一个负号，那么转移给绝对值最小的那个即可。

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int a[11][11];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, m, s=0, cnt = 0;
        cin >> n >> m;
        int mi = INF;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                cin >> a[i][j];
                if(a[i][j] < 0) cnt++;
                s += abs(a[i][j]);
                mi = min(mi, abs(a[i][j]));
            }
        }
        if(cnt % 2) s-=2*mi;
        cout << s << endl;
    }
}

C.
对于一个小于等于w的物品，如果它大于等于(w+1)/2，那就直接输出这个即可，如果小于(w+1)/2,那么sum+=这个数，直到最后大于(w+1)/2即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> ans;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, w;
        cin >> n >> w;
        int p = 0, s = 0;
        for(int i=1, x; i<=n; i++){
            cin >> x;
            if(x <= w)
            {
                if(x >= (w+1)/2) p = i;
                else if(s < (w+1)/2) ans.push_back(i), s+=x;
            }
        }
        if(p)
            cout << 1 << endl << p;
        else if(s >= (w+1)/2){
            cout << ans.size()<<endl;
            for(auto x:ans) cout << x << ' ';
        }
        else cout << -1;
        cout << endl;
        ans.clear();
    }
}

D.
给定两个字符串，求其中的贡献值最大，贡献值最大为4LCS(a,b)-|a|-|b|，
思路：dp[i][j]表示a的前i个字符和b的前j个字符的最大贡献值。如果a[i]=b[j], 那么dp[i][j] = dp[i-1][j-1]+2，否则dp[i][j]=max(dp[i-1][j], dp[i][j-1])

#include<bits/stdc++.h>
using namespace std;
int dp[5010][5010];
int main()
{
    int n, m;
    string a, b;
    cin >> n >> m;
    cin >> a;
    cin >> b;
    int ans = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(a[i-1] == b[j-1]) dp[i][j] = dp[i-1][j-1]+2;
            else{
                dp[i][j] = max({0, dp[i-1][j]-1, dp[i][j-1]-1});
            }
            ans = max(ans, dp[i][j]);
        }
    }
    cout << ans << endl;
}

待更新