[数据结构与算法]2021/8/6考试总结

T1 纸牌

在桌面上放着 n 张纸牌，每张纸牌有两面，每面都写着一个非负整数。你的邪王真眼可 以看到所有牌朝上的一面和朝下的一面写的数字。现在你需要将一些牌翻过来，使得所有牌
朝上的一面中，至少有一半（大于等于 n+1 除以 2 向下取整）的数字是一样的。请你求出最
少需要翻几张牌，或者判断无解。
注意：在翻牌的时候，你不能把牌扔掉，不能偷偷把别的牌放进来，也不能用笔涂改牌
上面的数字。

解题记录

只要用一个数组存每个值最大能有多少个朝上，也就是正面的出现次数+背面的出现次数，相同则算一次，然后枚举每个值，判断最大能否出现（n+1）/2次，记得如果正面出现次数大于（n+1）/2，要输出0

离散化过后就能把把每个值存下来了

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e5+7;
int a[N],b[N],c[2*N],cnt[2*N],kept[2*N];
int n,tot=0,ans=-1;
bool cmp(int x,int y)
{
	return x<y;
}
int main()
{
	freopen("card.in","r",stdin);
	freopen("card.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		c[++tot]=a[i];
		c[++tot]=b[i];
	}
	sort(c+1,c+1+tot,cmp);
	int len=unique(c+1,c+1+tot)-c-1;
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(c+1,c+len+1,a[i])-c;
		b[i]=lower_bound(c+1,c+len+1,b[i])-c;
		cnt[a[i]]++;
		cnt[b[i]]++;
		if(a[i]==b[i]) cnt[a[i]]--;		
		kept[a[i]]++;
	}
	for(int i=1;i<=len;i++)
	{
		if(cnt[i]>=((n+1)/2))
		ans=max(ans,kept[i]);
	}
	if(ans==-1) 
	{
		printf("Impossible");
		return 0;
	}
	else if(ans>=(n+1)/2) ans=0;
	else ans=(n+1)/2-ans;
	printf("%d",ans);
	return 0;
} 

T2 后缀数组

题目描述
给定一个字符串 S，它的长为 n，后缀数组的功能是，将其所有后缀按字典序从小到大
排好序。我们对其做一点小小的改动：再给定一个数字 m，记 ssi表示从 S 的第 i 位开始、
长度最多为 m 的子串，我们希望将这些字符串{ssi}按字典序从小到大排序。举个栗子，当
S=“abcab”，m=2 时，ssi 的值分别为：
ss1=“ab”
ss2=“bc”
ss3=“ca”
ss4=“ab”
ss5=“b”
但是，只是把{ssi}全部排好序还是太简单了。初始状态下，ss1~ssn 按顺序排成一行，我
们只能通过不断交换某两个相邻字符串的位置来做排序。再举个栗子，把上面提到的 ss1~ss5
排好序的一种方案是：
(0) 原序列：“ab”, “bc”, “ca”, “ab”, “b”
(1) 交换第 3 和第 4 个串：“ab”, “bc”, “ab”, ca", “b”
(2) 交换第 2 和第 3 个串：“ab”, “ab”, “bc”, ca", “b”
(3) 交换第 4 和第 5 个串：“ab”, “ab”, “bc”, b", “ca”
(4) 交换第 3 和第 4 个串：“ab”, “ab”, “b”, bc", “ca”
现在，你需要求出，最少通过多少次相邻字符串交换，才能把所有子串{ssi}排成字典序
从小到大的形式。

解题思路

如果是数字，那么答案就是逆序对个数，现在是字符串，肯定不能用树状数组，考虑CDQ分治求二维偏序，比较两个字符串的大小可以预处理字符串哈希，然后二分的找到两个串第一个不同的位置，比较这个位置即可

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4+50;
typedef long long LL;
typedef unsigned long long ULL;
ULL H[N],P[N];
int p[N],pl[N],pr[N];
char s[N];
int n,m;
ULL val(int l,int r)
{
	return H[r]-H[l-1]*P[r-l+1];
}
LL ans=0;
bool cmp(int x,int y)
{
	if(s[x]<s[y]) return 0;
	return 1;	 
}
bool calc(int a,int b)
{
	int l=1,r=min(m,n-(max(a,b))+1),mid,ans=-1;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(val(a,a+mid-1)==val(b,b+mid-1))
		{
			ans=mid;
			l=mid+1; 
		} 
		else r=mid-1;
	}
