日记 - 伊埃斯的博客站

我觉得我是时候去掏几张缇宝的横板图了。

依然是考试。

T1

神秘小 dp。设 $dp_{i,j,k}$ 表示第 $i$ 个数取了 $j$ 个，第 $i - 1$ 个数去了 $k$ 个，第 $i - 2$ 及以前的钦定取完的方案数。转移在代码里：

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
const int mod = 1e9 + 7;
5
int n,m;
6
signed main()
7
{
8
  ios::sync_with_stdio(0);
9
  cin.tie(0);
10
  cout.tie(0);
11
  cin >> n >> m;
12
  vector<int>b(m + 5),up(m + 5);
13
  for (int i = 1,x; i <= n; i++)
14
  {
15
    cin >> x;
16
    b[x]++;
17
  }
18
  for (int i = 1; i <= m; i++)
19
    up[i] = max(b[i - 1],b[i]);
20
  vector<vector<vector<int>>>dp(m + 5);
21
  dp[0].resize(1),dp[0][0].resize(1);
22
  for (int i = 1; i <= m; i++)
23
  {
24
    dp[i].resize(up[i] + 5);
25
    for (int j = 0; j <= up[i]; j++)
26
      dp[i][j].resize(up[i] + 5);
27
  }
28
  dp[0][0][0] = 1;
29
  for (int i = 1; i <= m; i++)
30
  {
31
    for (int j = 0; j <= b[i]; j++)
32
    {
33
      for (int k = 0; k <= b[i - 1]; k++)
34
      {
35
        for (int x = (b[i] - j) / 3; x >= 0; x--)
36
        {
37
          if (k + (b[i] - j) - x * 3 > up[i - 1])
38
            break;
39
          dp[i][j][k] = (dp[i][j][k] + dp[i - 1][k + (b[i] - j) - x * 3][(b[i] - j) - x * 3]) % mod;
40
        }
41
      }
42
    }
43
  }
44
  cout << dp[m][0][0];
45
  return 0;
46
}

也是十分潦草。

T2

我是打表仙人。显而易见的有当 $2k > n$ 时非法。让我们打个暴力代码出来。（此处省略一份 $O(n!)$ 暴力代码）让我们试试 6 3 的输出结果：4 5 6 1 2 3。再让我们试试 12 3 的输出结果：4 5 6 1 2 3 10 11 12 7 8 9。是不是有点初见端倪？再来一组：8 2 的输出：3 4 1 2 7 8 5 6。现在你可以看出规律了。把 $n$ 分成几段长度为 $2k$ 的段，每段结构为：

2k \times x + k + 1,2k \times x + k + 2,2k \times x + k + 3,...,2k \times x + k + k, \\ 2k \times x + 1,2k \times x + 2,2k \times x + 3,...,2k \times x + k

其中 $x$ 表示这是第几段，从 $0$ 开始计数。但是这是 $2k \mid n$ 的情况。

那么 $2k \nmid n$ 呢？试试 8 3。输出为 4 5 6 7 8 1 2。再来 10 3。输出为 4 5 6 1 8 9 10 2 3 7。多打几组，你会发现，前面 $[1,n - 2k]$ 平安无事，依然是上面的规律。直到 $n - 2k + 1$ 这个位置。我们发现它输出了 $[n - 2k + 1,n - k]$ 的 $k$ 个数，究其原因是，如果都到这了还按照原来的规律输出，最后几个一定是 $p_i = i$ 不合法的。所以我们需要提早把它输出以避免非法情况。至于最后的 $k$ 个数，把没输出的按照大小输出即可。可以证明一定合法。

code:

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
const int maxn = 3e5 + 5;
5
int n,k;
6
int p[maxn];
7
bool b[maxn];
8
vector<int>ans;
9
signed main()
10
{
11
    scanf("%lld%lld",&n,&k);
12
    if ((k << 1) > n)
13
        return printf("-1"),0;
14
    fill(b + 1,b + n + 1,1);
15
    for (int s = 1; s + (k << 1) - 1 <= n && ans.size() < n - (k << 1); s += (k << 1))
16
    {
17
        int t = s + (k << 1);
18
        for (int i = s + k; i < t && ans.size() < n - (k << 1); i++)
19
        {
20
            b[i] = 0;
21
            ans.push_back(i);
22
        }
23
        for (int i = s; i < s + k && ans.size() < n - (k << 1); i++)
24
        {
25
            b[i] = 0;
26
            ans.push_back(i);
27
        }
28
    }
29
    for (int i = n - k + 1; i <= n; i++)
30
    {
31
        b[i] = 0;
32
        ans.push_back(i);
33
    }
34
    for (int i = 1; i <= n; i++)
35
        if (b[i])
36
            ans.push_back(i);
37
    for (auto i : ans)
38
        printf("%lld ",i);
39
    return 0;
40
}

然后 T3 T4 都没打。今晚上还要打 CF。本来说 $14$ 天速通到翁法罗斯的，然后今天就到了。

Thanks for reading!

日记

周四 2月 27 2025

870 字 · 6 分钟

life 日记