A 数字计数

  • 分析

    较为基础，因为要最大最小，次大次小，可以先想到排序，但是不要忘了，数值中有重复的，所以还要去重。去重的方法有两种，一种是直接调用unique函数，另一种是遍历一遍将出现一次的计入数组

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

分析

枚举每一个区间的开头，记录每一种颜色的出现次数，如果第一次出现就可以+1，然后ans统计答案O(n^2)

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);

    int ans=0;
    for (int i=1;i<=n;i++)
    {
        int sum=0;
        memset(cnt,0,sizeof(cnt));
        for (int j=i;j<=n;j++)
        {
            if(cnt[a[j]]==0) sum++;
            cnt[a[j]]++;

            ans+=sum;
        }
    }

    printf("%d\n",ans);

    return 0;
}

还有一种就是O(n),记录这个颜色上一次出现的位置，设为x,pre[x],而这一段区间[pre[x],x]可以被加入(n-i+1)次

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);

    int ans=0;
    for (int i=1;i<=n;i++)
    {
        ans+=(n-i+1)*(i-pre[a[i]]);
        pre[a[i]]=i;
    }

    printf("%d",ans);

    return 0;
}

C 智斗恶龙

  • 分析

    题目中给出了n,m,sx,sy,d,x,想一想每一个的作用。n,m是地图的大小,d规定了人只能走到
    abs(x-sx)+abs(y-sy)<=d的位置，而x是必须要选的个数。但是题目中说，即使到了某一个
    点，也可以不取宝藏，那我就跑遍所有能到的点，记录宝藏的个数与值，去重，然后就可以求最小值了

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1100;

int n,m,sx,sy,d,len;ll cnt;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
ll a[N][N],f[N][N],ans[N*N];

struct nk
{
    int x,y;
    nk(int xx,int yy):x(xx),y(yy){}
};
queue<nk>q;

inline void Pre()
{
    cnt=0;
    memset(f,0,sizeof(f));
}

inline int check(int x,int y)
{
    if(abs(x-sx)+abs(y-sy)>d) return 1;
    return x<1||x>n||y<1||y>m;
}

inline ll Get(int h,int l)
{
    q.push(nk(h,l));f[h][l]=1;
    if(a[h][l]==-1) return -1;
    while(!q.empty())
    {
        nk t=q.front();q.pop();
        int x=t.x,y=t.y;
        if(a[x][y]>0) ans[++cnt]=a[x][y];

        for (int i=0;i<4;i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(check(xx,yy)) continue;
            if(f[xx][yy]) continue;
            if(a[xx][yy]==-1) continue;

            q.push(nk(xx,yy));
            f[xx][yy]=1;
        }
    }

    ll op=1e17;
    sort(ans+1,ans+cnt+1);
    cnt=unique(ans+1,ans+cnt+1)-ans-1;
    if(cnt<len) return -1;
    for (ll i=1;i<=cnt;i++)
    {
        ll nex=i+len-1;
        if(nex>cnt) break;
        op=min(op,ans[nex]-ans[i]);
    }

    return op;
}

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        Pre();
        scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&d,&len);

        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                scanf("%lld",&a[i][j]);

        ll las=Get(sx,sy);

        if(las==-1) puts("no");
        else printf("%lld\n",las);
    }

    return 0;
}

D 能量水晶

  • 分析

    这是好题啊。因为题目中说要用到不能用为止。假设当前我还剩k的能量，说明已经没有消耗值小于k的法术了,那这是不是意味着我可以枚举我剩余的能量值,然后用我大于当前剩余容量的法术去凑出m-k的能量，这难道不是一个01背包求方案数？

/*

*/
#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=3100;

ll n,m,ans;
ll a[N],cnt[N];

int main()
{
    scanf("%lld%lld",&n,&m);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
    sort(a+1,a+n+1);

    ll l=1;
    for (ll i=0;i<=m;i+=a[l],l++)
    {//枚举余下容量
        ll rem=m-i;
        if(rem<0) break;
        memset(cnt,0,sizeof(cnt));
        cnt[0]=1;
        for (ll j=l+1;j<=n;j++)
            for (ll k=rem;k>=a[j];k--)
                cnt[k]+=cnt[k-a[j]];

        for (ll j=rem;j>=rem-a[l]+1;j--) ans+=cnt[j];
    }

    printf("%lld\n",ans);

    return 0;
}