数字计数问题

# include <iostream>
# include <cmath>
using namespace std;

int digitCount(int num) // 计算整数num有多少位
{
    int result = 0;
    while (num) ++ result, num /= 10;
    return result;
}

int countDigit(int upper, int digit) // 计算从1到upper的整数中数字digit出现多少次 
{
    int result = 0, digits = digitCount(upper);
    for (int position = 1; position <= digits; ++ position) // 从右到左第position位上 数字digit出现多少次 
    {
        // left和right是第position位左边和右边的整数; digitValue是第position位的数字
        int power = pow(10, position - 1), left = upper / power / 10, right = upper % power, digitValue = upper / power % 10;
        // 计算第position位左边的整数小于left的情况 左边不等于left的时候 说明都是比left小的数字  
        if (digit) result += left * power; //如果不是统计数字0 左边直接乘power就行了 upper=ab3xxx power=1000  
//upper=1236055 6000-6999这里1000  第position位上的6出现了power次 但是左边还有16000-16999 26000-26999 36000-36999...1226000-12269999 共左边数字left（即123）个 所以是left*power 
        else if (!digit && left) result += (left - 1) * power; // 统计的数字digit = 0, 左边高位不能全为0 
//少了0000-0999的一种情况 从10000-10999 开始 ... 1220000-1220999 13000-13999 共(left-1)次 

// 计算第position位左边的整数等于left的情况 只会和*position位后面的数*有关



//下面就是left的左边相等的情况 对第position位上 不会多算6000-6999 ...1226000-1226999里面的任意个集合 123开始的情况
        if ( (digitValue > digit) && (digit || left) ) result += power;//第position位比现在统计的数字大 就可以直接加上power中情况 
// upper=1236055  则有1235000-1235999 999+1种情况 即power种 
//当统计的数字digit==0 且 left==0， 举例  upper=123456 left==0 第position位为1  就是power=100000 此时000000-099999是不成立的 因为我要统计第position位为digit的时候 有多少个这样的 数 而此时   000000-099999 显然和 100000-199999 第position-1位为2的时候重复了

        if ( (digitValue == digit) && (digit || left) ) result += right + 1;//这是right有多少个 就是多少个+1
//if(digitValue==digit) upper=1236055  1236000-1236055   即55+1种情况
//当统计的数字digit==0 且 left==0， 举例  upper=123456 left==0且digit==0 就是000000 -0123456 而这个时候显然和 第position-1的位的时候重复了100000-109999

//if(digitValue>digit) upper=1236000 则有1237000-1237999 所以是0 

    }
    return result;
}

int main()
{
    int start, end;
    while (cin >> start >> end , start)
    {
        if (start > end) swap(start, end);
        for (int digit = 0; digit <= 9; ++ digit) cout << countDigit(end, digit) - countDigit(start - 1, digit) << ' ';
        cout << endl;
    }
    return 0;
}

地板铺装问题

由于要求完全铺满，只需确定横向铺设方案，纵向铺设方案也随之确定。因此，我们只需计算横向铺设的方案数量。 逐列分析，设dp[i][j]表示前i-1列已铺设完成，j表示当前列的状态，j的每一位为1表示该行向右延伸。 两个转移条件：i列和i-1列的同一行不能同时延伸；当前列状态j与前一列状态k进行或运算，得到是否有奇数空行状态，奇数空行状态不允许转移。j&k==0 初始化条件dp[0][0] = 1，第0列只能是状态0，无任何格子延伸。最终返回dp[m][0]。第m+1列不能有任何延伸。 st数组预处理每个状态，标记该状态中连续空格是否均为偶数个，若是则为true，否则为false 判断二进制数i的第j位是否为1，为1表示第j行放置木块，不为1则不放置。

#include<bits/stdc++.h>
using namespace std;

const int ROWS=12, COLS = 1<< ROWS;  

long long dp[ROWS][COLS] ;// 第一维表示列数， 第二维表示所有可能的状态

bool valid[COLS];  //存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。

vector<vector<int>> transitions(COLS);  //记录每个状态可以转移的前置状态
int rows , columns;

