Day8

字数统计: 2.8k字   |   阅读时长: 14min

1.交换

【问题描述】
fateice 扔给了 fjzzq2002 一个长度为 n 的正整数序列，要让他排好序。
因为这太简单，所以 fjzzq2002 只能用规定的两种操作来将这个序列排成升序。
1. 将相邻的两个数调换位置，也就是𝑎𝑖, 𝑎𝑗变成𝑎𝑗, 𝑎𝑖。
2. 将连续的三个数调换位置，也就是𝑎𝑖, 𝑎𝑗, 𝑎𝑘变成𝑎𝑘, 𝑎𝑗, 𝑎𝑖。
其中， 𝑖, 𝑗(, 𝑘)必须满足条件（相邻/连续）。
由于使用操作 1 很累，所以 fjzzq2002 想要尽可能少的使用操作 1，你需要求出将这个
序列排成单调上升最少需要的操作 1 的次数。数据保证序列中不存在相同的两个数。

【输入格式】
输入文件名为 swap.in。
第一行，一个数 n，表示序列长度。
第二行， n 个互不相同的正整数，表示这个正整数序列。
【输出格式】
输出文件名为 swap.out
一行，一个数，表示答案。

输入：
4
1 4 2 3

输出：
1

【数据规模与约定】
对于 30% 的数据， 1 ≤ 𝑛 ≤ 10；
对于 60% 的数据， 1 ≤ 𝑛 ≤ 10^3；
对于 100% 的数据， 1 ≤ 𝑛 ≤ 10^5, 1 ≤ 𝑎𝑖 ≤ 10^9。

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
#include<bits/stdc++.h>
using namespace std;
struct node
{
	int s,i;
}a[100001];
int cmp(node a,node b)
{
	return a.s<b.s;
}
int n,ans;
int main()
{
	freopen("swap.in","r",stdin);
	freopen("swap.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i].s),a[i].i=i;
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		int c=i%2,d=a[i].i%2;
		if(c!=d) ans++;
	}
	cout<<ans/2;
	return 0;
}

找规律题…..

操作二暗示奇数编号可以在奇数编号随意移动，偶数一样。所以排序记录每个数之前的位置。如果当前位置的奇偶性与之前不符，ans++,最后ans/=2;

2.city

【问题描述】
在不远的未来，城市都是一层一层的排列的。
所有城市的上方有一个出发点，所有城市的下方有一个终点，旅行者们可以从出发点出
发穿越所有层城市到达终点。
这些城市有 m 层，从高往低为 1 到 m 层，每层都有 n 个城市。从出发点到第一层的第
i 个城市的花费为𝐴𝑖；从第 m 层的第 i 个城市到终点的花费为𝐶𝑖；在第 t 层到第 t+1 层穿越
时，当到达第 t+1 层的第 i 个城市时，花费为𝐵𝑖。
当旅行者到达终点时候，结算他总共的花费。为了吸引旅游者，所以花费对 p 取模。作
为一个旅游者的 fateice，当然需要使得花费最小（即为 0）。所以，请你求出 fateice 有多少
种走法使得花费为 0。
因为答案很大，所以良心出题人只要你输出答案对109 + 7取模后的值即可。
【输入格式】
输入文件名为 city.in。
第一行，三个数， 𝑛, 𝑚, 𝑝，分别表示城市层数，每层城市数和结算花费时候的取模。
第二行， n 个数𝐴𝑖，含义如题所示。
第三行， n 个数𝐵𝑖，含义如题所示。
第四行， n 个数𝐶𝑖，含义如题所示。
【输出格式】
输出文件名为 city.out。
仅一行，一个数，输出答案对109 + 7取模后的值。

输出：
2 3 13
6 4
1 2
4 3
输入：
2

【数据规模与约定】
对于 30% 的数据， 1 ≤ 𝑛 ≤ 5；
对于 60% 的数据， 1 ≤ 𝑛 ≤ 10^3；
对于另外 10% 的数据， 𝐵𝑖 = 1。
对于 100% 的数据， 1 ≤ 𝑛 ≤ 10^6,2 ≤ 𝑚 ≤ 10^5,2 ≤ 𝑝 ≤ 100,0 ≤ 𝐴𝑖,𝐵𝑖, 𝐶𝑖 ≤ 𝑝。

