2019.8.7 集训解题报告

这次拿的暴力分,让我觉得是考的最好的一次 QAQ


考试

直角三角形

考试的时候想了 20 分钟,想不出来,打了个暴力交了,60 分(用 cin 40分 哈哈哈哈哈哈

这题其实可以卡常,加上读入优化,输出优化,register ,可以跑到 70 分。估计加个 $O2$ 还可以更快,不过这在考试中当然是不可取的。

这题某位 $dalao$ 不加优化满分,太强了!

$Test’s$ $Code$:

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
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
const int MAXN = 1505;

struct Node {
int x, y;
};
Node p[MAXN];

int n, ans;

int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
scanf ("%d%d", &p[i].x, &p[i].y);
}

for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
for (int k = j + 1; k <= n; k++) {
int a = (p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y);
int b = (p[j].x - p[k].x) * (p[j].x - p[k].x) + (p[j].y - p[k].y) * (p[j].y - p[k].y);
int c = (p[i].x - p[k].x) * (p[i].x - p[k].x) + (p[i].y - p[k].y) * (p[i].y - p[k].y);
if (a + b == c || a + c == b || b + c == a) {
ans++;
}
}
}
}

printf ("%d\n", ans);
return 0;
}

排序

这题好像跟逆序对有关,应该可以用 $dp$ ,不过我就直接模拟求逆序对了,70 分 QAQ

正解不是 $dp$ ,在求答案的过程中其实可以使用数据结构维护,最简单的树状数组就可以了。只要在读取数据的时候用一下插入,每次把一个数归位以后就删掉这个数,然后再查询在需要移动的方向上,有几个数挡在路上。

时间复杂度 $O(n \log n)$

$Test’s$ $Code$:

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
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAXN = 1e5+5;
const int INF = 2e9;
int f[MAXN], n, a[MAXN], num[MAXN];
int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
scanf ("%d", &a[i]);
num[i] = a[i];
}

sort (num + 1, num + n + 1);
num[n + 1] = INF;
for (int i = 1; i <= n; i++) {
if (n % 2 == 1 && i == n / 2 + 1) {
f[i] = 0;
continue;
}
if (i <= n / 2) {
for (int j = 1; j <= n; j++) {
if (a[j] == num[i]) break;
if (a[j] > num[i] && a[j] < num[n - i + 2]) {
f[i]++;
}
}
}
else {
for (int j = n; j >= 1; j--) {
if (a[j] == num[i]) break;
if (a[j] < num[i] && a[j] > num[n - i + 1]) {
f[i]++;
}
}
}
}

for (int i = 1; i <= n / 2; i++) {
printf ("%d\n", f[i]);
printf ("%d\n", f[n - i + 1]);
}
if (n % 2 == 1) {
printf ("%d\n", f[n / 2 + 1]);
}
return 0;
}

$Fixed$ $Code$:

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 1e5 + 5;

int n, a[MAXN], num[MAXN];
int c[MAXN];

inline int lowbit (int x) {
return x & (-x);
}

inline void Add (int i, int num) {
while (i <= n) {
c[i] += num;
i += lowbit (i);
}
return;
}

inline int Sum (int i) {
int ans = 0;
while (i > 0) {
ans += c[i];
i -= lowbit (i);
}
return ans;
}

inline int Query (int l, int r) {
return Sum (r) - Sum (l - 1);
}

int main() {
scanf ("%d", &n);
for (int i = 1; i <= n; i++) {
scanf ("%d",&a[i]);
Add(i, 1);
num[a[i]] = i;
}

int Min = 1, Max = n;
for (int i = 1; i <= n; i++) {
if (i % 2 == 1) {
Add (num[Min], -1);
printf ("%d\n", Query (1, num[Min]));
Min++;
}
else {
Add (num[Max], -1);
printf ("%d\n", Query (num[Max], n));
Max--;
}
}
return 0;
}

自行车比赛

考试的时候直接跳过了,最后输出样例,不知道多少分 QAQ。现在知道了,当然没有分啦~

小 L 的数列

直接模拟 30 分,后面加了个快速幂,不知道多少分 QAQ。有 50 分,非常感动,嘤嘤嘤~

$Test’s$ $Code$:

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
#include <iostream>
#include <cstdio>

using namespace std;
const int MAXN = 4e7 + 5;
const int MAXK = 2e2 + 5;
const int Mod = 998244353;

long long f[MAXN];

int b[MAXK], n, k;

long long Pow (long long a, int x) {
if (x == 1) return a;
long long ans = 1;
long long temp = Pow (a, x>>1) % Mod;
ans = (temp * temp) % Mod;
if (x % 2 == 1) {
ans = (ans * a) % Mod;
}
return ans;
}

int main() {
freopen ("seq.in", "r", stdin);
freopen ("seq.out", "w", stdout);

scanf ("%d%d", &n, &k);

for (int i = 1; i <= k; i++) {
scanf ("%d", &b[i]);
}
for (int i = 1; i <= k; i++) {
scanf ("%lld", &f[i]);
}

int i = k + 1;
while (i <= n) {
int cnt = 0;
f[i] = 1;
for (int j = i - 1; j >= i - k; j--) {
long long s = 1;
cnt++;
s = Pow (f[j], b[cnt]);
f[i] = (f[i] * s) % Mod;
}
i++;
}

printf ("%lld\n", f[n]);
fclose (stdin);
fclose (stdout);
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×