前言
考试的时候只需要管考试的策略就行了, 其他的想他干嘛
看题
一般来说, 涨信心模拟赛都不会涨信心
像一位故人出的题?
\(\rm{T1}\) 相信自己, 冲一下
\(\rm{T2}\) 看不懂
\(\rm{T3}\) 博弈
\(\rm{T4}\) 困难
\(\rm{T1}\)
机房两青轴是真的蚌埠
思路
转化题意,
对于 \(N\) 条线段, 我们需要对每条线段选择一段长为 \(t_i\) 的部分, 一个选择的代价定义为, 对于 \(N - 1\) 条关系 \((A_i, B_i, C_i)\) , 如果 \(A_i, B_i\) 选择的部分重合了 \(x\) , 那么就会产生 \(f = C_i \cdot x\) 大小的贡献
首先一个很明确的性质是, 关系是一棵树, 怎么利用?
先考虑链上的情况, 也就是说每个人最多涉及到两个会产生代价的点
好吧, 链上的也不好做, 先考虑一下菊花图, 是好做的, 我们只需要枚举一下 \(1\) 点的情况, 然后其他点尽力避开即可
先跳一下, 暴力都不会了
实现
\(10 \rm{pts}\)
菊花的 \(10 \rm{pts}\)
框架
先枚举 \(1\) 点的所有情况, 标记之后对于每个点, 贪心选择最优情况即可
代码
class SolveSubtask4 {
private:
/*计算区间的重合大小*/
int Calc(int l, int r, int nowl, int nowr) {
int Left = std::max(l, nowl), Right = std::min(r, nowr);
return std::max(Right - Left + 1, 0);
}
public:
void solve()
{
int Ans = 0x3f3f3f3f;
/*外层枚举 1 点的选择情况*/
for (int l = Pep[1].l; l <= Pep[1].r - Pep[1].t + 1; l++) {
int r = l + Pep[1].t - 1;
int nowans = 0;
/*内层尽量避开*/
for (int j = head[1]; ~j; j = Edge[j].next) {
int i = Edge[j].to, C = Edge[j].w;
int MinCost = 0x3f3f3f3f;
for (int nowl = Pep[i].l; nowl <= Pep[i].r - Pep[i].t + 1; nowl++) {
int nowr = nowl + Pep[i].t - 1;
MinCost = std::min(MinCost, Calc(l, r, nowl, nowr));
}
nowans += MinCost * C;
}
Ans = std::min(Ans, nowans);
}
printf("%d", Ans);
}
} Sub4;
\(\rm{T2}\)
思路
已经有形式化题意了, 就不在这里重复
注意到如果要使得成为完全立方数, 一定要求满足 \({S^{\prime}}_i = \sum_j {T_j}^{3x}\)
一个初步的思路是, 对于每种质因数, 我们记录这个数需要的幂次, 然后最后统计怎么给幂次最优秀, 每次询问的复杂度是 \(\mathcal{O} (nM + 3^M)\)
考虑如何优化
插入和删除我们可以用 \(\rm{hash}\) 实现, 但是怎么做才能优化掉 \(3 ^ M\) 这个东西?
好像确实不会了, 但是想完整再说
注意到每个数相当于要求了一些约束条件, 如果都满足了才加入贡献
好吧不会
实现
\(20 \rm{pts}\)
框架
按照上面写的模拟即可
代码
class SolveSubtask1
{
private:
std::map<int, int> Set;
int pows[20][20]; // 需要的次幂
bool vis[20][20]; // 是否需要
int give[20];
int Ans = 0, AnsX = -1;
/*统计怎么给幂次最优秀*/
void dfs(int now) {
if (now > M + 1) return;
/*统计答案*/
if (now == M + 1) {
int NOW = 0;
int nowans = 0;
for (auto i : Set) {
NOW++; int Num = i.first;
bool flag = true;
for (int j = 1; j <= M; j++) {
if (!vis[NOW][j])
if (give[j] != 0) {
flag = false;
break;
}
if (give[j] != pows[NOW][j]) {
flag = false;
break;
}
}
if (flag) nowans += i.second;
}
int nowx = 1;
for (int i = 1; i <= M; i++) { for (int j = 1; j <= give[i]; j++) nowx *= Prime[i]; }
if (nowans > Ans) Ans = nowans, AnsX = nowx;
return;
}
for (int i = 0; i < 3; i++) {
give[now] = i;
dfs(now + 1);
}
}
public:
void solve()
{
while (Q--)
{
int op; scanf("%lld", &op);
if (op == 1) {
int New; scanf("%lld", &New);
Set[New]++;
}
if (op == 2) {
int Sub; scanf("%lld", &Sub);
Set[Sub]--;
}
if (op == 3)
{
Ans = 0, AnsX = -1;
int NOW = 0;
/*记录每个数所需要的幂次*/
for (auto i : Set) {
NOW++; int Num = i.first;
for (int j = 1; j <= M; j++) {
pows[NOW][j] = 0;
vis[NOW][j] = !(Num % Prime[j]);
while (!(Num % Prime[j])) {
pows[NOW][j]++;
Num /= Prime[j];
}
pows[NOW][j] = (3 - (pows[NOW][j] % 3)) % 3;
}
}
dfs(1);
printf("%lld\n", AnsX);
}
}
}
} Sub1;
\(\rm{T3}\)
思路
时间比较紧张, 看下题吧, 多半拿不到分了
今天暴力调太久了, 还是要练, 正解想不出来也是不行的
先考虑不加边的时候怎么判断先后手谁赢
先手只能在奇数层做改变, 后手只能在偶数层做改变
那么只要存在一条链, 使得在偶数层上, 这条脸上的点只能选择向这条链里面走