[atcoder abc180]解题报告

又好久都没更博客了……
最近的 abc 最后一题画风都有点不太对啊(
比赛链接


A – box
水题

#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, a, b;
inline void solve()
{
    cin >> n >> a >> b;
    cout << n - a + b;
}
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 – Various distances
水题。记得用 long double,不然精度要炸。

#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
}
long double x[N];
int n;
inline void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> x[i];
    long double ans1 = 0, ans2 = 0, ans3 = -llinf;
    for (int i = 1; i <= n; ++i)
        ans1 += fabs(x[i]), ans2 += x[i] * x[i], ans3 = max(ans3, fabs(x[i]));
    cout << setprecision(15) << ans1 << " " << sqrt(ans2) << " " << ans3 << endl;
}
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 – Cream puff
水题

#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
}
ll n;
vector<ll> ans;
inline void solve()
{
    cin >> n;
    for (ll i = 1; i * i < n; ++i)
    {
        if (n % i == 0)
            ans.push_back(i), ans.push_back(n / i);
    }
    if ((ll)sqrt(n) * (ll)sqrt(n) == n)
        ans.push_back((ll)sqrt(n));
    vecupsort(ans);
    for(auto i :ans)
        cout << i << '\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;
}

D – Takahashi Unevolved
贪心,先乘,直到乘以 $A$ 增加的值大于 $B$ 的时候后面就一直加 $B$,即当 $(A-1)X\ge B$ 的时候就一直加 $B$ 就可以了。
不过在判断 $(A-1)X\ge B$ 的时候要爆 long long……无奈之下我就套了个高精度板子上去。

#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
}
// 该模板不可实现负数
// vector 中从高位到低位
// 即输出时需要倒序输出
struct Wint : vector<ll>
{
    Wint(ll n = 0)
    {
        push_back(n);
        check();
    }
    Wint &check()
    {
        while (!empty() && !back())
            pop_back();
        if (empty())
            return *this;
        for (int i = 1; i < (int)size(); ++i)
        {
            (*this)[i] += (*this)[i - 1] / 10;
            (*this)[i - 1] %= 10;
        }
        while (back() >= 10)
        {
            push_back(back() / 10);
            (*this)[size() - 2] %= 10;
        }
        return *this;
    }
};
istream &operator>>(istream &is, Wint &n)
{
    string s;
    is >> s;
    n.clear();
    for (int i = (int)s.size() - 1; i >= 0; --i)
        n.push_back(s[i] - '0');
    return is;
}
ostream &operator<<(ostream &os, const Wint &n)
{
    if (n.empty())
        os << 0;
    for (int i = (int)n.size() - 1; i >= 0; --i)
        os << n[i];
    return os;
}
bool operator!=(const Wint &a, const Wint &b)
{
    if (a.size() != b.size())
        return 1;
    for (int i = (int)a.size() - 1; i >= 0; --i)
        if (a[i] != b[i])
            return 1;
    return 0;
}
bool operator==(const Wint &a, const Wint &b)
{
    return !(a != b);
}
bool operator<(const Wint &a, const Wint &b)
{
    if (a.size() != b.size())
        return a.size() < b.size();
    for (int i = (int)a.size() - 1; i >= 0; --i)
        if (a[i] != b[i])
            return a[i] < b[i];
    return 0;
}
bool operator>(const Wint &a, const Wint &b)
{
    return b < a;
}
bool operator<=(const Wint &a, const Wint &b)
{
    return !(a > b);
}
bool operator>=(const Wint &a, const Wint &b)
{
    return !(a < b);
}
Wint &operator+=(Wint &a, const Wint &b)
{
    if (a.size() < b.size())
        a.resize(b.size());
    for (int i = 0; i != (int)b.size(); ++i)
        a[i] += b[i];
    return a.check();
}
Wint operator+(Wint a, const Wint &b)
{
    return a += b;
}
Wint &operator-=(Wint &a, Wint b)
{
    if (a < b)
        swap(a, b);
    for (int i = 0; i != (int)b.size(); a[i] -= b[i], ++i)
        if (a[i] < b[i])
        {
            int j = i + 1;
            while (!a[j])
                ++j;
            while (j > i)
            {
                --a[j];
                a[--j] += 10;
            }
        }
    return a.check();
}
Wint operator-(Wint a, const Wint &b)
{
    return a -= b;
}
Wint operator*(const Wint &a, const Wint &b)
{
    Wint n;
    if (a.empty() || b.empty())
        return Wint(0);
    n.assign(a.size() + b.size() - 1, 0);
    for (int i = 0; i != (int)a.size(); ++i)
        for (int j = 0; j != (int)b.size(); ++j)
            n[i + j] += a[i] * b[j];
    return n.check();
}
Wint &operator*=(Wint &a, const Wint &b)
{
    return a = a * b;
}
Wint divmod(Wint &a, const Wint &b)
{
    Wint ans;
    for (int t = (int)a.size() - (int)b.size(); a >= b; --t)
    {
        Wint d;
        d.assign(t + 1, 0);
        d.back() = 1;
        Wint c = b * d;
        while (a >= c)
        {
            a -= c;
            ans += d;
        }
    }
    return ans;
}
Wint operator/(Wint a, const Wint &b)
{
    return divmod(a, b);
}
Wint &operator/=(Wint &a, const Wint &b)
{
    return a = a / b;
}
Wint &operator%=(Wint &a, const Wint &b)
{
    divmod(a, b);
    return a;
}
Wint operator%(Wint a, const Wint &b)
{
    return a %= b;
}
Wint Wpow(Wint a, Wint b)
{
    Wint ret = 1;
    while (b != 0)
    {
        if (b % 2 == 1)
            ret = ret * a;
        a = a * a;
        b /= 2;
    }
    return ret;
}
Wint Wpow(Wint a, Wint b, Wint p)
{
    Wint ret = 1;
    while (b != 0)
    {
        if (b % 2 == 1)
            ret = ret * a % p;
        a = a * a % p;
        b /= 2;
    }
    return ret;
}
Wint Wgcd(Wint a, Wint b)
{
    return (b == 0) ? a : Wgcd(b, a % b);
}
Wint A, B, X, Y;
Wint ans;
inline void solve()
{
    cin >> X >> Y >> A >> B;
    while ((A - 1) * X < B && A * X < Y)
    {
        X = A * X;
        ans = ans + 1;
    }
    ans += (Y - 1 - X) / B;
    cout << ans << endl;
}
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 – Traveling Salesman among Aerial Cities
水题。直接把 TSP 状压 dp 板子套上去就可以了。

