AtCoder Beginner Contest 207

A - Repression

题意：

题解：

代码：

#include <bits/stdc++.h>

#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;

inline int read() {
   int s = 0, w = 1;
   char ch = getchar();
   while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
   while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

int const MAXN = 2e5 + 10;
int n, m, T;

signed main() {
    cin >> n;
    int tmp = (int)floor((double)n * 1.08);
    if (tmp < 206) cout << "Yay!";
    else if (tmp == 206) cout << "so-so";
    else cout << ":(";
    return 0;
}

B - Hydrate

题意：

题解：

代码：

#include <bits/stdc++.h>

#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;

inline int read() {
   int s = 0, w = 1;
   char ch = getchar();
   while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
   while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

int const MAXN = 2e5 + 10;
int n, m, T;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        if ((i + 1) * i / 2 >= n) {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

C - Many Segments

题意：

题解：

代码：

#include <bits/stdc++.h>

#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;

inline int read() {
   int s = 0, w = 1;
   char ch = getchar();
   while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
   while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

int const MAXN = 2e5 + 10;
int n, m, T;
typedef pair<int, int> PII;
PII sec[MAXN];
int attr[MAXN];

bool check(int i, int j) {
    int at1 = attr[i], at2 = attr[j];
    int l1 = sec[i].first, l2 = sec[j].first;
    int r1 = sec[i].second, r2 = sec[j].second;
    if (l2 <= l1) {
        swap(at1, at2);
        swap(l1, l2);
        swap(r1, r2);
    }
    if (l2 == r1) {
        return (at1 == 1 || at1== 3) && (at2 == 1 || at2 == 2);
    }
    else if (l2 < r1) {
        return 1;
    }
    return 0;
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> attr[i] >> sec[i].first >> sec[i].second;
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (check(i, j)) res++;
        }
    }
    cout << res;
    return 0;
}

D - Congruence Points

题意： 给定2个点集S和T，均含义N个点，问能否将点集S进行任意次操作得到T，每次操作可以将S绕某个点p旋转任意角度。能的话输出Yes，不能的话输出No。 $1 < = N < = 100, ? 10 < = 坐标 x 和坐标 y < = 10$

题解： 问2个点集能够通过旋转平移相等，那么首先求出各自的重心，然后减去重心的偏移量使得二者的重心都变为原点。然后就只需要判断是否能够通过旋转某个角度p，使得二者重合即可。旋转时只需要去枚举所有的(b[i].x, b[i].y)旋转到(a[1].x, a[1].y)，这样就不需要考虑旋转角的精度问题（大概大家第一眼考虑选择都是想着枚举0 ~ 360度，这样就会产生误差）。旋转判定O(n^3)

代码：

#include <bits/stdc++.h>

#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;

inline int read() {
   int s = 0, w = 1;
   char ch = getchar();
   while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
   while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

int const MAXN = 2e5 + 10;
int n, m, T;
const double eps = 1e-8;

int sgn(double x) {
    if (fabs(x) < eps) return 0;  // =0
    if (x < 0)
        return -1;  // < 0
    else
        return 1;  // > 0
}

struct Point {
    double x, y;
    Point() {}
    Point(double _x, double _y) {
        x = _x;
        y = _y;
    }
    void input() { scanf("%lf%lf", &x, &y); }
    bool operator==(Point b) const {
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator<(Point b) const {
        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0 : x < b.x;
    }
    Point operator-(const Point &b) const { return Point(x - b.x, y - b.y); }
    //叉积
    double operator^(const Point &b) const { return x * b.y - y * b.x; }
    //点积
    double operator*(const Point &b) const { return x * b.x + y * b.y; }
    Point rotate(Point p, double angle) {
        Point v = (*this) - p;
        double c = cos(angle), s = sin(angle);
        return Point(p.x + v.x * c - v.y * s, p.y + v.x * s + v.y * c);
    }
}a[MAXN], b[MAXN];
double core_a1 = 0, core_a2 = 0, core_b1 = 0, core_b2 = 0;

signed main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        a[i].input();
        core_a1 += a[i].x, core_a2 += a[i].y;
    }
    core_a1 /= n, core_a2 /= n;

    for (int i = 1; i <= n; ++i) {
        b[i].input();
        core_b1 += b[i].x, core_b2 += b[i].y;
    }
    core_b1 /= n, core_b2 /= n;

    for (int i = 1; i <= n; ++i) a[i].x -= core_a1, a[i].y -= core_a2, b[i].x -= core_b1, b[i].y -= core_b2;
    for (int i = 1; i <= n; ++i) {
        if (sgn(a[i].x) != 0 && sgn(a[i].y) != 0) {
            swap(a[i].x, a[1].x);
            swap(a[i].y, a[1].y);
            break;
        }
    }

    Point origin(0, 0);
    for (int i = 1; i <= n; ++i) {
        double angle = atan2(a[1].y, a[1].x) - atan2(b[i].y, b[i].x);
        int flg2 = 1;
        for (int j = 1; j <= n; ++j) {
            Point tmp = b[j].rotate(origin, angle);
            int flg = 0;
            for (int k = 1; k <= n; ++k) {
                if (sgn(a[k].x - tmp.x) == 0 && sgn(a[k].y - tmp.y) == 0) {
                    flg = 1;
                    break;
                }
            }
            if (!flg) flg2 = 0;
        }
        if (flg2) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";

    return 0;
}

E - Mod i

题意： 给定长度为n的数组a，问将数组分为k段，且要求第i段的元素累加和满足 $b_i \% i == 0$ ，那么合法的分割方案有多少种？ $1<=N<=3000, 1<=A_i<=1e15$

题解： dp。比较显然能够看出来是一个dp， $d p [i] [j]$ ：前i个数字，分为j段。也比较显然能够写出状态转移方程：$dp[i][j] = \sum_{sum(1, i) % j == sum(1, k) % j}dp[k][j-1] $，但是如果直接 d p 就会发现是$ O(n^3)$的。因此需要优化。

观察这个dp式子，发现其实j确定时， $d p [i] [j]$ 只和 $d p [k] [j ? 1]$ 有关，即j的状态全为j-1转移而来，那么我们枚举的时候就可以先枚举j再去枚举i，同时从上面的转移方程也可以看出来这个式子其实是前缀和，因此可以使用前缀和去优化。

代码：

#include <bits/stdc++.h>

#define int long long
#define debug(x) cout << #x << " = " << x << endl;
using namespace std;

int const MAXN = 3e3 + 10, mod = 1e9 + 7;
int n, m, T, a[MAXN], dp[MAXN][MAXN], f[MAXN][MAXN], sum[MAXN];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], sum[i] = sum[i - 1] + a[i];
    // dp[i][j] = [累加]dp[k][j-1] (sum(1, i) % j == sum(1, k) % j)
    // dp[i][j]：前i个数字，分为j段
    f[0][0] = 1;
    for (int j = 1; j <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            dp[i][j] = f[sum[i] % j][j - 1];
            f[sum[i] % j][j - 1] = (f[sum[i] % j][j - 1] + dp[i][j - 1]) % mod;
        }
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) res = (res + dp[n][i]) % mod;
    cout << res;
    return 0;
}