数字计数

题意：求最大的数字与次大的数字之差,最大的数字与次小的数字之差,次大的数字与次小的数字之差,次大的数字与最小的数字之差。
思路：题目的数据量比较小，直接用一个sort排好序后进行求解即可，注意去重即可。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100010;
int a[1000];
int main(){
    int n;
    cin>>n;
    map<int,int> mp;
    int k=0;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        mp[x]++;
        if(mp[x]==1){
            a[k++]=x;
        }
    }
    sort(a,a+k);
    cout<<a[k-1]-a[k-2]<<" ";
    cout<<a[k-1]-a[1]<<" ";
    cout<<a[k-2]-a[1]<<" ";
    cout<<a[k-2]-a[0]<<endl;
    return 0;
}

数颜色

题意：给你一个序列，长度为n，求这个序列的所有的子区间中不同的数的个数之和。
思路：我们发现，我们的长度比较小，故可以直接用暴力求解，我们用两重循环来枚举这个序列所有的子区间，然后对于每个子区间，我们直接用set来存储数字，最后加上set的大小即可。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100010;
ll a[1010];
map<int,int> mp;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        set<int>st;
        for(int j=i;j<=n;j++){
            st.insert(a[j]);
            ans+=st.size();
        }
    }
    cout<<ans<<endl;
    return 0;
}

智斗恶龙

题意：给你一个矩阵，规定在某个位置开始移动，移动的距离最长为d，在可以移动的范围内，选择至少x个宝藏，然后使得这x个的最大和最小的差值最小。注意不能经过陷阱。
思路：一个很裸的bfs，我们先利用bfs来求出我们一共可以获得几种不同的宝藏，然后我们就可以对这些宝藏进行讨论了。其次是要注意几个点：1、可能一开始就在陷阱里面，这是我们要看x的具体值进行分析。2、假设我们求到的宝藏的个数为n>=x,我们要对这n个宝藏进行讨论，我们要维护一个区间长度为x的两端的差值。3、这个宝藏的表示的数可能十分大，我们可以用一个set进行去重和离散化即可。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,dx,dy,d,x;
ll a[1010][1010];
int X[]={0,0,1,-1},Y[]={1,-1,0,0};
bool inq[1010][1010];
struct node{
    int x,y;
    int dis;
}Node;
bool judge(int x,int y){
    if(x<1||y<1||x>n||y>m)  return false;
    if(a[x][y]==-1)  return false;
    if(inq[x][y]) return false;
    return true;
}
void solve(){
    set<ll> st;
    vector<ll> v;
    memset(inq,false,sizeof(inq));
    cin>>n>>m>>dx>>dy>>d>>x;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    if(a[dx][dy]==-1){
        if(x>0)  cout<<"no"<<endl;
        else  cout<<"0"<<endl;
        return;
    }
    Node={dx,dy,0};
    if(a[dx][dy]>0){
        st.insert(a[dx][dy]);
        v.push_back(a[dx][dy]);
    }
    queue<node> q;
    q.push(Node);
    inq[dx][dy]=true;
    while(q.size()){
        node top=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int newx=X[i]+top.x,newy=Y[i]+top.y;
            if(judge(newx,newy)&&top.dis<d){
                if(a[newx][newy]>0&&st.find(a[newx][newy])==st.end()){
                //    cout<<a[newx][newy]<<endl;
                    st.insert(a[newx][newy]);
                    v.push_back(a[newx][newy]);
                }
                Node={newx,newy,top.dis+1};
                inq[newx][newy]=true;
                q.push(Node);
            }
        }
    }
    if(st.size()<x)  cout<<"no"<<endl;
    else{
        int len=v.size();
        ll ans=1e18;
        sort(v.begin(),v.end());
        for(int i=x-1;i<len;i++){
            ll tmp=v[i]-v[i-x+1];
            ans=min(ans,tmp);
        }
        cout<<ans<<endl;
    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

能量水晶

由于对背包问题还不是太了解，先放着，也许一个礼拜后会回来补。ORZ