日度归档：15 1 月, 2019

团体程序设计天梯赛-练习集 L3-001 凑零钱

发表评论

DFS T一个点29分代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std;
int n,m;
int money[10005];
int recorder[10005];
bool dfs(int no,int curPos,int remainValue){
    recorder[no]=money[curPos];
    if(remainValue==0)return true;
    int upp=upper_bound(money+1,money+n+1,remainValue)-money;
    for(int i=curPos+1;i<upp;i++){
        if(dfs(no+1,i,remainValue-money[i]))return true;
        else i=upper_bound(money+1,money+n+1,money[i])-money-1;
    }
    recorder[no]=0; //忘加了这个，回溯差点没做好
    return false;
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",money+i);
    sort(money+1,money+n+1);
    bool flag=dfs(0,0,m);
    if(!flag)printf("No Solution");
    else{
        int i=1;
        while(recorder[i]!=0){
            if(i!=1)printf(" ");
            printf("%d",recorder[i++]);
        }
    }
}

团体程序设计天梯赛-练习集 L3-015 球队“食物链”

发表评论

如下三个坑点：
1、所给的图非对称，因为每个队打了两场比赛，每一场分别记输赢。所以每行数据都要做处理。
2、要求食物链的字典序最小，而且该食物链是从1到n的排列，因此只要有环，头一个一定从1开始是字典序最小的状况，只需要从1开始DFS即可。
3、剪枝：不剪枝T一个点。在DFS中把经过的点标记，若未标记的点集中不存在与1连通的点，则不可能构成环状结构，直接return false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
int n;
char arr[25][25];
deque<int> st;
bool visited[25];
bool dfs(int curNode,int visitedNodeCnt){
    if(visited[curNode]){
        if(visitedNodeCnt==n+1&&curNode==1)return true;
        else return false;
    }
    bool flag=false;
    for(int i=1;i<=n;i++){
        if(!visited[i]&&(arr[i][1]=='W'||arr[1][i]=='L'))flag=true;
    }
    if(!flag)return false;
    visited[curNode]=true;
    for(int i=1;i<=n;i++){
        if(i==curNode)continue;
        if(arr[curNode][i]=='W'||arr[i][curNode]=='L'){
            if(dfs(i,visitedNodeCnt+1)){
                st.push_back(i);
                return true;
            }
        }
    }
    visited[curNode]=false;
    return false;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%s",arr[i]+1);
    bool flag=dfs(1,1);
    if(!flag)printf("No Solution\n");
    else{
        printf("%d",st.front());
        st.pop_front();
        while(!st.empty()){
            printf(" %d",st.back());
            st.pop_back();
        }
    }
}