DFS

HDU 4405 Aeroplane chess

Posted on

昨天周赛的水搜索 然而………………

因为昨晚基地灯坏了,只能跟寝室里的煞笔一起打(当然他比我强,他10分钟A了 我越写越急

最后写了两个小时………………

不想多说什么了 先贴上源代码 再分析优化

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
char str[20];
int flag[20];
int len, ans;

bool judge()
{
    int mid;
    for (mid = 0; mid < len; mid++)
        if (flag[mid] == 2)
            break;
    if (mid == len)
        return false;
    long long lans = str[0] - '0', rans = str[mid] - '0', i;
    for (i = 1; i < mid; i++)
        if (flag[i])
            break;
        else
            lans = lans * 10 + str[i] - '0';
    while (i < mid) {
        long long tmp = str[i] - '0';
        i++;
        while (flag[i] == 0) {
            tmp = tmp * 10 + str[i] - '0';
            i++;
        }
        lans += tmp;
    }
    for (i = mid + 1; i < len; i++)
        if (flag[i])
            break;
        else
            rans = rans * 10 + str[i] - '0';
    while (i < len) {
        long long tmp = str[i] - '0';
        i++;
        while (flag[i] == 0) {
            tmp = tmp * 10 + str[i] - '0';
            i++;
        }
        rans += tmp;
    }
    return lans == rans;
}

void dfs(int pos, bool has_equal)
{
    if (pos == len) {
        if (has_equal && judge())
            ans++;
        return;
    }
    if (has_equal) {
        flag[pos] = 1;
        dfs(pos + 1, true);
        flag[pos] = 0;
        dfs(pos + 1, true);
    } else {
        flag[pos] = 0;
        dfs(pos + 1, false);
        flag[pos] = 1;
        dfs(pos + 1, false);
        // if(pos==len-1) return;
        flag[pos] = 2;
        dfs(pos + 1, true);
    }
}

int main()
{
    while (scanf("%s", str) != EOF) {
        if (strcmp(str, "END") == 0)
            break;
        len = strlen(str), ans = 0;
        memset(flag, 0, sizeof flag);
        flag[len] = 1000;
        dfs(1, false);
        printf("%d\n", ans);
    }
    return 0;
}

我当时的思路很明显了 先用DFS放置所有 + = 的位置 到最后判断一些能不能使等式成立

因为前面想的少,搞得后面的bug处理特别多

尤其是判断那里

对于优化建议

1.完全可以预处理一下 比如定义一个二维数组 num[27][27] 用num[x][y]表示 x-y 的数字 然后只要判断加号位置就好了

2.另外的话可以以一个循环判断=的位置 再对左右按序DFS 即可

好吧 我已经理论优化了

最后想说的是 打ACM 心态很重要 心态爆炸了 这场基本也是完了

DFS

HDU 4499 Cannon

Posted on

原创的思维和代码永远比看题解A的兴奋的多!

原创的思维和代码永远比看题解A的兴奋的多!!

原创的思维和代码永远比看题解A的兴奋的多!!!

原创的思维和代码永远比看题解A的兴奋的多!!!!

原创的思维和代码永远比看题解A的兴奋的多!!!!!

原创的思维和代码永远比看题解A的兴奋的多!!!!!!

哪怕算法效率上差别人很多

昨天的周常比赛我看到这题就知道用暴力回溯 想想应该和八皇后难度上差不了多少 就放到最后一小时再写 结果就懵逼了
越写越乱 最后也没写出来 晚上也一直在想 结果发现 越深究,我的思路漏洞越多,这个问题也变得越来越有趣,今天早上还是被我A了 真是痛快
思路就是暴力回溯 具体的 见注释(其实我不建议你看我代码,因为我觉得太臭了,但毕竟是自己亲生的,哈哈哈哈哈哈哈哈哈哈

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>

using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
int ans,row,col;
int mat[10][10];//整个棋盘我分为4种状态  0 空   1  其他棋子   2  放炮排斥位置   3  炮

void update(int x,int y)
{
    bool flag=true;
    for(int i=y+1; i<col-1&&flag; i++)//对坐标右行进行更新
        if(mat[x][i]==1&&mat[x][i+1]==1) break;//遇到两个相邻的其他棋子就不需要了
        else if(mat[x][i]==1)//如果只是一个其他棋子
            for(int j=i+1; j<col; j++)
                if(mat[x][j]==1){flag=false;break;}//再碰到一个其他棋子
                else mat[x][j]=2;
    for(int i=0; i<y; i++)//对坐标坐标进行更新
        if(mat[x][i]==3&&mat[x][i+1]!=1&&mat[x][i+2]!=1)//如果前面有炮并且没有两个相邻的其他棋子阻隔   (其实这里还写不大好,抄了小路,既然A了就算了
            for(int j=y+1; j<col; j++)
                if(mat[x][j]==1) break;//碰到一个其他棋子
                else mat[x][j]=2;
    flag=true;
    for(int i=x+1; i<row-1&&flag; i++)
        if(mat[i][y]==1&&mat[i+1][y]==1) break;
        else if(mat[i][y]==1)
            for(int j=i+1; j<row; j++)
                if(mat[j][y]==1) {flag=false;break;}
                else mat[j][y]=2;
    for(int i=0; i<x; i++)
        if(mat[i][y]==3&&mat[i+1][y]!=1&&mat[i+2][y]!=1)
            for(int j=x+1; j<row; j++)
                if(mat[j][y]==1) break;
                else mat[j][y]=2;
}

void dfs(int r,int num,int add,int st)
{
    if(r==row)
    {
        ans=max(num,ans);
        return ;
    }
    int temprow[7],tempcol[7],tt;
    for(int i=st; i<col; i++)
    {
        if(mat[r][i]==0)
        {
            for(int j=0; j<col; j++)
                temprow[j]=mat[r][j];
            for(int j=0; j<row; j++)
                tempcol[j]=mat[j][i];
            tt=mat[r][i];//最傻最暴力的备份方法
            mat[r][i]=3;//放炮
            update(r,i);//更新
            if(add<2&&i<col-1) dfs(r,num+1,add+1,i+1); //对于一行来说   最多可以放3个炮  同行递归
            dfs(r+1,num+1,0,0);//同行递归不行就下一行
            mat[r][i]=tt;//还原
            for(int j=0; j<col; j++)
                mat[r][j]=temprow[j];
            for(int j=0; j<row; j++)
                mat[j][i]=tempcol[j];
        }
    }
    dfs(r+1,num,0,0);//也有可能我一正行都不能放反而更优
}

int main()
{
    int num,x,y;
    while(scanf("%d%d%d",&row,&col,&num)!=EOF)
    {
        memset(mat,0,sizeof mat);
        for(int i=0; i<num; i++)
        {
            scanf("%d%d",&x,&y);
            mat[x][y]=1;
        }
        ans=0;
        dfs(0,0,0,0);
        printf("%d\n",ans);
    }
    return 0;
}
DFS

HDU 1198 Farm Irrigation

Posted on

不太一样的搜索水题

题意:
A--K对应不同水管 要事整个田地都能灌溉到水 ,问 需要到少水源

思路:
一开始想的就是深搜 只是方向都不同罢了 和求连通区域个数没什么区别 属于最水的搜索题

AC Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn=60;
char mat[maxn][maxn];
bool vis[maxn][maxn];
int row,col;
int dir[12][4]=
{
    {1,0,0,1},{1,1,0,0},{0,0,1,1},{0,1,1,0},
    {1,0,1,0},{0,1,0,1},{1,1,0,1},{1,0,1,1},
    {0,1,1,1},{1,1,1,0},{1,1,1,1}
};
int dx[]= {-1,0,1,0};
int dy[]= {0,1,0,-1};

bool judge(int x,int y)
{
    return x>0&&x<=row&&y>0&&y<=col&&!vis[x][y];
}

void dfs(int from,int x,int y)
{
    int num=mat[x][y]-'A',xx,yy;
    if(from<4)
        if(!dir[num][(from+2)%4]){vis[x][y]=false; return ;}
    for(int i=0; i<4; i++)
    {
        if(dir[num][i])
        {
            xx=x+dx[i];
            yy=y+dy[i];
            if(judge(xx,yy))
            {
                vis[xx][yy]=true;
                dfs(i,xx,yy);
            }
        }
    }
}

int main()
{
    while(scanf("%d%d",&row,&col),row>0&&col>0)
    {
        getchar();
        for(int i=1; i<=row; i++)
            scanf("%s",mat[i]+1);
        memset(vis,false,sizeof vis);
        int ans=0;
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++)
                if(!vis[i][j])
                {
                    ans++;
                    vis[i][j]=true;
                    dfs(maxn,i,j);
                }
        printf("%d\n",ans);
    }
    return 0;
}
DFS

CodeForces 14D Two Paths

Posted on

一看到这道题我就是大写的懵逼
因为上半年去华科还是地大打邀请赛的时候做过类似的题目,当初是写不来的 结果现在……………………还是写不来………………造孽啊

题意:
给你一个无向不成环的图 让你找出两条不相交的树链 使其乘积最大

思路 :
枚举每一条道路 并使其暂时断裂 再从这条道路的两端开始搜索 寻找最长的树链即可
说实话 搜索的题目虽然说做的还凑合 但是这种给你一个连通方式 并以此形成无向图 再加以搜索的题目我还是第一次做
我先想得是用二维矩阵保存路径 以G[u][v] 表示从 u到v是连通的 再用vector省点空间
之后我较为习惯的用了BFS 然后就进入了无限懵逼崩溃懵逼崩溃的状态 说到底用矩阵保存如果不用上结构体的话 很难记录链长
无奈还是写了DFS

AC Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;
const int maxn=220;
bool vis[maxn];
vector<int> G[maxn];
int ans;

int dfs(int v,int x)
{
    int sum=0;
    int max1=0,max2=0;
    for(int i=0; i<G[v].size(); i++)
    {
        if(G[v][i]!=x)
        {
            sum=max(sum,dfs(G[v][i],v));//sum得到从一个NODE出发的树的直径   循环操作得到最大
                                        //与此同时 ans也在计算着从改点出发的最长树链
            if(ans>max1)
            {
                max2=max1;
                max1=ans;
            }
            else max2=ans>max2?ans:max2;
        }
    }
    sum=max(sum,max1+max2);//最后sum得到从V出发的树的直径
    ans=max1+1;//max1为该node的最长树链  因为递归返回  最大树链长度+1
    return sum;
}

int main()
{
    int n,a,b;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<=n; i++) G[i].clear();
        for(int i=0; i<n-1; i++)
        {
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        int last_ans=0;
        for(int i=0; i<n; i++)
        {
            int num=G[i].size(),temp;
            for(int j=0; j<num; j++)
            {
                int ans=0;
                temp=dfs(i,G[i][j])*dfs(G[i][j],i);
                last_ans=max(last_ans,temp);
            }
        }
        printf("%d\n",last_ans);
    }
    return 0;
}
DFS