#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 dp[20][st(17) + 5];
int x[20], y[20], z[20], n;
int cal(int i, int j)
{
    return abs(x[i] - x[j]) + abs(y[i] - y[j]) + max(0, z[i] - z[j]);
}
inline void solve()
{
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i] >> z[i];
    memarray(dp, inf);
    dp[0][0] = 0;
    for (int nowst = 1; nowst < st(n); ++nowst)
    {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
            {
                if ((nowst >> i) & 1)
                    dp[i][nowst] = min(dp[i][nowst], dp[j][nowst - st(i)] + cal(j, i));
            }
    }
    cout << dp[0][st(n) - 1] << '\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 – Unbranched
嘛这个题画风就不太对了……
一开始去想了一下可不可以生成函数搞,类似于整数划分这种,但是想到还可以有环,以及这个题 $n\le 300$ 比较小,那就考虑 dp 算了(
设 $dp(n,m,lim)$ 表示还剩下 $n$ 个点和 $m$ 条边没用,最大的连通分量点数是否等于 $L$,$lim=1$ 表示达到了,$lim=0$ 表示还没有。
转移其实很简单……容易发现初值就是 $dp(i,0,1)=1,i\in [1,n]$,然后每次转移就拿 $k$ 个点组成一个新的连通分量,以及用这 $k$ 个点组成一个环还是一条链。
组成一个环,那么首先要满足的条件就是 $k\ge 2$。并且如果 $k\ge 3$ 的时候,因为这个环顺时针读还是逆时针读是等价的,那么这个环的总数就是 $\frac{(k-1)!}{2}$。然后要考虑哪些标号在这个环上,还要乘以一个组合数 $C_{n-1}^{k-1}$。那么,dp 方程就是 $dp(i,j) += dp(i-k,j-k) \times \frac{(k-1)!}{2} \times C_{n-1}^{k-1}$. 当然,当 $k=2$ 的时候就不用除以 $2$ 了。
组成一个链,那么首先要满足的条件就是 $k\ge 1$。并且如果 $k\ge 2$ 的时候,因为这个链从头到尾读还是从尾到头读是等价的,那么这个链的总数就是 $\frac{k!}{2}$。同样要乘以一个组合数 $C_{n-1}^{k-1}$。那么,dp 方程就是 $dp(i,j) += dp(i-k,j-k+1) \times \frac{k!}{2} \times C_{n-1}^{k-1}$。当然,当 $k=1$ 的时候就不用除以 $2$ 了。
上面 dp 方程没有把 lim 这一维加进去。加上去之后写一发记忆化搜索实际上很贱单,只要中间枚举的时候当前决策用了 $L$ 个点,那么之后的搜索过程 $lim=1$ 一直成立。那么这个题就做完了~

#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 = 350;
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, L;
ll dp[N][N][2], C[N][N];
ll fac[N], inv2;
ll mi(ll a, ll b)
{
    ll ret = 1;
    while (b)
    {
        if (b & 1)
            ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ret;
}
void initC(int lim)
{
    C[0][0] = 1;
    for (int i = 1; i <= lim; ++i)
    {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    }
}
ll work(int n, int m, bool lim)
{
    ll &now = dp[n][m][lim];
    if (!m)
        return lim;
    if (!n)
        return (!m && lim);
    if (now >= 0)
        return now;
    now = 0;
    for (int k = 1; k <= L; ++k)
    {
        if (k <= min(n, m) && k > 1)
        {
            now += work(n - k, m - k, lim || k == L) * fac[k - 1] % MOD * C[n - 1][k - 1] % MOD * ((k > 2) ? inv2 : 1) % MOD;
            now %= MOD;
        }
        if (k <= n && k - 1 <= m)
        {
            now += work(n - k, m - k + 1, lim || k == L) * fac[k] % MOD * C[n - 1][k - 1] % MOD * ((k > 1) ? inv2 : 1) % MOD;
            now %= MOD;
        }
    }
    return now;
}
inline void solve()
{
    memarray(dp, -1);
    fac[0] = 1;
    for (int i = 1; i <= 300; ++i)
        fac[i] = fac[i - 1] * i % MOD;
    inv2 = mi(2, MOD - 2);
    initC(300);
    cin >> n >> m >> L;
    ll ans = work(n, m, 0) % MOD;
    // ans = (ans + MOD) % MOD;
    printf("%lld\n", ans);
}
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;
}

 

发表评论

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