p1008三连击、UVa340猜数字游戏的提示、Uva1583生成元，POJ-2271（模拟）,fzcoj1787(模拟)

p1008三连击

将1，2，…，9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成1：2：3的比例，试求出所有满足条件的三个三位数。

一个个遍历过去，判断三个数字的每个位的数字是否重复，这里用的办法是先提取出每个位的数字，然后排序，将其与数组下标对齐，如果不数组的值与下标的值不相等，则出现重复。

这里可以用于构造几个数字，然后判断出现的数字是否重复。

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
#include<iostream>
#include<algorithm>
using namespace std;

int i, j, a[15];
bool ans;
int main()
{
    for (i = 123; i <= 329; i++)
    {
        a[1] = i % 10;
        a[2] = i % 100 / 10;
        a[3] = i /1 00;
        a[4] = 2 * i % 10;
        a[5] = 2 * i % 100 / 10;
        a[6] = 2 * i / 100;
        a[7] = 3 * i % 10;
        a[8] = 3 * i % 100 / 10;
        a[9] = 3 * i / 100;
        sort(a + 1, a + 10);
        ans = true;
        for (j = 1; j <= 9; j++) if (a[j] != j) ans = false;
        if (ans) cout << i << " " << i*2 <<" "<< i*3 << endl;
    }
    return 0;
}

UVa340猜数字游戏的提示

实现一个经典”猜数字”游戏。 给定答案序列和用户猜的序列，统计有多少数字位置正确
（A），有多少数字在两个序列都出现过但位置不对（B）。
输入包含多组数据。 每组输入第一行为序列长度n，第二行是答案序列，接下来是若干
猜测序列。 猜测序列全0时该组数据结束。 n=0时输入结束。

样例输入

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

样例输出

Game 1:
(1,1)
(2,0)
(1,2)
(1,2)
(4,0)
Game 2:
(2,4)
(3,2)
(5,0)
(7,0)

分析

这个题目求B时难一些。问的是由多少数字在两个序列都出现过，即两个序列都要有，因此可以分别计数2个序列的中1~9的每个数字个数c1,c2，然后选取其中最小的min(c1,c2)，这个最小的值就是1~9中某个数字在2个序列中出现的次数。然后将所有的min(c1,c2)进行相加，就求出了数字在序列中出现过，然后减去数字位置正确的数字，剩下的就是位置不对的数字了。

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
#include<stdio.h>
#define maxn 1010

int main() {
    int n, a[maxn], b[maxn];
    int kase = 0;
    while (scanf("%d", &n) == 1 && n) { //n=0时输入结束
        printf("Game %d:\n", ++kase);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        for (;;) {
            int A = 0, B = 0;
            for (int i = 0; i < n; i++) {
                scanf("%d", &b[i]);
                if (a[i] == b[i]) A++;
            }
            if(b[0] == 0) break;
            //正常的猜测序列不会有0，所以只判断第一个数是否为0即可
            for (int d = 1; d <= 9; d++) {
                int c1 = 0, c2 = 0;
                //统计数字d在答案序列和猜测序列中各出现多少次
                for (int i = 0; i < n; i++) {
                    if (a[i] == d) c1++;
                    if (b[i] == d) c2++;
                }
                if(c1 < c2) B += c1; else B += c2;
            }
            printf(" (%d,%d)\n", A, B - A);
        }
    }
    return 0;
  }

Uva1583生成元

如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n(1 <= 100000)，求最小生成元。无解输出0.例如,n=216, 121, 2005时的解分别为198,0,1979 。

分析

如果按照常规思路一个个去枚举的话，可能会超时，不妨我们转换思想，先求出所有数的生成元，最后查表即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
#define maxn 100005
int ans[maxn];
int main()
{
    int T,n;
    memset(ans,0,sizeof(ans));
    for(int m=1;m<maxn;m++)
    {
        int x=m,y=m;
        while(x>0){y+=x%10;x/=10;}
        if(ans[y]==0||m<ans[y])ans[y]=m;
    }
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",ans[n]);
    }
    return 0;
}

POJ-2271(模拟)

POJ - 2271

这个模拟可真是。。。刚开始用getline读写了无数个BUG版本代码，后来换cin保平安

题目大意：

​ 要求翻译一篇HTML文档，文档中只有两种HTML标记<br>和<hr>，分别表示换行和划线板，并将左右连续的空格、制表符、换行符当做一个空格输出，还有就是”abc,123”算作一个单词，而”abc, 123”算作两个单词，分别为”abc,”和”123”，具体要求为：

​ 1. 当读取一个单词，当前行不超过80个字符（包括空格），就直接打印在后面（注意单词直接用空格隔开），否则就另起一行在开头处打印该单词，所有单词的最大长度为80；

