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
就是第一列顺着填，中间一列从一半开始顺着填，最后一列一半奇数一半偶数，实现看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #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\n1");
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], " \n"[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], " \n"[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\)段，每段贡献分数是负的前缀和的前缀和(\(-\sum\limits_{l\le i\le r}\sum\limits_{l\le j\le i}a[i]\))，这里暂不考虑吃树
然后考虑吃树，吃完树之后如果在同一段，相当于后面每个位置不用减去这棵树的权值，不在同一段相当于每个位置会获得这棵树的权值，即分数是\(a[i] * (n - i + 1)\)，这个东西排序求前\(m\)大就好的
划分成\(k+1\)段是个经典的斜率dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #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\n", 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}\)的所有质因子，然后最多只剩四个因子，直接判断是不是四次方数，三次方数，二次方数即可