对于90后一代，小学时候我们没有微信，没有王者荣耀，也没有大吉大利，今晚吃鸡的喜悦。小时候我们玩的很多游戏，都是一些拼图，连接线段等等。这些问题，我们可以尝试用数组和字符串模拟。

我们以刘汝佳的《算法竞赛》来探讨一些这样的问题

Puzzle (Uva227)

问题描述如下图：

01

c++ STL vector

02
03

字母矩阵常用的方法

字母矩阵常常用string来表示
主要是要实现字母坐标值，和具体字母的分离。
grid[i][j]grid[i][j]表示字母具体值
i=node[k].xj=node[k].yi=node[k].x\quad j=node[k].y

下面介绍两种常用的数据结构stringmapstring\quad map的使用

04
05
06
07

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <iomanip>
#include <map>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <cctype>

using namespace std;

const int size = 5;

typedef struct point
{
    int x;
    int y;
    point(int x=0,int y=0):x(x),y(y) {}
}pos;
pos empty;

vector<string> puzzle;
map<char,pos> dir;

//重载运算符
pos operator+ (const pos& A,const pos& B) {return pos(A.x+B.x,A.y+B.y);}
pos operator- (const pos& A,const pos& B) {return pos(A.x-B.x,A.y-B.y);}
pos operator* (const pos& A,int m) {return pos(A.x*m,A.y*m);}
pos operator/ (const pos& A,int m) {return pos(A.x/m,A.y/m);}
bool operator== (const pos& A,const pos& B) {return A.x==B.x && A.y==B.y;}
bool operator< (const pos& A,const pos& B) {return A.x<B.x || (A.x==B.x && A.y<B.y);}

void printpuzzle()
{
    for(int i=0;i<size;i++)
    {
        for(int j=0;j<size;j++)
        {
            if(j)
                cout<<' ';
            cout<<puzzle[i][j];
        }
        cout<<endl;
    }
}

void getdir()
{
    dir['A']=pos(-1,0);
    dir['B']=pos(1,0);
    dir['L']=pos(0,-1);
    dir['R']=pos(0,1);
}

bool GetPuzzle()
{
    puzzle.clear();
    string line;
    bool flag=true;
    for(int i=0;i<size;i++)
    {
        getline(cin,line);
        if(line=="Z")
        {
            flag=false;
            break;
        }

        for(int j=0;j<size;j++)
        {
            if(line[j]==' ')
            {
                empty.x=i;
                empty.y=j;
            }
        }

        puzzle.push_back(line);  //puzzle为输入的值
    }

    if(flag)
        return true;
    else
        return false;
}

bool valid(const pos& p)
{
    return p.x>=0 && p.x<size && p.y>=0 && p.y<size;
}

bool move(char op)
{
    if(!dir.count(op))
        return false;
    pos next = empty+dir[op];

    if(!valid(next))
        return false;

    swap(puzzle[empty.x][empty.y],puzzle[next.x][next.y]);
    empty=next;   //结构体可以直接赋值
    return true;
}

bool getmoves()
{
    string moves;
    string line;
    while(true)
    {
        getline(cin,line);
        bool end= *(line.rbegin())=='0';
        if(!end)
            moves.append(line);
        else
            moves.append(line,0,line.size()-1);

        if(end)
            break;
    }

    bool legal = true;
    for(int i=0;i<moves.size();i++)
    {
        if(move(moves[i])==false)
        {
            legal=false;
            break;
        }
    }

    if(legal)
        return true;
    else
        return false;

}


int main()
{
    int flag=1;
    getdir();
    while(GetPuzzle())
    {

        bool ok = getmoves();
        if(flag>1)
            cout<<endl;
        cout<<"Puzzle #"<<flag++<<":"<<endl;

        if(ok)
            printpuzzle();
        else
            cout<<"This puzzle has no final configuration."<<endl;
    }
}

Digit counting uva1225

题目描述：
08

本题陈锋的答案写的过于繁琐，这里给出一种一维数组的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <stdio.h>
#include <iostream>

using namespace std;

//#define maxn 10005
#define data 15



void calculate()
{
    //int cnt[maxn][data];
    int cnt[data]={0};
    int maxn;
    scanf("%d",&maxn);

    for(int i=1;i<=maxn;i++)
    {
        //id=i

        int cur = i;
        //int id = i; //第id个数

        while(cur>0)
        {
            int val = cur%10;
            cnt[val]++;

            cur/=10;
        }
    }
    for(int i=0;i<9;i++)
      printf("%d ",cnt[i]);
    printf("%d\n",cnt[9]);
}

int main()
{
    int kase;
    scanf("%d",&kase);

    while(kase--)
    {
        calculate();
    }
    return 0;
}

