2018-04-20

区间k问题相关

A

给出一个长度为n的数组a 求出最长的子序列 满足和mod k==0
转跳链接 dp

B

给出一个长度为n的数组a 求出最长的子串满足和mod k==0

参考AC代码

#include<bits/stdc++.h>
#define maxn 100005 
using namespace std;
int n,k;
int s1[maxn],s2[maxn];
int main(){
    cin>>n>>k;
    int sum=0;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        sum+=x%k;       
        s1[sum]=i;       
        if(!s2[sum]) s2[sum]=i;
    }
    int Max=0;
    for(int i=0;i<k;i++){
    	f(s1[i]-s2[i]>Max) Max=s1[i]-s2[i];
	}
    printf("%d",maxx);
}

思路

由于是连续的子串我们对前缀和求mod
最后相当于求每个0到k-1的余数第一次出现和最后一次出现的长度差维护最大值这样可以把余数减去即可以被k整除
s1记录的是最后一次出现的位置 s2记录的是第一次出现的位置

C

给出一个长度为n的数组a 要求从中取出m个数字要求这m个数字中任意两数的差都是k的倍数
专挑连接组合数

D

给定一个长度为n的数组a 求有多少个子区间(i,j)满足sumij为k的倍数

参考AC代码

#include<bits/stdc++.h>
#define mm(a,b) memset(a,b,sizeof a)
#define maxn 100050
#define LL long long
using namespace std;
int a[maxn];
LL sum[maxn];
int hashh[maxn];
int main(){
//	freopen("input.txt","r",stdin);
	int n,k;
	scanf("%d%d",&n,&k);
	mm(sum,0),mm(hashh,0);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+1LL*a[i];
	}
	for(int i=1;i<=n;i++) sum[i]%=k;
	LL ans=0;
	for(int i=1;i<=n;i++){
		ans+=hashh[sum[i]];
		hashh[sum[i]]++;
		if(sum[i]==0) ans++;
	}
	printf("%lld\n",ans);
	return 0;
}

思路

(a[i]+a[i+1]+···+a[j])%k==0
(sum[j]-sum[i-1])%k==0
sum[j]%k==sum[i-1]%k
所以问题转换成前缀和取mod k后有多少个两两相同的位置
从i到n 实时维护hash可以把复杂度降到on

本文标题:区间k问题相关

文章作者:Hippopmonkey

发布时间:2018-04-20, 16:35:52

最后更新:2018-04-20, 16:53:26

原始链接:http://xuboming8.github.io/2018/04/20/区间k问题相关/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。