2019.8.7 集训解题报告

2019 年 8 月 7 日 星期三
/ , , , , ,
7

2019.8.7 集训解题报告

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

考试

直角三角形

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

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

这题某位 dalaodalao 不加优化满分，太强了！

正解有三种：

  1. 固定直角顶点，固定另外一个顶点，然后算这两点所连直线的解析式，然后算出垂直于该直线的解析式，然后看看有多少个点在这一条直线上，用数据结构维护进行优化，否则时间复杂度很高。

  2. 极角排序，不知道是什么东西 qwq

  3. 固定一个点，然后平移整个坐标系，枚举象限中的每一个点，旋转 k×90°k \times 90° 角到第一象限，然后计算该点到原点的斜率，然后对于其他每一个点，计算斜率后排序。斜率相同且象限符合情况时，算入答案。

三个正解复杂度都是 O(n2log⁡n)O(n^2 \log n) ，难怪 O(n3)O(n^3) 吸氧气可以跑满分 qwq

感谢 @znh 的翻译！

Test′sTest's CodeCode：60%
#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;
}

排序

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

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

时间复杂度 O(nlog⁡n)O(n \log n)

Test′sTest's CodeCode：70%
#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;
}
FixedFixed CodeCode：100%
#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 分，非常感动，嘤嘤嘤~

正解使用矩阵快速幂，首先先把矩阵推出来。对于原始 k=5k = 5 的矩阵，有： f[1] = f[1]^1 \quad f[2] = f[2]^1 \quad f[3] = f[3]^1 \quad f[4] = f[4]^1 \quad f[5] = f[5]^1 所以 f[1..k]f[1..k] 的原始 指数 矩阵为： \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 & 0 \ 0 & 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 0 & 1 \end{bmatrix} 然后就可以推出 f[2..k+1]f[2.. k+1] 的矩阵： \begin{bmatrix} 0 & 0 & 0 & 0 & b[5] \ 1 & 0 & 0 & 0 & b[4] \ 0 & 1 & 0 & 0 & b[3] \ 0 & 0 & 1 & 0 & b[2] \ 0 & 0 & 0 & 1 & b[1] \end{bmatrix} Test′sTest's CodeCode：50%

#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;
}

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...