int main(){

    while(cin>>rows>>columns, rows||columns){ //读入行数和列数，并且不是两个0即合法输入就继续读入

        //第一部分：预处理每个valid状态
        //对于每种状态，先预处理每列不能有奇数个连续的0

        for(int state=0; state< 1<<rows; state++){//共有1<<rows个数 数二进制表示rows个行的状态

            int consecutive =0 ;//记录连续的0的个数

            bool isValid = true; // 某种状态没有奇数个连续的0则标记为true

            for(int row=0;row<rows;row++){ //从上到下遍历每一行

                 if( state>>row &1){  //state>>row位运算，表示state（state在此处是一种状态）的二进制数的第row位； &1为判断该位是否为1，如果为1进入if
                    if(consecutive &1) { //这一位为1，看前面连续的0的个数，如果是奇数（consecutive &1为真）则该状态不合法
                        isValid =false;break;
                    } 
                    consecutive=0; // 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。
                 }
                 else consecutive++; //否则的话该位还是0，则统计连续0的计数器++。
            }
            if(consecutive &1)  isValid =false; //最下面的那一段判断一下连续的0的个数

            valid[state]  = isValid; //状态state是否有奇数个连续的0的情况,输入到数组valid中
        }

        //第二部分：预处理转移关系
        // 经过上面每种状态 连续0的判断，已经筛掉一些状态。
        //下面来看进一步的判断：看前一列伸出来的和当前列伸出去的是否冲突

        for(int current=0;current< 1<<rows;current++){ //对于每一个当前状态
            transitions[current].clear(); //清空上次操作遗留的状态，防止影响本次状态。
            for(int prev=0;prev< 1<<rows;prev++){ //对于前一列所有状态
                if((current&prev )==0 && valid[ current| prev] ) // 前一列伸出来的 和当前列伸出来的不冲突(不在同一行 如果相同位置上有1就 current和prev会不会是0了) 且这个状态有偶数个0
                //解释一下valid[current | prev] 
                //已经知道valid[]数组表示的是这一列没有连续奇数个0的情况，
                //我们要考虑的是当前列中从前一列横插过来的，还要考虑自己这一列横插到下一列的
                //比如 前一列插过来的是prev=10101，当前列插出去到下一列的是 current =01000，
                //那么合在当前列，到底有多少个1呢？自然想到的就是这两个操作共同的结果：两个状态或。 current | prev = 01000 | 10101 = 11101
                //这个 current|prev 就是当前列的到底有几个1，即哪几行是横着放木板的

                    transitions[current].push_back(prev);  //二维数组transitions[current]表示当前列为current状态时，可以从前一列的prev状态转移而来
            }

        }

        //第三部分：dp开始

        memset(dp,0,sizeof dp);  //全部初始化为0，因为是连续读入，这里是一个清空操作。

        dp[0][0]=1 ;// 这里需要回忆状态表示的定义，按定义这里是：前-1列都摆好，且从-1列到第0列伸出来的状态为0的方案数。
        //首先，这里没有-1列，最少也是0列。其次，没有伸出来，即没有横着摆的。即这里第0列只有竖着摆这1种状态。

        for(int col=1;col<= columns;col++){ //遍历每一列:第col列合法范围是(0~columns-1列)
            for(int current_state=0; current_state< 1<<rows; current_state++){  //遍历当前列（第col列）每一行的总和 所有状态current_state 
                for( auto prev_state : transitions[current_state])    // 遍历前一列 col-1列的状态prev_state，如果转移关系成立，就转移 而前一列的状态dp[col-1][prev_state]又有自带的属性

                    dp[col][current_state] += dp[col-1][prev_state];    // 当前列的方案数就等于之前的第col-1列所有状态prev_state的累加。
            }
        }

        //最后答案是什么呢？
        //dp[columns][0]表示 前columns-1列都处理完，并且第columns-1列没有伸出来的所有方案数。
        //即整个棋盘处理完的方案数

        cout<< dp[columns][0]<<endl;





    }
}   

简化版
#include<bits/stdc++.h>
using namespace std;
const int ROWS = 12, COLS = 1 << ROWS;
int valid[COLS];
long long dp[ROWS][COLS];


int main(){
    int rows, columns;
    while (cin >> rows >> columns && (rows || columns)){

        for (int state = 0; state < 1 << rows; state ++){
            int consecutive = 0;
            valid[state] = true;
            for (int row = 0; row < rows; row ++)
                if (state >> row & 1){
                    if (consecutive & 1) valid[state] = false; // consecutive 为当前已经存在多少个连续的0
                    consecutive = 0;
                }
                else consecutive ++;
            if (consecutive & 1) valid[state] = false; // 扫完后要判断一下最后一段有多少个连续的0
        }

        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int col = 1; col <= columns; col ++)
            for (int current = 0; current < 1 << rows; current ++)
                for (int prev = 0; prev < 1 << rows; prev ++)
                    if ((current & prev) == 0 && (valid[current | prev])) 
                    // current & prev == 0 表示 col 列和 col - 1列同一行不同时延伸
                    // valid[current | prev] == 1 表示 在 col 列状态 current， col - 1 列状态 prev 的情况下是合法的.
                        dp[col][current] += dp[col - 1][prev];      
        cout << dp[columns][0] << endl;
    }
    return 0;
}

最短哈密顿路径

注意：加减运算符的优先级比位运算高！

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

using namespace std;

const int NODES = 20, STATES = 1 << NODES;

int nodeCount;
int distanceMatrix[NODES][NODES];
int dp[STATES][NODES];//STATES存储的最大状态 
//nodeCount表示当前到达了第j个点

int main()
{
    cin >> nodeCount;
    for (int i = 0; i < nodeCount; i ++ )
        for (int j = 0; j < nodeCount; j ++ )
            cin >> distanceMatrix[i][j];

    memset(dp, 0x3f, sizeof dp);//初始为正无穷
    dp[1][0] = 0;//j表示到达了第0个点 i表示经过的是00001也就是第1个点 而这个值是0 不是正无穷

    for (int state = 0; state < 1 << nodeCount; state ++ )//对每个nodeCount个状态的数
        for (int end = 0; end < nodeCount; end ++ )//对所有的点 设置为终点 
            if (state >> end & 1)//需要包含end个点 
才需要进行状态转移 否则没有意义 
                for (int mid = 0; mid < nodeCount; mid ++ )//枚举所有mid尝试找到一个中间点
                    if (state >> mid & 1)//但需要这个状态包含mid这个点
                        dp[state][end] = min(dp[state][end], dp[state - (1 << end)][mid] + distanceMatrix[mid][end]);
//state-(1<<end) 表示出去end这个点 到达mid +mid 到达end的值的最小值

    cout << dp[(1 << nodeCount) - 1][nodeCount - 1];
//第一个表示 每一个nodeCount都是1 只需要二进制下1000000000-1就变成少了一位的111111111了 表示nodeCount个点都走完了 落脚到nodeCount-1这个点(从0开始)的最小值
    return 0;
}