标签归档：Openjudge

Openjudge 2019计算机学科夏令营上机考试 Hopscotch

发表评论

http://bailian.openjudge.cn/xly2019/C/

本体无法提交测试。样例已通过，可能TLE。

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<iostream>
#include<cstdio>
#include<queue>
#include<string>
using namespace std;
struct queueData {
    int p;
    string s;
    queueData(int p,string s):p(p),s(s){}
};
void bfs(int src, int dst) {
    queue<queueData> q;
    q.push(queueData(src, ""));
    while (!q.empty()) {
        queueData cur = q.front();
        q.pop();
        if (cur.p == dst) {
            cout << cur.s.size() << "\n";
            cout << cur.s << "\n";
            return;
        }
        q.push(queueData(cur.p * 3, cur.s + "H"));
        q.push(queueData(cur.p / 2, cur.s + "O"));
    }
}
int main() {
    int n, m;
    while (cin >> n >> m) {
        if (n == 0 && m == 0)break;
        else bfs(n, m);
    }
}

Openjudge 打印月历

发表评论

http://noi.openjudge.cn/ch0113/24/

描述
给定年月，打印当月的月历表。

输入
输入为一行两个整数，第一个整数是年份year（1900 ≤ year ≤ 2099），第二个整数是月份month（1 ≤ month ≤ 12），中间用单个空格隔开。

输出
输出为月历表。月历表第一行为星期表头，如下所示：
Sun Mon Tue Wed Thu Fri Sat
其余各行一次是当月各天的日期，从1日开始到31日（30日或28日）。
日期数字应于星期表头右对齐，即各位数与星期表头相应缩写的最后一个字母对齐。日期中间用空格分隔出空白。

样例输入

1
2006 5

样例输出

1
2
3
4
5
6
Sun Mon Tue Wed Thu Fri Sat
      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

提示
闰年判断方法：能被4整除但不能被100整除，或者能被400整除。
1900年1月1日是周一。
继续阅读 →

Openjudge BJUTACM 2018 周末集训 1005:Largest Rectangle in a Histogram

发表评论

可以说是非常不好想也非常不好做的一道题了……大佬的提示是单调栈，自己随便想了想就开始写，结果就挂掉了，然后看题解，也没太大用，最后是单步调试让我差不多搞清楚了。Solve()函数里的每一行都博大精深，有很多用。我也实在讲不清楚，把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
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
long long solve(vector<long long> & heights) {
    long long remax = 0;
    stack<long long> spos;
    heights.push_back(0);
    for (int i = 0; i < heights.size(); i++) {
        while (!spos.empty() && heights[spos.top()] >= heights[i]) {
            int curpos = spos.top();
            spos.pop();
            remax = max(remax, heights[curpos] * (spos.empty() ? i : ((i - 1) - (spos.top() + 1) + 1))); //这里大部分题解写的是i-spos.top()-1，我搞明白之后把这里写成了易于理解的形式
        }
        spos.push(i);
    }
    return remax;
}
int main() {
    do {
        int n;
        scanf("%d", &n);
        if (n == 0)break;
        vector<long long> v;
        for (int i = 1; i <= n; i++) {
            long long x;
            scanf("%lld", &x);
            v.push_back(x);
        }
        printf("%lld", solve(v));
    } while (1);
}

此题为LeetCode原题：https://leetcode.com/problems/largest-rectangle-in-histogram/description/
该题BJUTACM地址：http://bjutacm.openjudge.cn/bjut2018/1005/
（数据范围有可能会不相同）
题解：
https://www.cnblogs.com/grandyang/p/4322653.html
https://blog.csdn.net/princexiexiaofeng/article/details/79652003
https://siddontang.gitbooks.io/leetcode-solution/content/array/largest_rectangle_in_histogram.html
https://tech.pic-collage.com/algorithm-largest-area-in-histogram-84cc70500f0c
我个人看题解是没看懂的，单步调试拯救了我。。如果看不懂就单步吧。。有的地方我没解释清楚，从网上搜搜题解就好。
强烈建议这道题单步跟，多跟几个样例，不单步你看不懂其中的逻辑。。
我按照雪花大佬做法写的，经我垃圾的改编加了一堆cruft：不要问我怎么回事我也搞不清楚

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
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
struct P {
    long long h, i;
};
long long solve(vector<long long> & heights) {
    long long remax = 0;
    stack<P> s;
    heights.push_back(0);
    for (int i = 0; i < heights.size(); i++) {
        long long l = i;
        while (!s.empty() && s.top().h > heights[i]){
            l = s.top().i;
            remax = max(remax, s.top().h * ( (i - 1) - s.top().i + 1));
            s.pop();
        }
        s.push(P{ heights[i],l });
    }
    return remax;
}
int main() {
    do {
        int n;
        scanf("%d", &n);
        if (n == 0)break;
        vector<long long> v;
        for (int i = 1; i <= n; i++) {
            long long x;
            scanf("%lld", &x);
            v.push_back(x);
        }
        printf("%lld\n", solve(v));
    } while (1);
}

雪花大佬的不cruft的代码

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
#include <iostream>
#include <algorithm>

using namespace std;

using ll = long long;

struct Candidate { // candidate rectangle. area = height * (end_pos - start_pos)
  ll h; // the height
  ll i; // the start position;
        // end position is implied
};

Candidate monostack[100100];
ll size = 0;

