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

A	Boring Apartments

水题
嘛其实还是需要码两三分钟的......
总之就是先把答案预处理好，计算的时候再一个一个加就完事了~

#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 a[10005];
int x;
void INit()
{
    for (int i = 1; i <= 9; ++i)
    {
        int num = 0;
        for (int j = 1; j <= 4; ++j)
        {
            num = num * 10 + i;
            a[num] = j;
        }
    }
}
inline void solve()
{
    int ans = 0;
    cin >> x;
    int digit = x
    for (int i = 1; i < digit; ++i)
    {
        int num = 0;
        for (int j = 1; j <= 4;++j)
        {
            num = num * 10 + i;
            ans += a[num];
        }
    }
    while(x)
    {
        ans += a[x];
        x /= 10;
    }
    cout << ans << endl;
}
int main()
{
    INit();
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

B	Yet Another Bookshelf

结论题，容易发现答案就是把两头的 $0$ 给去掉之后，中间的 $0$ 的个数就是答案。

#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;
int a[55];
inline void solve()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    int ans = 0;
    bool gap = 0;
    int l = 1, r = n;
    while(a[l]==0)
        l++;
    while(a[r]==0)
        r--;
    for (int i = l; i <= r; ++i)
    {
        ans += (a[i] == 0);
    }
    cout << 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	Dominant Piranha

也是个结论题。
如果所有的水虎鱼的 $a_i$ 相等，显然大家都很和谐，谁也吃不了谁。
而如果不全相等，那就必然有一些 $a_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:
    system("pause");
#endif
}
int n;
int a[N];
inline void solve()
{
    scanf(
    for (int i = 1; i <= n; ++i)
        scanf(
    a[n + 1] = 0;
    int mx = 0, mxid = 0, changed = 0;
    for (int i = 1; i <= n; ++i)
        if (mx <= a[i])
            mx = a[i], mxid = i;
    for (int i = 1; i <= n; ++i)
        if (a[i] < mx)
            changed = 1;
    if (!changed)
        return printf("-1\n"), void();
    for (int i = 1; i < n; ++i)
    {
        if (a[i] == mx && a[i + 1] < mx)
        {
            mxid = i;
            break;
        }
    }
    for (int i = 2; i <= n; ++i)
    {
        if (a[i] == mx && a[i - 1] < mx)
        {
            mxid = i;
            break;
        }
    }
    printf(
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

D	Districts Connection

简单的构造。容易发现只需要出现两种或以上的帮派数就行。
构造方式就是拿第一个帮派的第一个人作为根节点，其他帮派的所有人都连向他。之后第一个帮派剩下的人再随便选择其他帮派的任何一个人连就可以了~

#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,a[5002];
vector<int> v[5002];
map<ll, int> mph;
vector<pair<int, int>> anse;
inline void solveproblem()
{
    anse.resize(0);
    cin >> n;
    for (int i = 0; i <= n; i++)
        v[i].clear();
    mph.clear();
    int tot = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf(
        if (!mph.count(a[i]))
            mph.insert(make_pair(a[i], ++tot));
        v[mph[a[i]]].push_back(i);
    }
    if (tot == 1)
    {
        printf("NO\n");
        return;
    }
    int rt = v[1][0] ;
    int rt2 = v[2][0];
    for (int i = 2; i <= tot; i++)
    {
        for (auto j : v[i])
            anse.emplace_back(make_pair(j, rt));
    }
    for (int i = 1; i < (int)v[1].size(); i++)
        anse.emplace_back(make_pair(v[1][i], rt2));
    printf("YES\n");
    for (auto i : anse)
    {
        int x = i.first, y = i.second;
        printf(
    }
}
int main()
{
    int Test = 1;
    scanf(
    while (Test--)
    {
        solveproblem();
    }
    return 0;
}

E	Two Round Dances

我愿称之为打表题（
因为直接康托展开或者hash一波就可以爆搜出所有的答案。
这个题就做完了（
实际上要推式子也是可以的，先留着。
代码里面打表的代码也在里面。

#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
}
ll C[35][35], fac[35];
int a[50];
set<ll> s;
ll ans;
ll Hash(int l, int r, int n)
{
    ll ret = 1;
    for (int i = l; i <= r; ++i)
    {
        int tmp = 0;
        for (int j = i + 1; j <= r; ++j)
        {
            if (a[i] > a[j])
                tmp++;
        }
        ret += 1ll * tmp * fac[n - (i - l) - 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];
    }
}
inline void solve(int n)
{
    initc(25);
    ans = 0;
    fac[0] = 1;
    s.clear();
    for (int i = 1; i <= 20; ++i)
        fac[i] = fac[i - 1] * i;
    // scanf(
    n >>= 1;
    for (int i = 1; i <= n; ++i)
        a[i] = i;
    do
    {
        bool exist = false;
        for (int i = 1; i <= n; ++i)
            a[i + n] = a[i];
        for (int i = 1; i <= n; ++i)
        {
            ll has = Hash(i, i + n - 1, n);
            if (s.count(has))
            {
                exist = true;
                break;
            }
        }
        if (!exist)
        {
            ans++;
            // for (int i = 1; i <= n; ++i)
            //     cout << a[i] << ' ';
            // cout << endl;
            for (int i = 1; i <= n; ++i)
            {
                ll has = Hash(i, i + n - 1, n);
                s.insert(has);
            }
        }
    } while (next_permutation(a + 1, a + n + 1));
    // cout << ans << endl;
    cout << ans * ans * C[2 * n][n] / 2 << ',';
}
long long ans[] = {0,1, 3, 40, 1260, 72576, 6652800ll, 889574400ll, 163459296000ll, 39520825344000ll, 12164510040883200ll};
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        // cout << "ll ansn[]={";
        // for (int n = 2; n <= 20; n += 2)
        // {
        //     solve(n);
        // }
        int n;
        cin >> n;
        cout << ansn[n / 2] << endl;
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

F	Zero Remainder Sum

就这个题，搞了半天，最后还被 hack 了......
难受（哭
这个题我们可以分成两部分来 dp。
第一部分，我们设 $dp(j,cnt,yu)$ 表示当前在这一行的第 $j$ 个数，这一行已经选了 $cnt$ 个数，这些数的和模 $k$ 的余数为 $yu$ 的最大和。那么 dp 方程就很简单，分为个数是选还是不选。于是 dp 方程就是：
$$
dp(j+1,cnt,yu)=\max\{dp(j,cnt,yu)\} \\
dp(j+1,cnt+1,(yu+a_{i,j+1}))=\max\{dp(j,cnt,yu)+a_{i,j+1}\}
$$
这个是第一部分。同时我们记录 $mxyu(i,yu)$ 表示第 $i$ 行和模 $k$ 的余数为 $yu$ 的最大和。
第二部分，设 $g(i,yu)$ 表示当前到第 $i$ 行，当前最大和模 $k$ 的余数是 $yu$ 的最大和。dp 方程也很好推：
$$
g(i+1,(yu+yunow)\bmod k)=\max\{g(i,yu)+mxyu(i+1,yunow)\}
$$
这个 dp 方程就是枚举上一行的余数和这一行的余数，进行的 dp。
最后答案就是 $g(n,0)$.
不过一定一定要注意不要转移到非法状态去......有些状态是达不到的，就设为 -1。转移的时候一定要从合法的状态转移过来（我就这里被叉了）
总的时间复杂度为 $\mathcal{O}(n^4)$.

#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, m, k;
int a[100][100];
ll ans;
ll dp[75][75][75], g[75][75], mxyu[75][75];
inline void solve()
{
    scanf(
    memarray(mxyu, -1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf(
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j <= m; ++j)
            for (int cnt = 0; cnt <= m / 2; ++cnt)
                for (int yu = 0; yu < k; ++yu)
                    dp[j][cnt][yu] = -1;
        dp[0][0][0] = 0;
        for (int j = 0; j < m; ++j)
        {
            for (int cnt = 0; cnt <= m / 2; ++cnt)
                for (int yu = 0; yu < k; ++yu)
                {
                    if (dp[j][cnt][yu] >= 0)
                    {
                        dp[j + 1][cnt][yu] = max(dp[j + 1][cnt][yu], dp[j][cnt][yu]);
                        if (cnt + 1 <= m / 2)
                            dp[j + 1][cnt + 1][(yu + a[i][j + 1])
                    }
                }
        }
        for (int yu = 0; yu < k; ++yu)
            for (int cnt = 0; cnt <= m / 2; ++cnt)
                mxyu[i][yu] = max(mxyu[i][yu], dp[m][cnt][yu]);
    }
    memarray(g, -1);
    g[0][0] = 0;
    for (int i = 0; i < n; ++i)
        for (int yu = 0; yu < k; ++yu)
            for (int yunow = 0; yunow < k; ++yunow)
                if (g[i][yu] >= 0 && mxyu[i + 1][yunow] >= 0)
                    g[i + 1][(yu + yunow)
    ans = max(ans, g[n][0]);
    printf(
}
int main()
{
    TIME__START = clock();
    int Test = 1;
    // scanf(
    while (Test--)
    {
        solve();
        // if (Test)
        //     putchar('\n');
    }
    TIME__END = clock();
    program_end();
    return 0;
}

G	Reducing Delivery Cost

这个题比 F 水多了好吧！！！
首先，直接就 $\mathcal{O}(n^2\log n)$ 求出任意两点间最短路，之后就 $\mathcal{O}(m)$ 枚举每一条边，让其权值为 $0$ 的话，那么这些点对要么就经过这条边，要么还是走原来的最短路。假设这条边的两个端点为 $eu,ev$，那么要经过这条边的话就肯定要经过这俩端点，于是我们就可以让 $u$ 首先到 $eu$ 或 $ev$，然后再从端点走向 $v$。这样加上原来的最短路一共 $3$ 种路径可走，取个最小值就完事了。
时间复杂度：$\mathcal{O}(n^2\log n + mk)$。

#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 = 1050;
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 dis[N][N];
int n, m, k;
vector<pii> e[N];
int a[N], b[N];
bool vis[N];
void sp(int st)
{
    queue<int> q;
    q.push(st);
    memarray(dis[st], inf);
    dis[st][st] = 0;
    memarray(vis, 0);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        for (auto v : e[u])
        {
            if (dis[st][v.first] > dis[st][u] + v.second)
            {
                dis[st][v.first] = dis[st][u] + v.second;
                if (!vis[v.first])
                    q.push(v.first), vis[v.first] = 1;
            }
        }
    }
}
vector<pii> edges;
inline void solve()
{
    scanf(
    for (int i = 1; i <= m; ++i)
    {
        int x, y, cost;
        scanf(
        e[x].push_back(mp(y, cost));
        e[y].push_back(mp(x, cost));
        edges.push_back(mp(x, y));
    }
    for (int i = 1; i <= k; ++i)
        scanf(
    for (int i = 1; i <= n; ++i)
        sp(i);
    ll ans = llinf;
    for (auto E : edges)
    {
        int eu = E.first, ev = E.second;
        ll tmp = 0;
        for (int i = 1; i <= k; ++i)
        {
            int u = a[i], v = b[i];
            int tmp2 = dis[u][v];
            tmp2 = min(tmp2, dis[u][eu] + dis[ev][v]);
            tmp2 = min(tmp2, dis[u][ev] + dis[eu][v]);
            tmp += tmp2;
        }
        ans = min(ans, tmp);
    }
    cout << 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;
}