文档章节

虫食算

机智的帝江
 机智的帝江
发布于 2016/10/30 09:55
字数 488
阅读 9
收藏 0

点击跟博主一起玩(zuo)耍(si)
这道题没有什么难度,纯粹考察代码能力。对于每一个字母代表的数字,采用dfs的方法进行枚举。同时在枚举过程中判断是否存在某个数字可以直接推出来。存在矛盾时退出dfs。
但是裸dfs会超时,所以需要剪枝。
剪枝优化:
考虑到加法运算要有进位,所以采取从低位向高位搜索的策略,这是十分重要的思想。
强剪枝:对于当前位的更高位,就是还没搜过的位,如果满足以下条件就剪枝:当前位三个数都已搜出来(记第一位为a,第二位b,第三位c),(a+b)mod n<>c and(a+b+1)mod n<>c ,就剪枝。
代码如下

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
bool vis[100];
char b[100][100];
int a[100],c[100];
int n;

    void print(){
        for (int i = 65;i < 65 + n; ++i) printf("%d ",a[i]);
        printf("\n");
        return ;
    }

    bool judge1(){
        for (int i = n;i; --i)
            if (a[b[i][1]] != -1 &&  a[b[i][2]] != -1 && a[b[i][3]] != -1  &&
               (a[b[i][1]] + a[b[i][2]]) % n != a[b[i][3]] &&
               (a[b[i][1]] + a[b[i][2]] + 1) % n != a[b[i][3]]) return 0;
        return 1;
    }

    bool judge2(){
     int k = 0;
        for (int i = n;i > 1; --i){
            k = a[b[i][1]] + a[b[i][2]] + k;
            if (a[b[i][3]] !=k % n) return 0;
            k /= n; 
        }   
        return 1;
    }

    void DFS(int m){
        int i;
        if (!judge1()) return ;
        if (a[b[1][1]] + a[b[1][2]] >= n) return ;
        if (m > n)
    if(judge2())
        {
       print();
       exit(0);
        }
            else return ;
        else
            for (i=n-1;i>=0;i--)
                if (vis[i]) {
                    a[c[m]]=i;
                    vis[i]=0;
                    DFS(m+1);
                    a[c[m]]=-1;
                    vis[i]=1;   
                }    
    }
    int main(){
        int k = 1;
        bool h[100];
        memset(h,1,sizeof(h));
        memset(vis,1,sizeof(vis));
        memset(a,-1,sizeof(a));
        scanf("%d",&n);
        for (int j = 1;j < 4;j++)
            for (int i = 1;i <= n; ++i)
               cin>>b[i][j];
        for (int i=n;i>0;i--)
            for (int j=1;j<4;j++)
            if (h[b[i][j]]) {
                    c[k++]=b[i][j];
                    h[b[i][j]]=0;
                }
        DFS(1);
        return 0;
    }

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/49000455

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
oschina 广州聚会 (8月28日) 今天下午2点

8月的广州,炎炎热日,找个地方坐下来,一杯冷饮让奔波一路的心情凉快下来,聊聊技术、聊聊工作、聊聊未来。 来吧,来参加8月28日在广州的oschina聚会! 人物:混迹OSChina的各位男女同胞,由...

红薯
2011/08/15
4.4K
85
她把一个“三无”产品做进故宫,还一举颠覆了蛋糕界,厉害了我的仙女姐姐

2016-12-01 不可辜负的 GirlUp 唯爱与美食, 不可辜负。 ··· “三无”蛋糕 一块“三无”蛋糕。 竟成了第一个, 走进故宫的蛋糕品牌。 一时间, “蛋糕界”炸开了锅。 人们纷纷猜测, 到底...

Betty__
2016/12/02
32
0
osc五周年庆,巽寮湾走起!(潘潘版)

osc五周年庆,巽寮湾走起!2013年8月31日早上的深圳还是有蒙蒙细雨,心里那个忐忑:如果海边下暴雨就煞风景了!结果后面一路上的好天气着实让人兴奋。此行兵分三路5辆车出发! 第一天: 一路...

丫头潘潘
2013/09/03
4.1K
47
贫穷限制了我的想象力 8月13日石破天行情解码

原创: 石破天 奇点区块 1 谈东说西 老石最近比较关注币圈大佬虫哥的新闻,跟首富笑来、宝二爷等被韭菜小散骂得狗血淋头的所谓大佬相比,虫哥在币圈的口碑还是比较正面的。而周六的火币全球行...

奇点区块
2018/08/13
0
0
上海某小学的幼升小题目,回答正确率只有1比176,你能做出来吗?

  前两天,有人发给学哥一个图片,说是上海某实验小学的幼升小题目,据说正确做出来的比例是1比176。让大家来体验看看,是不是大家都不能上小学了:      学哥以前也见过类似的题目,心...

零基础学编程
2018/10/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Leetcode PHP题解--D88 696. Count Binary Substrings

D88 696. Count Binary Substrings 题目链接 696. Count Binary Substrings 题目分析 给定一个01字符串,返回仅用连续的0和1串所能组成的二进制字符串个数。 例如,00110011,就包含0011,0...

skys215
8分钟前
0
0
基础工具类

package com.atguigu.util;import java.sql.Connection;import java.sql.SQLException;import java.util.Properties;import javax.sql.DataSource;import com.alibaba.druid......

architect刘源源
今天
43
0
P30 Pro劲敌!DxO官宣新机:排行榜又要变

5月26日晚间,DxOMark官方推特预告,将在5月27日公布一款新机型的DxOMark评分,猜猜是哪款? 网友猜想的机型有:红米K20、谷歌Pixel 3a、索尼Xperia 1、诺基亚9 PureView等。 DxOMark即将公布...

linux-tao
昨天
15
0
Ubuntu18.04.2窗口过小不能自适应(二次转载)

解决Ubuntu在虚拟机窗口不能自适应 2018年09月06日 16:20:08 起不了名儿 阅读数 855 此博文转载:https://blog.csdn.net/nuddlle/article/details/77994080(原地址) 试了很多办法这个好用 ...

tahiti_aa
昨天
2
0
死磕 java同步系列之CountDownLatch源码解析

问题 (1)CountDownLatch是什么? (2)CountDownLatch具有哪些特性? (3)CountDownLatch通常运用在什么场景中? (4)CountDownLatch的初始次数是否可以调整? 简介 CountDownLatch,可以...

彤哥读源码
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部