[数据结构与算法]【板刷 educational round】Educational Codeforces Round 1 A - F

总结

这场有两个计算几何，被push学习了一下计算几何的基础知识，其它的题都很简单。

A - Tricky Sum

题意

给定正整数 $n(n<=10^9)$，$i$ 从 $1$ 到 $n$ ，如果 $i$ 为二的整次幂，减去 $i$ ，否则加上 $i$ 。

思路

考虑从 $1$ 加到 $n$ ，可以使用等差数列求和公式，再减去其中所有 $2$ 的整次幂的两倍。复杂度 $O(T?logn)$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define int long long

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t;
    while(t--) {
        int x; cin >> x;
        int ans = (1+x)*x/2;
        for(int i = 0;; i++) {
            if((1ll << i ) <= x) ans -= (1ll << i)*2;
            else break;
        }
        cout << ans << endl;
    }

    return 0;
}

B - Queries on a String

题意

给定长度为 $1e4$ 的字符串，$m$ $(m\le 300)$ 次操作，每次操作给定 $l,r,k$ $(k\le 10^6)$，字符串的区间 $[l,r]$ 向右rotate $k$ 次，求最终的字符串。

思路

模拟题，但纯模拟一定超时。对于每次操作，$O(1)$ 计算出操作后的起始位置，再进行模拟。复杂度 $O(m?|s|)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s; cin >> s;
    int m; cin >> m;
    while(m--) {
        int l, r, k; cin >> l >> r >> k;
        l--, r--;
        int len = r - l + 1;
        k %= len;
        if(!k) continue;
        int p = r - k + 1;
        string ns;
        for(int i = p; i<=r; i++) ns.push_back(s[i]);
        for(int i = l; i<=p-1; i++) ns.push_back(s[i]);
        
        for(int i = 0; i<ns.size(); i++) {
            s[i+l] = ns[i];
        }
    }
    cout << s << "\n";
 
    return 0;
}

C - Nearest vectors

题意

给定 $n$ 个向量，输出形成的夹角最小的两个向量的编号。

思路

极角排序后扫一遍。复杂度 $O(n?logn)$ 。

本题对精度要求非常高，需要使用 long double，并且不能使用余弦定理求两向量的夹角。由于比较之前未进行浮点运算，无精度误差，索性不使用eps，并且用atan2进行极角排序。
如果考虑使用eps，按叉乘排序需要开到1e-8，按atan2排序需要开到1e-16。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define double long double
const double pi = acos(-1.);

struct Point {
    int id;
    double x, y;
};
using Vector = Point;
bool operator < (Vector a, Vector b) {
    return atan2(a.y, a.x) < atan2(b.y, b.x);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector<Vector> p(n);
    for(int i = 0; i<n; i++) {
        p[i].id = i+1;
        cin >> p[i].x >> p[i].y;
    }

    sort(p.begin(), p.end());

    double mn = 1e20;
    int ans1, ans2;

    for(int i = 0; i<n-1; i++) {
        Vector a = p[i], b = p[i+1];
        double ang = atan2(b.y, b.x) - atan2(a.y, a.x);
        if(ang < mn) {
            mn = ang; ans1 = p[i].id, ans2 = p[i+1].id;
        }
    }

    Vector a = p[0], b = p[n-1];
    double ang = 2 * pi + atan2(a.y, a.x) - atan2(b.y, b.x);
    if(ang < mn) {
        mn = ang; ans1 = p[0].id, ans2 = p[n-1].id;
    }

    cout << ans1 << " " << ans2 << "\n";

    return 0;
}

D - Igor In the Museum

题意

给定 $1000\times 1000$ 的网格，每个格子为空地或墙壁。对于每一片连通的空地，求这片空地与多少个墙壁四连通。

思路

对于每一单个空地，首先处理出其周围四个方向有对少个墙壁。再通过一次bfs求出每个连通块连接墙壁数量的总和。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxn = 1005;
string g[maxn];
int val[maxn][maxn];
bool vis[maxn][maxn];
int r, c, k;
 
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
 