crossword answers uva232

题目如下：
09

这里我谈一谈我编程的心得体会吧：
分享一些编程的技巧，就是main函数不宜写的很长，比如上面你要去模拟那个矩阵，怎么移动的，你不宜把main函数写太长，你要想：如果是你来移动这个矩阵，你会怎么做？
第一步，当然是获取数据，所以你要写一个获取数据的函数getpuzzle()
第二部是移动操作，往左？往右？于是你需要一个移动函数getmoves()
如果更细致一点？越界？不越界？这更细一点的在getmoves()里面再写一个move()来判断每一步怎么走？下一步可能出现的情况？层层递进～
这是编程最难的一点，就是把一个很复杂的问题，分解，在分解，然后，看到不同子问题之间的逻辑性，抽离出来。不同的抽离方法，会导致编程的难易程度不一样。如果你先入为主地想，怎么移动？万一越界了怎么办？万一不合法的移动怎么办？问题会变得很复杂，当然很难编程。如果你先入为主，首先不要考虑太多细节。然后，逐渐加入某些细节，再写代码。至于每一步，每一层，要加入哪些细节，可以减少编程难度呢？这就是编程艺术性所在的地方，跟画画一样。首先你要描绘一个轮廓，然后，近景？远景的布局是怎么样的，画出来有什么样的效果？这就是编程艺术所在的地方。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include <iostream>
#include <iomanip>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <map>

using namespace std;

typedef struct point
{
    int r;
    int c;
    point(int r=0,int c=0):r(r),c(c) {}
}pos;

pos operator+ (const pos& A,const pos& B) {return pos(A.r+B.r,A.c+B.c);}
const pos dLeft(0,-1),dUp(-1,0),dRight(0,1),dDown(1,0);

int row,col;
const int maxn = 16;
char grid[maxn][maxn];
char buf[maxn];

queue<pos> Crossletter;
queue<pos> Downletter;
map<int,int> Crossid;
map<int,int> Downid;

bool valid(const pos& p)
{
    return p.r>=0 && p.r<row && p.c>=0 && p.c<col;
}

bool getgrid()
{
    memset(grid,'0',sizeof(grid));
    if(scanf("%d%d",&row,&col)==2 && row)
    {
        for(int i=0;i<row;i++)
            scanf("%s",grid[i]);
        return true;
    }
    else
        return false;
}

/*void printgrid()
{
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
            cout<<grid[i][j]<<" ";
        cout<<endl;
    }
}*/

void CheckQueueEmpty(queue<pos> letter)
{
    while(!letter.empty())
    {
        letter.pop();
    }
}

void GetWordBegin()
{

    CheckQueueEmpty(Crossletter);
    CheckQueueEmpty(Downletter);
    int crosscnt=0,downcnt=0;
    Crossid.clear();
    Downid.clear();

    int k = 1;
    for(int i=0;i<row;i++)
    {
        for(int j=0;j<col;j++)
        {
            if(grid[i][j]=='*')
                continue;

            pos cur(i,j);
            pos left = cur+dLeft;
            pos up = cur+dUp;
            bool IsCrossBeg = !valid(left) || grid[left.r][left.c]=='*';
            bool IsDownBeg = !valid(up) || grid[up.r][up.c]=='*';
            if(IsCrossBeg)
            {
                Crossletter.push(cur);
                Crossid[++crosscnt]=k;
            }
            if(IsDownBeg)
            {
                Downletter.push(cur);
                Downid[++downcnt]=k;
            }
            if(IsCrossBeg || IsDownBeg)
                k++;
        }
    }
}

void GetCrossWord()
{
    int i=0;
    while(!Crossletter.empty())
    {
        int buflen=0;
        memset(buf,0,sizeof(buf));

        pos p = Crossletter.front();
        //id = PosCross[p];
        while(grid[p.r][p.c]!='*' && valid(p))
        {
            buf[buflen++]=grid[p.r][p.c];
            p=p+dRight;
        }
        printf("%3d.%s\n",Crossid[++i],buf);
        Crossletter.pop();
    }
}


void GetDownWord()
{
    int i=0;
    while(!Downletter.empty())
    {
        int buflen=0;
        memset(buf,0,sizeof(buf));

        pos p = Downletter.front();
        while(grid[p.r][p.c]!='*' && valid(p))
        {
            buf[buflen++]=grid[p.r][p.c];
            p=p+dDown;
        }
        printf("%3d.%s\n",Downid[++i],buf);
        Downletter.pop();
    }
}

