分类目录归档：模拟

蓝桥杯 历届试题 小计算器

发表评论

问题描述
　　模拟程序型计算器，依次输入指令，可能包含的指令有

　　1. 数字：’NUM X’，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数
　　2. 运算指令：’ADD’,’SUB’,’MUL’,’DIV’,’MOD’，分别表示加减乘，除法取商，除法取余
　　3. 进制转换指令：’CHANGE K’，将当前进制转换为K进制(2≤K≤36)
　　4. 输出指令：’EQUAL’，以当前进制输出结果
　　5. 重置指令：’CLEAR’，清除当前数字

　　指令按照以下规则给出：
　　数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出
　　运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令
　　重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令
　　进制转换指令可能出现在任何地方

　　运算过程中中间变量均为非负整数，且小于2^63。
　　以大写的’A’~’Z’表示10~35
输入格式
　　第1行：1个n，表示指令数量
　　第2..n+1行：每行给出一条指令。指令序列一定以’CLEAR’作为开始，并且满足指令规则
输出格式
　　依次给出每一次’EQUAL’得到的结果
样例输入
7
CLEAR
NUM 1024
CHANGE 2
ADD
NUM 100000
CHANGE 8
EQUAL
样例输出
2040

可以说样例给的挺恶心。会让人想不到，这玩意要考虑还是不考虑优先级！？最后在测试下是不需要考虑优先级的。直接挨着个的算即可。还有一个点是我进制转换写错了（竟然’A’->11，生无可恋脸）一直在调这里。。。。其他没啥了。

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
#include<iostream>
#include<deque>
#include<algorithm>
#include<cassert>
#include<cstdlib>
#include<string>
using namespace std;
int n;
int radix = 10;
string radixS = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
deque<long long> sll;
deque<string> sop;
long long value;
inline long long getCorDecimal(char c) {
    if ('0' <= c && c <= '9')return c - '0';
    if ('A' <= c && c <= 'Z')return c - 'A' + 10;
    assert(false);
    return -1;
}
long long Radix2Decimal(string s) {
    reverse(s.begin(), s.end());
    long long cntBase = 1, result = 0;
    for (int i = 0; i<s.size(); i++) {
        result += getCorDecimal(s[i])*cntBase;
        cntBase *= radix;
    }
    return result;
}
string Decimal2Radix(long long v) {
    string s = "";
    while (v) {
        s.push_back(radixS[v%radix]);
        v /= radix;
    }
    if (s == "")s = "0";
    reverse(s.begin(), s.end());
    return s;
}
bool calculate4Back() {
    if (sop.empty())return false;
    string & comm = sop.back();
    if (comm == "ADD")value += sll.back();
    else if (comm == "SUB")value = sll.back() - value;
    else if (comm == "MUL")value *= sll.back();
    else if (comm == "DIV")value = sll.back() / value;
    else if (comm == "MOD")value = sll.back() % value;
    else assert(false);
    sop.pop_back();
    sll.pop_back();
    sll.push_back(value);
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        string comm, radixV;
        cin >> comm;
        if (comm == "NUM") {
            cin >> radixV;
            value = Radix2Decimal(radixV);
            if (!calculate4Back())sll.push_back(value);
            //cout<<Decimal2Radix(sll.front())<<endl;
        }
        else if (comm == "ADD" || comm == "SUB" || comm == "MUL" || comm == "DIV" || comm == "MOD") {
            sop.push_back(comm);
        }
        else if (comm == "CHANGE") {
            cin >> radix;
        }
        else if (comm == "EQUAL") {
            cout << Decimal2Radix(sll.front()) << endl;
        }
        else if (comm == "CLEAR") {
            sll.clear();
            sop.clear();
        }
    }
}

洛谷 P1022 计算器的改良

