ABC374(A-G)
A - Takahashi san 2¶
题目大意
输入一个字符串 \(S\)，判断 \(S\) 是否以 san 结尾。
参考代码
#include <iostream>
using namespace std;
int main()
{
string s;
cin >> s;
int a = s.size() - 3;
if(s.substr(a, 3) == "san")
cout << "Yes";
else
cout << "No";
return 0;
}
B - Unvarnished Report¶
题目大意
给你两个字符串 \(S\) 和 \(T\)。如果这两个字符串相等，输出 0。否则输出第一个不相等的位置。
参考代码
#include <iostream>
using namespace std;
int main()
{
string s, t;
cin >> s >> t;
int k = min(s.size(), t.size());
for(int i = 0; i < k; i++)
{
if(s[i] != t[i])
{
cout << i + 1 << endl;
return 0;
}
}
if(s.size() == t.size())
cout << 0 << endl;
else
cout << k + 1 << endl;
return 0;
}
C - Separated Lunch¶
题目大意
给你 \(N(1 \le N \le 20)\) 个数字，第 \(i\) 个数字是 \(K_i\)。你需要将这些数字分成两组，每个数字可以任意分配在第一或者第二个小组。设两个小组的数字之和分别为 \(X\) 和 \(Y\)，且 \(T = \max(X,Y)\)，问：在所有可能的分配方案中，\(T\) 的最小值是多少？
解题思路
\(N \le 20\)，位运算直接枚举即可。
参考代码
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n;
cin >> n;
vector<LL> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
int len = 1 << n;
LL sum = accumulate(a.begin(), a.end(), 0);
LL ans = sum;
for(int s = 0; s < len; s++)
{
LL x = 0;
for(int i = 0; i < n; i++)
if(s >> i & 1)
x += a[i];
ans = min(ans, max(x, sum - x));
}
cout << ans << endl;
return 0;
}
D - Laser Marking¶
题目大意
在一个二维平面上，有一个机器可以描绘线段。你打算描绘 \(N(1 \le N \le 6)\) 条线段，每条线段用四元组 \((A_i, B_i, C_i, D_i)\) 来描述，表示由点 \((A_i, B_i)\) 和点 \((C_i, D_i)\) 连接而成的线段。
初始的时候，机器在 \((0, 0)\) 的位置。利用机器描绘线段的规则如下：
- 首先，将机器移动到线段的任意一个端点。在这一步移动的过程中，机器每秒可以移动 \(S\) 单位。
- 当机器到达线段的端点时，开始描绘线段，描绘线段会让机器从线段的一端移动到另一端。在这一步移动的过程中，机器每秒可以移动 \(T\) 单位。当机器到达另一端时，这条线段的描绘就完成了。注意：一旦决定描绘某条线段，就必须将其完整描绘，中途不能描绘其他线段。
某些线段可能存在重叠的部分，重叠的部分仍然需要多次描绘，不可忽略。
问：最少需要多少时间，才能描绘所有线段？
解题思路
\(N \le 6\)，用 \(O(N!)\) 枚举出线段之间的描绘顺序，\(O(2^N)\) 的时间确定每条线段从哪个点开始描绘，最后用 \(O(N)\) 的时间计算出每个情况的答案。总时间复杂度为 \(O(N!2^NN)\)
参考代码
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
long double cost(int x1, int y1, int x2, int y2, int s) { return sqrtl((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) / s; }
int main()
{
int n, s, t;
cin >> n >> s >> t;
int len = 1 << n;
vector<int> a(n), b(n), c(n), d(n);
vector<int> ord(n);
for (int i = 0; i < n; i++)
{
cin >> a[i] >> b[i] >> c[i] >> d[i];
ord[i] = i;
}
long double ans = numeric_limits<long double>::max();
do
{
for (int st = 0; st < len; st++)
{
long double sum = 0;
int x = 0, y = 0;
for (auto i : ord)
{
if (st >> i & 1)
{
sum += cost(x, y, a[i], b[i], s) + cost(a[i], b[i], c[i], d[i], t);
x = c[i];
y = d[i];
}
else
{
sum += cost(x, y, c[i], d[i], s) + cost(a[i], b[i], c[i], d[i], t);
x = a[i];
y = b[i];
}
}
ans = min(ans, sum);
}
} while (next_permutation(ord.begin(), ord.end()));
cout << setprecision(8) << ans << endl;
return 0;
}
E - Sensor Optimization Dilemma 2¶
题目大意
生产一件产品有 \(N(1 \le N \le 100)\) 道工序，每一道工序都会生产一些零件。每一道工序都需要购买一定数量的机器来完成生产，机器有两种类型，对于第 \(i\) 道工序而言，第一种类型的机器每台可生产 \(A_i(1 \le A_i \le 100)\) 个零件，售价为每台 \(P_i(1 \le P_i \le 10^7)\) 元。第二种类型的机器每台可生产 \(B_i(1 \le B_i \le 100)\) 个零件，售价为每台 \(Q_i(1 \le Q_i \le 10 ^7)\) 元。每道工序的机器不可用于其他工序中。你有 \(X(1 \le X \le 10 ^ 7)\) 元。你可以在所有工序中购买任意类型、任意数量的机器，也可以在同一种工序中混搭购买两种类型的机器。设第 \(i\) 道工序最终生产了 \(W_i\) 个零件，则最终能生产的产品数是 \(\min\limits_{i=1}^N W_i\)。问：最多能生产多少产品？
解题思路
显然是要二分答案，考虑怎么 check。注意到 \(1 \le A_i, B_i \le 100\)，设 \(L = \text{lcm}(A_i, B_i) \le 10000\)，则两台机器中性价比较低的类型在一道工序中至多使用 \(L\) 台，剩下的都是用性价比高的机器。这样总的时间复杂度就是 \(O(\log(A_{\max}X)NL)\) ，适当剪枝（预算不够提前 break）即可。
参考代码
#include <iostream>
#include <limits>
#include <numeric>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
LL n, x;
cin >> n >> x;
vector<LL> a(n), p(n), b(n), q(n), len(n);
for (int i = 0; i < n; i++)
{
cin >> a[i] >> p[i] >> b[i] >> q[i];
len[i] = lcm(a[i], b[i]);
if(q[i] / (double)b[i] < p[i] / (double)a[i])
{
swap(a[i], b[i]);
swap(p[i], q[i]);
}
}
LL l = 0, r = x * 100;
while (l < r)
{
LL mid = (l + r + 1) / 2;
LL sum = 0;
for (int i = 0; i < n && sum <= x; i++)
{
LL lim = min(len[i]/b[i]-1, (mid + b[i] - 1) / b[i]);
LL m = numeric_limits<LL>::max();
for(LL k = 0; k <= lim; k++)
m = min(m, k * q[i] + (mid - k * b[i] + a[i] - 1) / a[i] * p[i]);
sum += m;
}
if (sum <= x)
l = mid;
else
r = mid - 1;
}
cout << l << endl;
return 0;
}
F - Shipping¶
题目大意
有 \(N(1 \le N \le 100)\) 笔订单，第 \(i\) 笔订单会在第 \(T_i(1 \le T_1 \le T_2 \le \cdots \le T_N \le 10^{12})\) 天开始到达。你有一艘货船可以运送订单的货物，运送货物的规则如下：
- 货船最多装载 \(K(1 \le K \le N)\) 笔订单的货物同时发货。
- 第 \(i\) 笔订单的只能在第 \(T_i\) 天或之后开始发货，不能提前发货。
- 货船在出发之后需要 \(X(1 \le X \le 10^9)\) 天才会回来。换言之，如果你在第 \(a\) 天发货，需要在第 \(a+X\) 天才能发下一次货。
延迟发货会让买家的不满意，设某一笔订单的到达日期是 \(A\)，实际发货日期是 \(B\)，这笔订单的不满意度为 \(B-A\)。问：在所有订单发货之后，不满意度总和的最小值是多少？
解题思路
如果考虑 \(dp[i]\) 表示前 \(i\) 笔订单都发货且累计的不满意度的最小值，转移你会发现的时候因为不知道上一次发货的时间导致算不出来，所以需要新增一个状态。
如果用 \(dp[i][j]\) 表示前 \(i\) 笔订单都发货且将第 \(j+1\) 笔订单到第 \(i\) 笔订单打包一起发货累计的不满意度的最小值，这样也算不出来，因为货船延迟抵达会导致后续所有订单的发货时间都延迟，所以拿不到准确的发货时间。
正确的做法是在第二个维度中直接记录下每个订单发货出去后货船归来的时间，定义 \(dp[i][x]\) 表示前 \(i\) 笔订单都发货且发出订单 \(i\) 后货船归来时间为 \(x\) 的所有方案中累计的不满意度的最小值。
转移的时候，首先确定枚举第一个维度 \(i\)，转移的时候考虑到订单最多和之前的 \(K-1\) 个订单合并发货，所以遍历订单 \(i-K\) 到 \(i-1\) 的所有货船归来时间，这样可以确定出新的货船归来时间。由于时间的范围很大，但是实际的归来时间很稀疏，用哈希表存就可以了。
参考代码
#include <iostream>
#include <limits>
#include <unordered_map>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n, k, x;
cin >> n >> k >> x;
vector<LL> t(n + 1);
vector<LL> s(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> t[i];
s[i] = t[i] + s[i - 1];
}
vector<unordered_map<LL, LL>> dp(n + 1);
dp[0][-x] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = i - 1; j >= 0 && i - j <= k; j--)
{
for (auto [et, cost] : dp[j])
{
LL bt = max(et, t[i]);
LL next_et = bt + x;
LL sum = s[i] - s[j];
LL cnt = i - j;
LL next_cost = cnt * bt - sum + cost;
auto it = dp[i].find(next_et);
if (it == dp[i].end())
dp[i][next_et] = next_cost;
else
it->second = min(it->second, next_cost);
}
}
}
LL ans = numeric_limits<LL>::max();
for (auto [et, cost] : dp[n])
ans = min(ans, cost);
cout << ans << endl;
return 0;
}
G - Only One Product Name¶
题目大意
某公司的有 \(N(1 \le N \le 26^2)\) 个产品，第 \(i\) 个产品的名字是 \(S_i\)，其中 \(S_i\) 是一个长度为 \(2\) 且由大写字母构成的字符串。
这家公司不希望新产品的名字和原来的产品的名字冲突，因此决定构造一个列表。列表由若干个不限长度的字符串构成，其中：
- 每个字符串都由大写字母构成。
- 对于任意的 \(i\)，列表中至少存在一个字符串 \(T\)，使得 \(S_i\) 是 \(T\) 的子串。
- 对于 NG 列表中的任意一个字符串 \(T\) 的任意一个长度为 \(2\) 的子串 \(T'\)，都存在一个 \(i\)，使得 \(T' = S_i\)。
这个构造的列表的字符串数量应该越少越好，问：列表中至少有几个字符串？
解题思路
第三条规则要求我们字符串中任意的字串都是由产品名构成，且对于一个长度为 \(3\) 的子串 ABC，需要保证 AB 和 BC 都是产品名。于是可以想到将每一个产品视为点，根据 \(S_i\) 的结尾和开头连线。这样，列表中的每一个字符串就相当于是一条路径，根据条件二，我们需要覆盖每一个点，同时让路径的数量最少，这就是 P2764 最小路径覆盖问题 - 洛谷
不过这道题和模板题不太一样，还需要解决两个问题
-
模板题中每个点只能覆盖一次，但本题无此限制，可以重复的覆盖。假如有一些点形成了强连通分量，由于每个点可以被覆盖多次，进入一个环的时候可以把连通分量中的点都覆盖完。
- 这个缩点就可以了。
-
将重复覆盖转换成不可重复覆盖的情况。
- 可以发现，当一条路径重复的覆盖一个点，目的是为了访问其他更多的点。因此，我们做一次传递闭包，这样就相当于于越过了被重复覆盖的点，直接抵达目的地。
因为点的数量很少，做一次传递闭包时间复杂度也不过 \(O(N^6) \le 26^6\)，而且我们是先做缩点，再做传递闭包，实际的点数量会更少。
参考代码
#include <algorithm>
#include <cstring>
#include <iostream>
#include <limits>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
struct NetworkEdge
{
int to;
int cap;
int rev_idx;
};
int n, s, t;
vector<vector<NetworkEdge>> network_edge;
vector<int> cur;
vector<int> dep;
void add_network_edge(int u, int v, int c)
{
int iu = network_edge[u].size(), iv = network_edge[v].size();
network_edge[u].push_back({v, c, iv});
network_edge[v].push_back({u, 0, iu});
}
struct SccGraph
{
int n;
vector<vector<int>> edge;
vector<bool> inst;
vector<int> dfn, low, p;
stack<int> st;
int ti = 0, col = 0;
SccGraph(const vector<string> &s) : n(s.size()), edge(n), inst(n), dfn(n), low(n), p(n)
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
{
if (s[i][1] == s[j][0])
edge[i].push_back(j);
if (s[j][1] == s[i][0])
edge[j].push_back(i);
}
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ti;
st.push(u);
inst[u] = true;
for (auto v : edge[u])
{
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (inst[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
col++;
while (true)
{
int v = st.top();
st.pop();
inst[v] = false;
p[v] = col;
if (u == v)
break;
}
}
}
int prepare()
{
for (int u = 0; u < n; u++)
if (!dfn[u])
tarjan(u);
vector<vector<bool>> a(col + 1, vector<bool>(col + 1));
for (int u = 0; u < n; u++)
{
int pu = p[u];
for (auto v : edge[u])
{
int pv = p[v];
if (pu == pv)
continue;
a[pu][pv] = true;
}
}
for (int k = 1; k <= col; k++)
for (int u = 1; u <= col; u++)
for (int v = 1; v <= col; v++)
a[u][v] = a[u][v] || (a[u][k] && a[k][v]);
s = 0;
t = col + col + 1;
network_edge.resize(t + 1);
cur.resize(t + 1);
dep.resize(t + 1);
for (int u = 1; u <= col; u++)
{
add_network_edge(s, u, 1);
add_network_edge(u + col, t, 1);
}
for (int u = 1; u <= col; u++)
for (int v = 1; v <= col; v++)
{
if (u == v || !a[u][v])
continue;
add_network_edge(u, v + col, 1);
}
return col;
}
};
bool bfs()
{
fill(cur.begin(), cur.end(), 0);
fill(dep.begin(), dep.end(), 0);
queue<int> q;
q.push(s);
dep[s] = 1;
while (!q.empty())
{
int u = q.front();
q.pop();
for (const auto &e : network_edge[u])
{
int v = e.to;
if (e.cap && !dep[v])
{
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[t];
}
int dfs(int u, int in)
{
if (u == t)
return in;
int out = 0;
for (int &i = cur[u]; i < (int)network_edge[u].size(); i++)
{
auto &e = network_edge[u][i];
int v = e.to;
if (e.cap && dep[v] == dep[u] + 1)
{
int flow = dfs(v, min(e.cap, in));
auto &rev_e = network_edge[v][e.rev_idx];
in -= flow;
out += flow;
e.cap -= flow;
rev_e.cap += flow;
if (!in)
break;
}
}
return out;
}
int dinic()
{
int max_flow = 0;
while (bfs())
max_flow += dfs(s, numeric_limits<int>::max());
return max_flow;
}
int main()
{
cin >> n;
vector<string> str(n);
for (int i = 0; i < n; i++)
cin >> str[i];
SccGraph scc(str);
n = scc.prepare();
cout << n - dinic() << endl;
return 0;
}
创建日期: 2024-12-16