int main()
{
    for(int kase=1;getgrid();kase++)
    {
        if(kase>1)
            cout<<endl;
        printf("puzzle #%d:\n",kase);
        GetWordBegin();
        cout<<"Across"<<endl;
        GetCrossWord();
        cout<<"Down"<<endl;
        GetDownWord();
    }
    return 0;
}

Repeating Decimals uva202

10

这里我给出一种重要的数据处理技巧：

1
char example[maxn]

输入的时候

1
scanf("%s",example)

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>

using namespace std;

const int maxn = 30000;
int pos[maxn];
//int len;
//string ans;
char shang[maxn];

int solve(int a,int b)
{
    int len;
    int Integer = a/b;
    int r = a%b;
    memset(pos,0,sizeof(pos));
    memset(shang,0,sizeof(shang));
    //int pos[maxn];
    //char shang[maxn];

    printf("%d/%d = %d",a,b,Integer);

    shang[0]='.';

    if(r==0)
    {
        //ans+="(0)";
        printf(".(0)");
        len=1;
    }
    else
    {

    //小数部分

        int d = r*10;
        int cnt = 0;

        while(d && pos[d]==0)
        {
            pos[d]=++cnt;
            int cur_r = d%b;
            //ans+=(char) (d/b+'0');
            shang[cnt]=(char)(d/b+'0');
            d = cur_r*10;
        }
        if(d==0)
        {
          //ans+="(0)";
          //shang[cnt]='(';
          //flag! if(shang[i]==-1) printf("(0)");
            for(int i=0;i<=cnt;i++)
            //cout<<shang[i];
                printf("%c",shang[i]);
                //cout<<"(0)";
            printf("(0)");
            len=1;
        }
        if(pos[d])
        {
            int p = pos[d];
            len = cnt-p+1;
        /*if(len>50)
        {
            ans.erase(p+50,cnt-1);
            ans+="...";
        }
        ans.insert(p,"(");
        ans+=")";*/
            if(len>50)
            {
                for(int i=0;i<p;i++)
                //cout<<shang[i];
                    printf("%c",shang[i]);
                //cout<<"(";
                printf("(");
                int k=0;
                for(int i=p;i<=cnt && k<50;i++)
                {
                //cout<<shang[i];
                    printf("%c",shang[i]);
                    k++;
                }
                //cout<<"...)";
                printf("...)");
            }
            else
            {
                for(int i=0;i<p;i++)
                //cout<<shang[i];
                    printf("%c",shang[i]);
                //cout<<"(";
                printf("(");
                //int k=0;
                for(int i=p;i<=cnt;i++)
                //cout<<shang[i];
                    printf("%c",shang[i]);
                //cout<<")";
                printf(")");
            }

        }
    //printf("%d/%d = %d%s\n",a,b,Integer,ans.c_str());
    //printf("   %d = number of digits in repeating cycle\n\n",len);
    //cout<<endl;
    }
    printf("\n");
    return len;
}

int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b)==2 && b)
    {
        int reslen=solve(a,b);
        printf("   %d = number of digits in repeating cycle\n\n",reslen);
    }
    return 0;
}

box uva1587

这个例子我想分享一下简洁的代码怎样写。

题目如下：

11

1
2
bool operator< (const point& p1, const point& p2)  
{ return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y); }

这里是特别说明的一点：因为排序的时候，默认先比较x成员的大小，再比较y成员的大小，所以默认x成员小于y成员
另外涉及排序的时候，我们需要直接输入结构体变量的值，涉及重载运算符
用以下方法输入会导致wrong answer

1
2
3
4
5
6
7
8
for(int i=0;i<6;i++)
{
    if(scanf("%d%d",&a,&b)==EOF)
    flag=0;
    if(a>b)
        swap(a,b);
    r.push_back(point(a,b));
}

我们在处理结构体数组的时候，最好是直接对结构体数组的元素执行输入操作，重载>>运算符
example

1
2
3
4
5
6
7
8
9
typedef struct
{
    //
}node;
istream& operator>> (istream& is,point& p)
{ return is>>p.x>>p.y; }

node n;
cin>>n.x>>n.y

技巧：在处理EOF为终止的输入的时候，用如下方法，很好用

1
2
3
4
5
6
7
8
9
while(true)
{
    r.clear();
    for(int i=0;i<6;i++)
    {
        if(!(cin>>cur))
            return 0;
    }
}

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct point
{
    int x;
    int y;
    point(int x=0,int y=0):x(x),y(y) {}
};

bool operator< (const point& p1, const point& p2)  
{ return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y); }

istream& operator>> (istream& is,point& p)
{ return is>>p.x>>p.y; }




//typedef point rect;
vector<point> r;