发表评论
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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
int ratio = 0, constant = 0;
#define IfLetter if (ch <= 'Z'&&ch >= 'A' || ch <= 'z'&&ch >= 'a')
#define IfNumber if (ch >= '0'&&ch <= '9' || ch=='+' || ch=='-')
int main() {
    char letter;
    char ch;
    int num = 0;
    bool flag = true;
    while ((ch = getchar()) != '\n') {
        IfNumber{ // number(maybe with variable)
            ungetc(ch, stdin);
            int re = scanf("%d", &num); //specially prepared for the testcase form like "-a"
            if (re == 0) {
                getchar();
                ratio -= (flag ? 1 : -1);
            }
            ch = getchar();
            IfLetter{
                ratio += num * (flag ? 1 : -1);
                letter = ch;
            }
            else {
                constant += num * (flag ? 1 : -1);
                ungetc(ch, stdin);
            }
            num = 0;
        }
        else IfLetter{ //pure variable without ratio
            letter = ch;
            ratio+=(flag ? 1 : -1);
        }
        else if (ch == '=') {
            flag = false;
        }
    }
    printf("%c=%.3lf", letter, -1.0*constant / ratio);
}

洛谷 P1058 立体图

发表评论

虽然写的时间很长，但是AC之后随便画图可是很好玩的哦。。。

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int m, n, am, an;
int arr[55][55];
char output[500][500];
int calM(int m, int mh, int tm) { //每行挑最大的执行一次
    return (tm - m + 1) * 2 + max(1 + 3 * mh, 1 + 2 * (m - 1));
}
inline int calN(int m, int n) { //整体执行一次
    return 1 + 4 * n + 2 * m;
}
inline void printLine(int x, int y) {
    output[x][y] = output[x][y + 4] = '+';
    output[x][y + 1] = output[x][y + 2] = output[x][y + 3] = '-';
}
inline void printRow(int x, int y) {
    output[x][y] = output[x + 2][y - 2] = '+';
    output[x + 1][y - 1] = '/';
}
inline void printHeight(int x, int y) {
    output[x][y] = output[x + 3][y] = '+';
    output[x + 1][y] = output[x + 2][y] = '|';
}
inline void printSpace(int x, int y) {
    output[x + 1][y] = output[x + 1][y + 1] = output[x + 1][y + 2] = ' ';
    output[x + 3][y - 1] = output[x + 3][y] = output[x + 3][y + 1] = ' ';
    output[x + 4][y - 1] = output[x + 4][y] = output[x + 4][y + 1] = ' ';
    output[x + 2][y + 3] = output[x + 3][y + 3] = ' ';
}
inline void printCube(int x, int y) { //左上角坐标
    printLine(x, y);
    printLine(x + 2, y - 2);
    printLine(x + 5, y - 2);
    printRow(x, y);
    printRow(x, y + 4);
    printRow(x + 3, y + 4);
    printHeight(x + 2, y - 2);
    printHeight(x + 2, y + 2);
    printHeight(x, y + 4);
    printSpace(x, y);
}
inline void printCube2(int l, int r, int h) {
    printCube(am - 3 * h - 2 * (m-l+1), 1+2 * (m - l + 1) + (r - 1) * 4);
}
inline void printAns() {
    for (int i = 1; i <= am; i++) {
        cout << output[i] + 1 << endl;
    }
    cout << endl;
}
int main() {
    cin >> m >> n;
    an = calN(m, n);
    for (int i = 1; i <= m; i++) {
        int mmax = 0;
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
            mmax = max(mmax, arr[i][j]);
        }
        am = max(am, calM(i, mmax, m));
    }
    for (int i = 1; i <= am; i++) {
        for (int j = 1; j <= an; j++) {
            output[i][j] = '.';
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= arr[i][j]; k++) {
                printCube2(i, j, k);
                //printAns();
            }
        }
    }
    printAns();
}

