8月1号

第一题

题意（简化）：输入的第一行包含 N，接下来的 N 行每行包含一头奶牛的整数 ID。输出 ID 之和为 7 的倍数的最大连续奶牛组中的奶牛数量。如果不存在这样的组，则输出 0。

时间复杂度：O(n*n),

O(n的二次方)得部份分

重点：找出区间长度的最大值枚举

l

和

r

公式：

(a+b)%c=(a%c+b%c)%c

(a-b)%c=(a%c-b%c)%c

(ab)%c=((a%c)(b%c))%c

代码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int vis[15],n,pre[1000001],a[1000001],maxi=0;
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		pre[i]=pre[i-1]+a[i];
		pre[i]=pre[i]%7;
	}
	vis[0]=0;
	vis[1]=vis[2]=vis[3]=vis[4]=vis[5]=vis[6]=-1;
	for(int i=1;i<=n;i++)
	{
		int tmp=pre[i];
		if(vis[tmp]==-1)
		{
			vis[tmp]=i;
		}
		else
		{
			maxi=max(maxi,i-vis[tmp]);
		}
	}
	cout<<maxi;
	return 0;
}

第二题

题意（简化）：第一行包含两个整数 N 和 K，以下 N 行每行包含一个整数 A i 输出一个整数，代表 K 倍区间的数目。

(x-1)+(x-2)+(i)=二分之x(x-1)

a	3	5	1	6	2	14	10
sum	3	8	9	15	17	31	41
sum%7	3	1	2	1	3	3	6

代码：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int tong[N];
signed main(){
	int n,k;
	cin>>n>>k;
	tong[0]++;
	int cnt=0;
	int a,sum=0;
	for(int i=1;i<=n;i++){
		cin>>a;
		sum+=a;
		sum%=k;
		cnt+=tong[sum];
		tong[sum]++;
	}
	cout<<cnt;
}

文章操作

第一题

代码：

第二题

相关推荐

评论

8月1号