|
|
A. Polycarp and the Day of Pi 签到
题意：
求出一个数字的前几位和 \pi 相同。
分析：
最后一个样例就是 \pi ，直接抄过来，扫一遍。
代码：
string pi = "314159265358979323846264338327";
void solve()
{
string s;
cin >> s;
int ans = 0;
for (int i = 0; s; i++ ) {
if (s != pi) break;
else ans++ ;
}
cout << ans << endl;
}
B. Taisia and Dice 构造
题意：
已知道所有骰子的数量，骰子的点数总和，以及拿走一个最大值的点数总和，请构造所有骰子的点数。
分析:
可以推算出最大值，那么构造方法就是一直用最大值来构造，剩下的用 1 来弥补。
代码：
void solve()
{
cin >> n >> s >> r;
int mx = s - r;
while (s > 0 && n > 0 && s >= n) {
if (s - mx >= n) cout << mx << &#34; &#34;, s -= mx;
else cout << s - n + 1 << &#34; &#34;, s -= (s - n + 1);
n-- ;
}
for (int i = 1; i <= n; i++ ) cout << 1 << &#34; &#34;;
cout << endl;
}
C. Premutation
题意：
一个长度为 n 的排列，将 n 个这样的排列每个去掉一位然后打乱。根据打乱后的排列求出原排列。
分析：
分析很简单，但是代码写了一坨大便。
每个数能够出现的位置就是 i \space or \space i+1 。假如我们能够得知第一位的数是什么，就可以顺推出下一位，因为下一位出现的两个数的其中一个已经在前一位被推出来了。
第一位的判断依据就是出现次数最多的数，然后依次顺推。
代码：
void solve()
{
cin >> n;
for (int i = 1; i <= n; i++ )
for (int j = 1; j < n; j++ )
cin >> a[j];
int last = -1;
for (int j = 1; j < n; j++ ) {
int t1 = -1, t2 = -1;
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i++ ) {
if (t1 == -1) t1 = a[j], cnt1++ ;
else if (t1 == a[j]) cnt1++ ;
else if (t2 == -1 && a[j] != t1) t2 = a[j], cnt2++ ;
else if (t2 == a[j]) cnt2++ ;
}
if (last == t1) {
ans[j] = last;
last = t2;
} else if (last == t2) {
ans[j] = last;
last = t1;
} else {
if (cnt1 >= cnt2) ans[j] = t1, last = t2;
else ans[j] = t2, last = t1;
}
}
ans[n] = last;
for (int i = 1; i <= n; i++ ) cout << ans << &#34; \n&#34;[i == n];
}
D. Matryoshkas
题意：
给定一个集合，将该集合分成若干个由连续正整数组成的集合，求分成集合的数量的最小值。
分析:
贪心策略是每次都选择最长的连续整数作为一组，代码的话用 map 从小到大遍历所有出现过的数，每个数对答案的贡献是这个数出现的次数减去上一个数产生的次数。
代码：
void solve()
{
cin >> n;
map<int, int> mp;
int mx = 0;
for (int i = 1; i <= n; i++ ) cin >> a, mp[a]++ ;
int last = -1, cur = 0, ans = 0;
for (auto [x, y] : mp) {
if (last + 1 != x) cur = 0;
ans += max(0, y - cur);
last = x;
cur = y;
}
cout << ans << endl;
}
E. Vlad and a Pair of Numbers
题意：
给定一个数 n ，求出两个数字 a, b 满足 a \oplus b = \frac{a + b}{2} 。
分析：
对于 n 的每一位，如果这一位是 1 ，说明 a, b 在这一位上一个是 1 ，一个是 0 。 1 给谁是不影响答案的，我们默认 1 都给 a 。
对于 n 的某些位为 0 ，我们需要考虑另一个限制条件。想让两数之和右移一位变成原数，相当于最终的相加的结果是所有 1 往右移动一位，那么只需要在所有 n 为 1 的位的小一位的地方填上两个 1 ，此时这一位的 1 就可以向左移动一位。
样例解释
n: 0100100
a: 0110110
b: 0010010
a+b: 1001000
n<<1: 1001000
a+b>>1: 100100 = n对于每一个1的小一位如果还是1，则无法将这个两个1向左移动，无解。
代码：
void solve()
{
cin >> n;
int a = 0, b = 0;
if (n & 1) {
cout << -1 << endl;
return ;
}
for (int i = 1; i <= 30; i++ ) {
if (n >> i & 1) {
if (n >> (i - 1) & 1) {
cout << -1 << endl;
return ;
}
}
}
for (int i = 1; i <= 30; i++ ) {
if (n >> i & 1) {
a += 1 << i;
a += 1 << (i - 1);
b += 1 << (i - 1);
}
}
cout << a << &#34; &#34; << b << endl;
}
F. Timofey and Black-White Tree
题意：
给定一颗 n 个节点的树，刚开始所有节点都是白色的，但是只有一个节点 c 是黑色的。每次操作给定一个节点染黑，整颗树的权值定义为两个黑色节点的距离的最小值。求 [1, n - 1] 次操作每次的权值。
分析:
来自jiangly的思路，可能说的不太清楚但是真的很巧妙。
不知道自己在胡言乱语什么，我自己都听不懂了。
我们以刚开始的黑色的点为根，定义数组 dist_i 表示i点，在它的祖先节点中的的第一个黑点的距离。
在每一次操作加入一个新的节点的时候，是不会影响到这个点到祖先的路径上的点的 dist_i 值的，只会影响这个以这个点为子树的 dist_i 值。第一种做法就是直接暴力宽搜遍历子树，每一次的答案都取一次最小值。但是这样的时间复杂度是 O(n^2) ，会直接被树链卡住。
这道题的精华就在于对 ans 的把握。仔细思考我们会发现每一次操作后， ans 的大小都会减少成最多 \frac{n}{i} ，我们每次都往下宽搜一个不超过 ans 的距离，其中第i轮操作后的ans一定是小于等于 \frac{n}{i} 的。这些超过ans的节点的 dist_i 和 ans 进行取 min 更新是没有意义的。因此，每次更新的距离是一个 n ,\frac{n}{2}, \frac{n}{3}, \frac{n}{4} \dots, \frac{n}{n} 级别的东西，但是它和实际的复杂度没有关系。
但是宽搜x层不代表只有 x 个点被更新了。我们需要想想对于每一个点会被更新多少次。我自己也有点不太理解这个根号的问题，目前的感性理解是这样：（胡言乱语）
对于距离小于根号级别的更新，就算更新 n 次，他的数量级也不会很大，因此不做考虑。我们只考虑更新距离大于根号级别的次数，这样的次数一定是少于根号级别的。
考虑每个点会被更新多少次。
假如有根号级别个点，他的周围距离为根号范围以内都没有黑点(这样的状态下，需要每次都更新根号次)。此时所有点的数量为根号乘根号，是大于 n 级别的点的数量。因此可以发现更新距离大于根号级别的次数是少于根号级别的。并且每一次在更新后，答案也会变成根号级别，所以实际的更新应该是远少于这个值的。
结果就是：在前根号次更新中，答案会被降至根号级别。最坏情况下的更新量级是 On ，因此复杂度为 On\sqrt n 。更新距离为根号级别以下的次数为 On ，因为有距离限制，每个点的更新次数一定小于等于根号，因此复杂度还是 On\sqrt n 。
总结：每一个点被更新的次数不会超过根号次。
代码：抄的jiangly
int n, m, a[N], c[N];
int h[N], e[M], ne[M], idx;
int dist[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++ ;
}
void solve()
{
cin >> n >> c[1];
for (int i = 1; i <= n; i++ ) dist = INF, h = -1;
for (int i = 2; i <= n; i++ ) cin >> c;
for (int i = 1; i < n; i++ ) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
int ans = n;
for (int i = 1; i <= n; i++ ) {
ans = min(ans, dist[c]);
if (i > 1) cout << ans << &#34; \n&#34;[i == n];
queue<int> q;
q.push(c);
dist[c] = 0;
while (q.size()) {
auto t = q.front();
q.pop();
for (int i = h[t]; ~i; i = ne) {
int j = e;
if (dist[j] > dist[t] + 1 && ans > dist[t] + 1) {
dist[j] = dist[t] + 1;
q.push(j);
}
}
}
}
} |
|
发表于 2023-2-1 05:44:00