ABC344
A - Spoiler
题意:
给出一个字符串,串中有两个$|$,输出$|$两边的内容。
思路:
我写的代码非常丑陋,模拟写的。
赛后看到string的stl,感觉非常妙。
rfind(str)是从字符串右侧开始匹配str
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int a = s.find('|');
int b = s.rfind('|');
s.erase(a, b-a+1);
cout << s;
}
D - String Bags
题意:
给一个目标串和n$[1, 100]$个背包,每个背包有m$[1, 10]$个串,需要按顺序从每个背包拿出一个或者不拿,这些串能组成目标串。
求最少需要的背包数。
思路:
刚开始我以为是个dfs,判断子串,然后按照下标进行dfs。
zyw说是个dp,我觉得很妙。
写了一发,wa了一个点。
是因为题目要求每个背包只能最多拿一个串,我在dp的时候会同一组的字符串同时作用。
还有一个细节就是一个小字符串只能单独作用,需要从后往前更新(类似于01背包)
解决方法是开一个新的ndp数组,在每一个dp中用之前的ndp数组更新,这样背包里的每一个字符串的更新都是独立的。
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<string> v[101];
void solve() {
string str;
cin >> str;
int ls = str.length();
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
string st;
for (int j = 0; j < t; j++) {
cin >> st;
v[i].push_back(st);
}
}
vector<int> dp(ls + 1, 1e18);
dp[0] = 0;
for (int i = 0; i < n; i++) {
vector<int> ndp = dp;
for (auto s : v[i]) {
int len = s.length();
for (int j = ls - len; j >= 0; j--) {
if(str.substr(j, len) == s) {
ndp[j + len] = min(ndp[j + len], dp[j] + 1);
}
}
}
dp = ndp;
}
if(dp[ls] == 1e18) {
cout << -1 << endl;
}
else {
cout << dp[ls] << endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
E - Insert or Erase
题意:
模拟链表,按照数值插入和删除。
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int val, l, r;
};
void solve() {
int n;
cin >> n;
vector<node> v(n + 2);
v[0].val = -1;
v[0].r = 1;
v[n + 1].val = -2;
map<int, int> mp;
for (int i = 1; i <= n; i++) {
int t;
cin >> t;
v[i].val = t;
v[i].l = i - 1;
v[i].r = i + 1;
mp[t] = i;
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int op;
cin >> op;
if(op == 1) {
int x, y;
cin >> x >> y;
int loc1 = mp[x];
int loc2 = v[loc1].r;
node nt;
nt.val = y;
nt.l = loc1, nt.r = loc2;
v.push_back(nt);
v[loc1].r = v.size() - 1;
v[loc2].l = v.size() - 1;
mp[y] = v.size() - 1;
}
else {
int x;
cin >> x;
int loc = mp[x];
int ll = v[loc].l;
int rr = v[loc].r;
v[ll].r = rr;
v[rr].l = ll;
}
}
for (int i = 0; v[i].val != -2; i = v[i].r) {
if(v[i].val == -1) {
continue;
}
cout << v[i].val << " ";
}
cout << endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
ABC343
D Diversity of Scores
题意:
线段树,两个操作,
- 一个操作是改值
- 一个操作是求区间第二大出现的次数
思路:
改值容易,求区间第二大的数量需要同时记录最大和次大。
和正常的线段树差不多,主要是query有分裂区间需要比较两个区间,所以query的返回值我们干脆设置成node
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5;
struct node {
int l, r;
pair<int, int>p1, p2;
}tree[maxn << 2];
int arr[maxn];
void push_up(int u) {
map<int, int>mp;
mp[-tree[u << 1].p1.first] += tree[u << 1].p1.second;
mp[-tree[u << 1].p2.first] += tree[u << 1].p2.second;
mp[-tree[u << 1 | 1].p1.first] += tree[u << 1 | 1].p1.second;
mp[-tree[u << 1 | 1].p2.first] += tree[u << 1 | 1].p2.second;
int cnt = 0;
for (auto [x, y] : mp) {
if(!cnt) {
cnt++;
tree[u].p1 = {-x, y};
}
else {
tree[u].p2 = {-x, y};
break;
}
}
}
void build_tree(int u, int l, int r) {
tree[u].l = l, tree[u].r = r;
if(l == r) {
tree[u].p1 = {arr[l], 1};
tree[u].p2 = {-1, 0};
return ;
}
int mid = (l + r) >> 1;
build_tree(u << 1, l, mid);
build_tree(u << 1 | 1, mid + 1, r);
push_up(u);
}
void add(int u, int l, int r, int k) {
if(tree[u].l == l && tree[u].r == r) {
arr[l] += k;
tree[u].p1 = {arr[l], 1};
return ;
}
int mid = (tree[u].l + tree[u].r) >> 1;
if(mid >= l) {
add(u << 1, l, r, k);
}
if(mid < r) {
add(u << 1 | 1, l, r, k);
}
push_up(u);
}
node query(int u, int l, int r) {
if(tree[u].l >= l && tree[u].r <= r) {
return tree[u];
}
else {
node a, b;
bool flag1 = 0, flag2 = 0;
int mid = (tree[u].l + tree[u].r) >> 1;
if(mid >= l) {
flag1 = 1;
a = query(u << 1, l, r);
}
if(mid < r) {
flag2 = 1;
b = query(u << 1 | 1, l, r);
}
if(flag1 && flag2) {
node c;
map<int, int>mp;
mp[-a.p1.first] += a.p1.second;
mp[-a.p2.first] += a.p2.second;
mp[-b.p1.first] += b.p1.second;
mp[-b.p2.first] += b.p2.second;
int cnt = 0;
for (auto [x, y] : mp) {
if(!cnt) {
cnt++;
c.p1 = {-x, y};
}
else {
c.p2 = {-x, y};
break;
}
}
return c;
}
else if(flag1) {
return a;
}
else {
return b;
}
}
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
build_tree(1, 1, n);
for (int i = 0; i < m; i++) {
int op;
cin >> op;
if(op == 1) {
int x, y;
cin >> x >> y;
add(1, x, x, y - arr[x]);
}
else {
int l, r;
cin >> l >> r;
cout << query(1, l, r).p2.second << endl;
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
标签:03,val,int,18,cin,2024,++,mp,dp
From: https://www.cnblogs.com/yyc4591/p/18086327