2021牛客寒假算法基础集训营6 题解
sdxjzsq
2021-04-02 22:03:58
## 碎碎念
昨天老板找我交代了担任ACM校队总队长的事情，在感到荣誉的同时，我也感受到了身上肩负的责任与面临的压力——南邮ACM校队的总队长已经连续五年是金牌了，然而我目前却连个牌子都没有（留下了铁首的眼泪.jpg）。为了让历史延续下去，抱大腿是不行的，必须好好提升自身的能力。
## A,C,D,I
水题不写了。
## J-天空之城
开始看到这题还以为要缩点啥的，后来发现路重复走只计算一次贡献，那不就是最小生成树吗？结果因为最近写代码太少，被多测卡了好久，一度怀疑人生...
代码：
``` cpp
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <string>
using namespace std;
const int maxn = 5e3 + 7;
int n, q, top, fa[maxn];
long long ans;
string s;
struct node
{
int val;
string x, y;
bool operator<(const node &rhs) const { return val > rhs.val; }
};
priority_queue<node> Q;
map<string, int> M;
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y, int val)
{
x = find(x), y = find(y);
if (x == y) return;
fa[x] = y;
n--;
ans += val;
}
int main()
{
while (~scanf("%d%d", &n, &q))
{
cin >> s;
M.clear();
ans = top = 0;
for (int i = 1; i <= n; ++i) fa[i] = i;
string a, b;
for (int val; q--;) cin >> a >> b >> val, Q.push((node){val, a, b});
while (!Q.empty())
{
node x = Q.top();
Q.pop();
if (!M.count(x.x)) M[x.x] = ++top;
if (!M.count(x.y)) M[x.y] = ++top;
merge(M[x.x], M[x.y], x.val);
}
if (n > 1)
puts("No!");
else
printf("%lld\n", ans);
}
}
```
## G-机器人
这题乍一看，不就是个贪心水题吗？
根据贪心的证明来得到排序规则：
假设答案第 $i$ 和第 $j$ 个机器前后相邻，属性分别为$a_i,b_i,a_j,b_j$，那么将他们俩的顺序交换应该会使答案变小，可得：
$$
\begin{aligned}
a_j\times (a_i\times x+b_i)+b_j&>a_i\times (a_j\times x+b_j)+b_i\\
a_ia_jx+a_jb_i+b_j&>a_ia_jx+a_ib_j+b_i\\
(a_j-1)\times b_i&>(a_i-1)\times b_j
\end{aligned}
$$
得到排序条件 $(a_j-1)\times b_i>(a_i-1)\times b_j$。
结果写完发现 $n$ 竟然只有 $20$，一度怀疑是不是没那么简单，又写了一下最终结果的式子：
$$
ans = \prod_{i=1}^n{a_i\cdot x}+\sum_{i=1}^n\left(\prod_{j=i_1}^na_j\right)\cdot b_i
$$
简单证明发现确实是贪心...
然后意识到原来 $n=20$ 是考虑到了高精度的速度（不过100也跑的出来吧？），套个高精度板子即可：
``` cpp
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100;
int n, x;
struct node
{
int a, b;
bool operator<(const node &rhs) const { return (a - 1) * rhs.b < (rhs.a - 1) * b; }
} r[maxn];
struct hll
{
int v[maxn], len;
hll()
{
v[1] = 0; // memset(v,0,sizeof(v));
len = 1;
}
hll(char *ss) { *this = ss; }
hll(long long t) { *this = t; }
hll(int t) { *this = t; }
hll &operator=(const char *ss)
{
len = strlen(ss);
for (int i = 0; i < len; i++) v[len - i] = ss[i] - 48;
return *this;
}
hll &operator=(const long long &t)
{
len = 1;
if (t == 0)
{
v[len] = 0;
return *this;
}
long long ss = t;
while (ss)
{
v[len++] = ss % 10;
ss /= 10;
}
len--;
return *this;
}
hll &operator=(const int &t)
{
len = 1;
if (t == 0)
{
v[len] = 0;
return *this;
}
int ss = t;
while (ss)
{
v[len++] = ss % 10;
ss /= 10;
}
len--;
return *this;
}
hll &operator=(const hll &t)
{
len = t.len;
for (int i = 1; i <= len; i++) v[i] = t.v[i];
return *this;
}
inline bool operator==(const hll &t)
{
if (t.len > len || len > t.len) return 0;
for (int i = 1; i <= len; i++)
if (v[i] != t.v[i]) return 0;
return 1;
}
inline bool operator<(const hll &rhs) const
{
if (rhs.len > len) return 1;
if (rhs.len < len) return 0;
for (int i = len; i > 0; i--)
{
if (v[i] < rhs.v[i]) return 1;
if (v[i] > rhs.v[i]) return 0;
}
return 0;
}
hll operator+(const hll &t)
{
hll ans;
ans.len = max(t.len, len);
for (int i = 1; i <= ans.len + 1; i++) ans.v[i] = 0;
for (int i = 1; i <= ans.len; i++)
{
if (i <= len && i <= t.len)
ans.v[i] += v[i] + t.v[i];
else if (i > len)
ans.v[i] += t.v[i];
else
ans.v[i] += v[i];
if (ans.v[i] >= 10) ans.v[i + 1]++, ans.v[i] -= 10;
}
if (ans.v[ans.len + 1]) ans.len++;
return ans;
}
hll operator*(const hll &t)
{
hll ans;
ans.len = len + t.len;
for (int i = 1; i <= ans.len; i++) ans.v[i] = 0;
for (int i = 1; i <= len; i++)
for (int j = 1; j <= t.len; j++)
{
ans.v[i + j - 1] += v[i] * t.v[j];
if (ans.v[i + j - 1] >= 10)
{
ans.v[i + j] += ans.v[i + j - 1] / 10;
ans.v[i + j - 1] %= 10;
}
}
while (ans.v[ans.len] >= 10) ans.v[ans.len + 1] = ans.v[ans.len] / 10, ans.v[ans.len] %= 10, ans.len++;
while (ans.v[ans.len] == 0 && ans.len > 1) ans.len--;
return ans;
}
hll operator/(const long long &t)
{
hll tmp = *this, ans;
ans.len = len;
for (int i = 1; i <= ans.len; i++) ans.v[i] = 0;
for (int i = len; i > 0; i--)
{
if (tmp.v[i] < t)
tmp.v[i - 1] += (tmp.v[i] << 1) + (tmp.v[i] << 3);
else
{
ans.v[i] = tmp.v[i] / t;
tmp.v[i] %= t;
tmp.v[i - 1] += (tmp.v[i] << 1) + (tmp.v[i] << 3);
}
}
while (ans.v[ans.len] == 0 && ans.len > 1) ans.len--;
return ans;
}
inline void print()
{
for (int i = len; i > 0; i--) putchar(v[i] + 48);
}
} ans;
int main()
{
scanf("%d%d", &n, &x);
for (int i = 1; i <= n; ++i) scanf("%d%d", &r[i].a, &r[i].b);
ans = x;
sort(r + 1, r + n + 1);
for (int i = 1; i <= n; ++i) ans = ((hll)r[i].a) * ans + (hll)r[i].b;
ans.print();
return 0;
}
```
## F-组合数问题
这题就比较妙妙了，证明用到了复数，技巧性很强。