DP(但数据太大只能拿35分qwq),复杂度o(nmp)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
int dp[100001][101];
int n,m,p,w[3][1000001];
int main()
{
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
	scanf("%d %d %d",&n,&m,&p);
	for(int i=0;i<3;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&w[i][j]);
	for(int i=1;i<=n;i++) dp[1][w[0][i]%p]++;
	for(int i=1;i<m-1;i++)
	for(int j=1;j<=n;j++)
	for(int k=0;k<p;k++)
	dp[i+1][(k+w[1][j])%p]+=dp[i][k],dp[i+1][(k+w[1][j])%p]%=mod;
	for(int j=1;j<=n;j++)
	for(int k=0;k<p;k++)
	dp[m+1][(k+w[2][j]+w[1][j])%p]+=dp[m-1][k],dp[m+1][(k+w[2][j]+w[1][j])%p]%=mod;
	printf("%d",dp[m+1][0]%mod);
	return 0;
}

正解（DP用矩乘优化）o(p^3nlogm)

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int n,m,p,w[3][1000001],f[1001],ans;
struct matrix
{
	int n,m,a[105][105];
	inline void init(int _n,int _m)
	{
		n=_n,m=_m;
		memset(a,0,sizeof(a));
	}
	friend matrix operator * (matrix a,matrix b)
	{
		matrix c;c.init(a.n,b.m);
		for(int i=0;i<c.n;i++)
			for(int j=0;j<c.m;j++)
				for(int k=0;k<a.m;k++)
				{
					c.a[i][j]+=1ll*a.a[i][k]*b.a[k][j]%mod;
					if(c.a[i][j]>=mod)c.a[i][j]-=mod;
				}
		return c;
	}
	friend matrix operator ^ (matrix a,int b)
	{
		matrix ret;ret.init(a.n,a.m);
		for(int i=0;i<a.n;++i) ret.a[i][i]=1;
		while(b)
		{
			if(b&1) ret=ret*a;
			a=a*a;
			b>>=1;
		}
		return ret;
	}
}T,A;
int main()
{
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
	scanf("%d %d %d",&n,&m,&p);
	for(int i=0;i<3;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&w[i][j]),w[i][j]%=p;
	A.init(p,1);
	T.init(p,p);
	for(int i=1;i<=n;i++) A.a[w[0][i]][0]++;
	for(int j=0;j<p;j++)
	for(int i=1;i<=n;i++) T.a[j][j-w[1][i]<0?j-w[1][i]+p:j-w[1][i]]++;	//very important!!!
	T=T^(m-2);
	A=T*A;
	for(int i=0;i<p;i++) f[i]=A.a[i][0];
	for(int j=1;j<=n;j++)
	{
		int  t=w[1][j]+w[2][j];
		if(t>p) t=t%p;
		t=-t;
		if(t<0)t+=p;
		ans+=f[t];
		ans%=mod;
	}
	cout<<ans;
	return 0;
}

新加 一大佬的代码（比std还神！！！）

注意：：

矩阵乘法没有交换律，写时要慎重，一旦写错很难发现，前车之鉴，qwq;

3.最长公共子序列

【问题描述】
fateice 有一个长度为 n 的正整数序列 A， fjzzq2002 有一个长度为 m 的正整数序列 B。
良心出题人给了一个长度为 k 的正整数序列 C。
定义一个 A 和 B 的公共子序列是“完美的”，当且仅当这个公共子序列包含了正整数序列
C。换句话说， C 是这个公共子序列的一个子串（连续）。
求 A 和 B 最长的“完美的”公共子序列的长度。
【输入格式】
输入文件名为 lcs.in。
第一行，一个数 n，表示 fateice 的序列长度。
第二行， n 个正整数，描述 fateice 的序列。
第三行，一个数 m，表示 fjzzq2002 的序列长度。
第四行， m 个正整数，描述 fjzzq2002 的序列。
第五行，一个数 k，表示良心出题人的序列长度。
第六行， k 个正整数，描述良心出题人的序列。
【输出格式】
输出文件名为 lcs.out。
一行，一个正整数，表示 A 和 B 最长的“完美的“公共子序列的长度。如果不存在这样的
序列输出“-1”，如果 k=0 且不存在这样的序列输出 0。
输入：
4 1
2 3 5
4 1
3 4 5
2 3
5
输出：
3

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
#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[3001],b[3001],c[3001];
int f[3001][3001],g[3001][3001],na[3001],nb[3001],ans;
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	scanf("%d",&b[i]);
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
	scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+1;
			else f[i][j]=max(f[i-1][j],f[i][j-1]);
	if(!k)
	{
		printf("%d",f[n][m]);
		return 0;
	}
	for(int i=n;i;i--)
		for(int j=m;j;j--)
			if(a[i]==b[j]) g[i][j]=g[i+1][j+1]+1;
			else g[i][j]=max(g[i+1][j],g[i][j+1]);
	for(int i=1;i<=n;i++) na[i]=n+1;
	for(int i=1;i<=m;i++) nb[i]=m+1;
	for(int i=1,tmp=1;i<=n;i++)
	{
		tmp=1;
		for(int j=i;j<=n;j++)
		{
			if(a[j]==c[tmp]) tmp++;
			if(tmp==k+1)
			{
				na[i]=j;break;
			} 
		}
	}
	for(int i=1,tmp=1;i<=m;i++)
	{
		tmp=1;
		for(int j=i;j<=m;j++)
		{
			if(b[j]==c[tmp]) tmp++;
			if(tmp==k+1)
			{
				nb[i]=j;break;
			}
		}
	}
	ans=-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		if(na[i]!=n+1&&nb[j]!=m+1) ans=max(f[i-1][j-1]+g[na[i]+1][nb[j]+1]+k,ans);
	printf("%d",ans);
	return 0;
}

