分类目录归档：模拟

洛谷 机器翻译

发表评论

题号：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;
}

计蒜客 NOIP模拟赛（一） D1T1

发表评论

题库链接：https://nanti.jisuanke.com/t/16445
本程序80分：

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<iostream>
using namespace std;
int prefixsum[2005][2005];
int n,k;
int safe_prefix(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=n)return prefixsum[x][y];
    return 0;
}
int pong(int x,int y){
    int morse_cnt=0;
    bool flag=false;
    int cnt=0;
    for(int i=x-k+1;i<=x+k-1;i++){
        if(!flag&&cnt==k)flag=true;
        if(!flag)cnt++;
        else cnt--;
        if(i<1||i>n)continue;
        int jmin=y-cnt+1,jmax=y+cnt-1;
        morse_cnt+=safe_prefix(i,jmax)-safe_prefix(i,jmin-1);
    }
    return morse_cnt;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int t;
            cin>>t;
            prefixsum[i][j]=prefixsum[i][j-1]+t;
        }
    }
    int m=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int t=pong(i,j);
            if(t>m)m=t;
        }
    }
    cout<<m;
}

Openjudge Calling Extraterrestrial Intelligence Again 题解

发表评论

Calling Extraterrestrial Intelligence Again

总时间限制:
1000ms
内存限制:
65536kB
描述
A message from humans to extraterrestrial intelligence was sent through the Arecibo radio telescope in Puerto Rico on the afternoon of Saturday November 16, 1974. The message consisted of 1679 bits and was meant to be translated to a rectangular picture with 23 x 73 pixels. Since both 23 and 73 are prime numbers, 23 x 73 is the unique possible size of the translated rectangular picture each edge of which is longer than 1 pixel. Of course, there was no guarantee that the receivers would try to translate the message to a rectangular picture. Even if they would, they might put the pixels into the rectangle incorrectly. The senders of the Arecibo message were optimistic.

We are planning a similar project. Your task in the project is to find the most suitable width and height of the translated rectangular picture. The term “most suitable” is defined as follows. An integer m greater than 4 is given. A positive fraction a/b less than or equal to 1 is also given. The area of the picture should not be greater than m. Both of the width and the height of the translated picture should be prime numbers. The ratio of the width to the height should not be less than a/b nor greater than 1. You should maximize the area of the picture under these constraints.

In other words, you will receive an integer m and a fraction a/b. It holds that m > 4 and 0 < a/b <= 1. You should find the pair of prime numbers p, q such that pq <= m and a/b <= p/q <= 1, and furthermore, the product pq takes the maximum value among such pairs of two prime numbers. You should report p and q as the “most suitable” width and height of the translated picture.

输入
The input is a sequence of at most 2000 triplets of positive integers, delimited by a space character in between. Each line contains a single triplet. The sequence is followed by a triplet of zeros, 0 0 0, which indicates the end of the input and should not be treated as data to be processed.

The integers of each input triplet are the integer m, the numerator a, and the denominator b described above, in this order. You may assume 4 < m <= 100000 and 1 <= a <= b <= 1000.

输出
The output is a sequence of pairs of positive integers. The i-th output pair corresponds to the i-th input triplet. The integers of each output pair are the width p and the height q described above, in this order.

Each output line contains a single pair. A space character is put between the integers as a delimiter. No other characters should appear in the output.

样例输入
5 1 2
99999 999 999
1680 5 16
1970 1 1
2002 4 11
0 0 0
样例输出
2 2
313 313
23 73
43 43
37 53
来源
Japan 2002 Kanazawa

继续阅读 →