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;
}
- Beginner AtCoder Contest 332beginner atcoder contest 332 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 328 beginner atcoder contest 310 beginner atcoder contest 315