bool valid(int x, int y) {
    return x >= 0 && y >= 0 && x < r && y < c;
}
 
struct Node{
    int x, y;
};
void bfs(int sx, int sy) {
 
    vector<Node> tmp;
 
    queue<Node> q; q.push({sx, sy}); vis[sx][sy] = true;
    int tot = 0;
    while(q.size()) {
        int x = q.front().x, y = q.front().y; 
        tot += val[x][y]; tmp.push_back({x, y});
        q.pop();
        for(int i = 0; i<4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if(!valid(nx, ny) || vis[nx][ny] || g[nx][ny] == '*') continue;
            q.push({nx, ny}); vis[nx][ny] = true;
        }
    }
 
    for(auto node : tmp) {
        int x = node.x, y = node.y;
        val[x][y] = tot;
    }
}
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> r >> c >> k;
    for(int i = 0; i<r; i++) cin >> g[i];
 
    for(int i = 0; i<r; i++) 
        for(int j = 0; j<c; j++) 
            if(g[i][j] == '.') {
                for(int p = 0; p<4; p++) {
                    int nx = i + dx[p], ny = j+dy[p];
                    if(valid(nx, ny) && g[nx][ny] == '*') val[i][j]++;
                } 
            }
 
 
    for(int i = 0; i<r; i++) for(int j = 0; j<c; j++) {
        if(g[i][j] == '.' && !vis[i][j]) {
            bfs(i, j);
        }
    }
 
    while(k--) {
        int x, y; cin >> x >> y;
        x--, y--;
 
        cout << val[x][y] << "\n";
    }
 
    return 0;
}

E - Chocolate Bar

题意

对于一个由 $n$ 行 $m$ 列个小格子组成的矩形，我们称之为一块巧克力。对于一块巧克力，我们可以横向或纵向一刀切割为两块子巧克力（小格子是原子性的，无法切割成两部分），每次切割开需要切开长度的平方的代价。给定一块至多 $30\times 30$ 的巧克力，我们可以多次切割得到很多子巧克力，从其中选择一些巧克力，使得选择的巧克力总共恰好含有 $k$ $(k\le 50)$ 个小格子。寻求合法方案的最小代价。

思路

记忆化搜索。dp[i][j][k]表示 $i$ 行 $j$ 列的巧克力，想得到 $k$ 块，需要的最小代价。对于一块巧克力，可以由两个子巧克力横向或纵向拼接得到。也就是说可以枚举当前状态切割能够得到的所有子状态，由子状态转移给当前状态。dp问题复杂度计算方法为状态数量乘转移复杂度，本题有 $n\times m\times k$ 种状态，转移复杂度为 $O((n+m)?k)$ ，故总复杂度为 $O(n^3?k^2)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int dp[33][33][55];
 
int get(int r, int c, int k) {
    if(dp[r][c][k] != -1) return dp[r][c][k];
    if(r*c == k) return dp[r][c][k] = 0;
    if(k == 0) return dp[r][c][k] = 0;
 
    int ret = 0x3f3f3f3f;
 
    for(int t = 1; t<r; t++) {
        int d = r - t;
        for(int a = 0; a<=k; a++) {
            int b = k-a;
            if(t*c >= a && d*c >= b)
                ret = min(ret, get(t, c, a) + get(d, c, b) + c*c);
        }
    }
 
    for(int t = 1; t<c; t++) {
        int d = c - t;
        for(int a = 0; a<=k; a++) {
            int b = k - a;
            if(r*t >= a && r*d >= b)
                ret = min(ret, get(r, t, a) + get(r, d, b) + r*r);
        }
    }
    
    return dp[r][c][k] = ret;
}
 
 
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    memset(dp, -1, sizeof dp);
 
    int n; cin >> n;
    for(int i = 0; i<n; i++) {
        int r,  c, k; cin >> r >> c >> k;
        cout << get(r, c, k) << "\n";
    }
 
    return 0;
}