接近正解的错误代码qwq(并没正解考虑的那么周全qwq)

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
#include<bits/stdc++.h>
using namespace std;
int f[4][3001][3001],ans;
int n,a[3001],b[3001],c[3001],len[3000],tmp[2],maxx[2],vis[2][1001];
int m,k;
int main()
{
	freopen("lcs.in","r",stdin);
	freopen("lcs.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	scanf("%d",&b[i]);
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
	scanf("%d",&c[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++)
		{
			if(a[i]==c[j])f[0][i][j]=f[0][i-1][j-1]+1;
			else f[0][i][j]=max(f[0][i-1][j],f[0][i][j-1]);
			if(f[0][i][j]>maxx[0]) maxx[0]=f[0][i][j],tmp[0]=i;
		}	
	for(int i=1;i<=m;i++)
		for(int j=1;j<=k;j++)
		{
			if(b[i]==c[j])f[1][i][j]=f[1][i-1][j-1]+1;
			else f[1][i][j]=max(f[1][i-1][j],f[1][i][j-1]);
			if(f[1][i][j]>maxx[1]) maxx[1]=f[1][i][j],tmp[1]=i;
		}
	for(int i=tmp[0]+1;i<=n;i++)
		for(int j=tmp[1]+1;j<=m;j++)
			if(a[i]==b[j])f[2][i][j]=f[2][i-1][j-1]+1;
			else f[2][i][j]=max(f[2][i-1][j],f[2][i][j-1]);		
	for(int i=1;i<=tmp[0]-1;i++)
		for(int j=1;j<=tmp[1]-1;j++)
			if(a[i]==b[j])f[3][i][j]=f[3][i-1][j-1]+1;
			else f[3][i][j]=max(f[3][i-1][j],f[3][i][j-1]);		
	for(int i=1;i<=tmp[0];i++)
	{
		int d=1;
		for(int j=i;j<=tmp[0];j++)
		if(a[i]==c[d]) d++;
		if(d==k+1) vis[0][i]=1;
	}
	for(int i=1;i<=tmp[1];i++)
	{
		int d=1;
		for(int j=i;j<=tmp[1];j++)
		if(b[i]==c[d]) d++;
		if(d==k+1) vis[1][i]=1;
	}
	for(int i=1;i<=tmp[0];i++)
		for(int j=1;j<=tmp[1];j++)
			if(vis[0][i]==1&&vis[1][j]==1) ans=max(f[3][i-1][j-1]+f[2][n][m]+k,ans);
	if(k==0) printf("%d\n",f[2][n][m]);
	else if(f[0][n][k]!=k||f[1][n][k]!=k) printf("-1\n");
	else printf("%d",ans);
	return 0;
}

题解：

先处理出a和b的最长公共子序列，再倒着处理一遍。用na[i]来表示a从i开始匹配到c所需到的最小的编号。nb[i]表示b从i开始匹配到c所需到的最小的编号。ans=max(f[i-1][j-1]+k+g[na[i]+1][nb[i]+1],ans)。
本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/aad8cb40.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

    			  jsonContent:
				meta: false
				pages: false
				posts:
				  title: true
				  date: true
				  path: true
				  text: false
				  raw: false
				  content: false
				  slug: false
				  updated: false
				  comments: false
				  link: false
				  permalink: false
				  excerpt: false
				  categories: false
				  tags: true


There's nothing