7.11 C 乱搞题

有 \(n\) 个桶，每个桶中装有 \(n\) 个数。保证 \(1 \sim n\) 中的每种数字在所有桶中一共出现恰好 \(n\) 次。

每次操作选择一个区间 \([l,r]\)，若满足第 \(l \sim r\) 个桶最上端的数相同，可以将这些桶最上端的数一起取出。

求至少需要多少次操作才能取出所有的数。

保证数据随机

数据范围

\(1 \leq n \leq 1000\)

思路

考虑将相邻两个桶内的相同的数连一条边。可以发现如果两条边不存在交叉，就存在一种方案使得这两组数都可以同时被拿出，也就可以减少两次操作数。而如果想要选择最多不相交的边，不难发现就是求两个序列的最长公共子序列。

一般求 LCS 的方法是dp，时间复杂度为 \(O(n^2)\)，但由于本题数据保证随机，可以在dp的基础上优化。

对于第二个序列，记录每一个值出现的位置，并且从后往前遍历第一个序列，查询在第二个序列中以相同字符下标前的数字结尾的公共字串的最大值，可以用树状数组维护。由于数据随机，相邻两列之间相同对数的期望为 \(O(n)\)。

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1010;
int a[N][N],n,c[N],ans,f[N];
vector<int>id[N];
int lowbit(int x){return x&-x;}
void update(int x,int k){while(x<=n){c[x]=max(c[x],k);x+=lowbit(x);}}
int query(int x){int res=0;while(x){res=max(res,c[x]);x-=lowbit(x);}return res;}
int solve(int a[],int b[])// LCS
{
	for(int i=1;i<=n;i++) id[b[i]].push_back(i);
	for(int i=1;i<=n;i++)
	{
		for(auto j:id[a[i]]) f[j]=query(j-1)+1;
		for(auto j:id[a[i]]) update(j,f[j]);
	}
	int res=query(n);memset(c,0,sizeof(c));
	for(int i=1;i<=n;i++) id[i].clear();return res;
}
int main()
{
//	freopen("rand.in","r",stdin);
//	freopen("rand.out","w",stdout);
	scanf("%d",&n);ans=n*n;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
	for(int i=1;i<n;i++) ans-=solve(a[i],a[i+1]);printf("%d\n",ans);
	return 0;
}

7.11 D 奇怪题

有 \(n\) 个七位数，记作 \(a_1 \sim a_n\)。

对七位数 \(v\) 的一次位移会将 \(v\) 的最高位移到最低位，其余位相对顺序保持不变。例如 \(1234567\) 在一次位移后会变
成 \(2345671\)。

每次操作可以选定一段区间 \([l,r]\) 和一个整数 \(k\)，对 \(a_l \sim a_r\) 分别进行 \(k\) 次位移。
求至少需要多少次操作，才能将所有 \(a_i\) 都调整成 可能的最大值。

数据范围

\(1 \leq n \leq 501\)

思路

首先可以将七位数字都相同的数删去；对于剩下的数，由于 \(7\) 是一个质数，可能的最大值只能在一个位置取到，设为 \(c_i\)。

那么题目就转化为每次选择一个区间，给区间内的每一个数都加上 \(k\)，求最小的操作次数使得所有的数在模 \(7\) 意义下都为 \(0\)。

继续考虑差分，先对原序列求一个差分数组，每次的区间加操作就转化为给差分序列中的一个数加上一个数，另一个数减去相同的数。现在就是要用最少的操作次数使得差分序列中的每一个数在模 \(7\) 意义下都为 \(0\)（下面简称为 \(0\)）。

对于原差分序列的一个有 \(x\) 个元素的子集，如果这 \(x\) 个元素的和为 \(0\)，那么每次对集合中的两个数进行操作不会改变和的大小，那么必然能在 \(x-1\) 次操作内将这些元素都变成 \(0\)。那么现在就是要在满足和为 \(0\) 的情况下，将原差分序列中的 \(n+1\) 的数分成尽可能划分成多的子集。

首先可以将序列中和为 \(0\) 的两个数单独拎出来构成一个集合，这样操作后就剩下之多 \(3\) 种不相同的数。

设 \(f_{i,j,k}\) 表示三种数分别剩余 \(i,j,k\) 个时所需的最少次数。由于转移的方案特别多，可以首先剪去很多劣的方案。对于不劣的方案，显然满足以下两点：

1. \(a,b,c<7\)。如果一个数大于 \(7\) 了，那么显然把这 \(7\) 个数单独放一个集合更优。

2.\(gcd(a,b,c)=1\)，如果他们的最大公约数不为 \(1\)，那么就可以把这个集合拆分成若干个相等的子集，显然不是优的方案。

这样一稿剩余的合法转移方案数就很少了，可以通过本题。

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=521,T=1e7;
const int YY[9]={1111111,2222222,3333333,4444444,5555555,6666666,7777777,8888888,9999999};
int m,id[N],c[N],ans,n,a[N],cnt[N];
short f[N][N][N];
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
struct node{int a,b,c;}p[N];
int main()
{
//	freopen("strange.in","r",stdin);
//	freopen("strange.out","w",stdout);
	scanf("%d",&n);
	for(int x,i=1;i<=n;i++)
	{
		scanf("%d",&x);int j,maxv=0;
		for(j=0;j<9;j++) if(x==YY[j]) break;
		if(j!=9) {i--,n--;continue;}
		for(j=0;j<7;j++)
		{
			if(x>maxv) maxv=x,a[i]=j;
			x=x*10%T+x*10/T;
		}
	}
	for(int i=n+1;i>=1;i--) a[i]=(a[i]-a[i-1]+7)%7,cnt[a[i]]++;
	for(int x,i=1;i<=3;i++) x=min(cnt[i],cnt[7-i]),ans+=x,cnt[i]-=x,cnt[7-i]-=x;
	for(int i=1;i<=6;i++) if(cnt[i]) c[++m]=cnt[i],id[m]=i;m=0;
	for(int i=0;i<7;i++)
	    for(int j=0;j<7;j++)
	        for(int k=0;k<7;k++)
//	            if((i||j||k)&&(i*id[1]+j*id[2]+k*id[3])%7==0) p[++m]=node{i,j,k};
	            if((i||j||k)&&(i*id[1]+j*id[2]+k*id[3])%7==0&&gcd(gcd(i,j),k)==1) p[++m]=node{i,j,k};
	memset(f,0x3f,sizeof(f));f[0][0][0]=0;
	for(int i=0;i<=c[1];i++)
	    for(int j=0;j<=c[2];j++)
	        for(int k=0;k<=c[3];k++)
	            for(int t=1;t<=m;t++)
	                if(i>=p[t].a&&j>=p[t].b&&k>=p[t].c)
	                    f[i][j][k]=min(f[i][j][k],f[i-p[t].a][j-p[t].b][k-p[t].c]+p[t].a+p[t].b+p[t].c-1);
	printf("%d\n",f[c[1]][c[2]][c[3]]+ans);
	return 0;
}