8月1号

thomas1234567 · 2025-08-02 17:49:49 · 个人记录

第一题

题意（简化）：输入的第一行包含 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

代码：

#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)

代码：

#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;
}