提示：把79行的注释符号去掉可以看到图形生成全过程哦；
写了个好玩的小程序，随机生成数组中的高度哦。。。
各位OIer可以随便试试。。。

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
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
#include<ctime>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
int m, n, am, an;
int arr[55][55];
char output[500][500];
int calM(int m, int mh, int tm) { //每行挑最大的执行一次
    return (tm - m + 1) * 2 + max(1 + 3 * mh, 1 + 2 * (m - 1));
}
inline int calN(int m, int n) { //整体执行一次
    return 1 + 4 * n + 2 * m;
}
inline void printLine(int x, int y) {
    output[x][y] = output[x][y + 4] = '+';
    output[x][y + 1] = output[x][y + 2] = output[x][y + 3] = '-';
}
inline void printRow(int x, int y) {
    output[x][y] = output[x + 2][y - 2] = '+';
    output[x + 1][y - 1] = '/';
}
inline void printHeight(int x, int y) {
    output[x][y] = output[x + 3][y] = '+';
    output[x + 1][y] = output[x + 2][y] = '|';
}
inline void printSpace(int x, int y) {
    output[x + 1][y] = output[x + 1][y + 1] = output[x + 1][y + 2] = ' ';
    output[x + 3][y - 1] = output[x + 3][y] = output[x + 3][y + 1] = ' ';
    output[x + 4][y - 1] = output[x + 4][y] = output[x + 4][y + 1] = ' ';
    output[x + 2][y + 3] = output[x + 3][y + 3] = ' ';
}
inline void printCube(int x, int y) { //左上角坐标
    printLine(x, y);
    printLine(x + 2, y - 2);
    printLine(x + 5, y - 2);
    printRow(x, y);
    printRow(x, y + 4);
    printRow(x + 3, y + 4);
    printHeight(x + 2, y - 2);
    printHeight(x + 2, y + 2);
    printHeight(x, y + 4);
    printSpace(x, y);
}
inline void printCube2(int l, int r, int h) {
    printCube(am - 3 * h - 2 * (m - l + 1), 1 + 2 * (m - l + 1) + (r - 1) * 4);
}
inline void printArray() {
    cout << "Printing each element of the array:" << endl;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            cout << arr[i][j] << " ";
        }
        cout << endl;
    }
}
inline void printAns() {
    for (int i = 1; i <= am; i++) {
        cout << output[i] + 1 << endl;
    }
    cout << endl;
}
int main() {
    srand((unsigned)time(NULL));
    cout << "Please input the side length "n" of the cube array (n<=50):";
    int len;
    cin >> len;
    m = n = len;
    an = calN(m, n);
    cout << "Please input the max height "mh" of cubes in each array item (1<=mh<=100):";
    int mh;
    cin >> mh;
    cout << "Do you want to show the whole process of filling?(Answer with 0[No] or 1[Yes]):";
    bool flag;
    cin >> flag;
    for (int i = 1; i <= m; i++) {
        int mmax = 0;
        for (int j = 1; j <= n; j++) {
            arr[i][j] = rand() % mh + 1;
            mmax = max(mmax, arr[i][j]);
        }
        am = max(am, calM(i, mmax, m));
    }
    for (int i = 1; i <= am; i++) {
        for (int j = 1; j <= an; j++) {
            output[i][j] = '.';
        }
    }
    cout << "Automatically generated an array,printed in the following.Press ENTER to continue." << endl;
    printArray();
    cin.get(); cin.get();
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= arr[i][j]; k++) {
                if (flag)cout << "Printing cube on postion(" << i << "," << j << "," << k << ")." << endl;
                printCube2(i, j, k);
                if (flag)printAns();
            }
        }
    }
    cout << "Printing Final Result:" << endl;
    printAns();
}

洛谷 谁拿了最多奖学金

发表评论

这题本身没啥好说的，非常简单，要说的是C++的一个特性。
这个题写的比较复杂，其实不用这么多空间，也不要排序，直接线性处理就行了。但是我写题写习惯了，又接着搞排序，就出了这么个问题。

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
#include<bits/stdc++.h>
using namespace std;
int n;
struct stu{
    string name;
    int fs,cs;
    char sl,wp;
    int an;
    int money;
    stu(){
        money=0;
    }
    bool operator < (const stu& s2){
        return money>=s2.money;
    }
}stus[105];
int sum=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>stus[i].name>>stus[i].fs>>stus[i].cs>>stus[i].sl>>stus[i].wp>>stus[i].an;
    for(int i=1;i<=n;i++){
        if(stus[i].fs>80&&stus[i].an>=1)stus[i].money+=8000;
        if(stus[i].fs>85&&stus[i].cs>80)stus[i].money+=4000;
        if(stus[i].fs>90)stus[i].money+=2000;
        if(stus[i].fs>85&&stus[i].wp=='Y')stus[i].money+=1000;
        if(stus[i].cs>80&&stus[i].sl=='Y')stus[i].money+=850;
        sum+=stus[i].money;
    }
    sort(stus+1,stus+n+1);
    cout<<stus[1].name<<endl;
    cout<<stus[1].money<<endl;
    cout<<sum;
}

