The 2022 ICPC Asia Hangzhou Regional Programming Contest

The 2022 ICPC Asia Hangzhou Regional Programming Contest

No Bug No Game

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;

const int N = 3e3 + 10;

int f[N][N][2];

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    vector<vector<int>> vec(n + 1);
    int sum = 0;
    for(int i = 1; i <= n; i++){
        int sz; cin >> sz; sum += sz;
        vec[i].resize(sz + 1);
        for(int j = 1; j <= sz; j++){
            cin >> vec[i][j];
        }
    }
    memset(f, 128, sizeof(f));
    //前 i 个容量 j 是否装过一次部分物品
    f[0][0][0] = f[0][0][1] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= k; j++){
            int sz = vec[i].size() - 1;
            //不选
            f[i][j][0] = f[i - 1][j][0];
            f[i][j][1] = f[i - 1][j][1];
            //完全选择
            if(j - sz >= 0){
                f[i][j][0] = max(f[i][j][0], f[i - 1][j - sz][0] + vec[i].back());
                f[i][j][1] = max(f[i][j][1], f[i - 1][j - sz][1] + vec[i].back());
            }
            //不完全选择
            for(int k = 1; k <= sz; k++){
                if(j - k >= 0)f[i][j][1] = max(f[i][j][1], f[i - 1][j - k][0] + vec[i][k]);
                else break;
            }
        }
    }
    if(sum > k)cout << max(f[n][k][0], f[n][k][1]) << endl;
    else cout << f[n][sum][0] << endl;
    return 0;
}

Master of Both

题意：给出n个字符串，m种字母顺序，对于每一种字母顺序，输出给出的字符串有多少逆序对。

思路：不论字母表怎么变，比较两个字符串的相应字母是不会变的，可以用字典树把所有字母对个数预处理出来，在字母表上求出对应的贡献即可

#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;

const int N=1e6+5;
const int charsize=26;

int Trie[N][charsize];
bool isend[N];
int root,cnt,ans,res;
int calc[charsize][charsize], sum[N];

void insert(string s){
    int len=s.size();
    int now=0;
    for(int i=0;i<len;i++){
        int x=s[i]-'a';
        for(int j = 0; j < 26; j++){
            if(x == j) continue;
            calc[x][j] += sum[Trie[now][j]];
        }    
        if(!Trie[now][x])Trie[now][x]=++cnt;
        now=Trie[now][x];
        sum[now]++;
    }
    isend[now]=true;
    for(int i = 0; i < 26; i++) res += sum[Trie[now][i]];
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i++){
        string s; cin >> s;
        insert(s);
    }

    while(q--){
        string tmp; cin >> tmp;
        ans = 0;
        for(int i = 0; i < 26; i++){
            for(int j = i + 1; j < 26; j++){
                ans += calc[tmp[i] - 'a'][tmp[j] - 'a'];
            }
        }
        cout << ans + res << endl;
    }
    return 0;
}