Skip to content

2020 牛客国庆集训派对 Day1

Contents

Contest Info

Practice Link

Solved A B C D E F G H I J
6/10 O O O O O - - O - -
  • O 在比赛中通过
  • Ø 赛后通过
  • ! 尝试了但是失败了
  • - 没有尝试

Solutions

Problem A. ABB

Solved By Dup4. 00:08(+)

题意

给出一个字符串 S，问在该字符串末尾最少添加多少个字符使得该字符串能够变成一个回文串？

思路

找一个最长的回文后缀，然后在末尾补齐前缀所对应的回文的那部分即可。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 4e5 + 10;
int n;
char s[N];

struct Manacher {
    int len, l;
    char Ma[N << 1];
    int Mp[N << 1];
    void work(char *s) {
        len = strlen(s);
        l = 0;
        Ma[l++] = '$';
        Ma[l++] = '#';
        for (int i = 0; i < len; ++i) {
            Ma[l++] = s[i];
            Ma[l++] = '#';
        }
        Ma[l] = 0;
        int mx = 0, id = 0;
        for (int i = 0; i < l; ++i) {
            Mp[i] = mx > i ? min(Mp[2 * id - i], mx - i) : 1;
            while (Ma[i + Mp[i]] == Ma[i - Mp[i]]) Mp[i]++;
            if (i + Mp[i] > mx) {
                mx = i + Mp[i];
                id = i;
            }
        }
    }
    bool check(int l, int r) {
        int il = (l + 1) * 2, ir = (r + 1) * 2;
        int mid = (il + ir) / 2;
        int len = (r - l + 2) / 2;
        return (Mp[mid] / 2) >= len;
    }
} man;

