C++奥赛一本通刷题记录(回溯)

C++奥赛一本通刷题记录(回溯)

2017.11.13 By gwj1139177410

  1. LETTERS openjudge156

    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
    #include<iostream> //bugs:cin+*char[] will boom
    #include<string>
    #include<cstring>
    using namespace std;
    const int maxn = 30;
    int r, s, cnt, ans, ha[maxn*10];
    string a[maxn];
    const int dx[] = {0,1,0,-1};
    const int dy[] = {-1,0,1,0};
    void dfs(int x, int y){
    ans = max(ans, cnt);
    for(int i = 0; i < 4; i++){
    int nx = x+dx[i], ny = y+dy[i];
    if(nx<0||nx>=r||ny<0||ny>=s||ha[(int)a[nx][ny]])continue;
    ha[(int)a[nx][ny]] = 1; cnt++;
    dfs(nx,ny);
    ha[(int)a[nx][ny]] = 0; cnt--;
    }
    }
    int main(){
    cin>>r>>s;
    for(int i = 0; i < r; i++)cin>>a[i];
    ha[(int)a[0][0]] = 1; cnt = 1;
    dfs(0,0);
    cout<<ans<<"\n";
    return 0;
    }
  2. 八皇后问题 openjudge1700

    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
    //bugs:鬼畜的题目,列优先处理
    #include<iostream>
    using namespace std;
    int n = 8, c[10], ma[10][10], cnt; //c[]记录每一列的皇后所在的行的位置, ma[][]是整个矩阵
    void dfs(int cur){
    if(cur == 8){
    cout<<"No. "<<++cnt<<"\n";
    for(int i = 0; i < 8; i++){
    for(int j = 0; j < 8; j++)
    cout<<ma[i][j]<<" ";
    cout<<"\n";
    }
    }else for(int i = 0; i < 8; i++){//尝试每一行是否能填
    int ok = 1;
    for(int j = 0; j < cur; j++)
    if(c[j]==i||cur-i==j-c[j]||cur+i==j+c[j])
    { ok = 0; break; }
    if(ok){
    c[cur] = i;
    ma[i][cur] = 1;
    dfs(cur+1);
    ma[i][cur] = 0;
    }
    }
    }
    int main(){
    dfs(0);
    return 0;
    }
  3. 八皇后 openjudge1756

    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
    //枚举加打表
    #include<iostream>
    #include<vector>
    using namespace std;
    vector<int>ans;
    int n = 8, c[10];
    void dfs(int cur){
    if(cur == n){
    int res = 0;
    for(int i = 0; i < 8; i++)res = res*10+c[i];
    ans.push_back(res);
    }else for(int i = 1; i <= 8; i++){
    int ok = 1;
    for(int j = 0; j < cur; j++)
    if(c[j]==i||c[j]+j==i+cur||c[j]-j==i-cur)
    {ok = 0; break;}
    if(ok){
    c[cur] = i;
    dfs(cur+1);
    }
    }
    }
    int main(){
    dfs(0);
    int T; cin>>T;
    while(T--){
    int x; cin>>x;
    cout<<ans[x-1]<<"\n";
    }
    return 0;
    }
  4. 迷宫 openjudge1792

    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
    //模板
    #include<iostream>
    #include<string>
    #include<cstring>
    using namespace std;
    const int maxn = 1010;
    int n, x1, y1, x2, y2, vis[maxn][maxn], flag;
    string a[maxn];
    const int dx[] = {1,0,-1,0};
    const int dy[] = {0,1,0,-1};
    void dfs(int x, int y){
    if(x<0||x>=n||y<0||y>=n||a[x][y]=='#'||vis[x][y])return ;
    vis[x][y] = 1;
    if(x==x2&&y==y2)flag = 1;
    else for(int i = 0; i < 4; i++){
    dfs(x+dx[i],y+dy[i]);
    }
    }
    int main(){
    int T; cin>>T;
    while(T--){
    cin>>n;
    for(int i = 0; i < n; i++)cin>>a[i];
    cin>>x1>>y1>>x2>>y2;
    flag = 0;
    if(a[x1][y1]!='#'&&a[x2][y2]!='#'){
    memset(vis,0,sizeof(vis));
    dfs(x1,y1);
    }
    if(flag)cout<<"YES\n";else cout<<"NO\n";
    }
    return 0;
    }
  5. 红与黑 openjudge1818

    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
    //模板
    #include<iostream>
    #include<string>
    #include<cstring>
    using namespace std;
    const int maxn = 50;
    int n, m, x1, y1, vis[maxn][maxn], ans;
    string a[maxn];
    const int dx[] = {1,0,-1,0};
    const int dy[] = {0,1,0,-1};
    void dfs(int x, int y){
    ans++; vis[x][y] = 1;
    for(int i = 0; i < 4; i++){
    int nx = x+dx[i], ny = y+dy[i];
    if(nx<0||nx>=n||ny<0||ny>=m)continue;
    if(vis[nx][ny]||a[nx][ny]=='#')continue;
    dfs(nx,ny);
    }
    }
    int main(){
    while(cin>>m>>n &&m &&n){
    for(int i = 0; i < n; i++){
    cin>>a[i];
    for(int j = 0; j < m; j++)
    if(a[i][j]=='@'){x1=i;y1=j;}
    }
    memset(vis,0,sizeof(vis)); ans = 0;
    dfs(x1,y1);
    cout<<ans<<"\n";
    }
    return 0;
    }
  6. 棋盘问题 openjudge323

    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
    #include<iostream>
    #include<string>
    #include<cstring>
    using namespace std;
    const int maxn = 20;
    int n, k, vis[maxn], ans; //vis[i]:第i行是否可填
    string a[maxn];
    void dfs(int cur, int sum){
    if(sum > k)ans++;
    else for(int i = cur; i < n; i++){//枚举从哪一行开始填
    for(int j = 0; j < n; j++){//枚举填在第几列
    if(a[i][j]=='#'&&!vis[j]){
    vis[j] = 1;
    dfs(i+1, sum+1);
    vis[j] = 0;
    }
    }
    }
    }
    int main(){
    ios::sync_with_stdio(false);
    while(cin>>n>>k &&n!=-1&&k!=-1){
    for(int i = 0; i < n; i++)cin>>a[i];
    memset(vis,0,sizeof(vis)); ans = 0; dfs(0,1);
    cout<<ans<<"\n";
    }
    return 0;
    }
  7. 取石子游戏 openjudge6266

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //博弈论。。。
    #include<iostream>
    #include<algorithm>
    using namespace std;
    bool xht(int a, int b){
    if(a%b==0)return true;
    if((int)(a/b)>=2)return true;//bugs注意取整
    if((int)(a/b)==1)return !xht(b,a-b);
    }
    int main(){
    int a, b;
    while(cin>>a>>b &&a&&b){
    if(a<b)swap(a,b);
    if(xht(a,b))cout<<"win\n";
    else cout<<"lose\n";
    }
    return 0;
    }
  8. 马走日 openjudge8465

    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
    //bugs:马走日,马走的是日,马走的是日字型。。。。
    #include<iostream>
    #include<cstring>
    using namespace std;
    const int maxn = 20;
    int n, m, x, y, vis[maxn][maxn], cnt, ans;
    const int dx[] = {1,-1,1,-1,2,-2,2,-2};
    const int dy[] = {2,2,-2,-2,1,1,-1,-1};
    void dfs(int x, int y){
    if(x<0||x>=n||y<0||y>=m||vis[x][y])return ;
    vis[x][y] = 1;
    if(cnt == n*m-1)ans++;
    for(int i = 0; i < 8; i++){
    cnt++;
    dfs(x+dx[i],y+dy[i]);
    cnt--;
    }
    vis[x][y] = 0;
    }
    int main(){
    int T; cin>>T;
    while(T--){
    cin>>n>>m>>x>>y;
    memset(vis,0,sizeof(vis));
    cnt = ans = 0;
    dfs(x,y);
    cout<<ans<<"\n";
    }
    return 0;
    }
  9. 单词接龙 openjudge8783

    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
    //直接搜索就好啦,几乎没什么技巧,就是状态建模会有点难想到(应该有多种)
    //包含的情况可以证明是不需要考虑的,因为包含后一定不会比不包含要来的长
    #include<iostream>
    #include<algorithm>
    #include<string>
    using namespace std;
    const int maxn = 30;
    int n, ans, used[maxn];
    string w[maxn];
    //找到a的末尾与b的前端重复的子串并返回其长度
    int find(string a, string b){
    int mm = min(a.size(), b.size());
    for(int i = 1; i <= mm; i++)
    if(a.substr(a.size()-i)==b.substr(0,i))
    return i;
    return 0;
    }
    //深度优先搜索寻找解, 状态:cur为当前字符串
    void dfs(string cur){
    ans = max(ans, (int)cur.size());
    for(int i = 1; i <= n; i++)if(used[i]<2){
    int t = find(cur, w[i]);
    if(t == cur.size() && cur!=w[0])continue;//包含关系
    if(t){
    used[i]++;
    dfs(cur.substr(0,cur.size()-t)+w[i]);
    used[i]--;
    }
    }
    }
    int main(){
    cin>>n;
    for(int i = 1; i <= n; i++)cin>>w[i];
    cin>>w[0];
    dfs(w[0]);
    cout<<ans<<"\n";
    return 0;
    }
  10. 分成互质组 openjudge7834

    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
    //数据太水怪我咯?。。思路是每次对于新的一个数,与各组比对是否互质,若没有组能加就添加新组。
    #include<iostream>
    using namespace std;
    const int maxn = 20;
    int n, a[maxn], vis[maxn], cmp[maxn], cnt;
    int gcd(int a, int b){
    return !b?a:gcd(b,a%b);
    }
    int main(){
    cin>>n;
    for(int i = 0; i < n; i++)cin>>a[i];
    //1. 每次找出未分类的值并将其放入新的类别
    for(int i = 0; i < n; i++)if(!vis[i]){
    vis[i] = 1; cmp[i]=++cnt;
    //2. 找出所有未分类的值中与当前值所在类别全部互质的值并加入该类
    for(int j = 0; j < n; j++)if(!vis[j]){
    int ok = 1;
    for(int k = 0; k < n; k++)if(cmp[k]==cmp[i]){//遍历当前值所在类别的值
    if(gcd(a[j],a[k])!=1)ok = 0;
    }
    if(ok){
    vis[j] = 1;
    cmp[j] = cnt;
    }
    }
    }
    cout<<cnt<<"\n";
    return 0;
    }
    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
    //f[i][j],选到了第i个数,现在有j个集合
    //注:当要把这个数放进来之前前面的数在放进来的时候都已经判断好了
    #include<iostream>
    using namespace std;
    int n, a[20], b[20], ans;
    int gcd(int a, int b){
    return !b?a:gcd(b,a%b);
    }
    void dfs(int x, int y){
    int flag = 1;
    if(x==n){ ans = min(ans,y); return ;}
    else for(int i = 1; i <= y; i++){//1.遍历每一个已有类别
    int ok = 1;
    for(int j = 0; j < n; j++)if(b[j]==i)//2.遍历该类别所有数
    if(gcd(a[j],a[x])!=1){ ok=0; break; }
    if(ok){//3.如果满足全部互质,就加入该类,并判断下一个数
    flag = 0; //如果存在不互质,就不用新建组
    b[x] = i;
    dfs(x+1,y);
    b[x] = 0;
    }
    }
    if(flag){//4.如果没有与当前数互质的类别,就新建一个类别
    b[x] = y+1;
    dfs(x+1,y+1);
    b[x] = 0;
    }
    }
    int main(){
    cin>>n;
    for(int i = 0; i < n; i++)cin>>a[i];
    b[0]=1; ans=0xffffff;
    dfs(1,1);
    cout<<ans<<"\n";
    return 0;
    }
  11. 放苹果 openjudge666

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //这都第几遍了啊
    #include<iostream>
    using namespace std;
    int f(int n, int m){
    if(n==0||m==1)return 1;
    if(n>=m)return f(n-m,m)+f(n,m-1);
    else return f(n,m-1);
    }
    int main(){
    int T; cin>>T;
    while(T--){
    int n, m; cin>>n>>m;
    cout<<f(n,m)<<"\n";
    }
    return 0;
    }