2019 杭电多校第四场
1001. AND Minimum Spanning Tree
solved at 00:39(+1)
有一张(n)个点的完全图，点编号是(1)到(n)，边权是点编号的bitwise and，求最小生成树，输出字典序最小的
签到题，偶数直接连(1),二进制位不全是(1)的奇数连最低的为零的二进制位代表的二的幂次，全是(1)的看加一是不是小于等于(n)，是就往加一连，否则连(1)
1003. Divide the Stones
upsolved
(n)个石子，重量分别为(1)到(n)，你要把它们分为(k)堆，使得每堆石子数量一样，总重量也一样
构造，(n/k)是偶数很简单，直接两边往中间取就行了
如果(n/k)是奇数，(k)必须也是奇数，先蛇形从大到小填数使得每堆只需要填(3)个(可以保证当前每堆的和都一样），然后如下例所示：((n=27,k=3))
27 13 2
26 12 4
25 11 6
24 10 8
23 18 1
22 17 3
21 16 5
20 15 7
19 14 9
就是第一列顺着填，中间一列从一半开始顺着填，最后一列一半奇数一半偶数，实现看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int T, n, k, a, sum;
vector<int> ans[N];
int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &k);
if(n == k && k == 1) {
puts("yes
1");
continue;
}
if(n == k) {
puts("no");
continue;
}
a = n / k;
if(a % 2 == 0) {
puts("yes");
int l = 1, r = n;
for(int i = 0; i < k; ++i) {
for(int _ = 0; _ < a / 2; ++_)
ans[i].push_back(l++);
for(int _ = 0; _ < a / 2; ++_)
ans[i].push_back(r--);
}
for(int i = 0; i < k; ++i) {
for(int j = 0; j < a; ++j)
printf("%d%c", ans[i][j], "
"[j + 1 == a]);
ans[i].clear();
}
}
else if(k % 2 == 1) {
puts("yes");
int p = n, q = k / 2;
while(p > 3 * k) {
for(int i = 0; i < k; ++i)
ans[i].push_back(p--);
for(int i = k - 1; ~i; --i)
ans[i].push_back(p--);
}
for(int i = 0; i < k; ++i)
ans[i].push_back(p--);
for(int i = 0; i < k; ++i)
ans[(q + i) % k].push_back(p--);
p = 1;
for(int i = q; i < k; ++i)
ans[i].push_back(p), p += 2;
p = 2;
for(int i = 0; i < q; ++i)
ans[i].push_back(p), p += 2;
for(int i = 0; i < k; ++i) {
for(int j = 0; j < a; ++j)
printf("%d%c", ans[i][j], "
"[j + 1 == a]);
ans[i].clear();
}
}
else
puts("no");
}
return 0;
}
1006. Horse
upsloved
你有一匹马，马会跳过(n)颗树，每次跳过树需要消耗树的高度那么多体力，然后会获得剩余体力那么多分数，你还有另外两种操作：一是在跳一棵树之前吃掉这棵树，即这棵树高度归零，这种操作最多(m)次，二是跳完一棵树之后休息，将体力恢复成已经吃掉的树的高度和，这种操作最多(k)次，初始体力为零，求最大分数(1<=N<=5e4, 1<=m,k<=50)
首先考虑休息(k)次，显然是将序列划分成(k+1)段，每段贡献分数是负的前缀和的前缀和((-sumlimits_{lle ile r}sumlimits_{lle jle i}a[i]))，这里暂不考虑吃树
然后考虑吃树，吃完树之后如果在同一段，相当于后面每个位置不用减去这棵树的权值，不在同一段相当于每个位置会获得这棵树的权值，即分数是(a[i] * (n - i + 1))，这个东西排序求前(m)大就好的
划分成(k+1)段是个经典的斜率dp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e4 + 10;
int T, n, m, k, a[N];
int que[N], head, tail;
LL dp[55][N], s[N], ss[N], f[N];
inline LL X(int i) {return s[i];}
inline LL Y(int t, int i) {return dp[t][i] - ss[i] + i * s[i];}
int main() {
scanf("%d", &T);
while(T--) {
LL ans = 0;
scanf("%d%d%d", &n, &k, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
ss[i] = ss[i - 1] + s[i];
f[i] = 1LL * (n - i + 1) * a[i];
}
sort(f + 1, f + n + 1);
for(int i = n - m + 1; i <= n; ++i)
ans += f[i];
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for(int i = 1; i <= k + 1; ++i) {
head = tail = 0;
que[tail++] = 0;
for(int j = 1; j <= n; ++j) {
while(head + 1 < tail && (Y(i - 1, que[head + 1]) - Y(i - 1, que[head]) <= j * (X(que[head + 1]) - X(que[head])))) head++;
dp[i][j] = dp[i - 1][que[head]] + ss[j] - ss[que[head]] - (j - que[head]) * s[que[head]];
while(head + 1 < tail && (Y(i - 1, que[tail - 1]) - Y(i - 1, que[tail - 2])) * (X(j) - X(que[tail - 1])) >= (Y(i - 1, j) - Y(i - 1, que[tail - 1])) * (X(que[tail - 1]) - X(que[tail - 2]))) tail--;
que[tail++] = j;
}
}
ans -= dp[k + 1][n];
printf("%lld
", ans);
}
return 0;
}
1007. Just an Old Puzzle
solved at 00:51(+1)
给你一个15-puzzle,问你能否在120步之内找到解
判断逆序对数和(0)的位置就好了，120步对于所有有解的情况都足够了
1008. K-th Closest Distance
solved at 03:55(+16)
有一个数组(A)，每次给定一个区间和两个值(p, k)，询问区间内和(p)的差值的绝对值第(k)小的那个差值，强制在线
主席树，赛中一直T,12000ms过得，赛后一交4800ms...
1009. Minimal Power of Prime
solved at 01:31
(T(T<=50000))组样例，每次询问一个数(n(1<n<=1e18))，求(n)的所有质因子的最低幂次
先除掉小于等于(n^{0.2})的所有质因子，然后最多只剩四个因子，直接判断是不是四次方数，三次方数，二次方数即可