void run() {
    rd(n);
    cin >> s;
    man.work(s);
    for (int i = 0; i < n; ++i) {
        if (man.check(i, n - 1))
            return pt(i);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem B. Be Geeks!

Solved By Dup4. 01:19(+2)

题意

给出一个长度为 n 的序列 a_i, 定义：

  • G(i, j) = \gcd(a_i, a_{i + 1}, \cdots, a_j)
  • M(i, j) = \max(a_i, a_{i + 1}, \cdots, a_j)
  • P(i, j) = G(i, j) \cdot M(i, j)
  • F(A) = \sum P(i, j)

然后就是要求 F(A)。

思路

简单来说，就是求这个序列当中任意一个连续子序列的最大值乘上子序列的最大公约数的总和。

  • 首先我们通过笛卡尔树，求出每个值它所控制的那段范围。
  • 然后枚举每个值作为最大值，并且假设它控制的那段字段为 [l_i, r_i], 然后枚举短的那边，用二分去弄另一边。能这么做的原因是因为，一段序列中，控制了起点，对于不同终点来说，只有 \mathcal{O}(\log n) 个不同的最大公约数。
Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 2e5 + 10;
constexpr int INF = 0x3f3f3f3f;
int n, a[N];
pII r[N];

struct Cartesian_Tree {
    struct node {
        int id, val, fa;
        int son[2];
        node() {}
        node(int id, int val, int fa) : id(id), val(val), fa(fa) {
            son[0] = son[1] = 0;
        }
        bool operator<(const node &other) const {
            return val > other.val;
        }
    } t[N];
    int root;
    void init() {
        t[0] = node(0, INF, 0);
    }
    void build(int n, int *a) {
        for (int i = 1; i <= n; ++i) {
            t[i] = node(i, a[i], 0);
        }
        for (int i = 1; i <= n; ++i) {
            int k = i - 1;
            while (t[i] < t[k]) {
                k = t[k].fa;
            }
            t[i].son[0] = t[k].son[1];
            t[k].son[1] = i;
            t[i].fa = k;
            t[t[i].son[0]].fa = i;
        }
        root = t[0].son[1];
    }
    int dfs(int u) {
        if (!u)
            return 0;
        int lsze = dfs(t[u].son[0]);
        int rsze = dfs(t[u].son[1]);
        r[t[u].id] = pII(lsze, rsze);
        return lsze + rsze + 1;
    }
} CT;

template <typename RMQItem, RMQItem base>
struct RMQ {
    vector<RMQItem> v;
    vector<vector<RMQItem>> tl, tr;
    RMQItem op(const RMQItem &a, const RMQItem &b) {
        return __gcd(a, b);
    }
    int log2Up(int n) {
        int res = 0;
        while ((1 << res) < n) res++;
        return res;
    }
    RMQ() {}
    RMQ(const vector<RMQItem> &a) {
        int n = a.size();
        v = a;
        tl = tr = vector<vector<RMQItem>>(log2Up(n) + 1, vector<RMQItem>(n));
        for (int k = 0; (1 << k) <= n; ++k) {
            int ones = (1 << k) - 1;
            RMQItem tmp = base;
            for (int i = 0; i < n; ++i) {
                tmp = op(tmp, a[i]);
                tl[k][i] = tmp;
                if ((i & ones) == ones)
                    tmp = base;
            }
            tmp = base;
            for (int i = n - 1; i >= 0; --i) {
                tmp = op(tmp, a[i]);
                tr[k][i] = tmp;
                if ((i & ones) == 0)
                    tmp = base;
            }
        }
    }
    RMQItem query(int l, int r) {
        --l, --r;
        if (l == r)
            return v[l];
        int num = 31 - __builtin_clz(l ^ r);
        return op(tl[num][r], tr[num][l]);
    }
};
RMQ<int, 0> rmq;

int gao(int l, int r, int _g) {
    if (l > r)
        return 0;
    int res = 0;
    while (l <= r) {
        _g = __gcd(_g, a[l]);
        int _l = l, _r = r, pos = _l;
        while (_r - _l >= 0) {
            int mid = (_l + _r) >> 1;
            if (rmq.query(l, mid) % _g == 0) {
                pos = mid;
                _l = mid + 1;
            } else {
                _r = mid - 1;
            }
        }
        chadd(res, 1ll * (pos - l + 1) * _g % mod);
        l = pos + 1;
    }
    return res;
}

int gao1(int l, int r, int _g) {
    if (l > r)
        return 0;
    int res = 0;
    while (l <= r) {
        _g = __gcd(_g, a[r]);
        int _l = l, _r = r, pos = _r;
        while (_r - _l >= 0) {
            int mid = (_l + _r) >> 1;
            if (rmq.query(mid, r) % _g == 0) {
                pos = mid;
                _r = mid - 1;
            } else {
                _l = mid + 1;
            }
        }
        chadd(res, 1ll * (r - pos + 1) * _g % mod);
        r = pos - 1;
    }
    return res;
}

void run() {
    rd(n);
    for (int i = 1; i <= n; ++i) rd(a[i]);
    CT.init();
    CT.build(n, a);
    CT.dfs(CT.root);
    vector<int> vec(a + 1, a + 1 + n);
    rmq = RMQ<int, 0>(vec);
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        int now = 0;
        if (r[i].fi < r[i].se) {
            int _g = 0;
            for (int j = 0; j <= r[i].fi; ++j) {
                _g = __gcd(_g, a[i - j]);
                chadd(now, gao(i, i + r[i].se, _g));
            }
        } else {
            int _g = 0;
            for (int j = 0; j <= r[i].se; ++j) {
                _g = __gcd(_g, a[i + j]);
                chadd(now, gao1(i - r[i].fi, i, _g));
            }
        }
        chadd(res, 1ll * now * a[i] % mod);
        //		dbg(i, i - r[i].fi, i + r[i].se, now);
    }
    pt(res);
}

int main() {
    //	ios::sync_with_stdio(false);
    //	cin.tie(nullptr); cout.tie(nullptr);
    //	cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem C. Bob in Wonderland

Solved By Dup4. 01:50(+1)

题意

给出一棵树，每次可以断掉一条边变成两个连通块，然后可以加入一条边，将两个连通块连通。

问最少多少次操作可以将这棵树变成一个链。

思路

如果是一棵有根树，那么贪心策略是固定的，就是对于一个点，假设它的孩子有 x 个，那么对于这个点，要断掉 x - 1 条边。

现在的问题是，这是一棵无根树，那么换根 DP 一下即可。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 3e5 + 10;
constexpr int INF = 0x3f3f3f3f;
int n, f[N], g[N], fa[N], sze[N];
vector<vector<int>> G;

void dfs(int u) {
    sze[u] = 0;
    for (auto &v : G[u]) {
        if (v == fa[u])
            continue;
        fa[v] = u;
        dfs(v);
        ++sze[u];
        f[u] += f[v];
    }
    f[u] += max(0, sze[u] - 1);
}

void dfs1(int u) {
    for (auto &v : G[u]) {
        if (v == fa[u])
            continue;
        int _g = g[u];
        if (u == 1)
            _g += max(0, sze[u] - 2);
        else
            _g += max(0, sze[u] - 1);
        _g += f[u];
        _g -= f[v];
        _g -= max(0, sze[u] - 1);
        g[v] += _g;
        dfs1(v);
    }
}

void run() {
    rd(n);
    G.clear();
    G.resize(n + 1);
    for (int i = 1, u, v; i < n; ++i) {
        rd(u, v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    memset(f, 0, sizeof f);
    memset(g, 0, sizeof g);
    fa[1] = 0;
    dfs(1);
    dfs1(1);
    int res = INF;
    for (int i = 1; i <= n; ++i) {
        chmin(res, f[i] + g[i]);
        //	dbg(2, f[i] + g[i]);
    }
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem D. Deep800080

Solved By Dup4 & lts. 04:50(+7)

题意

给出 n 个点，然后可以在通过 (0, 0) 到 (A, B) 的这条直线上找一个点画一个圆，半径为 R，使得这个圆能够覆盖到尽可能多的点。

问最多能覆盖到多少个点？

思路

以每个点为圆心，半径为 R 画圆，然后它会跟那条直线最多相交两个点，只要我们选的点落在这两个点确定的线段之内，这个点就可以被覆盖。

那么问题变成了，有若干条线段，问被线段覆盖次数最多的点被覆盖了多少次？

至于精度问题的话，扩大一下转化成整数会好做一点。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
using pDD = pair<db, db>;
using pDI = pair<db, int>;
using pLI = pair<ll, int>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 3e5 + 10;
int n, r, a, b;

const db eps = 1e-5;
const db PI = acos(-1.0L);
int sgn(db x) {
    if (fabs(x) < eps)
        return 0;
    return x < 0 ? -1 : 1;
}
db sqr(db x) {
    return x * x;
}
db fixOut(db x) {
    if (sgn(x) == 0)
        return 0;
    return x;
}

struct Point {
    db x, y;
    Point(db x = 0, db y = 0) : x(x), y(y) {}
    void scan() {
        rd(x, y);
    }
    bool operator==(const Point &b) const {
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator<(const 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);
    }
    Point operator-(const Point &b) const {
        return Point(x - b.x, y - b.y);
    }
    Point operator*(const db &b) const {
        return Point(x * b, y * b);
    }
    Point operator/(const db &b) const {
        return Point(x / b, y / b);
    }
    db operator^(const Point &b) const {
        return x * b.y - y * b.x;
    }
    db operator*(const Point &b) const {
        return x * b.x + y * b.y;
    }
    db len() {
        return hypot(x, y);
    }
    db len2() {
        return x * x + y * y;
    }
    db dis(Point b) {
        return hypot(x - b.x, y - b.y);
    }
    db dis2(Point b) {
        return (x - b.x) * (x - b.x) + (y - b.y) * (y - b.y);
    }
    Point trunc(db r) {
        db l = len();
        if (!sgn(l))
            return *this;
        r /= l;
        return Point(x * r, y * r);
    }
};

struct Line {
    Point s, e;
    Line() {}
    Line(Point s, Point e) : s(s), e(e) {}
    bool operator==(const Line &b) const {
        return s == b.s && e == b.e;
    }
    void adjust() {
        if (e < s)
            swap(s, e);
    }
    db length() {
        return s.dis(e);
    }
    db getAngle() {
        db k = atan2(e.y - s.y, e.x - s.x);
        if (sgn(k) < 0)
            k += PI;
        if (sgn(k - PI) == 0)
            k -= PI;
        return k;
    }
    int relationPoint(Point p) {
        int c = sgn((p - s) ^ (e - s));
        if (c < 0)
            return 1;
        if (c > 0)
            return 2;
        return 3;
    }
    bool pointOnSeg(Point p) {
        return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0;
    }
    bool parallel(Line b) {
        return sgn((e - s) ^ (b.e - b.s)) == 0;
    }
    int segCrossSeg(Line b) {
        int d1 = sgn((e - s) ^ (b.s - s));
        int d2 = sgn((e - s) ^ (b.e - s));
        int d3 = sgn((b.e - b.s) ^ (s - b.s));
        int d4 = sgn((b.e - b.s) ^ (e - b.s));
        if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2)
            return 2;
        return ((d1 == 0 && sgn((b.s - s) * (b.s - e)) <= 0) || (d2 == 0 && sgn((b.e - s) * (b.e - e)) <= 0) ||
                (d3 == 0 && sgn((s - b.s) * (s - b.e)) <= 0) || (d4 == 0 && sgn((e - b.s) * (e - b.e)) <= 0));
    }
    db disPointToLine(Point p) {
        return fabs((p - s) ^ (e - s)) / length();
    }
    db disPointToSeg(Point p) {
        if (sgn((p - s) * (e - s)) < 0 || sgn((p - e) * (s - e)) < 0)
            return min(p.dis(s), p.dis(e));
        return disPointToLine(p);
    }
    Point lineProg(Point p) {
        return s + (((e - s) * ((e - s) * (p - s))) / ((e - s).len2()));
    }
};

struct Circle {
    Point p;
    db r;
    Circle() {}
    Circle(Point p, db r) : p(p), r(r) {}
    Circle(db x, db y, db r) : p(Point(x, y)), r(r) {}
    bool operator==(const Circle &b) const {
        return (p == b.p) && sgn(r - b.r) == 0;
    }
    bool operator<(const Circle &b) const {
        return ((p < b.p) || ((p == b.p) && sgn(r - b.r) < 0));
    }
    db area() {
        return PI * r * r;
    }
    db circumference() {
        return PI * r * 2;
    }
    Point getPoint(db rad) {
        return Point(p.x + cos(rad) * r, p.y + sin(rad) * r);
    }
    int relationPoint(Point b) {
        db dis = b.dis(p);
        if (sgn(dis - r) < 0)
            return 2;
        if (sgn(dis - r) == 0)
            return 1;
        return 0;
    }
    int relationSeg(Line b) {
        db dis = b.disPointToSeg(p);
        if (sgn(dis - r) < 0)
            return 2;
        if (sgn(dis - r) == 0)
            return 1;
        return 0;
    }
    int relationLine(Line b) {
        db dis = b.disPointToLine(p);
        if (sgn(dis - r) < 0)
            return 2;
        if (sgn(dis - r) == 0)
            return 1;
        return 0;
    }
    int pointCrossLine(Line b, Point &p1, Point &p2) {
        if (!(*this).relationLine(b))
            return 0;
        Point a = b.lineProg(p);
        db d = b.disPointToLine(p);
        d = sqrt(r * r - d * d);
        if (sgn(d) == 0) {
            p1 = p2 = a;
            return 1;
        }
        p1 = a + (b.e - b.s).trunc(d);
        p2 = a - (b.e - b.s).trunc(d);
        return 2;
    }
};

void run() {
    rd(n, r, a, b);
    Line l = Line(Point(0, 0), Point(a, b));
    int f = 0;
    if (a == 0)
        f = 1, a = b;
    int L = 0, R = a;
    if (L > R)
        swap(L, R);
    vector<pLI> vec, _vec;
    for (int i = 1; i <= n; ++i) {
        Point p;
        p.scan();
        Point p1, p2;
        Circle c = Circle(p, r);
        int num = c.pointCrossLine(l, p1, p2);
        if (f)
            swap(p1.x, p1.y), swap(p2.x, p2.y);
        if (num) {
            db l = p1.x;
            db r = p2.x;
            if (sgn(l - r) > 0)
                swap(l, r);
            //	if (sgn(l - R) > 0) continue;
            //	if (sgn(L - r) > 0) continue;
            //	if (sgn(L - l) > 0) l = L;
            //	if (sgn(r - R) > 0) r = R;
            ll _l = ll(l * 1000000);
            ll _r = ll(r * 1000000);
            vec.push_back(pLI(_l, 1));
            vec.push_back(pLI(_r + 1, -1));
        }
    }
    sort(all(vec), [&](pLI a, pLI b) {
        return a.fi < b.fi;
    });
    for (auto &it : vec) {
        if (_vec.empty())
            _vec.push_back(it);
        else {
            if (it.fi == _vec.back().fi)
                _vec.back().se += it.se;
            else {
                _vec.push_back(it);
            }
        }
    }
    int res = 0, now = 0;
    for (auto &it : _vec) {
        now += it.se;
        chmax(res, now);
    }
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem E. Zeldain Garden

Solved By Dup4. 01:28(+)

题意

求 [l, r] 中每个数的因数个数之和。

思路

[1, n] 中的因子数之和的答案是 \displaystyle \sum\limits_{i = 1}^n \lfloor \frac{n}{i} \rfloor。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e5 + 10;
int n;
ll l, r;

ll gao(ll n) {
    if (n < 0)
        return 0;
    if (n == 1)
        return 1;
    ll sq = sqrt(n);
    while (sq * sq <= n) ++sq;
    while (sq * sq > n) --sq;
    ll res = 0;
    for (ll i = 1; i <= sq; ++i) {
        res += n / i;
    }
    res *= 2;
    res -= sq * sq;
    return res;
}

void run() {
    rd(l, r);
    pt(gao(r) - gao(l - 1));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    // nextInt();
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem F. Light Emitting Hindenburg

Upsolved By -.

题意

思路

Problem G. K==S

Upsolved By -.

题意

思路

Problem H. Ponk Warshall

Solved By Dup4 & lts. 02:26(+)

题意

给出连个个字符串 S 和 T，并且只有四种字符 A,C,G,T，只有一种操作，就是交换 S 中任意两个位置的字符，问最少需要多少次操作能够将 S 变成 T。

思路

对于一个环，那么需要 \mbox{环的长度} - 1环的长度 次操作能够将这个环上的每一对都复原。

比如说 AC 和 CA，只需要一次交换。

并且环的长度越小越好，即环的个数越多越好。

我们虽然不知道怎么证，但是我们能猜出来贪心先去找二元环，再去找三元环，再去找四元环即可。

Code 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define mkp make_pair
#define all(x) (x).begin(), (x).end()
using db = double;
using ll = long long;
using ull = unsigned long long;
using pII = pair<int, int>;
using pLL = pair<ll, ll>;
using pCC = pair<char, char>;
constexpr int mod = 1e9 + 7;
template <class T1, class T2>
inline void chadd(T1 &x, T2 y, int Mod = mod) {
    x += y;
    while (x >= Mod) x -= Mod;
    while (x < 0) x += Mod;
}
template <class T1, class T2>
inline void chmax(T1 &x, T2 y) {
    if (x < y)
        x = y;
}
template <class T1, class T2>
inline void chmin(T1 &x, T2 y) {
    if (x > y)
        x = y;
}
inline int nextInt() {
    int x;
    cin >> x;
    return x;
}
void rd() {}
template <class T, class... Ts>
void rd(T &arg, Ts &...args) {
    cin >> arg;
    rd(args...);
}
#define dbg(x...)                             \
    do {                                      \
        cout << "\033[32;1m" << #x << " -> "; \
        err(x);                               \
    } while (0)
void err() {
    cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T &arg, const Ts &...args) {
    cout << arg << ' ';
    err(args...);
}
template <template <typename...> class T, typename t, typename... A>
void err(const T<t> &arg, const A &...args) {
    for (auto &v : arg) cout << v << ' ';
    err(args...);
}
void ptt() {
    cout << endl;
}
template <class T, class... Ts>
void ptt(const T &arg, const Ts &...args) {
    cout << ' ' << arg;
    ptt(args...);
}
template <class T, class... Ts>
void pt(const T &arg, const Ts &...args) {
    cout << arg;
    ptt(args...);
}
void pt() {}
template <template <typename...> class T, typename t, typename... A>
void pt(const T<t> &arg, const A &...args) {
    for (int i = 0, sze = arg.size(); i < sze; ++i) cout << arg[i] << " \n"[i == sze - 1];
    pt(args...);
}
inline ll qpow(ll base, ll n) {
    assert(n >= 0);
    ll res = 1;
    while (n) {
        if (n & 1)
            res = res * base % mod;
        base = base * base % mod;
        n >>= 1;
    }
    return res;
}
// head
constexpr int N = 1e6 + 10;
int n;
char s[N], t[N];
map<pCC, int> mp;

void run() {
    cin >> (s + 1) >> (t + 1);
    n = strlen(s + 1);
    //	int cnt = 0;
    //	for (auto &c1 : {'A', 'C', 'G', 'T'}) {
    //		for (auto &c2 : {'A', 'C', 'G', 'T'}) {
    //			if (c1 != c2) {
    //				mp[pCC(c1, c2)] = ++cnt;
    //			}
    //		}
    //	}
    for (int i = 1; i <= n; ++i) {
        char c1 = s[i];
        char c2 = t[i];
        if (c1 != c2) {
            ++mp[pCC(c1, c2)];
        }
    }
    int res = 0;
    vector<char> vec({'A', 'C', 'G', 'T'});
    for (auto &c1 : vec) {
        for (auto &c2 : vec) {
            if (c1 != c2) {
                pCC t1 = pCC(c1, c2);
                pCC t2 = pCC(c2, c1);
                int Min = min(mp[t1], mp[t2]);
                res += Min;
                mp[t1] -= Min;
                mp[t2] -= Min;
            }
        }
    }
    do {
        char c1 = vec[0], c2 = vec[1], c3 = vec[2];
        pII t1 = pCC(c1, c2);
        pII t2 = pCC(c2, c3);
        pII t3 = pCC(c3, c1);
        int Min = min({mp[t1], mp[t2], mp[t3]});
        res += Min * 2;
        mp[t1] -= Min;
        mp[t2] -= Min;
        mp[t3] -= Min;
    } while (next_permutation(all(vec)));
    int sum = 0;
    for (auto &it : mp) sum += it.se;
    assert(sum % 4 == 0);
    res += sum / 4 * 3;
    pt(res);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(20);
    int _T = 1;
    while (_T--) run();
    //    for (int kase = 1; kase <= _T; ++kase) {
    //        cout << "Case #" << kase << ": ";
    //        run();
    //    }
    //	while (cin >> n) run();
    //	run();
    return 0;
}

Problem I. Saba1000kg

Upsolved By -.

题意

思路

Problem J. The Bugs

Upsolved By -.

题意

思路

Last update: March 24, 2022
Created: March 23, 2022
Back to top