一些算法/技巧 （自用）

• 这个用来记录一些写代码时学到的一些算法/技巧 （自用）

检测数独是否正确：

位运算的巧妙方法

/*
输入一个数独如：
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2 

要求输出数独是否正确YES/NO
*/

#include <stdio.h>
int main() {
    long long ans[9] = {0}, x, i, j, flag = 0;
    for (i = 0; i <= 8; i++)
        for (j = 0; j <= 8; j++) {
            scanf("%d", &x);
            if (x > 9)
                flag = 1;
            else {
                //将ans这个桶一起遍历记录行，列，宫，分别占用一个longlong数的
                //前9，10-18，19-27位，每位mod（10）的余数表示数字出现次数
                //异或运算，默认为0，遇见一次后为1
                //9次不重复意味着连续9个位上的数为1
                ans[i / 3 * 3 + j / 3] |= 1 << (x + 17);
                //[i / 3 * 3 + j / 3] 表示宫，还是十分巧妙的
                ans[i] |= 1 << (x - 1);
                ans[j] |= 1 << (x + 8);
            }
        }
    for (i = 0; i <= 8; i++)
        if (ans[i] != 0x7ffffff)
        //一个正确的数独，后27位均为1，转化为16进制就是0x7ffffff
            flag = 1;
    printf("%s", flag ? "NO" : "YES");
    return 0;
}