Codeforces Round #367 (Div. 2)

A. Beru-taxi

给定n个出租车的位置和速度,问哪个最快到你家。。扫一遍即可。

#include bits/stdc++.h

using namespace std;

int n;
double a, b, c;
double x, y;

double dist(int a, int b, int c, int d) {
    return sqrt((a - c) * (a - c) + (b - d) * (b - d));
}

int main() {
    cin  x  y;
    cin  n;
    double ans = 10000000000000;
    for (int i = 0; i  n; i++) {
        cin  a  b  c;
        ans = min(ans, dist(a, b, x, y) / c);
    }
    printf("%.10lf\n", ans);
    return 0;
}

B. Interesting drink

给你n个数字,m个询问,每次询问一个数字t, 问小于等于t的数有多少个。。排序然后二分。。。。

#include bits/stdc++.h

using namespace std;

int n, m;
int arr[100005];
int main() {
    cin  n;
    for (int i = 1; i = n; i++)
        cin  arr[i];
    sort(arr + 1, arr + n + 1);
    cin  m;
    int t;
    while (m--) {
        cin  t;
        int ans = upper_bound(arr + 1, arr + n + 1, t) - arr - 1;
        cout  ans  endl;
    }
    return 0;
}
C. Hard problem

n个字符串,每个可以支付 ci 的代价翻转。现在要使这n个字符串按字典序排列,问最少代价。
dp[i][0] 表示考虑到第i个字符串,且第i个字符串没有翻转的最小代价,
dp[i][1] 表示考虑到第i个字符串,且第i个字符串翻转了的最小代价。

#include bits/stdc++.h

using namespace std;

int n;
long long cost[100005];
long long dp[100005][2];
string s[100005], rs[100005];

int main() {
    cin  n;
    for (int i = 1; i = n; i++)
        cin  cost[i];
    for (int i = 1; i = n; i++) {
        cin  s[i];
        rs[i] = s[i];
        reverse(rs[i].begin(), rs[i].end());
    }
    for (int i = 2; i = n; i++)
        dp[i][0] = dp[i][1] = 1000000000000000000;
    dp[1][1] = cost[1];
    for (int i = 2; i = n; i++) {
        if (s[i] = s[i - 1]) dp[i][0] = dp[i - 1][0];
        if (s[i] = rs[i - 1]) dp[i][0] = min(dp[i][0], dp[i - 1][1]);
        if (rs[i] = s[i - 1]) dp[i][1] = dp[i - 1][0] + cost[i];
        if (rs[i] = rs[i - 1]) dp[i][1] = min(dp[i][1], dp[i - 1][1] + cost[i]);
    }
    long long ans = min(dp[n][0], dp[n][1]);
    if (ans == 1000000000000000000) ans = -1;
    cout  ans  endl;
    return 0;
}
D. Vasiliy’s Multiset

一个multiset A ,最开始只有一个0,+ x表示将x加入A,- x表示将一个x移出A,? x表示询问max(xy)(yA)
插入操作时将x正序插入字典树,字典树每个节点记录cnt,即有多少个数经过这个节点,这样删除时只需要将路径上的cnt-1。询问时从高位开始贪心,假设x的第i位是 xi ,如果 xi XOR 1可以选(cnt 0)就选,否则只能选 xi
注意集合一开始有一个0哦。

#include bits/stdc++.h

using namespace std;

int q;
mapint, int vis;

int nex[6000005][2], cnt[6000005];
int tot = 0;
int bit[31];
void insert(int x) {
    for (int i = 29; i = 0; i--) {
        bit[i] = x  1;
        x = 1;
    }
    int pos = 0;
    for (int i = 0; i  30; i++) {
        int t = bit[i];
        if (!nex[pos][t]) nex[pos][t] = ++tot;
        pos = nex[pos][t];
        cnt[pos]++;
    }
}

void del(int x) {
    for (int i = 29; i = 0; i--) {
        bit[i] = x  1;
        x = 1;
    }
    int pos = 0;
    for (int i = 0; i  30; i++) {
        int t = bit[i];
        pos = nex[pos][t];
        cnt[pos]--;
    }
}