//	cout<<a<<' '<<b<<' '<<ans<<endl;
	if(ans==m) return 0;
	if(ans==-1) return cmp(a,b);
	else return cmp(a+ans,b+ans); 
}
void CDQ(int l,int r)
{
	if(l>=r) return;
	int mid=(l+r)>>1;
	CDQ(l,mid);
	CDQ(mid+1,r);
	int i=l,j=mid+1,top=0;
	while(i<=mid&&j<=r)
	{
		if(calc(p[i],p[j])==0) 
		{
			pl[++top]=p[i];
			i++;
		}
		else
		{
			ans+=(mid-i+1);
			pl[++top]=p[j];
			j++;
		}
	}
	while(i<=mid) 
	{
		pl[++top]=p[i];
		i++;
	}	
	while(j<=r)
	{
		ans+=(mid-i+1);
		pl[++top]=p[j];
		j++;		
	}
	for(int k=1;k<=top;k++)
	p[k+l-1]=pl[k];
}
int main()
{

	freopen("sort.in","r",stdin);
	freopen("sort.out","w",stdout);
	scanf("%d%d",&n,&m);
	scanf("%s",s+1);
	H[1]=s[1]-'a'+1; 
	P[1]=131; 
	p[1]=1;
	for(int i=2;i<=n;i++)
	{
		H[i]=H[i-1]*131+s[i]-'a'+1;
		P[i]=P[i-1]*131;
		p[i]=i;
	}
	CDQ(1,n);
	printf("%d",ans);
	return 0;
}

T3 巧克力

题目描述
有一块分成 nm 个格子的矩形巧克力，虽然形状上很规整但质量分布并不均匀，每一
格有各自的重量，用 nm 个正整数表示。你需要将这一整块巧克力切成 k 小块，要求每块
都是矩形，且它们的重量分别为 a1~ak。一块巧克力的重量等于它包含的所有格子的重量之
和。
切巧克力的时候，你可以每次选一块大的巧克力，沿着某条格线横向或纵向将其切成两
块小的巧克力。切下来的小块巧克力可以继续切割。切割路线不能是折线或斜线。任何时 候当前的所有巧克力块都必须是矩形的。
对于给定的巧克力和分割要求，请你判断是否存在一个切割方案满足上述要求。

考试思路

原本想写个暴力，结果没来得及

正解

搜索F（u，d，l，r，s）
表示当前块的上下左右界以及w集合的状态
用子集枚举进行下一次搜索，当只剩一个元素时，比较巧克力的价值和与w的值是否相等
剪枝：当当前巧克力的值之和小于w之和时返回0
但是莫名原因只有80pts

#include<bits/stdc++.h>
using namespace std;
const int N = 25;
int a[N][N],w[N],sum[N][N];
int n,m,k;
int count(int S)
{
	int res=0;
	for(int i=1;i<=k;i++)
	if((S>>(i-1))&1) res++;
	return res;
}
bool F(int u,int d,int l,int r,int S)
{
	int res=0;
	for(int i=1;i<=k;i++)
	if((S>>(i-1))&1) res+=w[i];
	if(res!=sum[d][r]-sum[d][l-1]-sum[u-1][r]+sum[u-1][l-1]) return 0;
	if(count(S)==1)
	{
		for(int i=1;i<=k;i++)
		{
			if((S>>(i-1))&1)
			if(w[i]==sum[d][r]-sum[d][l-1]-sum[u-1][r]+sum[u-1][l-1]) return 1;	
		}	
		return 0;	
	}
	for(int j=(S-1)&S;j;j=(j-1)&S)
	{
		for(int i=u;i<d;i++)
		if(F(u,i,l,r,j)&&F(i+1,d,l,r,S-j)) return 1;
		for(int i=l;i<r;i++)
		if(F(u,d,l,i,j)&&F(u,d,i+1,r,S-j)) return 1;
	}
	return 0;
}
int main()
{

    freopen("chocolate.in","r",stdin);
    freopen("chocolate.out","w",stdout);
	int t;
	cin>>t;
	while(t--)
	{
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				scanf("%d",&a[i][j]);
				sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
			}
		}
		for(int i=1;i<=k;i++)
		scanf("%d",&w[i]);
		if(F(1,n,1,m,(1<<k)-1))
		{
			printf("yes\n");
			
		}
		else printf("no\n");
	}
	return 0;
}

T4 三向城

