题解：【ARC183 A】Median of Good Sequences

JXR_Kalcium · 2024-08-25 21:57:42 · 题解

题目大意

给定一个 N 和 K，定义一个长度为 NK 的字符串为 “好串”，当且仅当由 1\sim N 每一个数刚好出现 K 次组成，令 S 为 “好串” 个数，问按字典序升序排列后第 \lceil\frac{S}{2}\rceil 个 “好串” 是什么，数据范围有 1\le N,K\le 500。

解题思路

首先肯定不能直接暴力枚举所有的 “好串”，于是这一题肯定是道数学/找规律题。我们可以先通过一遍全排列得出一个表（斜杠代表我没表）：

显然，N 的奇偶性会导致答案发生明显的变化，所以我们分开讨论。当 N 为奇数且 N>1 时，若 K=1，可以发现答案的前两个数分别为 \lceil\frac{N}{2}\rceil 和 \lfloor\frac{N}{2}\rfloor，而剩下的数就是 1\sim N 中除了这两个数以外降序排序的结果。对于 K>1 的情况，显然除了第二个数之外的其它数都重复了 K 次，而第二个数会在 K=1 的答案序列中 \lceil\frac{N}{2}\rceil+1 和 \lceil\frac{N}{2}\rceil+2 中间的位置重复 K-1 次（对于 N=1 的情况，特判一下即可）。

当 N 为偶数时，若 K=1，类比于 N 为奇数的情况，此时答案的第一个数就为 \frac{N}{2}，剩下的数就是 1\sim N 中除了这个数以外降序排序的结果。再看对于 K>1 的情况，除了第一个数之外的其它数都重复了 K 次，而第一个数会在原来 K=1 的答案序列中 \frac{N}{2} 和 \frac{N}{2}+1 中间的位置重复 K-1 次，这就是所有的规律了，模拟即可。

AC 代码

#include <bits/stdc++.h>
#define ll long long
#define endl putchar(10)
#define spc putchar(32)
#define R register
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " = " << x, endl
#endif

inline ll read()
{
    ll x=0,f=1; char c=getchar();

    while(c<48 || c>57)
    {
        if(c=='-') f=-1;
        c=getchar();
    }

    while(c>47 && c<58)
    x=(x<<1)+(x<<3)+c-48, c=getchar();
    return x*f;
}

inline void write(ll x)
{
    static ll sta[41]; ll top=0;
    if(x<0) putchar('-'), x=-x;
    do sta[top++]=x%10, x/=10; while(x);
    while(top) putchar(sta[--top]+48);
}

ll n,k,cnt;

int main()
{
    n=read(); k=read();

    if(n<2)
    {
        for(R int i=1; i<=k; ++i)
        write(1), spc; exit(0);
    }

    if(n&1)
    {
        for(R int i=1; i<=k; ++i)
        write(n+1>>1), spc; write(n>>1); spc;

        for(R int i=n; i; --i)
        {
            if(i!=n>>1 && i!=n+1>>1)
            {
                for(R int j=1; j<=k; ++j)
                write(i), spc;
            }

            if(++cnt==n>>1)
            {
                for(R int j=1; j<k; ++j)
                write(n>>1), spc;
            }
        }
    }

    else
    {
        write(n>>1); spc;

        for(R int i=n; i; --i)
        {
            if(i!=n>>1)
            {
                for(R int j=1; j<=k; ++j)
                write(i), spc;
            }

            if(cnt++==n>>1)
            {
                for(R int j=1; j<k; ++j)
                write(n>>1), spc;
            }
        }
    }

    return 0;
}