文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

模拟，题目很长，但不是很难。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

24点游戏是一种使用扑克牌来进行的益智类游戏，游戏内容是：从一副扑克牌中抽去大小王剩下52张，任意抽取4张牌，把牌面上的数(A代表1)运用加、减、乘、除和括号等进行运算得出24。每张牌都必须使用一次，但不能重复使用。

简单说就是给你4个数(1-13)，数字可以重复，然后让你运用加、减、乘、除和括号运算得出24，每个数字必须使用一次，但不能重复使用。当然，运算中出现的分数是允许的，如1 5 5 5和3 3 8 8这两组数字得到的24点表达式为((5-(1/5))*5) 和 (8/(3-(8/3)))，是不是很变态？

因为表达式是字符串，所以这次我没有用C语言实现，而是选择了具有string类型的C++语言，这样可以更好地处理字符串。在代码中我还使用了STL的Vector来过滤掉重复的解，感叹STL的方便之余对迭代器的使用也有了更深的认识。

至于24点求解的算法，仔细研究一下24点解集，可以发现解的形式无非就是2种。一种是(((A,B),C),D)，另一种是((A,B),(C,D))。有了这个发现，就可以在很大程度上避免对于括号的处理，接下来的工作就是...枚举，哈哈。

花了3个多小时敲代码，注释我写得很清晰了，测试了很多组数据，目前没有发现bug，下面是代码。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

今天翻手机里的游戏时，找到了以前经常玩的九宫格，也就是数独。拼出一个20个已知数字的数独后，我又想写代码解数独了...

思路比较清晰，依旧是DFS，感觉应该不难写。花了2个小时搞定代码，用手机里的数独游戏测试了几次，全部通过...

意外发现PKU 2676就是数独求解，用我写的代码交了2次全是TLE...看了Discuss以后得知要AC必须从后面开始搜...囧，数据问题，数据问题...

恩，代码的注释我写的异常清楚，就不再写废话了。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

周四的外教课，我们那个澳大利亚籍外教给了一个小朋友玩的游戏 -- Crossword Puzzles。规则就是先给你一个由字母组成的矩阵，里面隐藏了很多单词，之后再给你一排单词，让你把这些单词在矩阵里画出来...

11 11
r e h t o r b b r y g
y r e h t o m e a r z
l e l n n o h t a w r
i t c b i t z n w e g
m s n y a s d a u n t
a i u f n p u w e f e
f s w n a m t o r o w
u i c r t p r l c x p
t g e n d c e b s x u
u n c l r m z f e m a
t w q r v t o h c y t

9
aunt
brother
cousin
family
father
grandparent
mother
sister
uncle

恩，大概就是这么个意思。不过我最近比较烦啊，哪里有心情去一个一个找，还不说这些单词可以正向，可以反向，可以斜着...大爷没空

烦躁的时候就想写代码，顺手就把这个小游戏敲完了，懒得写printf和scanf，就用C++的cin和cout，不过没有什么高深算法，就是一个简单的深搜，上面的那堆就是测试数据，效果自己编译运行看去...

我发这个代码纯属凑文章数...

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

算了，博客不知道发什么，继续刷水题...

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

Kruskal算法的应用

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

下午研究了一下全排列算法，然后发现C++的STL有一个函数可以方便地生成全排列，这就是next_permutation

在C++ Reference中查看了一下next_permutation的函数声明：

#include <algorithm>
bool next_permutation( iterator start, iterator end );

The next_permutation() function attempts to transform the given range of elements [start,end) into the next lexicographically greater permutation of elements. If it succeeds, it returns true, otherwise, it returns false.

从说明中可以看到 next_permutation 的返回值是布尔类型。按照提示写了一个标准C++程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <algorithm>
#include <string>
 
using namespace std;
 
int main()
{
    string str;
    cin >> str;
    sort(str.begin(), str.end());
    cout << str << endl;
    while (next_permutation(str.begin(), str.end()))
    {
        cout << str << endl;
    }
    return 0;
}

其中还用到了 sort 函数和 string.begin()、string.end() ，函数声明如下：

#include <algorithm>
void sort( iterator start, iterator end );

sort函数可以使用NlogN的复杂度对参数范围内的数据进行排序。

#include <string>
iterator begin();
const_iterator begin() const;

#include <string>
iterator end();
const_iterator end() const;

string.begin()和string.end() 可以快速访问到字符串的首字符和尾字符。

在使用大数据测试的时候，发现标准C++的效率很差...换成C函数写一下，效率提升了不止一倍...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAX 100
 
using namespace std;
 
int main()
{
    int length;
    char str[MAX];
    gets(str);
    length = strlen(str);
    sort(str, str + length);
    puts(str);
    while (next_permutation(str, str + length))
    {
        puts(str);
    }
    return 0;
}