排位赛 13 题解

2017-07-15 本文已影响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 题解