Codeforces Round #667(Div.3) 解题报告

A - Yet Another Two Integers Problem
赤裸裸的签到题......

#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("\nTime used:
    system("pause");
#endif
}
ll a, b;
inline void solve()
{
    cin >> a >> b;
    ll cha = abs(a - b);
    ll ans = cha / 10 + (cha
    cout << ans << endl;
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

B - Minimum Product
好昨晚卡这个题卡了半天......（半天 $=$ 半小时）
这个题就是考虑各种情况，只考虑 $a\le b$ 的情况，那么第一种就是只减少 $a$，减少完了如果还有剩的操作次数再去减 $b$。这种情况很好考虑，而麻烦的就是下面这种：
首先减少 $b$ 这一堆，直到减少到 $max(a,y)$ 为止，这个时候 $b$ 这一堆要么和 $a$ 相同，这时就看 $a-x$ 和 $b-y$ 谁大，哪边大就优先减谁；而还有一种就是 $b$ 减完了只剩 $a$，那就只对这一堆操作就行。
（一定要想清楚，不然就想我昨晚搞了半个多小时......）

#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("\nTime used:
    system("pause");
#endif
}
ll a, b, x, y, n;
ll ans = llinf;
inline void solve()
{
    cin >> a >> b >> x >> y >> n;
    n = min(n, (a - x + b - y));
    if (a > b)
        swap(a, b), swap(x, y);
    ans = llinf;
    ll sum = a + b - n;
    ll cha = abs(a - b);
    cha = cha + min(n, a - x) - (n - min(n, a - x));
    ans = min(ans, (sum - cha) * (sum + cha) / 4);
    cha = abs(a - b);
    ll cnt = min(n, min(b - a, b - y));
    b -= cnt;
    ll tmp = cha - cnt;
    ll nxt = min(n - cnt, max(a - x, a - y));
    tmp += nxt;
    tmp -= n - cnt - nxt;
    cha = tmp;
    ans = min(ans, (sum - cha) * (sum + cha) / 4);
    cout << ans << endl;
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

C - Yet Another Array Restoration
这就是一个很简单的构造，因为 $x$ 和 $y$ 之间一定满足 $y=x+k\times d$，并且 $k,d$ 都是整数，那么因为 $x$ 和 $y$ 都特别小，直接枚举 $k$ 或者 $d$，之后再模拟复原整个序列，更新最大值的同时更新答案就可以了。

#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("\nTime used:
    system("pause");
#endif
}
int n, x, y;
int mx;
int ansd, ansk;
inline void solve()
{
    mx = inf;
    cin >> n >> x >> y;
    ansd = y - x, ansk = 1;
    for (int k = 1; k <= n - 1; ++k)
    {
        if ((y - x)
            continue;
        int d = (y - x) / k;
        int m = n - 2 - (k - 1), nx = x;
        while (nx - d > 0 && m > 0)
            m--, nx -= d;
        int ny = y;
        while (m)
            m--, ny += d;
        if (ny < mx)
        {
            mx = ny;
            ansd = d, ansk = k;
        }
    }
    int nx = x, ny = y, m = n - 2 - (ansk - 1);
    printf(
    for (int i = x + ansd; i < y; i += ansd)
        printf(
    while (nx - ansd > 0 && m > 0)
        nx -= ansd, m--, printf(
    while (m > 0)
        ny += ansd, m--, printf(
    puts("");
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

D - Decrease the Sum of Digits
这题再次暴露我的代码能力多么拉跨（
从低位开始往高位考虑，设前缀和 $sum(n)$ 从最高位开始前 $n$ 位的数字之和，然后从低位开始枚举。因为要消掉一些数字，那就只能让某一位之后全部变成 $0$ 就行。
于是就可以枚举消除后 $m$ 位，并且要注意第 $m+1$ 位的数字会 $+1$，并且如果第 $m+1$ 位数字是 $9$ 的话这一位实际上也被消除了，所以考虑的时候注意遇到第 $m+1$ 位数字是 $9$ 的话就直接跳过就行。
细节有一点多，总之还是要想清楚再写（

#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("\nTime used:
    system("pause");
#endif
}
char num[100];
int s;
int ans;
inline void solve()
{
    scanf(
    cin >> s;
    int n = strlen(num + 1), sum[100] = {0};
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + num[i] - '0';
    num[0] = '0';
    int l = n;
    if (sum[n] <= s)
        return puts("0"), void();
    ll nownum = 0;
    ll bei = 1;
    while (true)
    {
        if (num[l] == '9')
        {
            while (num[l] == '9')
                nownum += bei * (num[l] - '0'), bei *= 10, l--;
        }
        else
        {
            nownum += bei * (num[l] - '0'), bei *= 10, l--;
            if (num[l] == '9')
                continue;
        }
        int cha = sum[n] - sum[l] - 1;
        if (sum[n] - cha <= s)
        {
            return printf(
        }
        // l--;
    }
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

E - Two Platforms
~~赛后过题我最拿手了~~
很明显，这 $n$ 个点的 $y$ 坐标没有任何作用，因为都要往下掉的，所以输入的时候直接全部去掉就行。
然后就是考虑怎么放着两块板。显然，这两块板没有重叠的时候是最优的，并且每一块板的某个端点一定是某个点的 $x$ 坐标，方便起见，我们就设左端点是这样的。
那么就可以考虑枚举其中一块板的位置，如何快速求出另一块板的位置使得其贡献最大。显然，我们可以把所有 $x$ 离散化之后做一个前缀和，然后做一个后缀最大值。这个最大值就是在第 $i$ 个坐标及之后一块板能产生的最大贡献（即能接收到的最多的点的数量），这一步可以采用二分的方法，找到这个端点往右延伸长度 $k$ 之后对应的位置之间的区间和。
然后就可以 $\mathcal{O}(n)$ 的时间扫一遍就行。
总的时间复杂度为 $\mathcal{O}(n\log^2n)$。当然写法很好的话可以优化到 $\mathcal{O}(n\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("\nTime used:
    system("pause");
#endif
}
int n;
ll k;
ll x[N];
map<ll, int> id;
vector<ll> vec;
int mx[N], sum[N], cnt[N];
int findid(ll x)
{
    return id[vec[upper_bound(vecall(vec), x) - vec.begin() - 1]];
}
int findid2(ll x)
{
    return id[vec[lower_bound(vecall(vec), x) - vec.begin() - 1]];
}
inline void solve()
{
    cin >> n >> k;
    mem(mx, 0, n, int);
    mem(sum, 0, n, int);
    mem(cnt, 0, n, int);
    vec.resize(0);
    id.clear();
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        scanf(
    for (int i = 1; i <= n; ++i)
    {
        int y;
        scanf(
    }
    sort(x + 1, x + n + 1);
    vec.push_back(-1);
    id[-1] = 0;
    for (int i = 1; i <= n; ++i)
        vec.push_back(x[i]);
    vec.resize(unique(vecall(vec)) - vec.begin());
    int m = vec.size() - 1;
    for (int i = 1; i <= m; ++i)
        id[vec[i]] = i;
    vec.push_back(llinf);
    for (int i = 1; i <= n; ++i)
        cnt[id[x[i]]]++;
    for (int i = 1; i <= m; ++i)
        sum[i] = sum[i - 1] + cnt[i];
    for (int i = m; i; --i)
        mx[i] = max(mx[i + 1], sum[min(m, findid(vec[i] + k))] - sum[i - 1]);
    for (int i = 1; i <= m; ++i)
    {
        int tmp = sum[i] - sum[max(0, findid2(vec[i] - k))];
        tmp += mx[i + 1];
        ans = max(ans, tmp);
    }
    printf(
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

F - Subsequences of Length Two
（要好好练习读题啊啊啊啊，完全没看到 $t$ 串只有俩字母的条件，吐了）
直接上 $dp$ 吧，这题一看就是个 $dp$~
设 $dp(i,j,y)$ 表示 $s$ 串前 $i$ 个字母，用了 $j$ 次操作，$t_0$ 这个字母在 $s$ 串前 $i$ 个字母中有 $y$ 个。
实际上，这个题可以把 $s$ 串分成三种字母组成的：$t_0,t_1$ 和其他字母。也就是说转移的时候我们只需要考虑这几种情况就行。

不改变第 $i$ 位的字母。这种情况下，考虑第 $i$ 位为其他字母，$t_0,t_1$ 就有好几种情况。整合一下其实方程很简单：$dp(i+1,j,y+(s_i==t_0)) = \max\{dp(i+1,j,y+(s_i==t_0)),dp(i,j,y)+((s_i==t_1)?y:0)\}$.
改变第 $i$ 位的字母为 $t_0$，那么只有在 $t_0==t_1$ 的时候才会产生贡献，于是方程可以写成 $dp(i+1,j+1,y+1) = \max\{dp(i+1,j+1,y+1),dp(i,j,y)+((t_0==t_1)?y:0)\}$.
改变第 $i$ 位的字母为 $t_1$，那么就看前面有几个 $t_0$ 就会产生多少贡献，并且如果 $t_0==t_1$，那么改变后 $t_0$ 的数量也会 $+1$，于是方程可以写成 $dp(i+1,j+1,y+(t_0==t_1))=\max\{dp(i+1,j+1,y+(t_0==t_1),dp(i,j,y)+y\}$.

最后答案就是 $\max\limits_{0\le j \le k,0\le y \le n}\{dp(n,j,y)\}$.

#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("\nTime used:
    system("pause");
#endif
}
int n, k, ans;
int dp[205][205][205];
char s[205], t[5];
inline void solve()
{
    cin >> n >> k;
    scanf(
    scanf(
    memarray(dp, -inf);
    dp[0][0][0] = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= k; ++j)
            for (int y = 0; y <= n; ++y)
            {
                if (dp[i][j][y] == -inf)
                    continue;
                dp[i + 1][j][y + (s[i] == t[0])] = max(dp[i + 1][j][y + (s[i] == t[0])], dp[i][j][y] + ((s[i] == t[1]) ? y : 0));
                if (j < k)
                {
                    dp[i + 1][j + 1][y + 1] = max(dp[i + 1][j + 1][y + 1], dp[i][j][y] + ((t[0] == t[1]) ? y : 0));
                    dp[i + 1][j + 1][y + (t[0] == t[1])] = max(dp[i + 1][j + 1][y + (t[0] == t[1])], dp[i][j][y] + y);
                }
            }
    for (int j = 0; j <= k; ++j)
        for (int y = 0; y <= n; ++y)
            ans = max(ans, dp[n][j][y]);
    cout << ans << endl;
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
        solve();
    TIME__END = clock();
    program_end();
    return 0;
}

Codeforces Round #667(Div.3) 解题报告

[POI2015]Odwiedziny

[洛谷题单]欧拉函数与欧拉定理

Comments NOTHING

取消回复