三向城是一个巨大的城市，之所以叫这个名字，是因为城市中遍布着数不尽的三岔路口。
（来自取名力为 0 的出题人）
具体来说，城中有无穷多个路口，每个路口有唯一的一个正整数标号。除了 1 号路口外，
每个路口都连出正好 3 条道路通向另外 3 个路口：编号为 x（x>1）的路口连出 3 条道路通
向编号为 x2，x2+1 和 x/2（向下取整）的 3 个路口。1 号路口只连出两条道路，分别连向
2 号和 3 号路口。
所有道路都是可以双向通行的，并且长度都为 1。现在，有 n 个问题：从路口 x 到路口
y 的最短路长度是多少

解题思路

大水题，这是一颗二叉树，暴力向上找lca就可通过此题，但是计算深度稍有麻烦，于是考试时推了推发现如果A>B,则dep[A]>=dep[B]，这是因为
(((12+1)2+1)2+1)……<1222*2……
所以不需要比较深度，直接让比较大的数往上跳就可以了

#include<bits/stdc++.h>
using namespace std;
int n,x,y;
int main()
{
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
	cin>>n;
	while(n--)
	{
		int ans=0;
		scanf("%d%d",&x,&y);
		while(x!=y)
		{
			if(x<y) swap(x,y);
			x/=2;
			ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

T5 丑数

题目描述
对于一给定的素数集合 S = {p1, p2, …, pK},
来考虑那些质因数全部属于 S 的数的集合.这个集合包括,p1, p1p2, p1p1, 和 p1p2p3
(还有其它).
这是个对于一个输入的 S 的丑数集合.你的工作是对于输入的集合 S 去寻找集合中的
第 N 个丑数。longint(signed 32-bit)对于程序是足够的.
注意:我们不认为 1 是一个丑数

考试思路

一开始写的暴力，但觉得这样没多少分，于是开始推，突然想到可以用个堆维护最小丑数，再把这个数乘以每个质数并放进堆里，n次之后就是答案，但是感觉这样这个堆会爆炸，于是加了个小剪枝，就是如果堆内元素大于n，那么最大的那个肯定轮不上了，弹出就好了，但是堆不支持弹出最大元素，所以改写成set，成功拿到90pts

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int k,n,p[265];
set<LL>s;
int main()
{
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
    scanf("%d%d",&k,&n);
    for(int i=1;i<=k;i++)
    {
  		scanf("%d",&p[i]);
  		s.insert(p[i]);
    }
    LL ans=0;
    for(int i=1;i<=n;i++)
    {
    	ans=*s.begin();
    	for(int j=1;j<=k;j++)
		s.insert(1ll*ans*p[j]);
		s.erase(ans);
    	while(s.size()>n+2) 
		s.erase(--s.end());
    }
    cout<<ans<<endl;
    return 0; 
}

正解

貌似不用堆也不用set就可以，待填

T6 兔子

题目描述
我们认为 n 个位置的高度形成了 1 到 n 的一个排列,这个排列要么满足奇数项的高度比
相邻位置都大, 要么满足偶数项的高度比相邻位置都大.
n=1 时,有 1 种可能,就是这 1 个位置的高度为 1
n=2 时,有 2 种可能,可以是(1,2)或(2,1)
n=3 时,有 4 种可能,(1,3,2) (2,3,1),(2,1,3),(3,1,2)
答案可能很大,只需要输出答案对 mod 取模的结果

考试思路

dfs走人

正解

原题是[SDOI2010]地精部落
看了好多题解都不懂DP式的含义，终于找到了一个能看懂的
设DP[i]，表示长度为i的序列个数
首先如果一个序列合法，那么一最大值的位置为界，左右两边肯定也是合法的
所以，我们就枚举最大值的位置（要么全是奇数要么全是偶数），那么
$$DP[i]=\sum DP[j?1]\times DP[i?1?j]\times C_{i?1}^{j?1}$$
也就是从这些数里选若干个填在前面
因为模数不固定，所以不能求逆元，只能杨辉三角，但是由于n过大，存不下组合数，所以要与DP数组同步求解，可以用滚动数组优化

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4204;
LL f[N],C[2][N],mod;	
int n;
int main()
{
	cin>>n>>mod;
	f[0]=f[1]=1;
	C[0][0]=C[1][0]=C[1][1]=1;
	for(int i=2;i<=n;i++)
	{
		C[i&1][0]=C[i&1][i]=1;
		for(int j=1;j<i;j++) 
		C[i&1][j]=(C[(i-1)&1][j-1]+C[(i-1)&1][j])%mod;
		for(int j=0;j<i;j+=2)
		f[i]=(f[i]+f[j]*f[i-1-j]%mod*C[(i-1)&1][j]%mod)%mod;
	}
	cout<<(f[n]<<1)%mod;
}