暑期算法帖

一些算法碎碎念-不定时更新

最新一次更新：2025/7/1，更新《数独合理吗？》

[NOIP2018]标题统计

链接：https://ac.nowcoder.com/acm/contest/19305/1016
来源：牛客网

凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？
注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字 符数时，空格和换行符不计算在内


输入描述:

输入文件只有一行， 一个字符串s。

输出描述:

输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。

示例1

输入

234

输出

3

说明

标题中共有 3 个字符，这 3 个字符都是数字字符。

示例2

输入

Ca 45

输出

4

说明

标题中共有 5 个字符，包括 1 个大写英文字母，1 个小写英文字母和 2 个数字字符，
还有 1 个空格。由于空格不计入结果中，故标题的有效字符数为 4 个。

解：

#include <iostream>
using namespace std;
string t;
int main(){
    getline(cin, t);
    while( t.find(' ') != string::npos){
        t.erase(t.find(' '),1);
    }
    cout<<t.length();
}

string中find()返回值是字母在母串中的下标位置。
如果没有找到，那么会返回一个特别的标记npos，一般写作string::npos

说好听点叫练习函数用法，看上去也很简洁，但是感觉不如:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s;
    int n=0;
    while(cin>>s)
    {
        n++;
        if(s==' '){n--;}
    }
    cout<<n;
    return 0;
}

（摊手）

2025/7/1更新

[数独合理吗？]

链接：https://ac.nowcoder.com/acm/contest/19306/1025
来源：牛客网

众所周知，数独是一款简单上手（划掉）且极易打发时间的游戏，
fishfloss喜欢玩数独，虽然自己很菜。
数独的具体规则是这样的：
需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，

并满足每一行、每一列、每一宫（3x3）内的数字均含1-9并不重复


那么下面给出数独盘面，来判断一下它是否是数独的合法解吧

输入描述:

输入共9行，每行9个数，代表数独盘面

输出描述:

一行，如果输入是数独的合法解，则输出YES
反之输出NO

链接：https://ac.nowcoder.com/acm/contest/19306/1025
来源：牛客网

示例1

输入

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 5

输出

YES

示例2

输入

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 3 1 5 6 4 8 9 7
5 6 4 8 9 7 2 3 1
8 9 7 2 3 1 5 6 4
3 1 2 6 4 5 9 7 8
6 4 5 9 7 8 3 1 2
9 7 8 3 1 2 6 4 4

输出

NO

说明

对于宫9，行9及列9，显然有重复的4，故不满足合法解

解：

好，该给大家看看屎了（反正是我自己的网站不怕丢人）

我写之前以为这种写法没准会快不少，而且能少写点代码，抱着这样的心态我得到了：

（其实可以跳过不看，这段代码不是本文重点）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[22]={0},temp;
    for(int i=1;i<=9;i++){
        for(int i2=1;i2<=9;i2++){
            cin>>temp;
            a[12+temp]+=1;
            a[i2]+=temp; 
            a[0]+=temp;
            if (i2<4){
                a[10]+=temp;
            }
            else if(i2<7){
                a[11]+=temp;
            }
            else {
                a[12]+=temp;
            }
        }
        if (a[0]!=45){
            cout<<"NO";
            return 0;
        }
        else{
            a[0]=0;
        }
        if (i%3==0){
            if(a[10]!=45 || a[11]!=45 || a[12]!=45){
                cout<<"NO";
                return 0;
            }
            else{
                a[10]=a[11]=a[12]=0;
            }
        }
    }
    for(int i2=1;i2<=9;i2++){
        if(a[i2]!=45){
            cout<<"NO";
                return 0;
        }
    }
    for(int i2=13;i2<=21;i2++){
        if(a[i2]!=9){
            cout<<"NO";
                return 0;
        }
    }
    cout<<"YES";
}

没有任何想看下去的欲望，对吧（）

结果花了整整4毫秒，1058长（合着一个没捞着，人家都是3毫秒，而且用传统方法700+长就可以写完）

紧接着我看到了一个神仙：

#include<bits/stdc++.h>
using namespace std;
 
set<int> s1[10], s2[10], s3[10];
int a[9][9];
 
int main() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> a[i][j];
            s1[i].insert(a[i][j]);
            s2[j].insert(a[i][j]);
            s3[i / 3 * 3 + j / 3].insert(a[i][j]);
        }
    }
 
    for (int i = 0; i < 9; i++) {
        if (s1[i].size() != 9 || s2[i].size() != 9 || s3[i].size() != 9) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
     
    return 0;
}

3ms，457长，人傻了我，甚至还return 0；

废话不多说，这里贴上ai的带注释版本和解析：

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

// 定义三个集合数组用于存储数独的三种约束：
set<int> s1[10];  // s1[i] 存储第 i 行出现的数字
set<int> s2[10];  // s2[i] 存储第 i 列出现的数字
set<int> s3[10];  // s3[i] 存储第 i 个宫块（3x3子网格）出现的数字
int a[9][9];  // 存储数独矩阵的二维数组

int main() {
    // 读取数独输入并初始化集合
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> a[i][j];  // 读取当前位置的数字
            
            // 将数字添加到对应行的集合
            s1[i].insert(a[i][j]);
            
            // 将数字添加到对应列的集合
            s2[j].insert(a[i][j]);
            
            // 计算并添加到对应宫块的集合
            // 宫块索引的计算：i/3*3 + j/3
            // - i/3 将行分成三组（0-2, 3-5, 6-8）
            // - 乘以3得到宫块行的起始索引（0, 3, 6）
            // - j/3 将列分成三组（0-2, 3-5, 6-8）作为偏移
            // 最终得到0-8共9个宫块索引
            int block_index = i / 3 * 3 + j / 3;
            s3[block_index].insert(a[i][j]);
        }
    }

    // 检查所有约束条件
    for (int i = 0; i < 9; i++) {
        // 检查第 i 行是否包含9个不同数字（即无重复）
        // 检查第 i 列是否包含9个不同数字
        // 检查第 i 个宫块是否包含9个不同数字
        // 任何一个集合的大小不是9，说明有重复数字或数字缺失
        if (s1[i].size() != 9 || s2[i].size() != 9 || s3[i].size() != 9) {
            cout << "NO";  // 不满足数独规则
            return 0;     // 立即退出程序
        }
    }
    
    cout << "YES";  // 所有检查都通过，输出YES
    return 0;
}

解析实现原理：

数据结构设计：

使用set数据结构自动处理重复值，因为集合不能包含重复元素

三个集合数组分别跟踪行、列和宫块中出现的数字

宫块索引计算：

i / 3 * 3 + j / 3 是宫块计算的精髓

例如位置(2,2)：2/3=0 → 0*3=0，2/3=0 → 0+0=0（左上宫块）

位置(4,5)：4/3=1 → 1*3=3，5/3=1 → 3+1=4（中央宫块）

位置(8,8)：8/3=2 → 2*3=6, 8/3=2 → 6+2=8（右下宫块）

验证逻辑：

有效的数独必须同时满足三个条件：

每行包含1-9的不重复数字

每列包含1-9的不重复数字

每个宫块包含1-9的不重复数字

集合大小==9 是核心检查条件（保证9个不重复数字）

效率分析：

时间复杂度：O(n²) 对于9x9数独是常数时间

空间复杂度：O(1) 使用固定大小的数组（共3*9个集合）

太强大了竟然还可以这么写！！！！！！！！！！

评论