The 2022 ICPC Asia Hangzhou Regional Programming Contest
#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;
}
题意:给出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;
}
- Programming Hangzhou Regional Contest 2022programming hangzhou regional contest hangzhou regional contest 2022 hangzhou regional contest 2023 programming字典hangzhou regional programming shenyang regional contest programming regional contest 2023 programming regional contest aefhkl programming regional yinchuan contest intercollegiate programming regional contest regional contest nanjing 2022