问题就出在比较的>=号上。查找了资料（地址http://blog.sina.com.cn/s/blog_532f6e8f01014c7y.html），我没细看，总结出来就是sort的cmp不能用带=号的。这个问题我最后就用stable_sort解决了。好用。代码如下：

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
#include<iostream>
#include<algorithm>
using namespace std;
int n;
struct stu{
    string name;
    int fs,cs;
    char sl,wp;
    int an;
    int money;
    bool operator < (const stu& s2) const{
        return money>s2.money;
    }
}stus[205];
int sum1=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>stus[i].name>>stus[i].fs>>stus[i].cs>>stus[i].sl>>stus[i].wp>>stus[i].an;
    }
    for(int i=1;i<=n;i++){
        if(stus[i].fs>80&&stus[i].an>=1)stus[i].money+=8000;
        if(stus[i].fs>85&&stus[i].cs>80)stus[i].money+=4000;
        if(stus[i].fs>90)stus[i].money+=2000;
        if(stus[i].fs>85&&stus[i].wp=='Y')stus[i].money+=1000;
        if(stus[i].cs>80&&stus[i].sl=='Y')stus[i].money+=850;
        sum1+=stus[i].money;
    }
    stable_sort(stus+1,stus+n+1);
    cout<<stus[1].name<<endl;
    cout<<stus[1].money<<endl;
    cout<<sum1;
}

NOIP2017普及组前两道水题

发表评论

T1

1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int main() {
    double a, b, c;
    cin >> a >> b >> c;
    long long re = 0.2*a + 0.3*b + 0.5*c;
    cout << re;
}

T2

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
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
bool cmp(string s1, string s2) {
    if (s1.length() != s2.length())return s1.length() < s2.length();
    return s1 < s2;
}
int main() {
    int n, q;
    vector<string> arr;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        string tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end(), cmp);
    for (int i = 1; i <= q; i++) {
        int tmpi;
        string tmp;
        cin >> tmpi >> tmp;
        bool flag = false;
        for (vector<string>::iterator ptr = arr.begin(); ptr != arr.end(); ptr++) {
            if (ptr->length() - tmp.length() <=1e9 && ptr->substr(ptr->length() - tmp.length()) == tmp) {
                flag = true;
                cout << (*ptr) << endl;
                break;
            }
        }
        if (!flag)cout << "-1" << endl;
    }
}

洛谷 机器翻译

发表评论

题号：1540

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
#include<bits/stdc++.h>
using namespace std;
int m, n;
int head = 0, tail = 0;
int arr[105];
int cnt;
int main(){
    ios::sync_with_stdio(false);
    cin >> m >> n;
    m++;
    for (int i = 0; i < m; i++){
        arr[i] = -1;
    }
    for (int i = 1; i <= n; i++){
        int word;
        cin >> word;
        bool flag = false;
        for (int i = head; i != tail; i = (i + 1) % m){
            if (arr[i] == word){
                flag = true;
                break;
            }
        }
        if (!flag){
            if (head == (tail + 1) % m)head = (head + 1) % m;
            cnt++;
            arr[tail] = word;
            tail = (tail + 1) % m;
        }
    }
    cout << cnt;
}

洛谷 序言页码 Preface Numbering

发表评论

也是一道恶心的题，相比上面那一道一点不会2333.
题号：1465

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
char str[31][5] = {
    " ", "I", "II", "III", "IV", "V", "VI", "VII", "VIII",
    "IX", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX",
    "XC", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC",
    "CM", "M", "MM", "MMM"
};
char arr1[8] = "IVXLCDM";
int num[31] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200,
    300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000
};
int a[26];
void _find(int x){
    int j = 30;
    while (num[j] > x)j--;
    for (; j >= 1; j--){
        if (x >= num[j]){
            x -= num[j];
            for (int i = 0; i < strlen(str[j]); i++){
                a[str[j][i] - 'A']++;
            }
        }
        if (x == 0)return;
    }
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        _find(i);
    }
    if (a[int('I') - 65] != 0) printf("I %d\n", a[int('I') - 65]);
    if (a[int('V') - 65] != 0) printf("V %d\n", a[int('V') - 65]);
    if (a[int('X') - 65] != 0) printf("X %d\n", a[int('X') - 65]);
    if (a[int('L') - 65] != 0) printf("L %d\n", a[int('L') - 65]);
    if (a[int('C') - 65] != 0) printf("C %d\n", a[int('C') - 65]);
    if (a[int('D') - 65] != 0) printf("D %d\n", a[int('D') - 65]);
    if (a[int('M') - 65] != 0) printf("M %d\n", a[int('M') - 65]);
}

