美文网首页
排位赛 13 题解

排位赛 13 题解

作者: 染微言 | 来源:发表于2017-07-15 13:39 被阅读23次

    排位赛 13 题解

    题型

    • A - 贪心 √
    • B - 后缀数组 √
    • C - 环形DP
    • D - 二维树状数组/二维线段树 √
    • E - DFS找连通块 √
    • F - 快速傅里叶变换(FFT)
    • G - DFS/二分 √
    • H - 最小比率生成树/二分/迭代

    A - domino

    题意

    给出放骨牌位置之间的距离,和可以推骨牌的次数,求最少的骨牌高度和。

    思路

    贪心。统计只推一次所需要的骨牌高度,然后排序,减去最高高度即可。

    代码

    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    //#define LOCAL
    #define LL __int64 // 1e5*1e5会爆int
    
    const int maxn = 1e5+7;
    int h[maxn];
    
    int main(){
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif
        int t; scanf("%d", &t);
        while (t--) {
            int n, k;
            scanf("%d%d", &n, &k);
            for (int i = 0; i < n-1; ++i)
                scanf("%d", h+i);
            sort(h, h+n-1);
            LL ans = 0;
            for (int i = 0; i < n-k; ++i)
                ans += h[i];
            ans += n;
            printf("%I64d\n", ans);
        }
        return 0;
    }
    

    B - Sequence

    题意

    给出一个数字串,将其分为三段,每段都翻转过来,求可以得到的字典序最小的串。

    思路

    后缀数组。现学现卖系列。本来用贪心法,结果发现不能过,翻了大白书才发现是后缀数组。先将整个数列翻转过来求SA,然后找到第一个位置不在最后两个的后缀,作为一个的指针位置。然后求第二个指针位置。这里要注意一点,要将后面的串复制一遍然后求后缀数组。

    代码

    \\用的不是正统倍增法,而是用sort简化了
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    #define LOCAL
    
    const int maxn = 200000+107;
    int n, num[maxn], rev_num[maxn], k;
    int rank[maxn], temp[maxn], sa[maxn];
    
    bool cmp(int i, int j) {
        if (rank[i] != rank[j]) return rank[i] < rank[j];
        int x = i+k<=n?rank[i+k]:-1;
        int y = j+k<=n?rank[j+k]:-1;
        return x < y;
    }
    
    void get_sa(int a[], int m) {
        for (int i = 0; i <= m; ++i) {
            sa[i] = i;
            rank[i] = i<n? a[i] : -1;
        }
        for (k = 1; k <= n; k<<=1) {
            sort(sa, sa+m+1, cmp);
            temp[sa[0]] = 0;
            for (int i = 1; i <= m; ++i)
                temp[sa[i]] = temp[sa[i-1]] + (cmp(sa[i-1], sa[i])?1:0);
            for (int i = 0; i <= n; ++i)
                rank[i] = temp[i];
        }
    }
    
    int main(){
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) scanf("%d", num+i);
        reverse_copy(num, num+n, rev_num);
        get_sa(rev_num, n);
        int cur1;
        for (int i = 0; i <= n; ++i) {
            cur1 = n - sa[i];
            if (cur1 >= 1 && n-cur1 >= 2) break;
        }
        int m = n - cur1;
        reverse_copy(num+cur1, num+n, rev_num);
        reverse_copy(num+cur1, num+n, rev_num+m);
        get_sa(rev_num, m*2);
        int cur2;
        for (int i = 0; i <= m*2; ++i) {
            cur2 = n - sa[i];
            if (cur2-cur1 >= 1 && n-cur2 >= 1) break;
        }
        reverse(num, num+cur1);
        reverse(num+cur1, num+cur2);
        reverse(num+cur2, num+n);
        for (int i = 0; i < n; ++i)
            printf("%d\n", num[i]);
        return 0;
    }
    

    D - Matrix

    题意

    有一个$n\times n$的01矩阵,有两种操作,一种是将一个矩形内的元素全部异或1,另一种是单点查询。要求实现这些操作。

    思路

    关于树状数组区间染色,有一篇论文可以看——《浅谈信息学竞赛中的“0”和“1”》。其中第一块就用到了这个例题。只要对区间边缘的点更新,就能记录区间染色的次数,然后区间求前缀和就能得到染色了多少次,得到答案。

    很菜的是,有二重循环的bug调了一个小时才过。

    代码

    #include <bits/stdc++.h>
    using namespace std;
    
    const int maxn = 1e3+7;
    
    int n, tree[maxn][maxn];
    
    int lowbit(int x) {
        return x&(-x);
    }
    
    void add(int x, int y) {
        for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= n; j += lowbit(j))
            ++tree[i][j];
    }
    
    int query(int x, int y) {
        int rt = 0;
        for (int i = x; i; i -= lowbit(i))
        for (int j = y; j; j -= lowbit(j))
            rt += tree[i][j];
        return rt;
    }
    
    void solve() {
        char ins[2]; int t;
        scanf("%d%d", &n, &t);
        memset(tree, 0, sizeof tree);
        while (t--) {
            scanf("%s", ins);
            if (ins[0] == 'C') {
                int x1, y1, x2, y2;
                scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
                add(x1, y1); add(x1, y2+1);
                add(x2+1, y1); add(x2+1, y2+1);
            }
            else {
                int x, y; scanf("%d%d", &x, &y);
                printf("%d\n", query(x, y)&1);
            }
        }
    }
    
    int main(){
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif
        int t; scanf("%d", &t);
        while (t--) solve();
        return 0;
    }
    

    E - PaintBall

    题意

    一张1000*1000的图上有n个圆形障碍物,求是否能从最左侧走到最右侧。

    思路

    对每个障碍物缩点,然后从上边界开始DFS遍历所有相邻的障碍物,如果遍历到的障碍物可以接触到下边界就无解。遇到与左边界相邻的障碍物就更新入口位置,出口为右边界。

    代码

    /**
     * Author: wzhzzmzzy
     * Question: UVa - 11853
     * Algorithm: DFS
    **/
    
    #include <bits/stdc++.h>
    using namespace std;
    //#define LOCAL
    
    const int maxn = 1<<10;
    int n, flag, vis[maxn];
    double ent, exi;
    
    struct { double x, y, r; } node[maxn];
    
    bool check(int u, int v) {
        return hypot(node[u].x-node[v].x, node[u].y-node[v].y) < node[u].r+node[v].r;
    }
    
    int dfs(int s) {
        if (!flag) return 0;
        vis[s] = 1;
        if (node[s].y - node[s].r <= 0)
            return flag = 0;
        for (int i = 0; i < n; ++i)
            if (!vis[i] && check(s, i)) dfs(i);
        if (node[s].x - node[s].r <= 0)
            ent = min(ent, node[s].y - sqrt(node[s].r*node[s].r-node[s].x*node[s].x));
        if (node[s].x + node[s].r >= 1000)
            exi = min(exi, node[s].y - sqrt(node[s].r*node[s].r-(1000-node[s].x)*(1000-node[s].x)));
    }
    
    int main(){
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif
        while (~scanf("%d", &n)) {
            memset(vis, 0, sizeof vis);
            flag = 1, ent = exi = 1000;
            for (int i = 0; i < n; ++i)
                scanf("%lf%lf%lf", &node[i].x, &node[i].y, &node[i].r);
            for (int i = 0; i < n; ++i)
                if (!vis[i] && node[i].y+node[i].r >= 1000) dfs(i);
            if (!flag) puts("IMPOSSIBLE");
            else printf("0.00 %.2f 1000.00 %.2f\n", ent, exi);
        }
        return 0;
    }
    

    G - ztr loves lucky numbers

    题意

    找出一个最小的大于n的由相同数量的4和7组成的数字。

    思路

    先DFS打表,然后二分查找。

    代码

    /**
     * Author: wzhzzmzzy
     * Question: HDU - 5676
     * Algorithm: 二分
    **/
    
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    //#define LOCAL
    #define LL __int64
    
    const int maxn = 1<<21;
    
    LL n, num[maxn];
    int cur;
    
    void dfs(int u, int v, LL w) {
        if (!u && !v) {
            num[++cur] = w;
            return;
        }
        if (u) dfs(u-1, v, w*10+4);
        if (v) dfs(u, v-1, w*10+7);
    }
    
    void solve() {
        scanf("%I64d", &n);
        if (n > 777777777444444444) {
            puts("44444444447777777777");
            return;
        }
        int l = 1, r = cur;
        LL ans;
        while (l <= r) {
            int mid = (l+r)>>1;
            if (num[mid] >= n)
                r = mid-1, ans = num[mid];
            else l = mid+1;
        }
        printf("%I64d\n", ans);
    }
    
    void init() {
        cur = 0;
        for (int i = 2; i <= 18; i+=2)
            dfs(i>>1, i>>1, 0);
        sort(num+1, num+1+cur);
    }
    
    int main(){
    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
    #endif
        init();
        int t; scanf("%d", &t);
        while (t--) solve();
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:排位赛 13 题解

          本文链接:https://www.haomeiwen.com/subject/mqnahxtx.html