ll max_area = 0;

void monostack_push(ll h, ll i) {
  ll pos = i; // start pos

  while (size > 0 && monostack[size - 1].h >= h) { // equality is optional
    Candidate const & p = monostack[--size]; // pop

    pos = p.i; // update start pos

    max_area = max(max_area, p.h * (i - p.i));
  }

  monostack[size++] = {h, pos}; // push
}

int main() {
  // init
  size = 0;
  max_area = 0;

  // for each input
  //   monostack_push(height, pos);
  // monostack_push(0, last pos + 1); // another trick

  // output max_area
}

Openjudge BJUTACM 1036:括号画家

发表评论

智障的一开始竟然想用递归/记忆化做。。。老T。后来猛然醒悟是栈。。。

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
void E() {
    cout << "No";
    exit(0);
}
void S() {
    cout << "Yes";
    exit(0);
}
stack<char> s;
int main() {
    char c;
    while (cin >> c) {
        switch (c) {
        case '(':case '[':case '{':
            s.push(c);
            break;
        case ')':case ']':case '}':
            if (s.empty())E();
            switch (c) {
            case ')':
                if (s.top() == '(')s.pop();
                else E();
                break;
            case ']':
                if (s.top() == '[')s.pop();
                else E();
                break;
            case '}':
                if (s.top() == '{')s.pop();
                else E();
                break;
            }
        }
    }
    S();
}

http://bjutacm.openjudge.cn/lianxi/1036/

Openjudge BJUTACM 1018:简单计算器

发表评论
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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
int t;
stack<double> si;
stack<char> sc;
inline bool execute() {
    if (sc.empty()) return false;
    double x2 = si.top();
    si.pop();
    double x1 = si.top();
    si.pop();
    char symbol = sc.top();
    sc.pop();
    switch (symbol) {
    case '+':si.push(x1 + x2); break;
    case '-':si.push(x1 - x2); break;
    case '*':si.push(x1 * x2); break;
    case '/':si.push(x1 / x2); break;
    }
    return true;
}
int main() {
    scanf("%d", &t);
    do {
        char c = getc(stdin);
        if (c == -1)break;
        if (c == '\n') {
            while (execute());
            if (si.empty())continue;
            double v = si.top();
            while (!si.empty())si.pop();
            while (!sc.empty())sc.pop();
            printf("%.2lf\n", v);
            continue;
        }
        if (c <= '9' && c >= '0') {
            ungetc(c, stdin);
            double v;
            scanf("%lf", &v);
            if (sc.empty())si.push(v);
            else if (sc.top() == '-') {
                si.push(-v);
                sc.pop();
                sc.push('+');
            }
            else if (sc.top() == '/') {
                si.push(1.0 / v);
                sc.pop();
                sc.push('*');
            }
            else si.push(v);
        }
        else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (!sc.empty() && (c == '+' || c == '-') && (sc.top() == '*' || sc.top() == '/')) {
                execute();
            }
            sc.push(c);
        }
    } while (1);
}

http://bjutacm.openjudge.cn/lianxi/1018/

Openjudge BJUTACM 181A:素数和

发表评论
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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
int n, m;
bool isprime[10000005];
int prime[10000005];
vector<int> primeList;
inline void genPrime() {
    memset(isprime, true, sizeof(isprime));
    isprime[0] = isprime[1] = false;
    for (int i = 2; i <= 10000000; i++) {
        if (!isprime[i])continue;
        primeList.push_back(i);
        for (int j = 2 * i; j <= 10000000; j += i) {
            isprime[j] = false;
        }
    }
}
inline void putIn(int v) {
    for (int i = 0; i < primeList.size() && v >= primeList[i] && v != 1; i++) {
        if (v%primeList[i] == 0) {
            prime[primeList[i]]++;
            while (v%primeList[i] == 0)v /= primeList[i];
        }
        if (isprime[v]) {
            prime[v]++;
            break;
        }
    }
}
int main() {
    genPrime();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int v;
        scanf("%d", &v);
        putIn(v);
    }
    for (int i = 1; i <= 10000000; i++) {
        prime[i] += prime[i - 1];
    }
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        if (r > 10000000)r = 10000000;
        if (l > 10000000)l = 10000000;
        printf("%d\n", prime[r] - prime[l - 1]);
    }
}

http://bjutacm.openjudge.cn/lianxi/181A/

Openjudge 画家问题

发表评论

画家问题

总时间限制:
1000ms
内存限制:
65536kB
描述
有一个正方形的墙，由N*N个正方形的砖组成，其中一些砖是白色的，另外一些砖是黄色的。Bob是个画家，想把全部的砖都涂成黄色。但他的画笔不好使。当他用画笔涂画第(i, j)个位置的砖时， 位置(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)上的砖都会改变颜色。请你帮助Bob计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。

输入
第一行是一个整数n (1≤n ≤15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。
输出
一行，如果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”。
样例输入
5
wwwww
wwwww
wwwww
wwwww
wwwww
样例输出
15
来源
1681

继续阅读 →

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

继续阅读 →

Openjudge Sudoku 题解

发表评论

2982:Sudoku

总时间限制:
2000ms
内存限制:
65536kB
描述
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3×3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3×3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.
输入
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
输出
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.
样例输入
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
样例输出
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
来源
Southeastern Europe 2005

继续阅读 →