[atcoder abc181]解題報告

题目都还是挺套路的
比赛链接

A Heavy Rotation

水题

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
int n;
inline void solve()
{
    cin >> n;
    puts((n % 2 == 0) ? "White" : "Black");
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}
B Trapezoid Sum

水题

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
int n;
unsigned ll ans;
unsigned ll f(unsigned ll x) { return x * (x + 1) / 2; }
inline void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        ll l, r;
        cin >> l >> r;
        ans += f(r) - f(l - 1);
    }
    cout << ans << '\n';
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}
C Collinearity

水题。用叉积判一下就行。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
int n;
pair<ll, ll> p[N];
bool check(int i, int j, int k)
{
    pair<ll, ll> v1 = mp(p[i].first - p[j].first, p[i].second - p[j].second);
    pair<ll, ll> v2 = mp(p[j].first - p[k].first, p[j].second - p[k].second);
    if(v1.first * v2.second - v1.second * v2.first == 0)
        return 1;
    return 0;
}
inline void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> p[i].first >> p[i].second;
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
            for (int k = j + 1; k <= n; ++k)
            {
                if(check(i,j,k))
                    return puts("Yes"), void();
            }
    puts("No");
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}
D Hachi

注意到 $1000 \bmod 8 = 0$,那么实际上我们只需要注重最后三位的数字就可以了。只需要枚举 8 的倍数,直到这个数大于 3 位为止就行。
不过要注意 $n\le 2$ 的时候特判一下。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
int n;
char s[N];
int cnt[15];
inline void solve()
{
    scanf("%s", s);
    n = strlen(s);
    for (int i = 0; i < n; ++i)
        cnt[s[i] - '0']++;
    if (n == 1)
    {
        return puts((cnt[8]) ? "Yes" : "No"), void();
    }
    if (n == 2)
    {
        for (int d = 2;; ++d)
        {
            int now = d * 8;
            if (now > 100)
                break;
            int need[15] = {0};
            while (now)
            {
                need[now % 10]++;
                now /= 10;
            }
            bool yes = 1;
            for (int i = 0; i <= 9; ++i)
                if (need[i] > cnt[i])
                    yes = 0;
            if (yes)
                return puts("Yes"), void();
        }
        return puts("No"), void();
    }
    if (n >= 3)
    {
        for (int d = 13;; ++d)
        {
            int now = d * 8;
            if (now > 1000)
                break;
            int need[15] = {0};
            while (now)
            {
                need[now % 10]++;
                now /= 10;
            }
            bool yes = 1;
            for (int i = 0; i <= 9; ++i)
                if (need[i] > cnt[i])
                    yes = 0;
            if (yes)
                return puts("Yes"), void();
        }
        return puts("No"), void();
    }
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}
E Transformable Teacher

首先把 h 从小到大排序,显然最优解就是相邻两个人配对。将自己插进队之后方案是唯一的,接下来就观察答案的贡献部分。因为是相邻两个人配对,我们插进去之后实际上只会改变相邻的贡献,插入位置之前以及之后的配对情况不会改变,但是前面与后面的奇偶性不一样。所以我们记录两个前缀和,一个是偶数坐标的,一个是奇数坐标的,然后二分查找当前 $W_i$ 对应的应该插入的位置,之后三个部分分别计算即可。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
int n, m;
int h[N], w[N];
int ans = inf;
int sum1[N], sum2[N];
inline void solve()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &h[i]);
    for (int i = 1; i <= m; ++i)
        scanf("%d", &w[i]);
    sort(h + 1, h + n + 1);
    for (int i = 1, j = 2; i <= n; i += 2, j += 2)
    {
        sum1[i] = sum1[max(i - 2, 0)] + h[i + 1] - h[i];
        sum2[j] = sum2[j - 2] + h[j + 1] - h[j];
    }
    for (int i = 1; i <= m; ++i)
    {
        int pos = lower_bound(h + 1, h + n + 1, w[i]) - h;
        int tmp = 0;
        if (pos & 1)
        {
            tmp += h[pos] - w[i];
            tmp += sum1[pos - 2];
            tmp += sum2[n - 1] - sum2[pos - 1];
        }
        else
        {
            tmp += w[i] - h[pos - 1];
            tmp += sum1[pos - 3];
            tmp += sum2[n - 1] - sum2[pos - 2];
        }
        ans = min(ans, tmp);
    }
    cout << ans << '\n';
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}
F Silver Woods

套路题。显然答案是有单调性的,我们二分当前答案 $r$,接下来考虑怎么 check。
可以发现,两点的距离如果大于等于这个圆的直径的话,那么这个圆就可以穿过这两个点中间。而对于点到边界的话就是做一条垂线即可。
假设两点之间的距离小于直径,可以认为这两个点之间有一堵“墙”,总之圆是无法穿过去的。那么我们枚举所有的点对,如果这个点对间的距离小于直径,就将这两个点放入一个集合内。以及把上下边界分别看成两个点,距离就是垂线长度。如果上下边界在一个集合内的话,就相当于有一堵连续的墙连接了上下边界,这样这个圆就永远过不去了。上面就是check过程。

#include <bits/stdc++.h>
#define ll long long
#define ls id << 1
#define rs id << 1 | 1
#define mem(array, value, size, type) memset(array, value, ((size) + 5) * sizeof(type))
#define memarray(array, value) memset(array, value, sizeof(array))
#define fillarray(array, value, begin, end) fill((array) + (begin), (array) + (end) + 1, value)
#define fillvector(v, value) fill((v).begin(), (v).end(), value)
#define pb(x) push_back(x)
#define st(x) (1LL << (x))
#define pii pair<int, int>
#define mp(a, b) make_pair((a), (b))
#define Flush fflush(stdout)
#define vecfirst (*vec.begin())
#define veclast (*vec.rbegin())
#define vecall(v) (v).begin(), (v).end()
#define vecupsort(v) (sort((v).begin(), (v).end()))
#define vecdownsort(v, type) (sort(vecall(v), greater<type>()))
#define veccmpsort(v, cmp) (sort(vecall(v), cmp))
using namespace std;
const int N = 500050;
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0);
clock_t TIME__START, TIME__END;
void program_end()
{
#ifdef ONLINE
    printf("\n\nTime used: %.6lf(s)\n", ((double)TIME__END - TIME__START) / 1000);
    system("pause");
#endif
}
int n;
pair<double, double> p[N];
int f[N];
int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); }
void Union(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    if (fx != fy)
        f[fy] = fx;
}
bool check(double r)
{
    for (int i = 1; i <= n + 2; ++i)
        f[i] = i;
    for (int i = 1; i <= n; ++i)
    {
        if (fabs(p[i].second - 100) < r * 2)
            Union(i, n + 1);
        if (fabs(p[i].second + 100) < r * 2)
            Union(i, n + 2);
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i + 1; j <= n; ++j)
        {
            if (hypot(p[i].first - p[j].first, p[i].second - p[j].second) < 2 * r)
            {
                Union(i, j);
            }
        }
    return Find(n + 1) != Find(n + 2);
}
inline void solve()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lf%lf", &p[i].first, &p[i].second);
    double l = 0, r = 100.0;
    int cnt = 0;
    while ((cnt++) < 50)
    {
        double mid = (l + r) / 2;
        if (check(mid) == 0)
            r = mid;
        else
            l = mid;
    }
    printf("%.9lf\n", l);
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf("%d", &Test);
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注