F - Cut Length

题意

给定一个由 $n$ $(n\le 1000)$ 个点构成的多边形（可凹可凸），给出 $m$ $(m\le 100)$ 次询问， 每次询问给定一条直线，求直线与多边形公共部分的长度。

思路

对于每次询问，解决方式如下。

首先，结合下面的图片，我们感性地思考一下这个问题。直线 $P_1{P}_2$ ，可以将整个二维平面分为左右（相对直线而言）两部分。从边 $AB$ 开始逆时针遍历多边形的所有边，可以发现所有合法部分都是由多边形从右侧跨越到左侧的边和从左侧跨越到右侧的边夹成的。下图中，$BC$ 从右侧跨越到左侧，$CD$ 从左侧跨越到右侧，它们之间的部分为总长度做出贡献。同理，$DE$ 和 $EF$ 之间的部分为总长度做出贡献。同样的， $GH$， $HI$ 与 $IA$ 之间的部分为总长度做出贡献。

接着考虑，“跨越”该如何定义。对于任意一条边，计算其的一个整型值 flag，代表这条边的跨越方式。边和直线所有可能的位置关系如下图所示。

当边的端点在直线两侧时，flag 为 $\pm 2$ 。边的一端在直线上时，flag 为 $\pm 1$ 。边在直线上或与直线不相交，flag为 $0$ 。对于任意的有向线段 $AB$ ，可以通过 $signal(P_1{P}_2\times P_{1}B)?signal(P_1{P}_2\times P_{1}A)$ 快速计算 flag 值的变化，其中 $signal()$ 为符号函数，“$\times$”代表叉乘。

对于任意一条边，处理出来点 $P_1$ 到其的有向距离和 flag 。将所有 flag 不为 $0$ 的边拿出来，忽略 flag 为 $0$ 的边，进行下一步操作。

将些边以 $P_1$ 到其的有向距离为关键字升序排序，从前至后枚举，过程中维护 flag 的前缀。如果前缀不为 $0$ ，说明当前边与下一条边之间的部分为答案作出贡献，将这部分加入到答案中。

代码

#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 1e5;
#define double long double
 
const double eps = 1e-8;
int sign(double x) {
    if(fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}
 
struct Point{
    double x, y;
};
typedef Point Vector;
Vector operator - (Vector a, Vector b) {return Vector{a.x - b.x, a.y - b.y};}
bool operator < (const Point &a, const Point &b) {return a.x < b.x || (a.x == b.x && a.y < b.y);}
double cross(Vector a, Vector b) {return a.x * b.y - a.y * b.x;}
 
double get_length(Point p, Vector v, Point q, Vector w) {
    Vector u = p - q;
    double t = cross(w, u) / cross(v, w);
    return t;
}
 
int n, m;
Point p[maxn];
double solve(Point p1, Point p2) {
    Vector v = p2 - p1;
    vector<pair<double, int> > ans;
    for(int i = 0; i < n; i ++) {
        int f1 = sign(cross(v, p[i] - p1));
        int f2 = sign(cross(v, p[(i + 1) % n] - p1));
        if(f1 == f2) continue;
        double w = get_length(p1, v, p[i], p[(i + 1) % n] - p[i]);
        ans.push_back({w, f1 - f2});
    }
    sort(ans.begin(), ans.end());
    double sum = 0; int flag = 0;
    for(int i = 0; i < ans.size(); i ++) {
        flag += ans[i].second;
        if(flag) sum += ans[i + 1].first - ans[i].first;
    }
    return sum * sqrt(v.x * v.x + v.y * v.y);
}
 
signed main() {
 
    cin >> n >> m;
    for(int i = 0; i<n; i++) cin >> p[i].x >> p[i].y;
    while(m--) {
        Point p1, p2;
        cin >> p1.x >> p1.y >> p2.x >> p2.y;
        printf("%.20Lf\n", solve(p1, p2));
    }
 
    return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