昨晚 ABC A-F 题解
2025-12-21 14:09:14
发布于：广东
6阅读
0回复
0点赞
摆了这么久，这次要认真打了。
A
。
namespace cjdst{
void solve(){
int n, m;
std::cin >> n >> m;
std::cout << n * 12 + m << '\n';
}
}
B
用 map 记录每行每个数出现的次数，然后依次查询即可。
namespace cjdst{
void solve(){
int n, m, k;
std::cin >> n >> m >> k;
std::vector <std::vector <int>> a(n + 5, std::vector <int>(m + 5));
std::vector <int> b(k + 5, 0);
std::vector <std::map <int, int>> mp(n + 5);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
std::cin >> a[i][j];
mp[i][a[i][j]]++;
}
}
for(int i = 1; i <= k; i++){
std::cin >> b[i];
}
int ans = 0;
for(int i = 1; i <= n; i++){
int cur = 0;
for(int j = 1; j <= k; j++){
cur += mp[i][b[j]];
}
ans = std::max(ans, cur);
}
std::cout << ans << '\n';
}
}
C
差点以为是 candy（（（
首先让所有的驯鹿都拉雪橇。我们会发现如果让一个驯鹿改到骑雪橇，力量差会减少 。
所以我们可以将每只驯鹿按 排序，逐个枚举到哪个时候力量差会 。
namespace cjdst{
void solve(){
int n;
std::cin >> n;
std::vector <pii> a(n + 5);
ll cur = 0;
for(int i = 1; i <= n; i++){
std::cin >> a[i].first >> a[i].second;
cur += a[i].second;
}
std::sort(a.begin() + 1, a.begin() + n + 1, cmp);
for(int i = 1; i <= n; i++){
if(cur < a[i].first + a[i].second){
std::cout << i - 1 << '\n';
return;
}
cur -= (a[i].first + a[i].second);
}
}
}
D
D < C。
考虑拆开计算。显然可以分为 和 两组，这两个的贡献分别为 。
将 排序后二分即可。
，计算过程时得取模。
namespace cjdst{
void solve(){
const int mod = 998244353;
int n, m;
std::cin >> n >> m;
std::vector <ll> a(n + 5, 0), b(m + 5, 0);
for(int i = 1; i <= n; i++) std::cin >> a[i];
for(int i = 1; i <= m; i++) std::cin >> b[i];
std::sort(a.begin() + 1, a.begin() + n + 1);
std::vector <ll> qzh(n + 5, 0);
for(int i = 1; i <= n; i++){
qzh[i] = qzh[i - 1] + a[i];
}
ll ans = 0;
for(int i = 1; i <= m; i++){
int idx = lower_bound(a.begin() + 1, a.begin() + n + 1, b[i]) - a.begin() - 1;
ans += b[i] * idx - qzh[idx];
ans += qzh[n] - qzh[idx] - b[i] * (n - idx);
ans %= mod;
}
std::cout << ans % mod << '\n';
}
}
E
注意到如果给它建一棵 Trie，节点数不会超过 个。
所以直接动态开点建 Trie 然后按顺序遍历即可。
namespace cjdst{
class Trie{
public:
std::vector <int> v;
std::map <int, Trie*> sons;
};
void dfs(Trie *cur){
for(int i:cur -> v){
std::cout << i << ' ';
}
for(auto i:cur -> sons){
dfs(i.second);
}
}
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5, 0), b(n + 5, 0);
std::vector <Trie*> tr(n + 5);
tr[0] = new Trie;
for(int i = 1; i <= n; i++){
std::cin >> a[i] >> b[i];
if(!tr[a[i]] -> sons.count(b[i])) tr[a[i]] -> sons[b[i]] = new Trie;
tr[i] = tr[a[i]] -> sons[b[i]];
tr[i] -> v.push_back(i);
}
dfs(tr[0]);
}
}
F
诶我去怎么是二维的啊。诶我去怎么还有区间查。
不用慌，题目中让我们求的是曼哈顿距离。
所以考虑分类讨论。分成左上，左下，右上，右下的情况，然后分别取最大值就行了。
显然，如果某个点在左上，那么只有左上的查询曼哈顿距离是最大的。其他同理。
所以可以直接无脑线段树。
namespace cjdst{
template <typename T>
class Segtree{
std::vector <T> tr;
std::vector <int> left, right;
std::vector <T> lazytag;
void push_up(int u){
tr[u] = std::max(tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r, std::vector <T> &a){
left[u] = l, right[u] = r;
if(l == r){
tr[u] = a[l];
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid, a);
build(u << 1 | 1, mid + 1, r, a);
push_up(u);
}
void _modify(int u, int idx, T val){
if(left[u] == right[u]){
tr[u] = val;
return;
}
if(right[u << 1] >= idx) _modify(u << 1, idx, val);
else _modify(u << 1 | 1, idx, val);
push_up(u);
}
T _query(int u, int l, int r){
if(left[u] >= l && right[u] <= r){
return tr[u];
}
T ans = -0x3f3f3f3f3f3f3f3fll;
if(right[u << 1] >= l) ans = std::max(ans, _query(u << 1, l, r));
if(left[u << 1 | 1] <= r) ans = std::max(ans, _query(u << 1 | 1, l, r));
return ans;
}
public:
Segtree(){}
Segtree(int n, std::vector <T> a){
tr.resize(n * 4 + 5);
left.resize(n * 4 + 5);
right.resize(n * 4 + 5);
lazytag.resize(n * 4 + 5);
build(1, 1, n, a);
}
void modify(int idx, T val){
_modify(1, idx, val);
}
T query(int l, int r){
return _query(1, l, r);
}
};
void solve(){
int n, m;
std::cin >> n >> m;
std::vector <ll> a(n + 5, 0), b(n + 5, 0), c(n + 5, 0), d(n + 5, 0);
for(int i = 1; i <= n; i++){
int x, y;
std::cin >> x >> y;
a[i] = x + y, b[i] = x - y;
c[i] = -x - y, d[i] = -x + y;
}
Segtree <ll> tr1(n, a), tr2(n, b), tr3(n, c), tr4(n, d);
while(m--){
int tmp;
std::cin >> tmp;
if(tmp == 1){
int idx, x, y;
std::cin >> idx >> x >> y;
tr1.modify(idx, x + y), tr2.modify(idx, x - y);
tr3.modify(idx, -x - y), tr4.modify(idx, -x + y);
}else{
int l, r, x, y;
std::cin >> l >> r >> x >> y;
std::cout << std::max({-x - y + tr1.query(l, r), -x + y + tr2.query(l, r), x + y + tr3.query(l, r), x - y + tr4.query(l, r)}) << '\n';
}
}
}
}
这里空空如也
有帮助，赞一个