【题解】牛客NOIP暑期七天营-普及组3

X操作
100分以下做法：我也不知道怎么写
100分做法：
首先，判断的第一条件是m>=abs(x-y)，表示操作次数大于两数的差，因为如果操作次数小于两数的差了，那么x一定时无法变成y的，其次，如果操作abs(x-y)次后使x变成了y，这时如果操作次数是奇数，那么就无法达成，是偶数，我们可以通过反复加减的方式来使得x==y。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll x,y,m;
        scanf("%d%d%d",&x,&y,&m);
        ll s=abs(x-y);
        if(m>=s&&(s&1)==(m&1)) printf("Yes\n");
        else printf("No\n");
    }
}

填数
100分以下做法：我也不知道怎么写
100分做法：
首先，对于没有限制的，显然我们填1即可，对于限制1，贪心的使得a[i]==a[i-1]，对于限制2，贪心的使得a[i]==a[i-1]+1，这样贪心下去，然后判断最终得到的总和是否小于等于m即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int b[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%d",&b[i]);
        bool flag=true;
        int pre=0,sum=0;
        for(int i=1;i<=n;i++)
        {
            if(b[i]==0) sum++,pre=1;
            else if(b[i]==1) sum+=pre;
            else sum+=pre+1,pre++;
            if(sum>m) {flag=false;break;}
        }
        printf(flag?"Yes\n":"No\n");
    }
}

区间中最多的数
10分做法：暴力枚举
100分做法：1<=a[i]<=100，用前缀和维护1100每个数出现的次数，就可以O(1)的查询某个数在区间里出现的次数了，然后对于一次查询，只需要O(100)的暴力去统计即可，时间复杂度O(100q+100n)
50分做法：在100分做法的基础上，用数据结构去维护1100每个数出现的次数，咋们就可以TLE了,时间复杂度O(100qlog2(n)+100nlog2(n))。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,a[N],sum[N][105];
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=100;j++)
        sum[i][j]=sum[i-1][j]+(a[i]==j);
    while(q--)
    {
        int l,r,mx=0,ans;
        scanf("%d%d",&l,&r);
        for(int i=1;i<=100;i++)
            if(sum[r][i]-sum[l-1][i]>=mx) ans=i,mx=sum[r][i]-sum[l-1][i];
        printf("%d\n",ans);
    }
}

子段和
100分以下做法：我也不知道怎么写
100分做法：
1.f[i][j]表示[i,j]这段区间的和，开一个vis数组保存每个和出现的次数，如果之星操作1，我们只需要删除n个区间的值，执行操作2，只需要假如n个区间的值，时间复杂度O(nm)。
2.记录前缀和和一个vis数组，vis数组里保存某个前缀和出现的次数，对于每次查询O(n)的去跑所有前缀和，判断sum-x这个前缀和是否存在即可,时间复杂度最坏O(nm)。
3.由于数据水，时间复杂度O(n^2 m)的算法也被放过了，很遗憾我的数据这么水。
做法1：

【题解】牛客NOIP暑期七天营-普及组3

全站热榜

创作者周榜