2019.8.7 集训解题报告
浏览 107 | 评论 0 | 字数 5198
Snowflake_Pink
2019年08月07日
  • 这次拿的暴力分,让我觉得是考的最好的一次 QAQ


    考试

    直角三角形

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

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

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


    正解有三种:

    1. 固定直角顶点,固定另外一个顶点,然后算这两点所连直线的解析式,然后算出垂直于该直线的解析式,然后看看有多少个点在这一条直线上,用数据结构维护进行优化,否则时间复杂度很高。
    2. 极角排序,不知道是什么东西 qwq
    3. 固定一个点,然后平移整个坐标系,枚举象限中的每一个点,旋转 $k \times 90°$ 角到第一象限,然后计算该点到原点的斜率,然后对于其他每一个点,计算斜率后排序。斜率相同且象限符合情况时,算入答案。

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

    感谢 @znh 的翻译!

    $Test's$ $Code$: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;
    }
    

    排序

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

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

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

    $Test's$ $Code$: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;
    }

    $Fixed$ $Code$: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 = 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]$ 的原始 指数 矩阵为:

    $$ \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]$ 的矩阵:

    $$ \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's$ $Code$: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;
    }
    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/75/
    最后修改时间:2020-04-13 11:41:52
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论