伊埃斯的小站
日记

日记

Thu Feb 27 2025
6 分钟
life 日记
878 字

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

依然是考试。

T1#

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

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

也是十分潦草。

T2#

我是打表仙人。显而易见的有当 2k>n2k > n 时非法。让我们打个暴力代码出来。（此处省略一份 O(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。现在你可以看出规律了。把 nn 分成几段长度为 2k2k 的段，每段结构为：

2k×x+k+1,2k×x+k+2,2k×x+k+3,...,2k×x+k+k,2k×x+1,2k×x+2,2k×x+3,...,2k×x+k2k \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

其中 xx 表示这是第几段，从 00 开始计数。但是这是 2k∣n2k \mid n 的情况。

那么 2k∤n2k \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][1,n - 2k] 平安无事，依然是上面的规律。直到 n−2k+1n - 2k + 1 这个位置。我们发现它输出了 [n−2k+1,n−k][n - 2k + 1,n - k] 的 kk 个数，究其原因是，如果都到这了还按照原来的规律输出，最后几个一定是 pi=ip_i = i 不合法的。所以我们需要提早把它输出以避免非法情况。至于最后的 kk 个数，把没输出的按照大小输出即可。可以证明一定合法。

code:

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

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