牛客IOI周赛18-普及组题解

A:数字计数
简单题，基础模拟，我们sort一遍就可以了
但是我们要用一个unique去重，不太熟悉unique的同学可以用一个桶，或者和上一次的值比较一下手动去重！
然后直接输出，这个没什么好说的吧？
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,a[105];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);n=unique(a+1,a+n+1)-a-1;
    printf("%d %d %d %d\n",a[n]-a[n-1],a[n]-a[2],a[n-1]-a[2],a[n-1]-a[1]);
    return 0;
}

B:数颜***r>这题有两种做法，一种我们直接暴力考虑，然后模拟扫一遍就好了！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e3+5;
int n,a[N],ans;bool usd[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        for(int j=1;j<N;j++)usd[j]=false;
        for(int j=i,now=0;j<=n;j++){
            if(!usd[a[j]])usd[a[j]]=true,now++;
            ans+=now;
        }
    }
    printf("%d\n",ans);
    return 0;
}

然后第二种做法是我们常见的套路，我们发现可以根据每个数看它的贡献，就是其他区间所不存在的，单独出现的贡献我们可以记录一下出现的位置直接算出来！
提示一类重要的套路关于算贡献的，可能在一些对于答案无法直接下手的情况方便做好多！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e3+5;
int n,a[N],lst[N],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)ans+=(i-lst[a[i]])*(n-i+1),lst[a[i]]=i;
    printf("%d\n",ans);
    return 0;
}

C:智斗恶龙
这题是一道对于初学者稍微要码点细节的题
我们可以先bfs一遍，这里要注意一下边界
然后bfs出来可以满足的结果我们直接sort就可以了
sort以后我们要判断两种情况一种无解还有一种我们就根据题目要求更新答案就好了！
需要注意的使我们要判断起点的合法性！
讲一下关于这个状态我们可以把它搞成二维的，也可以把它重标号改成一维的，这里如果是一维的可能能方便我们平常的写题，包括模板之类的养成习惯比较好！
类比我们可以参考n进制的重标号，以及排列的重标号就是康托展开！
这里引申一下，可能和本题并没有什么直接关系！
（下面的代码用了fread，只是加速，考试的时候卡常，看不懂的同学可以跳过，和题目没有直接关系哦！）
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e6+5;
const LL Inf=1e18;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int n,m,sx,sy,d,x,len,px[N],py[N],dfn,dis[N];LL a[N],mp[N];
char buf[1<<21],*p1=buf,*p2=buf;
inline int getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
inline LL read(){
    LL x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
int id(int x,int y){return (x-1)*m+y;}
int main(){
    int T=read();
    while(T--){
        n=read();m=read();sx=read();sy=read();d=read();x=read();dfn=len=0;
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)dfn++,px[dfn]=i,py[dfn]=j,mp[dfn]=read();
        for(int i=1;i<=dfn;i++)dis[i]=-1;
        if(mp[id(sx,sy)]==-1){puts("no");continue;}
        queue<int>que;while(!que.empty())que.pop();
        que.push(id(sx,sy));dis[id(sx,sy)]=0;
        while(!que.empty()){
            int np=que.front(),x=px[np],y=py[np];que.pop();
            if(~dis[np]&&dis[np]<=d&&mp[np])a[++len]=mp[np];
            for(int i=0,nx,ny;i<4;i++){
                nx=x+dx[i];ny=y+dy[i];
                if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&mp[id(nx,ny)]!=-1&&dis[id(nx,ny)]==-1)
                    dis[id(nx,ny)]=dis[np]+1,que.push(id(nx,ny));
            }
        }
        if(len<x){puts("no");continue;}
        sort(a+1,a+len+1);len=unique(a+1,a+len+1)-a-1;
        if(len<x)puts("no");
        else{
            LL ans=Inf;
            for(int i=x;i<=len;i++)ans=min(ans,a[i]-a[i-x+1]);
            printf("%lld\n",ans);
        }
    }
    return 0;
}

D:能量水晶
我们枚举这个不能选的点，然后我们为了防止多算钦定一个最后一定要选的点，然后对于之前的做01背包
注意背包大小的范围必须满足题目条件
然后这题的妙处是我们可以一边01背包一边更新答案
这样可以保证复杂度是平方的！
然后出题人说不要写高精，因此玄学的用long long就可以了！
代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e3+5;
int n,m,a[N],s[N];LL dp[N],ans;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    if(s[n]<m){puts("0");return 0;}
    else if(s[n]==m){puts("1");return 0;}
    dp[0]=1;
    for(int i=n;i;i--){
        for(int j=max(m+1-a[i]-s[i-1],0);j+s[i-1]<=m;j++)ans+=dp[j];
        for(int j=m;j>=a[i];j--)dp[j]+=dp[j-a[i]];
    }
    printf("%lld\n",ans);
    return 0;
}