526互联

Codeforces Round 892 div2.C

发布时间 2023-08-13 12:36:44作者: Thecode_Wm

这C真的魔幻，官方题解完全和写的不一样，太玄学了，打表发现的规律

这是打表代码:

int main()
{
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = i;
    LL ans = 0;
    do
    {
        auto b = a;
        LL sum = 0, mx = 0;
        for (LL i = 1; i <= n; i++)
        {
            sum += b[i] * i;
            mx = max(mx, b[i] * i);
        }
        sum -= mx;
        if (sum > ans)
        {
            ans = sum;
            cout << "ans = " << ans << endl;
            for (int i = 1; i <= n; i++)
                cout << b[i] << ' ';
            cout << endl;
        }
    } while (next_permutation(a.begin() + 1, a.end()));
    return 0;
}

然后通过打表发现的数据发现是反转一段后缀区间就行了0.o

以下是暴力求解正解:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f; // 无穷大
const int MOD = 1e9 + 7;    // 取余
const int N = 2e5 + 10;     // 初始N
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define endl '\n'
LL n, m;
void solve()
{
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        a[i] = i;
    LL ans = 0;
    for (int i = 1; i <= n; i++)
    {
        auto b = a;
        reverse(b.begin() + i, b.end());
        int sum = 0, mx = 0;
        for (int j = 1; j <= n; j++)
        {
            sum += j * b[j];
            mx = max(mx, j * b[j]);
        }
        if (sum - mx > ans)
        {
            ans = sum - mx;
            // cout << "ans=" << ans << endl;
            // for (int i = 1; i <= n; i++)
            //     cout << b[i] << ' ';
            // cout << endl;
        }
    }
    cout << ans << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}