https://ac.nowcoder.com/acm/contest/67741/E

题目叫做本题主要考察贪心，实际上不是 alt

题目大意：

t组测试，每组给出一个n和m,n是初始选手数量，然后给出这n个选手的初始分数，接着给出m对数，为每次对战的两个选手。规则是赢+3，输+0，平都+1。

赛时状态：

比赛时，发现这题名字叫贪心，而且最气人的是，看帮时AC第三的题就是这道，于是乎，照着贪心写了。完全没考虑数据量如此小，也有迷惑性在内，因为t有一个范围，n,m又有范围，也没怎么具体看，误认为范围巨大。

题目思路

用dfs枚举所有组的三种情况，然后得出最小的rk.

看完方法后的第一次补题目

之前学过dfs，于是完全按照之前全排列等的回溯逻辑去写，其实第一次补提时，完全没深入理解dfs，仅仅是背了个模板。于是写出了内存超限，运行超时，等各种错误。附上代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int>arr;
int cot=0; int te=1,rk=1;
int dfs(map<pair<int,int>,int> M,vector<int> arr,int n){
    if(n>=cot){
        for(int i=1;i<=arr.size();i++){
            if(arr[i]>arr[1]) te++;
        }
        rk=max(te,rk);
    }
    for(auto &x:M){
        if(x.second){
            x.second--;
             
            arr[x.first.first]+=3;
            dfs(M,arr,n+1);
             
            arr[x.first.second]+=3;
            dfs(M,arr,n+1);
            arr[x.first.first]++,arr[x.first.second]++;
            dfs(M,arr,n+1);
             
            x.second++;
        }
    }
    return rk;
}
signed main(){
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m; 
        arr.claer();
        arr.resize(n);
        cot=0;
        for(int i=1;i<=n;i++) cin>>arr[i];
        map<pair<int,int>,int>M;
        for(int i=0;i<m;i++){
            int x,y; cin>>x>>y;
            if(x>y) swap(x,y);
            if(x==1) arr[1]+=3;
            else{
                M[{x,y}]++;
                cot++;
            }
        }
        //cout<<dfs(M,arr,0)<<"\n";
    }
}

代码问题一：对数组和pair结合体理解不到位

完全没必要利用map存值进去，以前没写过一个引索能进行两个值的索引的数组，所以对vector<pair<int,int>>的使用不到位，这题这样用，确实能避免许多麻烦

代码问题二：对dfs的理解不到位

dfs(int x){
	if(x>n) return 数组 //从1开始版本
    for(int i=1;i<=n;i++){
    	if(!bool[i]){
        	arr[x]=i;//此层
            bool[i]=ture; //此数
            dfs(x+1);
            bool[x]=false;
         }
     }
 }

误认为dfs的回溯功能只能是for循环结合bool特判实现的，但其实不然，for循环主要用于循环填数，全排列的实现类似滚动数组，最外层的顺序是先利全false的bool将一整个数组填入如：1.2.3。 最后一层bool[1.2.3]都=ture。由于递归的回溯，会回到f(2),3那层被全部释放（包括bool[3]是ture这回事），这时的for指向了3，所以f(2)=3,又让bool[2]=false，这样就能将f(3)=2了，由于f(2)那里本身是不存在bool[2]=ture,所以下一步f(3)也能顺利赋到2。同理，最后一层的所有东西都被释放。刚刚我们退到了dfs(2)，这次回退到dfs(1)，可bool[1]=ture,于是for指向了2,于是arr[1]=2,bool[1]=ture。

理解完递归后，于是发现，这题只需要暴力遍历三种情况就行

因为我想要的效果是，从1组对战，到第m组，每个对战都进行三种情况的枚举。我需要的效果是，每组都3种情况，那一共是3^m种情况。请看dfs代码:

void dfs(int x){
    tr=1; 
    if(x==m){
        for(int i=1;i<=n;i++){
            if(arr[i]>arr[1]) tr++;
        }
        rk=min(tr,rk);
        return ;
    }
    for(int i=1;i<=3;i++){
        if(i==1){
            arr[ma[x].first]+=3;
            dfs(x+1);
            arr[ma[x].first]-=3;
        }
        if(i==2){
            arr[ma[x].second]+=3;
            dfs(x+1);
            arr[ma[x].second]-=3;
        }
        else{
            arr[ma[x].first]++,arr[ma[x].second]++;
            dfs(x+1);
            arr[ma[x].first]--,arr[ma[x].second]--;
        }
    }
}

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int arr[102];
vector<pair<int,int>>ma;
int n,m;
int rk=10000,tr=1;
void dfs(int x){
    tr=1; 
    if(x==m){
        for(int i=1;i<=n;i++){
            if(arr[i]>arr[1]) tr++;
        }
        rk=min(tr,rk);
        return ;
    }
    for(int i=1;i<=3;i++){
        if(i==1){
            arr[ma[x].first]+=3;
            dfs(x+1);
            arr[ma[x].first]-=3;
        }
        if(i==2){
            arr[ma[x].second]+=3;
            dfs(x+1);
            arr[ma[x].second]-=3;
        }
        else{
            arr[ma[x].first]++,arr[ma[x].second]++;
            dfs(x+1);
            arr[ma[x].first]--,arr[ma[x].second]--;
        }
    }
}
signed main(){
    int t;cin>>t;
    while(t--){
        cin>>n>>m;
        for(int i=1;i<=n;i++) cin>>arr[i];
        for(int i=0;i<m;i++){
            int x,y;cin>>x>>y;
            ma.push_back({x,y});
        }
        dfs(0);
        ma.clear();
        memset(arr,0,sizeof(arr));
        cout<<rk<<'\n';
        rk=10000,tr=1;
    }
}

样例给的非常好，因为写好后tr（第二行）未进行初始化，导致样例没过，调了很久之后才醒悟，return并不能将rt（全局）清除。 收获满满。