AtCoder Beginner Contest 332
A - Online Shopping
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
void solve()
{
int n, s, k;
cin >> n >> s >> k;
vector<int> v(n + 1);
ll m = 0;
for (int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
m += a * b;
}
if (m >= s)
{
cout << m << endl;
}
else
{
cout << m + k << endl;
}
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
B - Glass and Mug
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
void solve()
{
int k, g, m;
cin >> k >> g >> m;
int a = 0;
int b = 0;
for (int i = 1; i <= k; i++)
{
if (a == g)
{
a = 0;
}
else if (b == 0)
{
b = m;
}
else
{
int t = min(b, g - a);
a += t;
b -= t;
}
}
cout << a << ' ' << b << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
C - T-shirts
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
void solve()
{
int n, m;
cin >> n >> m;
string s;
cin >> s;
vector<int> cnt(5, 0);
ll ans = 0;
cnt[1] = m;
int i = 0;
for (auto c : s)
{
if (c == '0')
{
cnt[2] = 0;
cnt[1] = m;
}
else if (c == '1')
{
if (cnt[1] > 0)
{
cnt[1]--;
}
else
{
cnt[2]++;
}
}
else
{
cnt[2]++;
}
ans = max(ans, ((ll)cnt[2]));
// cout << (i++) << ' ' << abs(cnt[1]) + (ll)abs(cnt[2]) << endl;
}
ans = max(ans, ((ll)cnt[2]));
cout << ans << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
D - Swapping Puzzle
解题思路：
\(bfs\)搜索所有状态，遇到第一个和\(b\)一样的变换距离就是最短变换距离。没遇到就是无解。
所有状态数\(5! \times5! = 14400\)。
当然，也可以直接枚举所有状态，一一判断是否和\(b\)相等。变换距离为行列序号最终逆序对数量。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
void solve()
{
int n, m;
cin >> n >> m;
vector<vector<int>> a(n + 1, vector<int>(m + 1)), b(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> b[i][j];
}
}
map<vector<vector<int>>, int> d;
queue<vector<vector<int>>> q;
d[a] = 0;
q.push(a);
while (q.size())
{
auto t = q.front();
q.pop();
if (t == b)
{
cout << d[t] << endl;
return;
}
bool f = false;
for (int i = 1; i < n; i++)
{
// cout << i << endl;
auto r = t;
swap(r[i], r[i + 1]);
if (r == b)
{
cout << d[t] + 1 << endl;
return;
}
if (!d.count(r))
{
d[r] = d[t] + 1;
q.push(r);
}
}
for (int i = 1; i < m; i++)
{
// cout << i << endl;
auto r = t;
for (int j = 1; j <= n; j++)
{
swap(r[j][i], r[j][i + 1]);
}
if (r == b)
{
cout << d[t] + 1 << endl;
return;
}
if (!d.count(r))
{
d[r] = d[t] + 1;
q.push(r);
}
}
// cout << "dfsa" << endl;
}
cout << -1 << endl;
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
E - Lucky bag
解题思路:
数据很小，可贪心随机化。
遍历物品，再所有物品集，将当前的物品放入总和最小的物品集，如此分配。
建议看看状态压缩dp写法。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
typedef pair<ll, ll> pii;
void solve()
{
int n, d;
cin >> n >> d;
vector<int> w(n + 1);
double s = 0;
for (int i = 1; i <= n; i++)
{
cin >> w[i];
s += w[i];
}
double avg = s / d;
int t = 2000000;
double ans = 1e18;
while (t--)
{
int k = 1;
s = 0;
vector<int> b(d + 1, 0);
random_shuffle(w.begin() + 1, w.end());
for (int j = 1; j <= n; j++)
{
for (int i = 1; i <= d; i++)
{
if (b[i] < b[k])
{
k = i;
}
}
b[k] += w[j];
k = 1;
}
for (int i = 1; i <= d; i++)
{
s += (b[i] - avg) * (b[i] - avg);
}
s = s / d;
ans = min(1.0 * s, ans);
}
printf("%.15lf", ans);
}
int main()
{
int t = 1;
// cin >> t;
while (t--)
{
solve();
}
return 0;
}
F - Random Update Query
解题思路:
我们在\((l,r)\)中随机选取一个位置的概率为\(\frac{1}{r - l + 1}\)，修改后的值为\(x\)，所以该位置不变的概率为\(\frac{r-l}{r-l+1}\)。
所以，对于区间中每个位置的期望值影响为\(val = val \times \frac{r-l}{r-l + 1} + \frac{x}{r-l + 1}\)。
区间乘法和加法，懒标记线段树。
代码:
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 2e5 + 10;
const int Base = N / 2;
const int M = 2 * N;
const int P = 998244353;
typedef pair<int, int> PII;
typedef long long ll;
typedef long long LL;
int n, m;
ll w[N];
vector<int> primes;
const LL mod = 1e9 + 7;
unordered_map<char, int> q;
const int p = 998244353;
string s;
vector<double> ys;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
{
res = (res * a) % p;
}
b >>= 1;
a = (a * a) % p;
}
return res;
}
struct Node
{
int l, r;
LL sum, add, mul;
} tr[N * 4];
void pushup(int u)
{
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum % p;
}
void eval(Node &u, LL add, LL mul)
{
u.sum = (u.sum * mul % p + ((LL)add * (u.r - u.l + 1))) % p;
u.mul = u.mul * mul % p;
u.add = ((u.add * mul % p) + add) % p;
}
void pushdown(int u)
{
eval(tr[u << 1], tr[u].add, tr[u].mul);
eval(tr[u << 1 | 1], tr[u].add, tr[u].mul);
tr[u].add = 0;
tr[u].mul = 1;
}
void build(int u, int l, int r)
{
if (l == r)
{
tr[u] = {l, r, w[r], 0, 1};
return;
}
tr[u] = {l, r, 0, 0, 1}; // 这道题记得初始化mul = 1
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void modify(int u, int l, int r, LL add, LL mul)
{
if (tr[u].l >= l && tr[u].r <= r)
{
eval(tr[u], add, mul);
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid)
{
modify(u << 1, l, r, add, mul);
}
if (r > mid)
{
modify(u << 1 | 1, l, r, add, mul);
}
pushup(u);
}
LL query(int u, int l, int r)
{
if (tr[u].l >= l && tr[u].r <= r) // 这里条件写错了
{
return tr[u].sum;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
LL res = 0;
if (l <= mid)
{
res = query(u << 1, l, r);
}
if (r > mid)
{
res = (res + query(u << 1 | 1, l, r)) % p;
}
return res;
}
void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> w[i];
}
build(1, 1, n);
// cout << 1 << endl;
for (int i = 1; i <= m; i++)
{
ll l, r, x;
cin >> l >> r >> x;
ll len = r - l + 1;
modify(1, l, r, (x * qmi(len, p - 2)) % p, (len - 1) * qmi(len, p - 2) % p);
// cout << (x * qmi(len, mod - 2)) % mod << ' ' << (len - 1) * qmi(len, mod - 2) % mod << endl;
}
for (int i = 1; i <= n; i++)
{
cout << query(1, i, i) << ' ';
}
}
int main()
{
int t;
// init(N);
t = 1;
while (t--)
{
solve();
}
return 0;
}