POJ 1011 sticks

Posted on

题意简单说就是本来几根一样长的棍子 被小明乱切(乱切 没切中也是有可能的) 切成了n根小棍子

要你把n根小棍子恢复原样 可能有多组解

要求输出 每根棍子最短的情况时 棍子长度

据说是极为经典的dfs题

一开始真的不知道怎么搜好(辣鸡无力)闷了1个多小时无奈去看了一下题解 恍然大悟

看完自己敲一A后 细看一下 还是原来那些东西 dfs传参 之前积累的棍长 棍的数量 累加棍的位置

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <stack>

using namespace std;

int stick[70];
bool flag[70];
int len,sum,num,n;//len 棍长   sum所有棍子总长度   num棍数目   n小棍数目

bool dfs(int pre_len,int pre_num,int pos)
{
    if(pre_num==num) return true;
    for(int i=pos;i<n;i++)
    {
        if(flag[i]) continue;
        if(pre_len+stick[i]==len)
        {
            flag[i]=true;
            if(dfs(0,pre_num+1,0)) return true;
            flag[i]=false;//回溯
            return false;
        }
        else if(len>(pre_len+stick[i]))
        {
            flag[i]=true;
            if(dfs(pre_len+stick[i],pre_num,i+1)) return true;
            flag[i]=false;
            if(pre_len==0) return false;//这时 之前一根棍都没有   len>stick[i]
            while(i+1<n&&stick[i]==stick[i+1]) i++;//相邻一样的情况就不用算了
        }
    }
    return false;
}


int main()
{
    while(scanf("%d",&n),n)
    {
        num=sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&stick[i]);
            sum+=stick[i];
        }
        sort(stick,stick+n,greater<int>());
        memset(flag,false,sizeof flag);
        for(len=stick[0];len<=sum;len++)
        {
            if(sum%len) continue;//必须整除
            num=sum/len;//总共棍子的数量
            if(dfs(0,0,0))
            {
                printf("%d\n",len);
                break;
            }
        }
    }
    return 0;
}