[atcoder abc179]解題報告

好久都没写 atcoder 的题解了
还是先从 abc 开始吧(
比赛链接


A – Plural Form
签到题(

#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
}
char s[N];
inline void solve()
{
    cin >> s;
    int n = strlen(s);
    if(s[n-1] == 's')
        s[n] = 'e', s[n + 1] = 's';
    else
        s[n] = 's';
    cout << s;
}
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 – Go to Jail
签到题)

#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
}
pair<int, int> p[N];
bool yes[N];
inline void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> p[i].first >> p[i].second;
        if (p[i].first == p[i].second)
            yes[i] = 1;
    }
    for (int i = 1; i <= n - 2; ++i)
    {
        if (yes[i] && yes[i + 1] && yes[i + 2])
            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;
}

C – A x B + C
我写得比较麻烦……
可以把 $C$ 移到右边去,变成 $A\times B = N-C$,然后只需要枚举右边,左边可以用因数个数公式,分解质因数之后求出来即可。
不过好像只需要枚举 $A\times B$ 就行了……
时间复杂度:$\mathcal{O}(N\ln N)$.

#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 = 1000050;
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;
ll ans;
int vis[N], pri[N], tot;
void shaipri(int lim)
{
    for (int i = 2; i <= lim; ++i)
    {
        if (!vis[i])
            vis[i] = i, pri[++tot] = i;
        for (int j = 1; j <= tot && i * pri[j] <= lim; ++j)
        {
            vis[i * pri[j]] = pri[j];
            if (i % pri[j] == 0)
                break;
        }
    }
}
inline void solve()
{
    cin >> n;
    for (int c = 1; c < n; ++c)
    {
        ll now = n - c;
        ll tmp = 1;
        while (now > 1)
        {
            ll cnt = 1;
            int nowpri = vis[now];
            while (now % nowpri == 0)
                now /= nowpri, cnt++;
            tmp *= cnt;
        }
        ans += tmp;
    }
    cout << ans;
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    shaipri(1000000);
    // scanf("%d", &Test);
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

D – Leaping Tak
一个很简单的 $dp$.
直接设 $dp(n)$ 表示走到第 $n$ 个格子的方案数,那么就有
$$
dp(i)=\sum\limits_{j\in S}dp(i-j)
$$
初始条件 $dp(1)=1$。然后这个递推式是一段一段的和,所以可以直接维护一个前缀和即可。
时间复杂度 $\mathcal{O}(nk)$.

#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, k;
ll dp[N], sum[N];
int l[N], r[N];
inline void solve()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; ++i)
        scanf("%d%d", &l[i], &r[i]);
    dp[1] = sum[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 1; j <= k; ++j)
            dp[i] += (sum[max(0, i - l[j])] - sum[max(0, i - r[j] - 1)]) % mod, dp[i] %= mod, dp[i] += mod, dp[i] %= mod;
        sum[i] = (sum[i - 1] + dp[i]) % mod;
    }
    cout << dp[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;
}

E – Sequence Sum
注意到 $M\le 10^5$,也就是说循环节的大小也不会超过 $M$。
然后这个循环实际上构成了一棵基环树,跑到环上去了就是 $x$ 开始循环了,所以只需要找到循环节,中间一大段可以直接算,边界再单独处理一下即可。
时间复杂度 $\mathcal{O}(M)$.

#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<int> r;
ll n;
int x, m;
map<int, int> vis;
inline void solve()
{
    scanf("%lld%d%d", &n, &x, &m);
    int initx = x;
    int tot = 1;
    ll ans = 0;
    while (tot <= n)
    {
        ans += x;
        vis[x] = tot;
        r.push_back(x);
        x = 1ll * x * x % m;
        tot++;
        if (vis.count(x))
            break;
    }
    if (tot == n + 1 || vis.count(0))
        return printf("%lld", ans), void();
    ll sum = 0;
    int sz = r.size();
    for (int i = vis[x] - 1; i < sz; ++i)
        sum += r[i];
    ans = 0;
    for (int i = 0; i < vis[x] - 1; ++i)
        ans += r[i];
    n -= vis[x] - 1;
    sz -= vis[x] - 1;
    ans += sum * (n / sz);
    int re = n % sz;
    for (int i = vis[x] - 1; i < re + vis[x] - 1; ++i)
        ans += r[i];
    cout << 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;
}

F – Simplified Reversi
维护两棵线段树,分别是横着的和竖着的,这一列或者这一行最上 / 最左的白棋的位置。每次查询就先查询这个位置,设为 $pos$,那么黑棋总数就减去 $pos-2$。之后再修改,对行操作就对列进行区间修改(注意修改的时候一定要取最小值),对列操作就对行进行区间修改。
这样,模拟一下这个过程,答案就出来了。
时间复杂度 $\mathcal{O}(Q\log N)$.

#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;
struct segtree
{
    struct T
    {
        int val;
        int lazy;
        int l, r;
    } t[N << 2];
    inline void pushup(int id) { t[id].val = min(t[ls].val, t[rs].val); }
    inline void pushdown(int id)
    {
        if (t[id].lazy)
        {
            t[ls].val = t[id].lazy, t[rs].val = t[id].lazy;
            t[ls].lazy = t[rs].lazy = t[id].lazy;
            t[id].lazy = 0;
        }
    }
    void build(int l, int r, int id)
    {
        t[id].l = l, t[id].r = r;
        if (l == r)
            return t[id].val = n, void();
        int mid = (l + r) >> 1;
        build(l, mid, ls), build(mid + 1, r, rs);
        pushup(id);
    }
    void change(int L, int R, int id, int val)
    {
        int l = t[id].l, r = t[id].r;
        if (L <= l && r <= R)
        {
            if (t[id].val > val)
            {
                t[id].val = val;
                t[id].lazy = val;
            }
            return;
        }
        pushdown(id);
        int mid = (l + r) >> 1;
        if (R <= mid)
            change(L, R, ls, val);
        else if (L > mid)
            change(L, R, rs, val);
        else
        {
            change(L, mid, ls, val);
            change(mid + 1, R, rs, val);
        }
        pushup(id);
    }
    int query(int pos, int id)
    {
        int l = t[id].l, r = t[id].r;
        if (l == r)
            return t[id].val;
        pushdown(id);
        int mid = (l + r) >> 1;
        if (pos <= mid)
            return query(pos, ls);
        else
            return query(pos, rs);
    }
} heng, shu;
int Q;
inline void solve()
{
    scanf("%d%d", &n, &Q);
    heng.build(1, n, 1), shu.build(1, n, 1);
    ll sum = (n - 2ll) * (n - 2);
    while (Q--)
    {
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1)
        {
            int pos = shu.query(x, 1);
            sum -= (pos - 2);
            heng.change(1, pos, 1, x);
        }
        else
        {
            int pos = heng.query(x, 1);
            sum -= (pos - 2);
            shu.change(1, pos, 1, x);
        }
    }
    printf("%lld\n", sum);
}
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;
}

 

发表评论

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