算法竞赛入门：基础算法(一)

algorithm 阅读量

函数的嵌套，加上递归处理，能够解决非常多生活背景下的模拟问题

Ancient Cipher

核心算法图解：

ancient-cipher

实现方法：

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <cstdlib>
#include <iostream>

int cmp(const void *a,const void *b)
{
    return *(int *)a - *(int *)b;
}

int main()
{
    char s1[200], s2[200];
    while((scanf("%s%s",s1,s2)==2))
    {
        int n = strlen(s1);
        int cnt1[26]={0}, cnt2[26]={0};

        for(int i = 0; i < n; i++)
            cnt1[ s1[i]-'A' ]++;
        for(int i = 0; i < n; i++)
            cnt2[ s2[i]-'A' ]++;
        
        qsort(cnt1,26,sizeof(int),cmp);
        qsort(cnt2,26,sizeof(int),cmp);

        int flag = 1;
        for(int i = 0 ; i < 26; i++)
        {
            if(cnt1[i] != cnt2[i])
                flag = 0;
        }

        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

message-decoding

算法图解：

message-decoding

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
#include <stdio.h>
#include <string.h>

int code[8][1<<8];
//二进制编码
//code[len][val]，len表示编码长度
//val表示二进制编码所对应的十进制的值
//code[len][val]表示这个编码所对应的字符‘

//处理换行读入问题
int readchar()
{
    for(;;)
    {
        int ch = getchar();
        if(ch != '\n' && ch != '\r')
            return ch;
    }
}
//执行功能：一个一个字母读入
//绕过'\n' '\r'执行输出

//按位读入二进制数并且转换为十进制整数
int getint(int bits)
{
    int val = 0;
    while(bits--)
    {
        // v = v * 2 means v << 1
        val = val * 2 + readchar() - '0';
    }
    return val;
}

int readcodes()
{
    memset(code,0,sizeof(code));
    code[1][0] = readchar();
    //用来储存编码头代表的译码

    for(int len = 2; len <= 7; len++)
    {
        for(int v = 0; v < (1<<len)-1; v++)
        {
            int ch = getchar();
            if(ch == EOF)
                return 0;
            if(ch == '\n' || ch == '\r')
                return 1;
            code[len][v] = ch;
        }
    }
    return 1;
}
//对编码头信息的解码
//表示编码内容读取的长度

void printcodes()
{
    for(int len = 1; len <= 7; len++)
    {
        for(int v = 0; v < (1<<len)-1; v++)
        {
            if(code[len][v] == 0)
                return;
            //printf("code[%d][%d] = %c\n",len,v,code[len][v]);
        }
    }
}

int main()
{
    while(readcodes())
    //input codes，输入第一行的编码
    {
        printcodes();
        for(;;)
        {
            int len = getint(3);
            if(len == 0)
                break;
            // 000 quit
            
            //printf("len = %d\n",len);
            for(;;)
            {
                int val = getint(len);
                if(val == (1<<len)-1 )
                    break;
                putchar(code[len][val]);
                //printf(" ");
            }
        }
        putchar('\n');
    }
    return 0;
}

spreadsheet-tracking 用2种方法，用flag简化计算

直接模拟

sheet-tracking

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <string.h>

#define maxd 100
#define BIG 10000

using namespace std;

int sh[maxd][maxd], sh_buf[maxd][maxd], ans[maxd][maxd];
int row, col;
int begr, begc;
int change[maxd];

// int oldr,oldc;
// int newr,newc;

void init()
{
    for(int i = 1; i <= row; i++)
    {
        for(int j = 1; j <= col; j++)
            sh[i][j] = i*BIG+j;
    }
}

void movesh(char type,int fresh,int old)
{
    if(type == 'R')
    {
        for(int i = 1; i <= col; i++)
            sh[fresh][i] = sh_buf[old][i];
    }
    else
    {
        for(int i = 1; i <= row; i++)
            sh[i][fresh] = sh_buf[i][old];
    }
}
//算法处理一：用type=='R'，选择的方式，来把行变换和列变换统一起来

void del(char type)
{
    // memset(sh_buf,0,sizeof(sh_buf));
    //memset(change,0,sizeof(change));
    memcpy(sh_buf,sh,sizeof(sh));

    int cnt = 0;
    int way = (type == 'R' ? row : col);

    for(int i = 1; i <= way; i++)
    {
        if(change[i] == 0)
            movesh(type,++cnt,i);
    }
    if(type == 'R')
    {
        row = cnt;
        for(int i = row+1; i <= way; i++)
            for(int j = 1; j <= col; j++)
                sh[i][j] = 0;
    }
    else
    {
        col = cnt;
        for(int i = 1; i <= row; i++)
            for(int j = col+1; j <= way; j++)
                sh[i][j] = 0;
    }
}


void printsheet()
{
    for(int i = 0; i <= row+2; i++)
    {
        for(int j = 0; j <= col+2; j++)
            cout << sh[i][j] <<" ";
        cout << endl;
    }
}

void insert(char type)
{
    // memset(sh_buf,0,sizeof(sh_buf));
    memcpy(sh_buf,sh,sizeof(sh));

    int cnt = 0;
    int way = (type == 'R' ? row : col);
    for(int i = 1; i <= way; i++)
    {
        if(change[i] == 1)
            movesh(type,++cnt,0);
        movesh(type,++cnt,i);
        //这一步卡住了
    }
    if(type == 'R')
        row = cnt;
    else
        col = cnt;
}

// void reset()
// {
//     memcpy(sh_buf,sh,sizeof(sh));
//     for(int i = 1; i <= maxd; i++)
//     {
//         for(int j = 1; j <= maxd; j++)
//         {
//             if(i > row || j > col)
//                 sh_buf[i][j] = 0;
//         }
//     }
// }

int main()
{
    // cin >> row >> col;
    // // begr = row, begc = col;
    // init();
    // memset(change,0,sizeof(change));
    // printsheet();
    //
    // string cmd;
    // cin >> cmd;
    //
    // int op_row;
    // cin >> op_row;
    // change[op_row] = 1;
    // del(cmd[1]);
    // // reset();
    // printsheet();
    // memset(change,0,sizeof(change));
    // cmd.clear();
    //
    // cin >> cmd;
    // int op_col;
    // cin >> op_col;
    // change[op_col] = 1;
    // insert(cmd[1]);
    // // reset();
    // printsheet();
    // 操作数必须和原来的值保持一致
    int kase;
    char cmd[10];
    int sit = 0;
    memset(sh,0,sizeof(sh));

    while(scanf("%d%d%d",&row,&col,&kase)==3 && row)
    {
        init();

        while (kase--)
        {
            scanf("%s",cmd);
            int r1,c1,r2,c2;
            if(cmd[0] == 'E')
            {
                scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
                swap(sh[r1][c1],sh[r2][c2]);
                // printsheet();
            }
            else
            {
                int oper;
                scanf("%d",&oper);
                memset(change,0,sizeof(change));
                //算法处理二：用change[]来标记需要处理的行/列
                //把要操作的数全部选出来
                for(int i = 0; i < oper; i++)
                {
                    //memset(change,0,sizeof(change));
                    int cur;
                    // int r1,c1,r2,c2;
                    scanf("%d",&cur);
                    change[cur] = 1;
                }
                //将change标记预先选出来

                if(cmd[0] == 'D')
                {
                    //change[cur] = 1;
                    del(cmd[1]);
                }
                if(cmd[0] == 'I')
                {
                    //change[cur] = 1;
                    insert(cmd[1]);
                }
                // printsheet();
                // printsheet();
            }
       }

       memset(ans,0,sizeof(ans));
       //这是一个好习惯！
       //所有全局变量在赋值之前需要初始化
       for(int i = 0; i <= row; i++)
       {
          for(int j = 0; j <= col; j++)
          {
              ans[sh[i][j]/BIG][sh[i][j]%BIG] = i*BIG+j;
              //算法处理三：ans相当于一个hash map
              //将原来的坐标ans[sh[r]/BIG][sh[c]%BIG] --> newr*BIG+newc
              //这样最后查询(qr,qc),直接用ans[qr][qc]就可以了
              //ans[qr][qc]/BIG   ---    ans[qr][qc]%BIG就是最后的结论
          }
       }

       if(sit > 0)
          printf("\n");
       printf("Spreadsheet #%d\n",++sit);

       int query;
       int rq,cq;
       scanf("%d",&query);
       while(query--)
       {
            if(scanf("%d%d",&rq,&cq) == 2 && rq)
            {
              printf("Cell data in (%d,%d) ",rq,cq);
              int data = ans[rq][cq];
              if(data == 0)
                  printf("GONE\n");
              else
                  printf("moved to (%d,%d)\n",data/BIG,data%BIG);
            }
       }
    }
}

使用结构体简化

sheet-tracking2

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <cstring>

#define maxd 10000

using namespace std;

struct Command
{
    char c[5];
    int r1, c1, r2, c2;
    int op_n, change[20];
} cmd[maxd];

int row, col, cn;
int oldr, oldc;
int rq,cq;

// int flag = 1;

bool operation(int* rq, int* cq)
{
    for(int i = 0; i < cn; i++)
    {
        if(cmd[i].c[0] == 'E')
        {
            if(cmd[i].r1 == *rq && cmd[i].c1 == *cq)
            {
                *rq = cmd[i].r2;
                *cq = cmd[i].c2;
            }
            else if(cmd[i].r2 == *rq && cmd[i].c2 == *cq)
            {
                *rq = cmd[i].r1;
                *cq = cmd[i].c1;
            }
        }
        //other Command
        else
        {
            int dr = 0, dc = 0;

            if(cmd[i].c[0] == 'I')
            //INSERT
            {
                for(int j = 0; j < cmd[i].op_n; j++)
                {
                    if(cmd[i].c[1] == 'R' && cmd[i].change[j] <= *rq)
                        //cmd[i].change[j] --> row insert
                        dr++;
                    if(cmd[i].c[1] == 'C' && cmd[i].change[j] <= *cq)
                        //col insert;
                        dc++;
                }
            }

            if(cmd[i].c[0] == 'D')
            //delete
            {
                for(int j = 0; j < cmd[i].op_n; j++)
                {
                    if(cmd[i].c[1] == 'R' && cmd[i].change[j] == *rq)
                        return 0;
                    if(cmd[i].c[1] == 'C' && cmd[i].change[j] == *cq)
                        return 0;
                    if(cmd[i].c[1] == 'R' && cmd[i].change[j] < *rq)
                        dr--;
                    if(cmd[i].c[1] == 'C' && cmd[i].change[j] < *cq)
                        dc--;
                }
            }

            *rq += dr;
            *cq += dc;
        }
    }
    return 1;
}


int main()
{
    // int row,col,cn;
    // int rq, cq;
    int kase = 0;

    while(scanf("%d%d%d",&row,&col,&cn) == 3 && row)
    {
        for(int i = 0; i < cn; i++)
        {
            scanf("%s",cmd[i].c);
            // cout << cmd[i].c[0] << endl;
            if(cmd[i].c[0] == 'E')
            {
                scanf("%d%d%d%d",&cmd[i].r1,&cmd[i].c1,&cmd[i].r2,&cmd[i].c2);
            }
            else
            {
                scanf("%d",&cmd[i].op_n);
                for(int j = 0; j < cmd[i].op_n; j++)
                    scanf("%d",&cmd[i].change[j]);
            }
        }

        //QUERY:
        if(kase > 0)
            printf("\n");
        printf("Spreadsheet #%d\n",++kase);

        int query;
        scanf("%d",&query);
        while(query--)
        {
            scanf("%d%d",&rq,&cq);

            oldr = rq; oldc = cq;
            printf("Cell data in (%d,%d) ",oldr,oldc);
            int flag = operation(&rq,&cq);

            if(flag == 0)
                printf("GONE\n");
            else
                printf("moved to (%d,%d)\n",rq,cq);

        }

    }


}

A Typical Homework

这题目我AC了整整十几次！

记录一下自己弄错的地方

typical-homework1

typical-homework2

typical-homework3

typical-homework4

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <algorithm>
#include <vector>

#define EPS 1e-5
#define maxs 105
//105 students

#define maxid 105
//15 digits

using namespace std;


//int n;
//int removed[maxs] = {0};

int subject[6];
//subject[1] pass subject 1 --> subject[2] pass subject 2
int lastid = 0;

typedef struct Students
{
    bool removed;
    char sid[maxid];
    int cid;
    char name[maxid];

    int chinese;
    int math;
    int english;
    int coding;

//    int rank;
    int totscore;

    bool operator < (const Students& s) const{
        return totscore > s.totscore;
    }
    Students()
    {
        memset(this,0,sizeof(Students));
    }
}students;

typedef struct Klass
{
    int totstu;

    int score[4];
    int pass[4];

    Klass()
    {
        memset(this,0,sizeof(Klass));
    }

}klass;

//vector<klass> kl(maxs);

klass kl[maxs + 5];
vector<students> stu;


bool valid(students fresh)
{
    vector<students>::iterator it;
    for(it = stu.begin(); it != stu.end(); it++)
    {
        if(! (*it).removed )
        {
            if(strcmp((*it).sid, fresh.sid) == 0)
                return 0;
        }

    }
    return 1;
}

void add()
{
    for(;;)
    {
        students fresh;
        printf("Please enter the SID, CID, name and four scores. Enter 0 to finish.\n");
        scanf("%s",fresh.sid);

        if(strcmp(fresh.sid, "0") == 0)
            break;

        scanf("%d%s%d%d%d%d",&fresh.cid,fresh.name,&fresh.chinese,&fresh.math,&fresh.english,&fresh.coding);

        if(valid(fresh))
        {
            fresh.totscore = fresh.chinese + fresh.math + fresh.english + fresh.coding;
            fresh.removed = 0;

            int k = fresh.cid;
            kl[k].score[0] += fresh.chinese;
            kl[k].score[1] += fresh.math;
            kl[k].score[2] += fresh.english;
            kl[k].score[3] += fresh.coding;

            if(fresh.chinese >= 60)   kl[k].pass[0]++;
            if(fresh.math >= 60)  kl[k].pass[1]++;
            if(fresh.english >= 60)   kl[k].pass[2]++;
            if(fresh.coding >= 60)    kl[k].pass[3]++;

            kl[k].totstu++;
            stu.push_back(fresh);
        }
        else
            printf("Duplicated SID.\n");
    }
}
//add() finished!

int getrank(students cur)
{
    int r = 0;

    vector<students>::iterator it;
    for(it = stu.begin(); ((*it).sid != cur.sid) && it != stu.end(); it++)
    {
        if(!((*it).removed) && (*it).totscore > cur.totscore)
            r++;
    }
    return r+1;
}
//rank() finished

void DQ(int isq)
{
    for(;;)
    {
        char choose[maxs];
        printf("Please enter SID or name. Enter 0 to finish.\n");
        scanf("%s",choose);

        if(strcmp(choose,"0") == 0)
            break;

        int cal = 0;
        vector<students>::iterator it;
        for(it = stu.begin(); it != stu.end(); it++)
        {
            if(!(*it).removed)
            {
//                cout << stu[i].sid << "-->" << choose << endl;
//                cout << stu[i].name << "-->" << choose << endl;
                if(strcmp((*it).sid,choose) == 0 || strcmp((*it).name,choose) == 0 )
                {
                    if(isq)
                        //printf("%d %s %d %s %d %d %d %d %d %.2f\n", stu[i].rank, stu[i].sid, stu[i].cid, stu[i].name,stu[i].chinese,stu[i].math,stu[i].english,stu[i].coding,stu[i].totscore,stu[i].totscore/4.0+EPS);
                        printf("%d %s %d %s %d %d %d %d %d %.2f\n",getrank(*it),(*it).sid, (*it).cid, (*it).name,(*it).chinese,(*it).math,(*it).english,(*it).coding,(*it).totscore,(*it).totscore/4.0+EPS);
                    else
                    {
                        (*it).removed = 1;

                        //removed students also infect klass
                        int rid = (*it).cid;

                        kl[rid].totstu--;
                        kl[rid].score[0] -= (*it).chinese;
                        kl[rid].score[1] -= (*it).math;
                        kl[rid].score[2] -= (*it).english;
                        kl[rid].score[3] -= (*it).coding;

                        if((*it).chinese >= 60) kl[rid].pass[0]--;
                        if((*it).math >= 60) kl[rid].pass[1]--;
                        if((*it).english >= 60) kl[rid].pass[2]--;
                        if((*it).coding >= 60) kl[rid].pass[3]--;

                        cal++;
                    }
                }
//                if(!isq)
//                    printf("%d student(s) removed.\n",cal);
            }
        }

        if(!isq)
            printf("%d student(s) removed.\n",cal);

    }
}
//DQ test finished!

void overall_stat(int check)
{
    memset(subject, 0, sizeof(subject));
    vector<students>::iterator it;
    for(it = stu.begin(); it != stu.end(); it++)
    {
        if(!(*it).removed && (check == 0 || (*it).cid == check))
        {
            int k = 0;
            if((*it).chinese >= 60) k++;
            if((*it).math >= 60) k++;
            if((*it).english >= 60) k++;
            if((*it).coding >= 60) k++;

            subject[k]++;
        }
    }
//    for(int i = 0; i < 6; i++)
//        printf("pass %d : %d ", i , subject[i]);
}
//test finished




void stat()
{
    int check;
    printf("Please enter class ID, 0 for the whole statistics.\n");
    scanf("%d",&check);


    if(check != 0)
    {
        printf("Chinese\n");
        printf("Average Score: %.2f\n",(double)kl[check].score[0]/(double)kl[check].totstu+EPS);
        printf("Number of passed students: %d\n",kl[check].pass[0]);
        printf("Number of failed students: %d\n",kl[check].totstu-kl[check].pass[0]);
        printf("\n");

        printf("Mathematics\n");
        printf("Average Score: %.2f\n",(double)kl[check].score[1]/(double)kl[check].totstu+EPS);
        printf("Number of passed students: %d\n",kl[check].pass[1]);
        printf("Number of failed students: %d\n",kl[check].totstu-kl[check].pass[1]);
        printf("\n");

        printf("English\n");
        printf("Average Score: %.2f\n",(double)kl[check].score[2]/(double)kl[check].totstu+EPS);
        printf("Number of passed students: %d\n",kl[check].pass[2]);
        printf("Number of failed students: %d\n",kl[check].totstu-kl[check].pass[2]);
        printf("\n");

        printf("Programming\n");
        printf("Average Score: %.2f\n",(double)kl[check].score[3]/(double)kl[check].totstu+EPS);
        printf("Number of passed students: %d\n",kl[check].pass[3]);
        printf("Number of failed students: %d\n",kl[check].totstu-kl[check].pass[3]);
        printf("\n");
    }
    else
    {
        int s1=0, s2=0, s3=0, s4=0;
        int p1=0, p2=0, p3=0, p4=0;

        int m = 0;
        vector<students>::iterator it;
        for(it = stu.begin(); it != stu.end(); it++)
        {
            if(!(*it).removed )
            {
                m++;
                s1 += (*it).chinese;
                s2 += (*it).math;
                s3 += (*it).english;
                s4 += (*it).coding;

                if((*it).chinese >= 60)    p1++;
                if((*it).math >= 60)   p2++;
                if((*it).english >= 60)    p3++;
                if((*it).coding >= 60)     p4++;
            }
        }

        printf("Chinese\n");
        printf("Average Score: %.2f\n",(double)s1/(double)m+EPS);
        printf("Number of passed students: %d\n",p1);
        printf("Number of failed students: %d\n",m-p1);
        printf("\n");

        printf("Mathematics\n");
        printf("Average Score: %.2f\n",(double)s2/(double)m+EPS);
        printf("Number of passed students: %d\n",p2);
        printf("Number of failed students: %d\n",m-p2);
        printf("\n");

        printf("English\n");
        printf("Average Score: %.2f\n",(double)s3/(double)m+EPS);
        printf("Number of passed students: %d\n",p3);
        printf("Number of failed students: %d\n",m-p3);
        printf("\n");

        printf("Programming\n");
        printf("Average Score: %.2f\n",(double)s4/(double)m+EPS);
        printf("Number of passed students: %d\n",p4);
        printf("Number of failed students: %d\n",m-p4);
        printf("\n");

    }

    overall_stat(check);
    printf("Overall:\n");
    printf("Number of students who passed all subjects: %d\n",subject[4]);
    printf("Number of students who passed 3 or more subjects: %d\n",subject[3]+subject[4]);
    printf("Number of students who passed 2 or more subjects: %d\n",subject[2]+subject[3]+subject[4]);
    printf("Number of students who passed 1 or more subjects: %d\n",subject[1]+subject[2]+subject[3]+subject[4]);
    printf("Number of students who failed all subjects: %d\n",subject[0]);
    printf("\n");
}

void print_menu()
{
    printf("Welcome to Student Performance Management System (SPMS).\n");
    printf("\n");
    printf("1 - Add\n");
    printf("2 - Remove\n");
    printf("3 - Query\n");
    printf("4 - Show ranking\n");
    printf("5 - Show Statistics\n");
    printf("0 - Exit\n");
    printf("\n");
}

//void printdata(int n)
//{
//    for(int i = 0; i < n; i++)
//    {
//        printf("%s %d %s %d %d %d %d %d rank: %d\n",stu[i].sid,stu[i].cid,stu[i].name,stu[i].chinese,stu[i].math,stu[i].english,stu[i].coding,stu[i].totscore,stu[i].rank);
//    }
//}



int main()
{
    for( ; ; )
    {
        int choice;
        print_menu();
        scanf("%d",&choice);



        if(choice == 0)
            break;
        if(choice == 1)
        {
            add();
//        cout << stucnt;
//            getrank(cnt);
//            getklass(cnt);
//            cout << cnt << " students "<< endl;
        }

//        for(int i = 0; i < cnt; i++)
//            printf("students %s ",stu[i].name);
//        printf("\n removed: ");
//        for(int i = 0; i < cnt; i++)
//            printf("%d ",removed[i]);

//        sort(stu,stu+cnt);

//        printdata(cnt);
//        printf("\n");


//        printf("enter check : ");
//        int check;
//        scanf("%d",&check);
//        overall_stat(cnt,check,subject);

        if(choice == 2)
            DQ(0);
        if(choice == 3)
            DQ(1);

        if(choice == 4)
            printf("Showing the ranklist hurts students' self-esteem. Don't do that.\n");
        if(choice == 5)
            stat();

    }
}

Xiangqi

这个题我也纠结了好久，就是判断是否将军，这很关键

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct Points
{
    int x;
    int y;
    Points(int x = 0, int y = 0): x(x), y(y) {}
}points;


points operator+ (const points& A, const points& B) { return points(A.x+B.x,A.y+B.y); }
points operator- (const points& A, const points& B) { return points(A.x+B.x,A.y+B.y); }
points operator* (const points& A, int m) { return points(A.x*m,A.y*m); }
points operator/ (const points& A, int m) { return points(A.x/m,A.y/m); }
//运算符重载，判断马腿，容易写错
bool operator== (const points& A, const points& B) { return (A.x == B.x && A.y == B.y); }
bool operator< (const points& A, const points& B) { return (A.x < B.x) || (A.x == B.x && A.y < B.y) ; }

char grid[16][16] = {0};
points dirs[4] = {points(-1,0),points(0,1),points(1,0),points(0,-1)};
points hdirs[8] = {points(2,1),points(1,2),points(-1,2),points(-2,1),points(2,-1),points(1,-2),points(-1,-2),points(-2,-1)};

//红子吃掉黑子的情况要单独判断
//要把原来的那个位置放置什么类型的棋子给放到buffer中
//每判断一种情况后进行复原，再进行新一轮棋子的判断

points blackG, redG;
vector <points> redcheck;

bool valid(const points& p)
{
    bool flagx = (p.x>=1 && p.x<=3);
    bool flagy = (p.y>=4 && p.y<=6);
    return (flagx && flagy);
}

bool straight(const points& p1,const points& p2, int between)
// chariot and cannon
{
    int lx = min(p1.x,p2.x);
    int hx = max(p1.x,p2.x);
    int ly = min(p1.y,p2.y);
    int hy = max(p1.y,p2.y);

    int cnt = 0;
    if(p1.x == p2.x)
    {
        for(int y = ly+1; y < hy; y++)
        {
            if(grid[p1.x][y])
                cnt++;
            if(cnt > between)
                return false;
        }
        return cnt == between;
    }

    if(p1.y == p2.y)
    {
        for(int x = lx+1; x < hx; x++)
        {
            if(grid[x][p1.y])
                cnt++;
            if(cnt > between)
                return false;
        }
        return cnt == between;
    }
    return false;
}

bool checkmate(const points& r, const points& b)
{
    switch(grid[r.x][r.y])
    {
        case 'G':
            return r.y == b.y && straight(r,b,0);
        case 'R':
            return (r.y == b.y || r.x == b.x) && straight(r,b,0);
        case 'C':
            return (r.x == b.x || r.y == b.y) && straight(r,b,1);
        case 'H':
            for(int i = 0; i < 8; i++)
            {
                points hnext = r + hdirs[i];
                points leg = r + hdirs[i]/2;

                if(hnext == b && grid[leg.x][leg.y] == 0)
                    return true;
            }
            return false;

        default:
            return false;
    }
}
//将军的判断，是否完成了一次成功的将军

bool canwin()
{
    if(blackG.y == redG.y && straight(blackG,redG,0))
        return false;
//    bool live = true;

    for(int i = 0; i < 4; i++)
    {
        points bnext = blackG + dirs[i];
        bool live = true;

        if(!valid(bnext))
            continue;

        char buffer = grid[bnext.x][bnext.y];
        grid[bnext.x][bnext.y] = 0;

        //红子吃掉黑子的情况要单独判断
        //要把原来的那个位置放置什么类型的棋子给放到buffer中
        //每判断一种情况后进行复原，再进行新一轮棋子的判断
        //这里是特别需要注意的

        for(vector<points>::iterator it = redcheck.begin(); it != redcheck.end(); it++)
        {
            points rcur = *it;
            if(grid[rcur.x][rcur.y] && checkmate(rcur,bnext))
            {
                live = false;
                break;
            }
        }

        grid[bnext.x][bnext.y] = buffer;
        if(live)
            return false;
    }
    return true;
}

int main()
{
    int kase;
    while(scanf("%d%d%d",&kase,&(blackG.x),&(blackG.y))==3 && kase)
    {
        redcheck.clear();
        memset(grid,0,sizeof(grid));

        char type;
        int x,y;

        while(kase)
        {
//            cout << "kase: " << kase << endl;
            cin >> type >> x >> y;
            points p(x,y);
            redcheck.push_back(p);
            grid[p.x][p.y] = type;

            if(type == 'G')
                redG = p;
            kase--;
        }

        if(canwin())
            printf("YES\n");
        if(!canwin())
            printf("NO\n");
    }
}

othello

这是我当时最快速度ac的题目，纪念一下

特别注意一下优先队列和一些排序

othello1
othello2

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
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
#include <iostream>
#include <cstring>
#include <string.h>
#include <cstdio>
#include <set>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

typedef struct points
{
    int row;
    int col;
    points(int row = 0, int col = 0):row(row),col(col) {}
}pos;

bool operator< (const pos& A,const pos& B) {return (A.row<B.row) || (A.row==B.row && A.col<B.col);}
bool operator== (const pos& A,const pos& B) {return (A.row==B.row) && (A.col==B.col);}
bool operator!= (const pos& A,const pos& B) {return (A.row!=B.row) || (A.col!=B.col);}
pos operator+ (const pos& A,const pos& B) {return pos(A.row+B.row,A.col+B.col);}
pos operator- (const pos& A,const pos& B) {return pos(A.row-B.row,A.col-B.col);}

char board[16][16];
bool mark[16][16];
char player;

pos dr1[4] = {pos(-1,0),pos(-1,1),pos(0,1),pos(1,1)};
pos dr2[4] = {pos(1,0),pos(1,-1),pos(0,-1),pos(-1,-1)};
pos walk[8] = {pos(-1,0),pos(-1,1),pos(0,1),pos(1,1),pos(1,0),pos(1,-1),pos(0,-1),pos(-1,-1)};

set<pos> res;
map<pos,int> dir;
//remember clear()!

bool valid(const pos& p)
{
    bool flag1 = p.row >= 1 && p.row <= 8;
    bool flag2 = p.col >= 1 && p.col <= 8;
    return flag1 && flag2;
}

bool empty(const pos& p){
    return board[p.row][p.col] == '-';
}

char getboard(){
    for(int i = 1; i <= 8; i++){
        for(int j = 1; j <= 8; j++){
            cin >> board[i][j];
        }
    }
    cin >> player;
    return player;
}

void printboard(int kase)
{
    for(int i = 1; i <= 8; i++){
        for(int j = 1; j <= 8; j++){
            cout << board[i][j];
        }
        cout << endl;
    }
    if(kase)
        cout << endl;
}

void checkdisk(char opp,char curp){
    for(int i = 1; i <= 8; i++){
        for(int j = 1; j <= 8; j++){
            if(board[i][j] == opp){
                pos cur(i,j);
//                pos up = cur, down = cur;

                for(int k = 0; k < 4; k++){
                    pos up = cur, down = cur;
                    do{
                        up = up + dr1[k];
                        if(!valid(up))
                            break;
                    }while(board[up.row][up.col] == opp);

                    do{
                        down = down + dr2[k];
                        if(!valid(down))
                            break;
                    }while(board[down.row][down.col] == opp);

                    if(!valid(up) || !valid(down))
                        continue;

                    char flag1 = board[up.row][up.col];
                    char flag2 = board[down.row][down.col];

                    if(flag1 == '-' && flag2 == curp){
                        res.insert(up);
                        dir[up] = k;
                    }
                    if(flag1 == curp && flag2 == '-'){
                        res.insert(down);
                        dir[down] = k;
                    }
                }
            }
        }
    }
}

void printpos()
{
    set<pos>::iterator it;
    int cnt = 0;
    if(!res.size()){
        printf("No legal move.");
    } else{
        for(it = res.begin(); it != res.end(); it++){
            cnt++;
            printf("(%d,%d)",(*it).row,(*it).col);
            if(cnt!=res.size())
                printf(" ");
        }
    }
    printf("\n");
}

void change(const pos& p, char opp, char curp)
{
    pos start = p;
    mark[start.row][start.col] = 1;

    for(int i = 0; i < 8; i++){
        pos next = p + walk[i];

        if(empty(next))
            continue;

        while(board[next.row][next.col] == opp){
            next = next + walk[i];
        }

        if(board[next.row][next.col] == curp){
            for(next = next-walk[i]; next!=start; next = next-walk[i]){
                if(!mark[next.row][next.col]){
                    mark[next.row][next.col] = 1;
                }
            }
        }
    }

    for(int i = 1; i <= 8; i++){
        for(int j = 1; j <= 8; j++){
            if(mark[i][j] == 1){
                board[i][j] = curp;
            }
        }
    }
}

pos getmove(){
    int row,col;
    cin >> row >> col;
    return pos(row,col);
}

void list(){
    int w = 0,b = 0;
    for(int i = 1; i <= 8; i++){
        for(int j = 1; j <= 8; j++){
            if(board[i][j] == 'W')
                w++;
            if(board[i][j] == 'B')
                b++;
        }
    }
    printf("Black - %2d White - %2d\n",b,w);
}


int main()
{
    /*char curp = getboard();
    char opp;
    if(curp == 'B')
        opp = 'W';
    if(curp == 'W')
        opp = 'B';

    checkdisk(opp,curp);
//    printdir();
    printpos();

    pos disk = getmove();
    change(disk,opp,curp);
    printboard();

//    char cmd;
//    cin >> cmd;
//
//    if(cmd == 'L')
//        printpos();*/

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

    while(kase--){
        memset(board,0, sizeof(board));
        memset(mark,0, sizeof(mark));
        res.clear();
        dir.clear();

        char gamer[2];
        gamer[0] = getboard();//cur

        if(gamer[0] == 'B')
            gamer[1] = 'W'; //another
        if(gamer[0] == 'W')
            gamer[1] = 'B';

        int flag = 0;

        char cmd[5];
        for(;;){
            scanf("%s",cmd);

            if(cmd[0] == 'Q'){
                printboard(kase);
                break;
            }
            if(cmd[0] == 'L'){
                checkdisk(gamer[1-flag],gamer[flag]);
                printpos();

                if(!res.size()){
//                    memset(mark,0, sizeof(mark));
                    flag = 1-flag;
                    checkdisk(gamer[1-flag],gamer[flag]);
                }
                res.clear();
            }
            if(cmd[0] == 'M'){
                int x = cmd[1]-'0';
                int y = cmd[2]-'0';
                pos move = pos(x,y);
                memset(mark,0,sizeof(mark));

                change(move,gamer[1-flag],gamer[flag]);
                list();

//                printboard();

                flag = 1-flag;
            }


//            flag = 1-flag;
        }
    }


}

squares

squares1
squares2

这里重点了解一下方形网格的结构体设计

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
#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;

const int MAXN = 16;

int vexp[MAXN][MAXN],hexp[MAXN][MAXN];
int hstart[MAXN][MAXN], vstart[MAXN][MAXN];
int square[MAXN];

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

void getdata(int& kase)
{
    while(kase--)
    {
        char type;
        int x,y;

        cin >> type >> x >> y;

        if(type == 'H')
            hstart[x][y] = 1;
        if(type == 'V')
            vstart[y][x] = 1;
    }
}

void stretch(int n)
{
    for(int i = n; i >= 1; i--){
        for(int j = n; j >= 1; j--){
            if(hstart[i][j]){
                hexp[i][j] = hexp[i][j+1] + 1;
            }
            if(vstart[i][j]){
                vexp[i][j] = vexp[i+1][j] + 1;
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int mins = min(hexp[i][j],vexp[i][j]);

            for(int len = 1; len <= mins; len++){
                if(hexp[i+len][j] >= len && vexp[i][j+len] >= len){
                    square[len]++;
                }
            }
        }
    }
}

int main()
{
    int n;
    for(int t = 1; scanf("%d",&n)==1; t++)
    {
        if(t > 1)
            printf("\n**********************************\n\n");
        memset(vexp,0,sizeof(vexp));
        memset(hexp,0,sizeof(hexp));
        memset(hstart,0,sizeof(hstart));
        memset(vstart,0,sizeof(vstart));
        memset(square,0, sizeof(square));

        int kase;
        scanf("%d",&kase);
        getdata(kase);

        stretch(n);

//        for(int i = 0; i <= n; i++){
//            for(int j = 0; j <= n; j++)
//                cout << hexp[i][j] << " ";
//            cout << endl;
//        }
//        for(int i = 0; i <= n; i++){
//            for(int j = 0; j <= n; j++)
//                cout << vexp[i][j] << " ";
//            cout << endl;
//        }

        printf("Problem #%d\n\n",t);
        bool flag = false;
        for(int i = 1; i <= n; i++){
            if(square[i]){
                flag = true;
                printf("%d square (s) of size %d\n",square[i],i);
            }
        }
        if(!flag)
            printf("No completed squares can be found.\n");
    }
}