ABC374

A

字符串是否有san后缀

B

两个字符串第一个不同的位置

C

将一个数组分为两部分，求不同分法中更大那一部分和的最小值。

D

给定一些线段，机器从(0,0)点开始移动，画线段时的速度为S，不画时的移动速度为T
求机器画完所有线段的最短时间

E

N道工序，每道工序有两部分机器组成，你可以选任意个机器去制造零件
第一部分：每个机器制造A个零件，每个零件需要P元
第二部分：每个机器制造B个零件，每个零件需要Q元
设每道工序最后的零件数为$w_i$
给一个公式W=$\min w_i$，在总的预算X约束下
求最大的W

---

设$x_{1i}$为第i个工序的第一部分机器数量，$x_{2i}$为第二部分机器数量
给定约束$A_i{x}_{1i}{P}_i+B_i{x}_{2i}{Q}_i\le X$
求 m a x { min ⁡ ( A i x 1 i + B i x 2 i ) } max\left\{\min (A_ix_{1i}+B_ix_{2i}) \right \} max{min(Ai​x1i​+Bi​x2i​)}

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;struct Mach {ll a, p, b, q;
} m[101];
int n;
ll x;ll get(ll v) {ll ret = 0;for (int i = 1; i <= n; ++i) {auto [a, p, b, q] = m[i];if (b * p < a * q) {swap(a, b);swap(p, q);}ll t = v / b;ll y; if (v % b) t++;y = q * t;if (v % b) {for (int j = 1; j <= min(2000, int(t)); ++j) {ll lft = v - b * (t - j);ll t0 = lft / a;if (lft % a) t0++;ll z = q * (t - j) + p * t0;y = min(y, z);}}ret += y;}return ret <= x;
}int main(){//freopen("in.txt", "r", stdin);cin >> n >> x;for (int i = 1; i <= n; ++i) {int a, p, b, q;cin >> a >> p >> b >> q;m[i] = { a, p, b, q };}ll lo = 1, hi = 1e10;//get(4);if (!get(1)) {printf("0\n");return 0;}while (lo <= hi) {ll mi = (lo + hi) / 2;bool rt = get(mi);if (rt) {lo = mi + 1;}else {hi = mi - 1;}}if (get(hi)) lo = hi;printf("%lld\n", lo);return 0;
}

F

需要运送n个货物，每个货物的运送时间都不能在$t_i$前($\ge t_i$)
每一天可以运送K个货物，
对于天数D，每个货物的代价是$x_i-D$
求代价和的最小值

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <algorithm>using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;int n, K;
ll x;
ll t[110];
ll a[10200];
ll s[110];
map<ll, int> idx;
int m;
ll f[10200][110];
ll mn[10200][110];int main(){//freopen("in.txt", "r", stdin);cin >> n >> K >> x;for (int i = 1; i <= n; ++i) {cin >> t[i];s[i] = s[i - 1] + t[i];}set<ll> can;for (int i = 1; i <= n; ++i) {for (int j = 0; j <= n; ++j) {can.insert(t[i] + x * j);}}int i = 0;ll bg = -ll(1e16);idx[bg] = i;a[i++] = bg;for (auto it = can.begin(); it != can.end(); ++it) {idx[*it] = i;a[i] = *it;i++;}m = idx.size();memset(f, 0x3f, sizeof(f));memset(mn, 0x3f, sizeof(mn));f[0][0] = 0;mn[0][0] = 0;ll ans = f[0][n];for (int i = 1; i <= m; ++i) {int pre = upper_bound(a, a + m + 1, a[i] - x) - a - 1;mn[i][0] = min(f[i][0], mn[i - 1][0]);for (int j = 1; j <= n; ++j) {//f[i][j] = min(f[i][j], f[i - 1][j]);if (a[i] >= t[j]) {for (int k = 0; k < j; ++k) {if (j - k <= K) {ll val = a[i] * (j - k) - (s[j] - s[k]);f[i][j] = min(f[i][j], mn[pre][k] + val);}}}mn[i][j] = min(f[i][j], mn[i - 1][j]);if (j == n) {ans = min(f[i][j], ans);}}}printf("%lld\n", ans);return 0;
}