只有这样才能过……

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
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
char str[31][5] = {
    " ", "I", "II", "III", "IV", "V", "VI", "VII", "VIII",
    "IX", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX",
    "XC", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC",
    "CM", "M", "MM", "MMM"
};
char arr[8] = "IVXLCDM";
int num[31] = {
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200,
    300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000
};
int a[26];
void _find(int x){
    int j = 30;
    while (num[j] > x)j--;
    for (; j >= 1; j--){
        if (x >= num[j]){
            x -= num[j];
            for (int i = 0; i < strlen(str[j]); i++){
                a[str[j][i] - 'A']++;
            }
        }
        if (x == 0)return;
    }
}
int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        _find(i);
    }
    for (int i = 0; i < 8; i++){
        if (a[arr[i] - 'A'] != 0)cout << (char)(arr[i]) << " " << a[arr[i] - 'A'] << endl;
    }
}

这样莫名其妙多出来一行输出@_500，根本不知道怎么回事……

洛谷 派对灯 Party Lamps

发表评论

USACO原题，比较恶心……看得题解
表示DFS只有三十分，就不用尝试DFS了，去看洛谷题解吧
题号：1468
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1468
作者: ☜闪耀星空☞ 更新时间: 2017-08-10 10:11

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
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int n, c, a, t;
bool light[10], dark[10],flag;
int map[10][10] = {
    { 0, 1, 1, 1, 1, 1, 1 }, //0
    { 0, 0, 0, 0, 0, 0, 0 }, //1
    { 0, 0, 1, 0, 1, 0, 1 }, //2
    { 0, 1, 0, 1, 0, 1, 0 }, //3
    { 0, 0, 1, 1, 0, 1, 1 }, //4
    { 0, 1, 0, 0, 1, 0, 0 }, //1,4
    { 0, 1, 1, 0, 0, 0, 1 }, //2,4
    { 0, 0, 0, 1, 1, 1, 0 }, //3,4
};
void print(int x){
    for (int i = 1; i <= 6; i++){
        if (light[i] && !map[x][i] || dark[i] && map[x][i])return;
    }
    flag = true;
    for (int i = 0; i < n; i++)cout << map[x][i % 6 + 1];
    cout << endl;
}
int main(){
    cin >> n >> c;
    while (cin >> t, t != -1)light[(t - 1) % 6 + 1] = true;
    while (cin >> t, t != -1)dark[(t - 1) % 6 + 1] = true;
    c = min(3, c);
    switch (c){
    case 0:print(0); break;
    case 1:print(1); print(2); print(4); print(3); break;
    case 2:print(1); print(7); print(2); print(4); print(3); print(6); print(0); break;
    case 3:print(1); print(7); print(2); print(4); print(5); print(3); print(6); print(0); break;
    }
    if (!flag)cout << "IMPOSSIBLE" << endl;
}

USACO Section 1.2 Transformations

发表评论