bool judge()
{
    if(r[0].x!=r[1].x || r[0].y!=r[1].y)  return false;
    if(r[2].x!=r[3].x || r[2].y!=r[3].y)  return false;
    if(r[4].x!=r[5].x || r[4].y!=r[5].y)  return false;

    const point &r1 = r[1], &r2 = r[3], &r3 = r[5];    
    return r1.x == r2.x && r1.y == r3.x && r2.y == r3.y;
}

int main()
{
    point cur;
    
    while(true)
    {
        r.clear();
        for(int i=0;i<6;i++)
        {
            if(!(cin>>cur))
                return 0;
            if(cur.x>cur.y)
                swap(cur.x,cur.y);
            r.push_back(cur);
        }
        sort(r.begin(),r.end());
        bool ok = judge();
        if(ok)
            printf("POSSIBLE\n");
        else
            printf("IMPOSSIBLE\n");
    }
    return 0;
}

字符串匹配：模板链方法 uva1588

这里以uva1588为例子，简单讲讲字符串匹配中的模板链方法。

题目描述如下：
12

模板链方法描述

13

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

string s1,s2;

bool getstring()
{
    if(cin>>s1>>s2)
    {
        if(s2.length()>s1.length())
        {
            swap(s1,s2);
        }
        return true;
    }
    else
        return false;
}

int maxv(int a,int b)
{
    return a>b?a:b;
}

int minv(int a,int b)
{
    return a<b?a:b;
}

void calculate()
{
    int len1 = s1.length();
    int len2 = s2.length();
    int inside = 0;

    int minres = 0x3f3f3f3f;

    for(int i=-len2;i<=len1+len2-1;i++)
    {
        int flag = 1;

        for(int bias=0;bias<len2;bias++)
        {
            if(i+bias>=0 && i+bias<=len1-1)
            {
                if(s1[i+bias]-'0'+s2[bias]-'0'>3)
                    flag=0;
            }
        }
        //bias遍历完成，意味着标签贴完毕了

        if(flag && i<0)
            minres=min(minres,(-i)+len1);
        if(flag && i+len2>=len1)
            minres=min(minres,i+len2);
        if(flag && i>=0 && i<len1-len2)
            inside=1;
    }

    if(inside==1)
        cout<<len1<<endl;
    else
        cout<<minres<<endl;
}

int main()
{
    while(getstring())
    {
        calculate();
    }
    return 0;
}

c++11中涉及精度的问题

涉及精度的问题并不难，关键是c++提供了一些非常重要的思路：
问题描述：

14

一些重要的思路

c++11中，中提供了一个round()函数，用来做四舍五入操作

**strchr是计算机的一个函数，原型为char strchr(const char s,char c)，可以查找字符串s中首次出现字符c的位置
strcmp() C/C++函数，比较两个字符串,设这两个字符串为str1，str2，若str1==str2，则返回零；若str1<str2，则返回负数；若str1>str2，则返回正数。

原型：

1
*strchr(const char *s,char c)
1
2
3
4
5
6
7
8
9
10
11
char line[maxn];
double A;
int B;
while(scanf("%s",line)==1 && strcmp(line,"0e0")!=0)
{
    *strchr(line,'e') = ' '; //将line中首次出现‘e’的地方，用‘ ’来代替
    sscanf(line,"%lf%d",&A,&B); //sscanf()是很重要的输入方法，将line中
    //符合%lf %d格式的
    //分别输入到A,B中，
    //其中，%lf-->A %d-->B，A和B用空格分开，表示输入两个变量
}

上面注释部分，表示一种非常重要的编程技巧。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;
const int maxn = 256;
const double eps = 1e-6;

int main()
{

    /*char A[256];
    scanf("%s",A);
    char *ptr = strchr(A,'e');
    cout<<ptr<<" "<<*ptr<<endl;
    *strchr(A,'e')='f';
    printf("%s\n",A);*/

    char line[maxn];
    double lg2 = log10(2);
    double A,lgV;
    int B;

    while(scanf("%s",line)==1 && strcmp(line,"0e0")!=0)   //这种输入方式要记住
    {
        *strchr(line,'e')=' ';
        sscanf(line,"%lf%d",&A,&B);
        //cout<<A<<" "<<B<<endl;
        lgV = log10(A)+B;

        for(int M=1;M<=10;M++)
        {
            int E = round( log10( (lgV+M*lg2-log10(pow(2,M)-1))/lg2+1 )/lg2 );
            if( fabs( ((1<<E)-1)*lg2 + log10(pow(2,M)-1) - M*lg2 - lgV ) <= eps )
            {
                printf("%d %d\n",M-1,E);
                break;
            }
        }
    }
    return 0;
}