Daiwa Securities Co. Ltd. Programming Contest 2023（AtCoder Beginner Contest 331）
A - Tomorrow
解题思路:
模拟。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
ll f(ll a, ll b)
{
if (b < a)
{
return b;
}
return f(a, b / a) + (b % a);
}
void solve()
{
int M, D;
cin >> M >> D;
int y, m, d;
cin >> y >> m >> d;
d++;
if (d >= D)
{
d = 1;
m++;
if (m >= M)
{
m = 1;
y++;
}
}
cout << y << ' ' << m << ' ' << d << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Buy One Carton of Milk
解题思路:
n很小，直接枚举所有情况。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
ll f(ll a, ll b)
{
if (b < a)
{
return b;
}
return f(a, b / a) + (b % a);
}
void solve()
{
int n;
cin >> n;
int s, m, l;
cin >> s >> m >> l;
ll ans = 1e9 + 10;
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
for (int k = 0; k <= n; k++)
{
if (i * 6 + j * 8 + k * 12 >= n)
{
ans = min(ans, (ll)i * s + j * m + k * l);
}
}
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - Sum of Numbers Greater Than Me
解题思路:
排序，前缀和，二分。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
b[i] = a[i];
}
sort(b.begin() + 1, b.end());
vector<ll> s(n + 1);
for (int i = 1; i <= n; i++)
{
s[i] = s[i - 1] + b[i];
}
for (int i = 1; i <= n; i++)
{
auto idx = upper_bound(b.begin() + 1, b.end(), a[i]) - b.begin();
cout << s[n] - s[idx - 1] << ' ';
}
cout << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Tile Pattern
解题思路:
二维前缀和。
我们将\((a,b,c,d)\)进行拆分，拆成二维前缀和,\((a,b,c,d)=(1,1,c,d)-(1,1,c,b - 1)-(1,1,a - 1,d)+(1,1,a- 1,b- 1)\)。
计算每个以\((1,1)\)为左上角的矩形块，按上式计算即可。
如何计算一个矩形块？
如上图所示，
- 蓝色区域块为\(g[n][n] * (\frac{a}{n} * \frac{b}{n})\)。
- 绿色为\(g[n][a \% n] \times \frac{b}{n} + g[b \%n][n] \times \frac{a}{n}\)
- 黑色区域为\(g[b \%n][a\%n]\)。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
void solve()
{
ll n, q;
cin >> n >> q;
vector<vector<ll>> g(n + 10, vector<ll>(n + 10, 0));
for (int i = 1; i <= n; i++)
{
string s;
cin >> s;
s = ' ' + s;
for (int j = 1; j <= n; j++)
{
if (s[j] == 'B')
{
g[i][j] = 1;
}
g[i][j] = g[i][j] + g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
}
}
auto f = [&](ll a, ll b) -> ll
{
ll res = (a / n) * (b / n) * (ll)g[n][n];
res += g[n][b % n] * (ll)(a / n);
res += g[a % n][n] * (ll)(b / n);
res += g[a % n][b % n];
return res;
};
while (q--)
{
int a, b, c, d;
cin >> a >> b >> c >> d;
a++;
b++;
c++;
d++;
cout << f(c, d) - f(a - 1, d) - f(c, b - 1) + f(a - 1, b - 1) << endl;
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
E - Set Meal
解题思路:
如果我们直接遍历两两配对，一定会超时。
我们先对\(a,b\)数组升序排序。
如图：
首先，最大价钱的配对一定是右下角，就是\(a,b\)都取最大值相加。
通过简单画图可以发现，每个格子右下区域块一定都比当前区域要大。也就是说，最优解的右下区域块一定全部都是不可选块。
由此，我们可以遍历每个不可选块，比较他们的上面一块和左边一块，最优解一定在其中。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
void solve()
{
int n, m, l;
cin >> n >> m >> l;
vector<int> a(n + 1), b(m + 1);
vector<pii> da(n + 1), db(m + 1);
for (int i = 1; i <= n; i++)
{
cin >> a[i];
da[i] = {a[i], i};
}
for (int i = 1; i <= m; i++)
{
cin >> b[i];
db[i] = {b[i], i};
}
sort(da.begin() + 1, da.end());
sort(db.begin() + 1, db.end());
set<pii> s;
for (int i = 1; i <= l; i++)
{
int x, y;
cin >> x >> y;
s.insert({x, y});
}
ll ans = 0;
if (s.find({da[n].se, db[m].se}) == s.end())
{
cout << da[n].fi + db[m].fi << endl;
return;
}
for (auto t : s)
{
auto pa = lower_bound(da.begin() + 1, da.end(), (pii){a[t.fi], t.fi}) - da.begin();
auto pb = lower_bound(db.begin() + 1, db.end(), (pii){b[t.se], t.se}) - db.begin();
// cout << pa << ' ' << pb << endl;
if (pa > 1 && s.find({da[pa - 1].se, t.se}) == s.end())
{
ans = max(ans, da[pa - 1].fi + b[t.se]);
}
if (pb > 1 && s.find({t.fi, db[pb - 1].se}) == s.end())
{
ans = max(ans, a[t.fi] + db[pb - 1].fi);
}
}
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
F - Palindrome Query
解题思路:
线段树维护字符串前后哈希值。
结点元素有：区间左右端点，区间前缀哈希值\(pre\)，区间后缀哈希值\(suf\)。
\(pushup\):
\[\begin{align*} l.len &= l.r - l.l + 1\\ r.len &= r.r - r.l + 1\\ tr[u].pre &= l.pre \times hash[r.len] + r.pre \\ tr[u].suf &= r.suf \times hash[l.len] + l.suf. \end{align*} \]修改操作：就是单点修改。
查询操作：返回间前缀哈希值\(pre\)，区间后缀哈希值\(suf\)，合并过程中需要求取子区间长度，为了过程计算也要返回。
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<ll, ll> pii;
#define fi first
#define se second
const int mod = 1e9 + 7;
using ull = unsigned long long;
const ull base = 13331;
const int N = 1e6 + 10;
ull h[N];
int n, q;
string s;
struct node
{
ll l, r;
ull pre, suf;
} tr[4 * N];
void pushup(int u)
{
int mid = (tr[u].r - tr[u].l) >> 1;
int len1 = tr[u << 1].r - tr[u << 1].l + 1;
int len2 = tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1;
tr[u].pre = tr[u << 1].pre * h[len2] + tr[u << 1 | 1].pre;
tr[u].suf = tr[u << 1 | 1].suf * h[len1] + tr[u << 1].suf;
}
void build(int u, int l, int r)
{
tr[u].l = l;
tr[u].r = r;
if (l == r)
{
tr[u] = {l, r, s[l], s[l]};
return;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int idx, char c)
{
if (tr[u].l == tr[u].r)
{
tr[u].pre = tr[u].suf = c;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if (idx <= mid)
{
modify(u << 1, idx, c);
}
else
{
modify(u << 1 | 1, idx, c);
}
pushup(u);
}
array<ull, 3> query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r)
{
int len = tr[u].r - tr[u].l + 1;
return {tr[u].pre, tr[u].suf, len};
}
int mid = tr[u].l + tr[u].r >> 1;
if (r <= mid)
{
return query(u << 1, l, r);
}
if (l > mid)
{
return query(u << 1 | 1, l, r);
}
auto lv = query(u << 1, l, r);
auto rv = query(u << 1 | 1, l, r);
array<ull, 3> res;
res[0] = lv[0] * h[rv[2]] + rv[0];
res[1] = rv[1] * h[lv[2]] + lv[1];
res[2] = lv[2] + rv[2];
return res;
}
void solve()
{
cin >> n >> q >> s;
s = ' ' + s;
h[0] = 1;
for (int i = 1; i < N; i++)
{
h[i] = h[i - 1] * base;
}
build(1, 1, n);
while (q--)
{
int op;
cin >> op;
if (op == 1)
{
int idx = 0;
char str[2];
cin >> idx >> str;
modify(1, idx, *str);
}
else
{
int l, r;
cin >> l >> r;
array<ull, 3> t = query(1, l, r);
// cout << t[0] << ' ' << t[1] << endl;
if (t[0] == t[1])
{
puts("Yes");
}
else
{
puts("No");
}
}
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}