企业网站推广的线上渠道_adobe dreamweaver官网_百度爱采购怎么优化排名_百度指数工具

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 { // Pointdb 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$, 然后计算每天的开销.

每天的部分考虑背包, 可以发现对容量 $2\ast \text{lcm}(a[i],b[i])$ 肯定只选性价比高的好.
所以我们可以考虑剩一个 $[\text{lcm}(a[i],b[i]),2[\text{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\ast x(j\in [0,n))$.
总共有 $n^2$ 个关键点.

考虑 DP, $f[i][j]$ 表示第 $i$ 个关键点时,已经让 $j$ 部船靠岸的最小靠岸时间和.

显然有 $f[i][j]\leftarrow f[i-1][j]$ 的转移.
再根据题目驳船要间隔时间 $x$ 的要求, 我们可以求一个最大的时刻 $p$ (单调指针), 满足关键点$i,p$ 间的间隔 $\ge 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

将一个词组 $\text{XY}$ 看作一条边 $(x,y)$.
这时候题意可以转化为 用最少的链(可重复地)覆盖所有边.

需要注意的是图可能有环. 这样就不能直接用DAG上的经典可重链覆盖套路.

把一条链看作一个流, 那么只有起点终点有流量变化. (一个流会贡献 $-1,+1$的流量变化给两点) 我们对图作一个传递闭包, 记 $flow(x)$ 为 流入的流量-流出的流量,则直观的答案就是 $\frac{\sum |flow(x)|}{2}$.
然后对于可达的点对 $(x,y)(\text{i.e. y can be accessed by x})$, 可以令 $flow(x)-=1,flow(y)+=1$.
此时, 若 $flow(x)>0,flow(y)<0$ 则合式可以变小.

Note: 一个连通块至少需要一条链, 故每个连通块的答案应该纠正为 $\max (1,\frac{\sum |flow(x)|}{2})$. (不然遇到 $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;
}