avatar

20200528 考试总结

【背景】

到了妹子中学以后,小 Z 和小 W、小 L、小 S、小 Y 一起上了一门屑课,在考试中遇到了一些问题。

这次考试题很屑但是我考的很炸,并且这里面涉及到一些神奇的思路,所以我来写总结(((

【描述】

T1

题意

给定一个长度为 $2n$ 的序列,其中有 $2n-2$ 元素成对出现,还有两个元素不成对,请求出这两个元素。空间限制 2MB

解法

如果没有这个空间限制,那么这是一个 sb 题,然而加上了这个空间限制就变得很恶心。

正确的做法是:先求出所有元素的异或和(记为 ans),因为相等元素异或为 0,所以这里的异或和就是要求的两个元素异或值。然后开一个大小为 32 的数组 a[32] ,将二进制第 i 位上为 1 的数异或起来。对于第 i 位有如下几种情况:

  1. 两个数的这一位都为 0,那么 a[i] == 0
  2. 两个数的这一位都为 1,那么 a[i] == ans
  3. 两个数的这一位分别为 1 和 0,那么 a[i] 就是其中一个答案,另一个答案为 ans ^ a[i]

然而这道题的标程并没有考虑第一种情况,所以有三个点数据错误,真正的正解只有 70 分。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
using namespace std;

int n, a[32], x, i, j, p, q, ans;

int main() {
scanf("%d", &n);
for(i = 1; i <= n << 1; i++) {
scanf("%d", &x);
ans ^= x;
for(j = 0; j < 31; j++) if(x & (1 << j)) a[j] ^= x;
}
for(register int i = 0; i < 31; i++)
if(a[i] != ans && a[i]) {
printf("%d %d", ans ^ a[i], a[i]);
break;
}
return 0;
}

T2

题意

求区间 $[l,r]$ 子段和取模 $p$ 的最小值(不带修)$p\leq 100$

解法

很容易得出这样的暴力做法:枚举左右端点,前缀和相减,时间复杂度为 $O(mn^2)$。

然而我们发现,如果区间有两个前缀和相等,那么答案为 0。一个长度为 $k$ 的区间前缀和最多有 $k$ 种情况,然而根据鸽巢原理,如果 $k>p$ 那么必然有相等的区间前缀和,所以如果 $p<r-l$ 那么可以直接输出 0,其他情况枚举即可。时间复杂度为 $O(mp^2)$

由于数据水,这个做法跑得比正解还快。

代码

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int get() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}

const int N =50005;
int n, m, a[N];

signed main() {
n = get(), m = get();
for(register int i = 1; i <= n; i++) a[i] = a[i - 1] + get();
for(register int i = 1; i <= m; i++) {
int l = get(), r = get(), p = get();
if(r - l > p) {
printf("0\n");
continue;
}
else {
int ans = 0x3f3f3f3f;
for(register int ll = l; ll <= r && ans != 0; ll++)
for(register int rr = ll; rr <= r; rr++) {
ans = min(ans, (a[rr] - a[ll - 1]) % p);
if(ans == 0) break;
}
printf("%lld\n", ans);
}
}
return 0;
}

T3

题意

概括不能

很久很久以前,森林里住着一群兔子。

其中有三只兔子,第一只兔子喜欢吃萝卜,第二只兔子喜欢吃青菜,第三只兔子喜欢吃三文鱼中卷寿司。

有一天,他们收集了 nn 个篮子的食物,其中每个篮子里恰好装了一只萝卜,一捆青菜和一个三文鱼中卷寿司,每个食物都有一个美味度。然后他们打算分吃篮子里的食物。如果第一只兔子得到了一些篮子,那么他只会吃每个篮子里面的胡萝卜,然后它获得的美味度即为它吃到的美味度最大的胡萝卜。同理第二只兔子只会吃青菜,第三只兔子只吃三文鱼中卷寿司,同时他们也分别能获得一个美味度。

出于嫉妒心,其余的没有食物的兔子希望计算,如果给这三只兔子划分篮子,使得他们三人获得的美味值之和最小。注意每个篮子是最小的划分单位,不能把篮子里的食物拿出来和放入新食物。如果一个兔子没有得到任何篮子,那么它获得的美味度为0。

解法

前 20 分写搜索 + 剪枝。另 30 分不需要考虑 c,所以直接把所有篮子按照 a 排序然后求出 b 的后缀最大值再统计一下就可以了。

另外 50 分暂时不会(

代码

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

inline int get() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}

int n, a[100005], b[100005], c[100005], maxn = 2000000000, fa[100005], fb[100005], fc[100005], maxa, maxb, maxc;

inline void dfs(int dep, int x, int y, int z) {
if(x + y + z > maxn) return;
if(dep == n + 1) maxn = x + y + z;
else dfs(dep + 1, max(x, a[dep]), y, z),
dfs(dep + 1, x, max(y, b[dep]), z),
dfs(dep + 1, x, y, max(z, c[dep]));
}

struct shit {
int a, b;
} v[1000005];

inline bool cmp(shit a, shit b) { return a.a < b.a; }

int suf[1000005];

signed main() {
n = get();
for(register int i = 1; i <= n; i++) a[i] = get(), b[i] = get(), c[i] = get(), maxa = max(maxa, a[i]), maxb = max(maxb, b[i]), maxc = max(maxc, c[i]);
if(n <= 20) {
dfs(1, 0, 0, 0);
cout << maxn;
}
else {
for(register int i = 1; i <= n; i++) v[i].a = a[i], v[i].b = b[i];
sort(v + 1, v + 1 + n, cmp);
for(register int i = n; i >= 1; i--) suf[i] = max(suf[i + 1], v[i].b);
int ans = suf[1];
for(register int i = 1; i <= n; i++)
ans = min(ans, v[i].a + suf[i + 1]);
cout << ans;
}
return 0;
}

【提示与说明】

这分明就是一次暴力大赛好吗……

文章作者: SocialZxy
文章链接: http://socialzxy.github.io/2020/05/28/20200528test/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 SocialZxy's Blog

评论