​ 2. 当读取<br>时直接开启一新行；

​ 3. 当读取<hr>时，如果<hr>不在新行开头就另起一行连续打印80个’-‘后再开启一新行；

​ 4. 全部翻译完后用一个空行结束；

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
/*
Memory: 136K		Time: 16MS
Language: C++		Result: Accepted
Time:  2018-07-19 18:26:23
*/
#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    int cnt = 0;
    while(cin >> s)
    {
        if(s == "<hr>")
        {
            if(cnt) //防止两个<hr>相连时出现多余的换行
                cout << endl;
            for(int i = 0; i < 80; i++)
                cout << "-";
            cnt = 0;
            cout << endl;
        }
        else if(s == "<br>")
        {
            cnt = 0;
            cout << endl;
        }
        else
        {
            int flag = 0; //用来记录空格，因为空格也算一个长度，两个单词之间要有空格
            if(cnt) //前面已经有输出了。要加上空格那个长度
                flag = 1;
            if(cnt + s.size() + flag > 80)
            {
                cout << endl << s;
                cnt = s.size();
            }
            else
            {
                if(cnt)
                {
                    cout << " " << s;
                    cnt += s.size() + 1;
                }
                else
                {
                    cout << s;
                    cnt += s.size();
                }
            }
        }
    }
    return 0;
}

<<<<<<< HEAD

FZCOJ1787

普通的一道模拟题，因为考虑不周加上循环判断语句写得很复杂，导致写了100多行的模拟代码，（而且还wa，emmm），看了题解后才知道不要一蹴而就，要一步步判断，当初就是想判断完这个跳过去，导致无限wa

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
/*
	Ext.Time：13ms
	Time:2018-10-03 21:07:26
*/
#include <iostream>
#include <string>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int test;
    cin >> test;
    while(test--)
    {
        string s1 = "";
        int len = 0;
        cin >> len >> s1;
        int pos1 = 0, pos2 = len - 1;
        while(pos1 <= pos2)
        {
            int tmp1 = pos1;
            int tmp2 = pos2;
            while(tmp1 < tmp2 && s1[tmp1] == s1[tmp2])
            {
                tmp1++;
                tmp2--;
            }
            if(s1[tmp1] > s1[tmp2])
            {
                cout << s1[pos2];
                pos2--;
            }
            else
            {
                cout << s1[pos1];
                pos1++;
            }
        }
        cout << endl;
        s1 = "";
    }
    return 0;
}

附上当初bug代码

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
#include <iostream>
#include <string>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    int test;
    cin >> test;
    while(test--)
    {
        string s1 = "";
        string s2 = "";
        int len = 0;
        cin >> len >> s1;
        int pos1 = 0, pos2 = s1.size() - 1;
        int flag = 0;
        while(1)
        {
            if(pos1 == pos2)
                flag = 2;
            if(flag)
            {
                if(flag == 1)
                    cout << s2 << endl;
                else
                    cout << (s2 += s1[pos1]) << endl;
                break;
            }
            if(s1[pos1] > s1[pos2])
            {
                s2 += s1[pos2];
                pos2--;
            }
            else if(s1[pos1] < s1[pos2])
            {
                s2 += s1[pos1];
                pos1++;
            }
            else
            {
                const int tmp1 = pos1, tmp2 = pos2;
                int cnt = 0;
                while(s1[pos1] == s1[pos2])
                {
                    int tmp = pos1;
                    pos1++;
                    pos2--;
                    cnt++;
                    if(s1[tmp] != s1[pos1])
                        break;
                }
                if(cnt >= 2)
                {
                    for(int k = tmp1; k < pos1; k++)
                        s2 += s1[k];
                    if(pos1 > pos2 || pos1 >= s1.size() || pos2 < 0)
                    {
                        flag = 1;
                        continue;
                    }
                    if(s1[pos1] > s1[pos2])
                    {
                        pos1 = tmp1;
                        s2 += s1[pos2];
                        pos2--;
                    }
                    else
                    {
                        pos2 = tmp2;
                        s2 += s1[pos1];
                        pos1++;
                    }
                }
                else
                {
                    pos1 = tmp1;
                    pos2 = tmp2;
                    if(s1[pos1] < s1[pos2 - 1])
                    {
                        s2 += s1[pos1];
                        pos1++;
                    }
                    else if(s1[pos1] > s1[pos2 - 1])
                    {
                        s2 += s1[pos2];
                        pos2--;
                    }
                    else
                    {
                        s2 = s2 + s1[pos1] + s1[pos1];
                        pos1++;
                        pos2--;
                    }
                    if(pos1 > pos2 || pos1 >= s1.size() || pos2 < 0)
                    {
                        flag = 2;
                    }
                }
            }
        }
    }
    return 0;
}