int ans[31];
void query(int x) {
    for (int i = 29; i = 0; i--) {
        bit[i] = x  1;
        x = 1;
    }
    int pos = 0;
    for (int i = 0; i  30; i++) {
        int t = bit[i];
        if (cnt[nex[pos][t ^ 1]]) {
            ans[i] = 1;
        } else {
            ans[i] = 0;
        }
        pos = nex[pos][t ^ ans[i]];
    }
}

int get() {
    int ret = 0;
    int t = 1;
    for (int i = 29; i = 0; i--) {
        ret += ans[i] * t;
        t = 1;
    }
    return ret;
}

int main() {
    cin  q;
    string s;
    int a;
    while (q--) {
        cin  s;
        cin  a;
        if (s[0] == '+') {
            if (!vis[a]) {
                insert(a);
            }
            vis[a]++;
        } else if (s[0] == '-') {
            if (vis[a] == 1) {
                del(a);
            }
            vis[a]--;
        } else {
            query(a);
            cout  max(a, get())  endl;
        }
    }
    return 0;
}
E. Working routine

给一个 nm 的矩阵,每次操作交换两个大小形状相同的子矩阵,且保证这两个子矩阵没有公共边,输出最后的矩阵。
暴力的话 O(nmq) 。。但是注意到每次操作的两个子矩阵没有公共边这个奇怪的条件,所以就有这么一个有趣的做法。。
每个位置(i, j)维护两个值 rightij,downij ,表示 (i,j) 右边和下边的位置。。不理解的话参考下面初始化的代码:

for (int i = 0; i = n + 1; i++) {
    for (int j = 0; j = m + 1; j++) {
        rig[p(i, j)] = p(i, j + 1);
        down[p(i, j)] = p(i + 1, j);
    }
}

这样的话每次操作只需要交换子矩阵边界的right和down,复杂度 O(q(m+n))

#include bits/stdc++.h

#define p(i, j) ((i) * (m + 2) + (j))

using namespace std;

int n, m, q;
int arr[1005][1005];
int rig[1100005], down[1100005];

int find(int x, int y) {
    int pos = 0;
    while (x--) pos = down[pos];
    while (y--) pos = rig[pos];
    return pos;
}

int main() {
    cin  n  m  q;
    for (int i = 1; i = n; i++) {
        for (int j = 1; j = m; j++) {
            scanf("%d", arr[i][j]);
        }
    }
    for (int i = 0; i = n + 1; i++) {
        for (int j = 0; j = m + 1; j++) {
            rig[p(i, j)] = p(i, j + 1);
            down[p(i, j)] = p(i + 1, j);
        }
    }

    int x1, y1, x2, y2, h, w;
    while (q--) {
        scanf("%d %d %d %d %d %d", x1, y1, x2, y2, h, w);
        int a = find(x1 - 1, y1), b = find(x2 - 1, y2);
        int c = a, d = b;
        for (int i = 0; i  h; i++)
            c = down[c], d = down[d];
        for (int i = 0; i  w; i++) {
            swap(down[a], down[b]);
            swap(down[c], down[d]);
            a = rig[a], b = rig[b];
            c = rig[c], d = rig[d];
        }
        a = find(x1, y1 - 1), b = find(x2, y2 - 1);
        c = a, d = b;
        for (int i = 0; i  w; i++)
            c = rig[c], d = rig[d];
        for (int i = 0; i  h; i++) {
            swap(rig[a], rig[b]);
            swap(rig[c], rig[d]);
            a = down[a], b = down[b];
            c = down[c], d = down[d];
        }
    }
    int s = 0;
    for (int i = 1; i = n; i++) {
        s = down[s];
        int t = s;
        for (int j = 1; j = m; j++) {
            t = rig[t];
            if (j != 1) printf(" ");
            printf("%d", arr[t / (m + 2)][t % (m + 2)]);
        }
        printf("\n");
    }
    return 0;
}
最新回复(0)
/jishuLmy7Dcv_2BcUI11D9h_2Bi9aiJJfzuJIhfNViyq1AdKF5eI_3D4858339
8 简首页