AtCoder Beginner Contest 374 Solution
A
void solve() {
string s;
qr(s);
Yes(s.substr(s.size() - 3) == "san");
}
B
void solve() {
string s, t;
qr(s, t);
if(s == t) return pr2(0);
int p = 0;
while(p < SZ(s) && p < SZ(t) && s[p] == t[p]) p++;
pr2(p + 1);
}
C
const int N = 22, inf = 0x3f3f3f3f;
const ll INF = 4E18;
int n, m, a[N], s, ans;
void dfs(int i, int v) {
if(v > s / 2) return;
if(i == n + 1) {
cmin(ans, s - v);
return;
}
dfs(i + 1, v + a[i]);
dfs(i + 1, v);
}
void solve() {
qr(n);
FOR(i, n) qr(a[i]), s += a[i];
ans = s;
dfs(1, 0);
pr2(ans);
}
D
const int N = 22, inf = 0x3f3f3f3f;
const ll INF = 4E18;
int n, m;
struct P { // Point
db x, y;
P(db x = 0, db y = 0):x(x),y(y){}
P operator +(P b) const {return P(x + b.x, y + b.y);}
P operator -(P b) const {return P(x - b.x, y - b.y);}
P operator *(db t) const {return P(x * t, y * t);} // 数乘
P operator /(db t) const {return P(x / t, y / t);}
friend db dot(P a, P b) {return a.x * b.x + a.y * b.y;}//点乘
db operator *(P b) const {return x * b.y - y * b.x;} // 叉积
db len() {return hypotl(x, y);} //求模长
friend db dis(P a, P b) {return (a - b).len();} // 两点距离
friend P normal(P a) {return P(-a.y, a.x);} //法向量(逆时针旋转90度)
friend P unit(P a) {return a / a.len();} //单位化
friend db angle(P a, P b) {return atan2(b.y - a.y, b.x - a.x); } // b -> a 的极角
friend db area(P a, P b, P c) {return fabs((c - a) * (b - a)) / 2;} // 三角形面积
P turn(db t) { //顺时针旋转 t(theta)(弧度)
return P(x * cos(-t) + y * sin(t), x * sin(-t) + y * cos(t));
}
P Turn(P b, db t) {// 绕b点顺时针旋转 t(theta)(弧度)
P c = *this - b;
return c.turn(t) + b;
}
void in() {qr(x, y);}
} p[N];
db f[1 << 6][12], d[6];
void solve() {
int s, t;
qr(n, s, t);
memset(f, 0x7f, sizeof f);
FOR(i, 2 * n) {
p[i - 1].in();
f[0][i - 1] = dis(P(), p[i - 1]) / s;
}
rep(i, 0, n - 1) d[i] = dis(p[i * 2], p[i * 2 + 1]) / t;
int S = (1 << n) - 1;
rep(u, 0, S - 1) {
rep(i, 0, 2 * n - 1)
if(f[u][i] <= inf) {
int o = i / 2;
if(u >> o & 1) continue;
db val = f[u][i] + d[o];
int _u = u + (1 << o);
rep(j, 0, 2 * n - 1)
cmin(f[_u][j], val + dis(p[i ^ 1], p[j]) / s);
}
}
cout << *min_element(f[S], f[S] + 2 * n) << endl;
}
E
二分 W W W, 然后计算每天的开销.
每天的部分考虑背包, 可以发现对容量
2
∗
lcm
(
a
[
i
]
,
b
[
i
]
)
2*\text{lcm}(a[i], b[i])
2∗lcm(a[i],b[i]) 肯定只选性价比高的好.
所以我们可以考虑剩一个
[
lcm
(
a
[
i
]
,
b
[
i
]
)
,
2
[
lcm
(
a
[
i
]
,
b
[
i
]
)
]
[\text{lcm}(a[i], b[i]), 2[\text{lcm}(a[i], b[i])]
[lcm(a[i],b[i]),2[lcm(a[i],b[i])] 的容量, 这一部分暴力背包即可.
const int N = 110, inf = 0x3f3f3f3f;
const ll INF = 4E18;
int n, sz[N];
ll m, f[N][N * N * 2];
pii a[N], b[N];
void add(int i, int x, int y) {
int w = sz[i] * 2;
rep(j, 0, w - x)
cmin(f[i][j + x], f[i][j] + y);
REP(j, 2, w) cmin(f[i][j - 1], f[i][j]);
}
ll ask(int i, ll x) {
if(x <= sz[i]) return f[i][x];
return (x / sz[i] - 1) * (sz[i] / a[i].fi) * a[i].se + f[i][x % sz[i] + sz[i]];
}
bool check(ll x) {
ll r = m;
FOR(i, n) {
r -= ask(i, x);
if(r < 0) return 0;
}
return 1;
}
void solve() {
qr(n, m);
FOR(i, n) qr(a[i], b[i]);
memset(f, 63, sizeof f);
FOR(i, n) {
sz[i] = a[i].fi * b[i].fi;
if(a[i].se * b[i].fi > b[i].se * a[i].fi) swap(a[i], b[i]);
// a更实惠
f[i][0] = 0;
add(i, a[i].fi, a[i].se);
add(i, b[i].fi, b[i].se);
}
int l = 0, r = m * 100 / n, mid;
while(l < r) {
mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
pr2(l);
}
F
值域过大,需要离散化,可以发现关键点只有
a
[
i
]
+
j
∗
x
(
j
∈
[
0
,
n
)
)
a[i] + j*x(j\in [0, n))
a[i]+j∗x(j∈[0,n)).
总共有
n
2
n^2
n2 个关键点.
考虑 DP, f [ i ] [ j ] f[i][j] f[i][j] 表示第 i i i 个关键点时,已经让 j j j 部船靠岸的最小靠岸时间和.
显然有
f
[
i
]
[
j
]
←
f
[
i
−
1
]
[
j
]
f[i][j] \leftarrow f[i - 1][j]
f[i][j]←f[i−1][j] 的转移.
再根据题目驳船要间隔时间
x
x
x 的要求, 我们可以求一个最大的时刻
p
p
p (单调指针), 满足关键点
i
,
p
i,p
i,p 间的间隔
≥
x
\ge x
≥x. 然后再贪心地让尽量多的船靠岸即可.
const int N = 1e4 + 10, inf = 0x3f3f3f3f;
const ll INF = 3E18;
int n, k, x, tot;
ll a[N], s[N], f[N][110];
void solve() {
qr(n, k, x);
map<ll, int> cnt;
ll ans = 0;
int t = n;
FOR(i, n) {
qr(a[i]);
cnt[a[i]]++;
ans -= a[i];
for(ll j = 1; j < t; j++)
cnt[a[i] + j * x];
}
for(auto [x, y]: cnt) {
s[tot + 1] = s[tot] + y;
a[++tot] = x;
}
a[0] = -x;
memset(f[0], 63, sizeof f[0]);
f[0][0] = 0;
int p = 0;
ll mn = f[0][1];
FOR(i, tot) {
rep(j, 0, n) f[i][j] = f[i - 1][j];
while(p + 1 < i && a[i] - a[p + 1] >= x) p++;
rep(j, 0, s[p]) if(f[p][j] <= INF) {
int r = s[i] - j;
cmin(f[i][j + min(k, r)], f[p][j] + min(k, r) * a[i]);
}
cmin(mn, f[i][n]);
}
pr2(ans + mn);
}
G
将一个词组
XY
\text{XY}
XY 看作一条边
(
x
,
y
)
(x,y)
(x,y).
这时候题意可以转化为 用最少的链(可重复地)覆盖所有边.
需要注意的是图可能有环. 这样就不能直接用DAG上的经典可重链覆盖套路.
把一条链看作一个流, 那么只有起点终点有流量变化. (一个流会贡献
−
1
,
+
1
-1,+1
−1,+1的流量变化给两点) 我们对图作一个传递闭包, 记
f
l
o
w
(
x
)
flow(x)
flow(x) 为 流入的流量-流出的流量,则直观的答案就是
∑
∣
f
l
o
w
(
x
)
∣
2
\dfrac {\sum |flow(x)|}{2}
2∑∣flow(x)∣.
然后对于可达的点对
(
x
,
y
)
(
i.e. y can be accessed by x
)
(x,y) (\text{i.e. y ~ can ~be accessed~by ~x})
(x,y)(i.e. y can be accessed by x), 可以令
f
l
o
w
(
x
)
−
=
1
,
f
l
o
w
(
y
)
+
=
1
flow(x)-=1, flow(y)+=1
flow(x)−=1,flow(y)+=1.
此时, 若
f
l
o
w
(
x
)
>
0
,
f
l
o
w
(
y
)
<
0
flow(x) > 0, flow(y) < 0
flow(x)>0,flow(y)<0 则合式可以变小.
Note: 一个连通块至少需要一条链, 故每个连通块的答案应该纠正为 max ( 1 , ∑ ∣ f l o w ( x ) ∣ 2 ) \max(1, \dfrac {\sum |flow(x)|}{2}) max(1,2∑∣flow(x)∣). (不然遇到 A B , B A AB,BA AB,BA 可能会出错.)
#include <bits/stdc++.h>
#define VT vector
#define all(a) (a).begin(), (a).end()
#define rep(i, a, b) for (int i = a, i##_ = b; i <= i##_; i++)
#define FOR(i, n) rep(i, 1, n)
using namespace std;
void qr(auto& x) {cin >> x;}
const int N = 28;
int n, m, deg[N];
bool exist[N];
bitset<N> E[N];
struct DSU {
VT<int> fa, sz;
DSU(int n): fa(n + 1), sz(n + 1, 1) {iota(all(fa), 0);}
void init(int n) {fa.resize(n + 1); iota(all(fa), 0); sz.assign(n + 1, 1);}
int get(int x) {return fa[x] == x? x: fa[x] = get(fa[x]);}
bool unite(int x, int y) {
x = get(x); y = get(y);
if(x == y) return 0;
if(sz[x] < sz[y]) swap(x,y);
fa[y] = x; sz[x] += sz[y]; return 1;
}
bool same(int x, int y) {return get(x) == get(y);}
~DSU() {fa.clear(); sz.clear();}
};
void solve() {
qr(m);
n = 25;
string s;
DSU b(n);
while(m--) {
qr(s);
for(auto &c: s) c -= 'A', exist[c] = 1;
E[s[0]][s[1]] = 1;
deg[s[0]]--;
deg[s[1]]++;
b.unite(s[0], s[1]);
}
rep(k, 0, n) rep(i, 0, n) if(E[i][k]) E[i] |= E[k]; // 传递闭包
rep(i, 0, n) rep(j, 0, n) if(E[i][j]) {
while(deg[i] > 0 && deg[j] < 0)
deg[i]--, deg[j]++;
}
int ans = 0;
rep(i, 0, n) if(b.get(i) == i && exist[i]) {
int c = 0;
rep(j, 0, n) if(b.same(i, j)) c += abs(deg[j]);
ans += max(c / 2, 1);
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(15);
solve();
return 0;
}
原文地址:https://blog.csdn.net/qq_42886072/article/details/142720280
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!