T20200904

Posted on Edited on In Word count in article: 975 Reading time ≈ 4 mins.
大东辰的测试

T1(count)

45分做法

直接暴力乱搞！！！

Code

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
#include <bits/stdc++.h>

using namespace std;

int n, m, nm(1), cnt, ans;
int son[50];

void dfs(int dep, int fac)
{
	if (fac > nm) return;
	if (dep == m * 2) 
	{
		++ans;
		return;
	}
	for (int i = 1; i <= cnt; ++i)
		dfs(dep + 1, fac * son[i]);
}

int main()
{
	freopen ("count.in", "r", stdin);
	freopen ("count.out", "w", stdout);
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= m; ++i) nm *= n;
	for (int i = 1; i <= n; ++i)
		if (n % i == 0) son[++cnt] = i;
	dfs(0, 1);
	printf ("%d\n", ans);
}

因为你大概算一下，发现其实\(100\)以内的答案还是真的挺少的

100分做法

下面上PDF，先鸽着

T2(delet)

题解说，贪心删即可

然后根据某高级定理

每次删除一个最长单调的链，他的长度大概是一个\(\log\)级别的

所以最多\(800\)次可以删完

然后题解保证的是\(500\)次能删完

那么有\(n\log n\)求最长上升/下降子序列的做法

总时间复杂度\(O(500\;n\log n)\)

乱搞也能过。。。

Code

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <memory.h>
#include <vector>

using namespace std;
typedef long long LL;

const int maxn = 64005;
#define pb push_back

int a[maxn],a0[maxn],n,tot,f[maxn],g[maxn];
vector<int> vec[maxn];
int mx1[maxn],mx2[maxn],bac[maxn],del[maxn];

void Print()
{
	printf("%d\n",tot);
	for (int i=1;i<=tot;i++)
	{
		int len=vec[i].size();
		printf("%d ",len);
		for (int j=len-1;j>=0;j--)
			printf("%d%c",vec[i][j]," \n"[j==0]);
	}
}
void insert1(int x,int v) {
	for (int i=x;i<=n;i+=i&-i)
		mx1[i]=max(mx1[i],v);
}
void insert2(int x,int v) {
	for (int i=x;i;i-=i&-i)
		mx2[i]=max(mx2[i],v);
}
int query1(int x) {
	int res=0;
	for (int i=x;i;i-=i&-i)
		res=max(res,mx1[i]);
	return res;
}
int query2(int x) {
	int res=0;
	for (int i=x;i<=n;i+=i&-i)
		res=max(res,mx2[i]);
	return res;
}

void DP()
{
	++tot;
	memset(mx1,0,n+1<<2);
	memset(mx2,0,n+1<<2);
	int ans1=0,ans2=0;;
	for (int i=1;i<=n;i++)
	{
		f[i]=query1(a[i])+1;
		g[i]=query2(a[i])+1;
		insert1(a[i],f[i]);
		insert2(a[i],g[i]);
		ans1=max(ans1,f[i]);
		ans2=max(ans2,g[i]);
	}
	
	memset(del,0,n+1<<2);
	if (ans1>ans2) {
		for (int t=ans1,i=n;t;i--)
			if (f[i]==t) del[a[i]]=1,t--,vec[tot].pb(a0[i]);
	}
	else {
		for (int t=ans2,i=n;t;i--)
			if (g[i]==t) del[a[i]]=1,t--,vec[tot].pb(a0[i]);
	}
	for (int i=1;i<=n;i++)
		bac[i]=bac[i-1]+1-del[i];
	int pos=0;
	for (int i=1;i<=n;i++)
		if (!del[a[i]]) a0[++pos]=a0[i],a[pos]=bac[a[i]];
	n=pos;
}
int main()
{
	#ifndef ONLINE_JUDGE
		freopen("delete.in","r",stdin);
		freopen("delete.out","w",stdout);
	#endif
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]),a0[i]=a[i];
	while (n) DP();
	Print();
	return 0;
}
//std

T3(floor)

这是我今天特别失败的地方

我\(TM\)花了\(2h\)来打表找规律，结果，结果！！

我\(TM\)打错表了！！！

T20200903-1.gif

最后还是搞出来了，真是惊悚啊

打表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1   	1
2    	3
4 		4
6 	 	7
11 		11
17  	18
29   	29
46   	47
76   	76
122     123
199     199
321     322
521     .
842     .
1364    .
2206    .
3571    .
5777    .
9349    .
15126   .

左边这个是没有取模的值

右边这个是不是有点像斐波那契数列呢？

看看数据范围\(n\le10^{18}\)

矩阵乘法，那就结束了？ \[ \begin{vmatrix}f_i&f_{i-1}\\0&0\end{vmatrix}\qquad \begin{vmatrix}1&1\\1&0\end{vmatrix} \] 就用这两个矩阵做快速幂

然后因为没有对\(1\)做贡献的数，所以我们让矩阵的\(0\)次方的值为\(3\)

如果\(n\)是个偶数，那么答案还要减一

Code

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n, p;
struct matrix{ll a[2][2];};

matrix ppt (matrix x, matrix y) {
	matrix ans;
	memset (ans.a, 0, sizeof ans.a);
	for (int i = 0; i <= 1; ++i)
		for (int j = 0; j <= 1; ++j)
			for (int k = 0; k <= 1; ++k)
				ans.a[i][j] = (ans.a[i][j] + x.a[i][k] * y.a[k][j] % p) % p;
	return ans;
}

inline ll Pow(ll y)
{
	matrix x, ans;
	x.a[0][0] = x.a[0][1] = x.a[1][0] = 1;
	ans.a[0][0] = 3, ans.a[0][1] = 1;
	ans.a[1][0] = ans.a[1][1] = x.a[1][1] = 0;
	while (y) {
		if (y & 1) ans = ppt(ans, x);
		x = ppt(x, x);
		y >>= 1;
	}
	return ans.a[0][0];
}

int main()
{
	cin >> n >> p;
	if (p == 1) return puts("0") & 0;
	if (!n || n == 1) return puts("1") & 0;
	ll ans = Pow(n - 2);
	if (!(n % 2)) --ans;
	cout << ans << endl;
}