[AtCoder Beginner Contest 183]解题报告

发布于 2020-11-15  17 次阅读


A - ReLU
水题

#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:
    system("pause");
#endif
}
int n;

inline void solve()
{
    cin>>n;
    if(n<0)
        n = 0;
    cout << n;
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

B - Billiards
水题

#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:
    system("pause");
#endif
}
double sx, sy, gx, gy;

inline void solve()
{
    cin >> sx >> sy >> gx >> gy;
    sy = -sy;
    if (sx == gx)
        return cout << setprecision(12) << sx << endl, void();
    double ans = ((gy - sy) / (gx - sx) * gx - gy) / ((gy - sy) / (gx - sx));
    cout << setprecision(12) << ans << endl;
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

C - Travel
因为 $N=8$，所以路径总数一共也只有 $8!$ 条，直接枚举每一条路线即可。

#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:
    system("pause");
#endif
}
int n;
ll a[10][10];
int p[10];
ll ans, k;

inline void solve()
{
    memarray(a, llinf);
    scanf(
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf(
    for (int i = 1; i <= n; ++i)
        p[i] = i;
    p[n + 1] = 1;
    do
    {
        ll cost = 0;
        for (int i = 1; i <= n; ++i)
        {
            cost += a[p[i]][p[i + 1]];
        }
        if (cost == k)
            ans++;
    } while (next_permutation(p + 2, p + 1 + n));
    cout << ans;
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

D - Water Heater
区间加变成处理差分即可。

#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:
    system("pause");
#endif
}
int n;
ll w;
int s[N], t[N], p[N];
ll c[N];

inline void solve()
{
    scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    for (int i = 1; i <= n; ++i)
    {
        c[t[i]] += p[i];
        c[s[i]] -= p[i];
    }
    for (int i = 2e5; i >= 0; --i)
    {
        c[i] += c[i + 1];
    }
    for (int i = 0; i <= 2e5;++i)
        if(c[i] > w)
            return puts("No"), void();
    puts("Yes");
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

E - Queen on Grid
设 $dp(i,j)$ 表示走到 $(i,j)$ 的方案数，因为每次可以从三个不同的方向，每个方向上不同的格子到达，所以容易写出 dp 方程：
$$
dp(i,j)=\sum\limits_{k=1}^{i-1}dp(k,j)+\sum\limits_{k=1}^{j-1}dp(i,k)+\sum\limits_{k=1}^{\min(i-1,j-1)}dp(i-k,j-k)
$$
分别是上面下来的、左边往右过来的和对角线过来的。用三个前缀和分别维护这三个东西即可。

#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 = 2050;
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:
    system("pause");
#endif
}
ll dp[N][N], sum[3][N][N];
char s[N][N];
int n, m;

inline void solve()
{
    scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    sum[2][0][0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if (s[i][j] == '#')
                continue;
            dp[i][j] += (sum[0][i - 1][j] + sum[1][i][j - 1] + sum[2][i - 1][j - 1])
            dp[i][j]
            sum[0][i][j] = sum[0][i - 1][j] + dp[i][j];
            sum[1][i][j] = sum[1][i][j - 1] + dp[i][j];
            if (i - 1 != 0 || j - 1 != 0)
                sum[2][i][j] = sum[2][i - 1][j - 1] + dp[i][j];
            else
                sum[2][i][j] = 1;
            for (int i = 0; i < 3; ++i)
                sum[i][i][j]
        }
    }
    // for (int i = 1; i <= n; ++i, puts(""))
    //     for (int j = 1; j <= n; ++j)
    //         cout << dp[i][j] << ' ';
    printf(
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

F - Confluence
这个题着实让我体会到什么叫码力不足......
1 操作实际上就是并查集的合并操作。我们考虑如何维护操作 2。
我们可以对每一个集合建立一棵平衡树，键值为班级编号，权值为属于该集合以及该班级的人数。这样，两个集合合并的时候，就是一个平衡树往另外一个平衡树逐点插入的过程。
看到逐点插入，可以想到这其实可以用启发式合并来优化，即把 size（点数） 小的平衡树往大的平衡树插入，并查集就简单用路径压缩优化即可。
这样，总的时间复杂度为 $\mathcal{O}(Q\sigma(N)\log^2N)$

#include <bits/stdc++.h>
// #include <bits/extc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#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;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
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:
    system("pause");
#endif
}
int n, Q, c[N], f[N];
tree<int, int> t[N];
int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); }

inline void solve()
{
    scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    while (Q--)
    {
        int op, a, b;
        scanf(
        if (op == 1)
        {
            int fa = Find(a), fb = Find(b);
            if (fa != fb)
            {
                if (t[fa].size() > t[fb].size())
                    swap(fa, fb);
                while (t[fa].size() > 0)
                {
                    pii now = *t[fa].begin();
                    auto sec = t[fb].find(now.first);
                    if (sec != t[fb].end())
                    {
                        now.second += (*sec).second;
                        t[fb].erase(sec);
                    }
                    t[fb].insert(now);
                    t[fa].erase(t[fa].begin());
                }
                f[fa] = fb;
            }
        }
        else
        {
            int fa = Find(a);
            auto ans = t[fa].find(b);
            if (ans == t[fa].end())
                printf("0\n");
            else
                printf(
        }
    }
}

int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}