Transformations
A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations: #1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees. #2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees. #3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees. #4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image). #5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3). #6: No Change: The original pattern was not changed. #7: Invalid Transformation: The new pattern was not obtained by any of the above methods. In the case that more than one transform could have been used, choose the one with the minimum number above. PROGRAM NAME: transform INPUT FORMAT Line 1: A single integer, N Line 2..N+1: N lines of N characters (each either `@' or `-'); this is the square before transformation Line N+2..2*N+1: N lines of N characters (each either `@' or `-'); this is the square after transformation SAMPLE INPUT (file transform.in) 3 @[email protected] --- @@- @[email protected] @-- [email protected] OUTPUT FORMAT A single line containing the number from 1 through 7 (described above) that categorizes the transformation required to change from the `before' representation to the `after' representation. SAMPLE OUTPUT (file transform.out) 1 标准输入输出:

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
#include<iostream>
#include<string>
#include<cstring>
int n;
namespace function {
    void reverse_str(char * s) {
        int len = strlen(s);
        for (int i = 0,j=len-1; i <j; i++,j--) {
            std::swap(s[i], s[j]);
        }
    }
    bool cmp(char arr1[11][11], char arr2[11][11]) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (arr1[i][j] != arr2[i][j])return false;
            }
        }
        return true;
    }
    void rotate90(char arr1[11][11], char arr2[11][11]) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr2[j][n-1-i] = arr1[i][j];
            }
        }
    }
    void rotate180(char arr1[11][11], char arr2[11][11]) {
        rotate90(arr1, arr2);
        rotate90(arr2, arr1);
        std::memcpy(arr2, arr1, sizeof(char)*11*11);
    }
    void rotate270(char arr1[11][11], char arr2[11][11]) {
        rotate90(arr1, arr2);
        rotate90(arr2, arr1);
        rotate90(arr1, arr2);
    }
    void reflection(char arr1[11][11], char arr2[11][11]) {
        std::memcpy(arr2, arr1, sizeof(char) * 11 * 11);
        for (int i = 0; i < n; i++) {
            reverse_str(arr2[i]);
        }
    }
    bool combination(char arr1[11][11], char arr2[11][11],char original[11][11],char transfered[11][11]) {
        std::memcpy(arr1, original, sizeof(char) * 11 * 11);
        reflection(arr1, arr2);
        std::memcpy(arr1, arr2, sizeof(char) * 11 * 11);
        rotate90(arr1, arr2);
        if (cmp(transfered, arr2))return true;
        rotate180(arr1, arr2);
        if (cmp(transfered, arr2))return true;
        std::memcpy(arr1, original, sizeof(char) * 11 * 11);
        reflection(arr1, arr2);
        std::memcpy(arr1, arr2, sizeof(char) * 11 * 11);
        rotate270(arr1, arr2);
        if (cmp(transfered, arr2))return true;
        return false;
    }
}
namespace std {
    char arr_original[11][11],arr_transfered[11][11];
    char temp1[11][11], temp2[11][11];
    int main() {
        function::rotate90(arr_original, temp1);
        if (function::cmp(temp1, arr_transfered))return 1;
        function::rotate90(temp1, temp2);
        if (function::cmp(temp2, arr_transfered))return 2;
        function::rotate90(temp2, temp1);
        if (function::cmp(temp1, arr_transfered))return 3;
        function::reflection(arr_original, temp1);
        if (function::cmp(temp1, arr_transfered))return 4;
        if(function::combination(temp1, temp2, arr_original,arr_transfered))return 5;
        if (function::cmp(arr_original, arr_transfered))return 6;
        return 7;
    }
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::cin >> std::arr_original[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> std::arr_transfered[i];
    }
    std::cout<<std::main();
}

洛谷 [USACO1.1]坏掉的项链Broken Necklace

发表评论

题号：1203
并不知道为什么AC，本来45分瞎改了改AC的。。。这破题也是神烦……

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
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int n;
string s;
char search(int start, int ptr){
    for (int i = ptr; i - start +1 <= n; i++){
        if (s[i] != 'w')return s[i];
    }
    return 'w';
}
int run(int start,char c, char a){
    int tmax = 0;
    bool flag = false;
    int ptr = start;
    char cur;
    if (s[start] == a)return 0;
    while (1){
        if (!flag){
            if (s[ptr] == c || s[ptr] == 'w')tmax++;
            else {
                flag = true;
                tmax++;
                cur = search(start, ptr); //就这里，我觉得reference 2应该是ptr+1才对。。
            }
        }
        else{
            if (s[ptr] == cur || s[ptr] == 'w')tmax++;
            else break;
        }
        ptr++;
        if (ptr - start >= n){
           
            break;
        }
    }
    return tmax;
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> s;
    s.append(s);
    int m = 0;
    for (int i = 0; i <= n; i++){
        int t = run(i, 'b', 'r');
        if (t>m)m = t;
        t = run(i, 'r', 'b');
        if (t > m)m = t;
    }
    cout << m;
}