ABC417题解

A. A Substring

简单模拟即可

code

#include<bits/stdc++.h>
using namespace std;
string s;
int n,a,b;
int main(){cin >> n >> a >> b;cin >> s;for(int i = a; i < n-b; ++i){cout << s[i];}
}

B. Search and Delete

对 \(B\) 排序后简单模拟即可

code

#include<bits/stdc++.h>
using namespace std;
const int NN = 108;
int n,m;
int a[NN],b[NN];
int main(){cin >> n >> m;for(int i = 1; i <= n; ++i) cin >> a[i];for(int i = 1; i <= m; ++i) cin >> b[i];sort(b+1,b+1+m);for(int i = 1,j = 1; i <= n; ++i){while(j <= m && b[j] < a[i]) ++j;if(a[i] == b[j]){++j;}else{cout << a[i] << " ";}}
} 

C. Distance Indicators

tag: 思维题

这道题，让我们判定 \(j−i=A_i+A_j\) 的对数

我们先分离变量，发现就是找 \(A_i + i = A_j - j\) 的对数

我们从前往后扫，对于每个 \(A_i\)，我们在 \(map\) 中查 \(A_i+i\) 并且将结果加入答案，然后我们向 \(map\) 中将 \(A_i-i\) 的出现次数 \(+1\)

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 2e5 + 8;
int n;
ll ans;
int a[NN];
map<int,int> ps,mn;
int main(){cin >> n;for(int i = 1; i <= n; ++i){cin >> a[i];ans += ps[i-a[i]];ans += mn[a[i]+i];++ps[a[i]+i];++mn[i-a[i]];
//		cout << ans << endl;}cout << ans;}

bonus：满足 \(j-i < A_i+A_j\) 的 \((i,j)\) 的对数？

答案

用树状数组即可

D. Takahashi's Expectation

tag：DP

害，线上同步考试的时候没做起，被 \(X_i\leq 10^9\) 卡了半天，结果发现 \(P_i,A_i,B_i\leq 500\)

显然如果心情值一开始大于 \(500\)，那么一定会一点一点减少

我们可以用 \(DP\)，设 \(f_{i,j}\) 表示若第 \(i\) 个礼物送出去之前还有 \(j\) 的心情值，到最后的心情值大小

\(DP\) 的转移显然是容易的，从最后倒推即可。

而一开始心情值大于 \(500\)，我们只需要通过前缀和+二分，就可以找到第一次心情值小于等于 \(500\) 是在哪一次送出礼物之后，然后直接调用 \(DP\) 结果即可求得答案

E. A Path in A Dictionary

tag：贪心 搜索

给一张无向图，然后要求 \(U\to V\) 的字典序最小的路径

我们显然贪心地每一步都走编号更小的点，然后我们再加一个记忆化记录从一个点 \(x\) 出发，不能走回上一个来时的点 \(fa\) 能不能走到 \(V\) 即可，然后搜到的第一条路径就是答案

至于证明，显然先走向编号更大的点找到的路径字典序一定比走向编号更小的点的字典序更大

这样记忆化之后，我们保证了每条边只会走一次，复杂度 \(O(\sum m)\)

code

#include<bits/stdc++.h>
using namespace std;
const int NN = 1e3 + 8;vector<int> e[NN];
vector<int> sta;
bool fm[NN][NN];
bool vis[NN],gt;
void dfs(int u,int t,int fa){if(fm[fa][u]) return;sta.push_back(u);vis[u] = 1;if(u == t){gt = 1;return;}for(int i = 0; i < e[u].size(); ++i){int v = e[u][i];if(vis[v]) continue;dfs(v,t,u);if(gt) return;else fm[u][v] = 1;}sta.pop_back();vis[u] = 0;
}
int T,n,m,s,t;
int main(){cin >> T;while(T--){sta.clear();cin >> n >> m >> s >> t;gt = 0;for(int i = 1; i <= n; ++i) e[i].clear(),vis[i] = 0;for(int i = 1,u,v; i <= m; ++i){cin >> u >> v;e[u].push_back(v);e[v].push_back(u);}for(int i = 1; i <= n; ++i)sort(e[i].begin(),e[i].end());dfs(s,t,s);for(int i = 0; i < sta.size(); ++i){cout << sta[i] << ' ';}for(int i = 1; i <= n; ++i){for(int j = 0; j < e[i].size(); ++j)fm[i][e[i][j]] = 0;}cout << '\n';}
}

F. Random Gathering

tag：期望 线段树

去掉期望的外壳之后就是一道 区间平均的题

我们显然对于区间平均操作，可以用一个区间查询 + 区间赋值操作平替

这样之后，接下来的就是线段树的板子了

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const int NN = 2e5 + 8;int n,m;
ll a[NN];inline ll ksm(ll x,ll k){ll ans = 1;while(k){if(k & 1) ans = ans * x % MOD;x = x * x % MOD;k >>= 1;}return ans;
}
inline ll inv(ll x){return ksm(x, MOD - 2);
}struct Seg{int l,r;ll sum,tag;#define l(x) tree[x].l#define r(x) tree[x].r#define ls(x) (x << 1)#define rs(x) (x << 1 | 1)#define sum(x) tree[x].sum#define tag(x) tree[x].tag
}tree[NN << 2];
void addlz(int x,ll num){sum(x) = (r(x) - l(x) + 1) * num % MOD;tag(x) = num;
}
void pushdown(int x){if(tag(x) != -1) addlz(ls(x),tag(x)), addlz(rs(x),tag(x));tag(x) = -1;
}
void pushup(int x){sum(x) = sum(ls(x)) + sum(rs(x));if(sum(x) >= MOD) sum(x) -= MOD;
}
void build(int x,int l,int r){l(x) = l;r(x) = r;if(l == r){addlz(x,a[l]);return;}tag(x) = -1;int mid = (l + r) / 2;build(ls(x),l,mid);build(rs(x),mid+1,r);pushup(x); 
}
ll query(int x,int l,int r){if(l <= l(x) && r(x) <= r){return sum(x);}pushdown(x);ll ans = 0,mid = (l(x) + r(x)) / 2;if(l <= mid) ans += query(ls(x),l,r);if(mid + 1 <= r) ans += query(rs(x),l,r);return ans % MOD;
}
void modify(int x,int l,int r,int num){if(l <= l(x) && r(x) <= r){addlz(x,num);return;}int mid = (l(x) + r(x)) / 2;pushdown(x);if(l <= mid) modify(ls(x),l,r,num);if(mid + 1 <= r) modify(rs(x),l,r,num);pushup(x);return;
}
void print(int x){if(l(x) == r(x)){printf("%lld ",sum(x));return;}pushdown(x);print(ls(x)); print(rs(x));return;
}int main(){ios::sync_with_stdio(false),cin.tie(0);cin >> n >> m;for(int i = 1; i <= n; ++i){cin >> a[i];}build(1,1,n);for(int i = 1,l,r; i <= m; ++i){cin >> l >> r;ll num = query(1,l,r) * inv(r-l+1) % MOD;
//		printf("%lld\n",num);modify(1,l,r,num);}print(1);return 0;
}