算法小计B1

发表于 | 分类于
字数统计: 9,468 | 阅读时长 ≈ 52

每天坚持做算法题，熟悉基本的套路，巩固语言基础，总结经验记下所学所想。

2018-3-20

P60近似计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <math.h>

int main()
{

    int i = 0;

    double sum = 0;
    double term;
    do{
        term = 1.0/(2*i+1);//注意写成1.0而不是1
        sum+=pow(-1,i)*term;
        ++i;
    }while(term>=pow(10, -6));

    cout<<sum;
    return 0;
}

P62阶乘之和

要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数，可以在
每步计算之后对n取余，结果不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
#include<time.h>
int main()
{
    const int MOD = 1000000;
    int n, S = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int factorial = 1;
            for(int j = 1; j <= i; j++)
                factorial = (factorial * j % MOD);
            S = (S + factorial) % MOD;
    }
    printf("%d\n", S);
    printf("Time used = %.2f\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

P94键盘输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
string s = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
// 这里s为47个char，s[47] = null
int main() {
    int i, c;
    while((c = getchar())!=EOF){

        for (i = 1;  s[i]&&s[i]!=c ; ++i);

        if (s[i])//如果找不到 s[47] = null
            putchar(s[i-1]);
        else
            putchar(c);

    }
    return 0;
}

2018-3-21

P140刽子手

关键在于设立win和lose以及bad的标志位，没猜一个更新标志位

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<stdio.h>
#include<string.h>
#define maxn 100
int left, chance; //还需要猜left个位置,错chance次之后就会输
char s[maxn], s2[maxn]; //答案是字符串s,玩家猜的字母序列是s2
int win, lose; //win=1表示已经赢了;lose=1表示已经输了
void guess(char ch) ;
int main() {
    int rnd;
    while(scanf("%d%s%s", &rnd, s, s2) == 3 && rnd != -1) {
        printf("Round %d\n", rnd);
        win = lose = 0; //求解一组新数据之前要初始化
        left = strlen(s);
        chance =7;
        for(int i = 0; i < strlen(s2); i++) {
            guess(s2[i]); //猜一个字母
            if(win || lose) break; //检查状态
        }
        //根据结果进行输出
        if(win) printf("You win.\n");
        else if(lose) printf("You lose.\n");
        else printf("You chickened out.\n");
    }
    return 0;
}
void guess(char ch) {
    int bad = 1;
    for(int i = 0; i < strlen(s); i++)
        if(s[i] == ch) { left--; s[i] = ' '; bad = 0; }
    if(bad) --chance;
    if(!chance) lose = 1;
    if(!left) win = 1;
}

P145信息编码

使用char code[n][1<<n]存放编码本，n。前面的n表示二进制长度，后面的表示该二进制数的十进制表示

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
#include<stdio.h>
#include<string.h> //使用memset

int readchar() ;

int readint(int c) ;

int code[8][1<<8];
int readcodes() ;
int main() {
    while(readcodes()) { //无法读取更多编码头时退出
//printcodes();
        for(;;) {
            int len = readint(3);
            if(len == 0) break;
//printf("len=%d\n", len);
            for(;;) {
                int v = readint(len);
//printf("printf("v=%d\n", v);
                if(v == (1 << len)-1) break;
                putchar(code[len][v]);
            }
        }
        putchar('\n');
    }
    return 0;
}

int readchar() {
    for(;;) {
        int ch = getchar();
        if(ch != '\n' && ch != '\r') return ch; //一直读到非换行符为止
    }
}
int readint(int c) {
    int v = 0;
    while(c--) v = v * 2 + readchar() - '0';
    return v;
}

// 生成编码本
int readcodes() {
    memset(code, 0, sizeof(code)); //清空数组
    code[1][0] = readchar(); //直接调到下一行开始读取。如果输入已经结束，会读到EOF
    for(int len = 2; len <= 7; len++) {
        for(int i = 0; i < (1<<len)-1; i++) {
            int ch = getchar();
            if(ch == EOF) return 0;
            if(ch == '\n' || ch == '\r') return 1;
            code[len][i] = ch;
        }
    }
    return 1;
}

2018-3-24

北邮OJ-11网研第三题-中序遍历树

题目描述

给一棵树，你可以把其中任意一个节点作为根节点。每个节点都有一个小写字母，中序遍历，得到一个字符串，求所有能得到的字符串的字典序最小串。因为这棵树不一定是二叉树，所以中序遍历时，先中序遍历以节点序号最小的节点为根的子树，然后再遍历根节点，最后根据节点序号从小到大依次中序遍历剩下的子树。

HINT

意思就是请枚举所有的点为根，然后中序遍历
最后输出所有结果中字典序最小的
比如说第二组数据
以0为根时结果为 bacd
以1为根时结果为 cadb

以2为根时结果为 badc
以3为根时结果为 bacd
所以字典序最小的是bacd

输入格式

多组数据，以EOF结束。

第一行一个数n（0< n < =100）,表示树的节点的个数，节点从0开始。

然后一个长度为n的串，第i（0< = i < n）个字符表示节点i的字符。
接下来n-1行，每行两个数a，b,(0< = a,b < n),表示a和b之间有一条无向边。

输出格式

题中要求的最小的字符串

输入样例

3

bac

0 1

1 2

4

abcd

0 1

0 2

0 3

输出样例

bac

bacd

代码

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
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
char func[101];
bool relation[100][100]={false};
bool visited[100]={false};
string result;
string temp;

void dfs(int pos,int n)
{

    int son[100];
    int size=0;
    visited[pos]=true;
    for(int j=0;j<n;j++)
    {
//        if(j==pos)continue;
        if(relation[pos][j]==true&&!visited[j])
        {

            son[size++]=j;

        }
    }
    if(size>0)
    {

        dfs(son[0],n);
        temp+=func[pos];
        for(int j=1;j<size;j++)
        {

            dfs(son[j],n);

        }

    }
    else if(size==0)temp+=func[pos];
}
int main()
{

    int n,a,b,t;
    while(cin>>n)
    {
        result="";
        temp="";
        cin>>func;
        t=n;
        t--;
        memset(relation,0,sizeof(relation));
        //cout<<relation[99][99];
        while(t--)
        {
            cin>>a>>b;
            relation[a][b]=true;
            relation[b][a]=true;

        }
        int it=-1;
        for(int i=0;i<n;i++)
        {
            memset(visited,0,sizeof(visited));
            dfs(i,n);
            // cout<<"以"<<i<<"("<<func[i]<<")"<<"为根"<<temp<<endl;
            if(i==0){
                result=temp;it=i;}
            else if(result>temp){
                result=temp;it=i;}
            temp="";
        }
        cout<<result<<endl;
    }



}

2018-3-25

P186反片语

HINT

这里的map用于统计字符串的数量，如果出现两次则不输出。注意此时的key应该是标准化的。

代码

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
#include <iostream>
#include <string>
#include <cctype>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
string lowerstr(const string& s)
{
    string ss = s;
    for (auto it = ss.begin(); it != ss.end() ; ++it) {
        *it = tolower(*it);
    }
    sort(ss.begin(), ss.end());// 核心
    return ss;
}
int main(){

    vector<string> strvec;
    map<string, int> strmap;
    string str;

    while(cin>>str){

        if (str[0] == '#') break;
        strvec.push_back(str);
        string strlower = lowerstr(str);
        if (!strmap.count(strlower)) strmap[strlower] = 0;
        ++strmap[strlower];

    }

    vector<string> vec;

    for (auto it = strvec.begin(); it != strvec.end() ; ++it) {
        if (strmap[lowerstr(*it)] == 1) vec.push_back(*it);
    }

    sort(vec.begin(), vec.end());

    for (int i = 0; i < vec.size(); ++i) {
        cout<<vec[i]<<endl;
    }
}

p189集合栈

HINT

使用vector存放集合，并把其和其在vector中的下标映射成map（因为ID是唯一的，避免每次查找vector使用map），stack中只需要存ID

代码

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
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())

typedef set<int> Set;

vector<Set> vec;
map<Set, int> smap;

int ID(Set s){
    if (smap.count(s)) return smap[s];

    vec.push_back(s);

    return smap[s] = vec.size() - 1;
}

int main(){

    string cmd;

    stack<int> st;

    int n;
    cin>>n;

    while(n--){

        cin>>cmd;
        Set x = Set();
        int s1,s2;
        switch (cmd[0]) {
            case 'P':
                st.push(ID(Set()));
                break;
            case 'D':
                st.push(st.top());
                break;
            case 'U':
                s1 = st.top();
                st.pop();
                s2 = st.top();
                st.pop();
                set_union(ALL(vec[s1]), ALL(vec[s2]), INS(x));
                st.push(ID(x));
                break;
            case 'I':
                s1 = st.top();
                st.pop();
                s2 = st.top();
                st.pop();
                set_intersection(ALL(vec[s1]), ALL(vec[s2]), INS(x));
                st.push(ID(x));
                break;
            case 'A':
                s1 = st.top();
                st.pop();
                s2 = st.top();
                st.pop();
                x = vec[s2];
                x.insert(ID(vec[s1]));
                st.push(ID(x));
                break;
            default:
                cout<<"error!";
                break;

        }
        cout<<vec[st.top()].size()<<endl;

    }
}

P195 丑数

HINT

priority_queue, greater>优先级队列，数小的排前面

代码

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
const int coef[3] = {2,3,5};// x为丑数，他的2，3，5倍均为丑数
typedef long long LL;
int main(){
    set<int> s;
    priority_queue<LL, vector<LL>, greater<LL>> prioque;

    s.insert(1);
    prioque.push(1);

    for (int i = 1; ; ++i) {

        LL x = prioque.top();prioque.pop();


        if (i == 1500) {
            cout << "The 1500'th ugly number is " << x << ".\n";
            break;
        }

        for (int j = 0; j < 3; ++j) {//关键

            if (!s.count(x*coef[j])) {
                s.insert(x*coef[j]);
                prioque.push(x*coef[j]);
            }
        }

    }

    return 0;
}

2018-3-26

P205 UNIX命令

HINT

总数是定长的，每个是不定长的字符串，所以采用string a[max]的数据结构

代码

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
const int MAX = 100;
const int maxcol = 16;

void println(string s, int i, char j){
    cout<<s;
    while (i--){
        cout<<j;
    }
}

int main()
{
    // input number
    int n;
    cin>>n;

    // init space and M
    string a[MAX];
    string b;
    int M = 0;

    // input single string, get M
    for(int i = 0; i < n; ++i)
    {
        cin>>b;
        a[i] = b;
        if (b.length() > M){
            M = b.length();
        }
    }

    sort(a, a+n);

    // get cols and rows
    int cols = (maxcol - M) / (M + 2) + 1, rows = (n - 1) / cols + 1;

    println("", maxcol, '-');

    cout<<endl;

    // output key : i*rows + j
    for (int j = 0; j < rows; ++j) {
        for (int i = 0; i < cols; ++i) {
            if ((i*rows + j) < n)
            println(a[i*rows + j], (((i == cols -1)?M:M+2)-a[i*rows + j].length()), ' ');
        }
        cout<<endl;
    }
}

P212 城市正视图

HINT

离散化，不能遍历所有x坐标，只遍历建筑物可能出现区间内的一点即可

代码

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
const int maxn = 100 + 5;

struct Building{

    int id;
    double x, y, w, d, h;

    bool operator > (const Building&rhs) const{
        return (x<rhs.x)||(x == rhs.x && y < rhs.y);
    }
} b[maxn];

int n;
double x[maxn*2];

// 建筑物i是否包含x轴坐标j
bool cover(int i, double j){
    return b[i].x <= j && (b[i].x + b[i].w) >= j;
}

// 建筑物i是否在x坐标j可视
bool visable(int i, double j){
    if (!cover(i, j)) return false;

    for(int k = 0; k < n; k++)
        if(b[k].y < b[i].y && b[k].h >= b[i].h && cover(k, j)) return false;
    return true;
}

int main(){

    // input number
    int n;
    cin>>n;

    // input buildings
    for (int i = 0; i < n; ++i) {
        cin >> b[i].x >> b[i].y >> b[i].w >> b[i].d >> b[i].h;
        x[2*i] = b[i].x;
        x[2*i+1] = b[i].x + b[i].w;
        b[i].id = i+1;
    }

    // sort buildings and coordinate
    sort(b, b+n);
    sort(x, x+2*n);

    // coordinate num
    int m = unique(x, x+2*n) - x;//unique去重，属于algorithm包

    // key:cout visable buildings' id
    for (int j = 0; j < n; ++j) {
        bool vis = false;

        // judge if visable between all the coordinate
        for (int i = 0; i < m-1; ++i) {
            if (visable(j, (x[i] + x[i+1])/2))
            {
                vis = true;
                break;
            }
        }
        if (vis) cout<<b[j].id<<" ";
    }

}

建筑物正视图拓展

题目

假设平面内有n个矩形，并输入n个矩形的左下角和右上角的坐标，求矩形重叠的最大次数。

HINT

离散化，离散化出所有x和y坐标构成的点，在所有的点处作判断

代码

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
//
// Created by 程潇 on 2018/3/28.
//

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(){

    // input n
    int n;
    while(cin>>n) {

        // input space
        vector<vector<double>> pos(4, vector<double>(n));

        vector<double> uniqx;
        vector<double> uniqy;

        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < n; ++j) {
                cin >> pos[i][j];

                if (i == 0 || i == 2) uniqx.push_back(pos[i][j]);
                else uniqy.push_back(pos[i][j]);
            }
        }

        // init count
        int count[100][100] = {0};

        // sort and unique
        sort(uniqx.begin(), uniqx.end());
        uniqx.erase(unique(uniqx.begin(), uniqx.end()), uniqx.end());

        sort(uniqy.begin(), uniqy.end());
        uniqx.erase(unique(uniqy.begin(), uniqx.end()), uniqx.end());

        // key:update count
        for (int k = 0; k < n; ++k) {
            int x1 = lower_bound(uniqx.begin(), uniqx.end(), pos[0][k]) - uniqx.begin();
            int x2 = lower_bound(uniqx.begin(), uniqx.end(), pos[2][k]) - uniqx.begin();
            int y1 = lower_bound(uniqy.begin(), uniqy.end(), pos[1][k]) - uniqy.begin();
            int y2 = lower_bound(uniqy.begin(), uniqy.end(), pos[3][k]) - uniqy.begin();

            for (int x = x1; x < x2; ++x) {
                for (int y = y1; y < y2; ++y) {
                    ++count[x][y];
                }
            }
        }

        //update maxn
        int maxn = 0;
        for (int i = 0; i < 100; ++i) {
            for (int j = 0; j < 100; ++j) {
                if (count[i][j] > maxn) maxn = count[i][j];
            }
        }

        cout << maxn << endl;
    }

    return 0;

}

2018-3-27

P225铁轨

HINT

使用栈存储中间，明确每次操作的流程

代码

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
const int MAXN = 1000 + 10;

int main(){

    // init space
    int target[MAXN];


    // input num
    int n;

    while(cin>>n) {

        if (n == 0) return 0;

        // init space
        stack<int> st;
        int count1 = 1, count2 = 1;
        int flag = 0;

        // input target
        for (int i = 1; i <= n; ++i) {
            cin >> target[i];
        }

        // key update flag
        while (count2 != n + 1) {
            if (target[count2] == count1) {
                // 不入栈直接入队
                ++count1;
                ++count2;
            } else if (!st.empty() && st.top() == target[count2]) {
                // 出栈入队
                ++count2;
                st.pop();
            } else if (count1 <= n) {
                // 进栈
                st.push(count1);
                ++count1;
            } else {
                // 失配
                flag = 1;
                break;
            }
        }

        if (flag)cout << "False";
        else
            cout << "True";
    }
    return 0;
}

P226矩阵乘法

HINT

读到右括号出栈两个字母并做一次判断

代码

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
struct Matrix {
    int a, b;
    Matrix(int a=0, int b=0):a(a),b(b) {}
} m[26];

stack<Matrix> st;

int main(){

    // input n
    int n;
    cin>>n;

    // input Matrix
    for (int i = 0; i < n; ++i) {
        string name;
        cin>>name;

        int k = name[0] - 'A';

        cin>>m[k].a>>m[k].b;
    }

    string line;

    while(cin>>line){
        int len = line.length();

        bool error = false;
        int ans = 0;

        // key
        for (int i = 0; i < len; ++i) {
            if (isalpha(line[i]))
                // 字母入栈
                st.push(m[line[i]-'A']);
            else if (line[i] == ')'){
                // 做运算
                Matrix m1 = st.top();st.pop();
                Matrix m2 = st.top();st.pop();

                if (m1.b != m2.a) {
                    error = true;
                    break;
                }

                ans += m1.a * m1.b * m2.b;
                st.push(Matrix(m1.a, m2.b));
            }
        }
        if (error) cout<<"error"<<endl;
        else
            cout<<ans<<endl;
    }
    return 0;

}

P229 破损键盘

代码

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
int main(){

    string str;
    while(getline(cin, str)){

        if (str == "EOF") break;

        list<char> flist;

        list<char>::iterator it = flist.begin();

        for (int i = 0; i < str.length(); ++i) {
            if (str[i] == '[') {
                it = flist.begin();
                continue;
            }
            if (str[i] == ']') {
                it = flist.end();
                continue;
            }
            flist.insert(it, str[i]);// insert 会将str[i]插到it之前，返回插入部分的前迭代器
        }

        for (it = flist.begin();  it != flist.end() ; ++it) {
            cout<<*it;
        }

    }

}

2018-3-28

P231 移动盒子

HINT

list的学习与使用

代码

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
int main(){

    list<int> li;
    int n, m;
    cin>>n>>m;

    for (int i = 0; i < n; ++i) {
        li.push_back(i);
    }
    for (auto i = li.begin(); i != li.end() ; ++i) {
        cout<<*i<<" ";
    }
    cout<<endl;

    while(m--){
        int ap;
        cin>>ap;

        if (ap == 4)
        {
            li.reverse();
        }
        else
        {
            int bp, cp;
            cin>>bp>>cp;

            if (ap == 1){
                // bp move to the left of cp

                // get bp
                auto bpit = li.begin();
                bp--;
                while(bp--){
                    ++bpit;
                }

                // get cp
                auto cpit = li.begin();
                cp--;
                while (cp--){
                    ++cpit;
                }

                li.insert(cpit, *bpit);

                li.erase(bpit);

            } else if (ap == 2){
                // bp move to the right of cp

                // get bp
                auto bpit = li.begin();
                bp--;
                while(bp--){
                    ++bpit;
                }

                // get cp
                auto cpit = li.begin();
                cp--;
                while (cp--){
                    ++cpit;
                }
                ++cpit;

                li.insert(cpit, *bpit);

                li.erase(bpit);



            } else{
                // swap bp and cp

                // get bp
                auto bpit = li.begin();
                bp--;
                while(bp--){
                    ++bpit;
                }

                // get cp
                auto cpit = li.begin();
                cp--;
                while (cp--){
                    ++cpit;
                }

                li.insert(bpit, *cpit);
                li.insert(cpit, *bpit);

                li.erase(bpit);
                li.erase(cpit);

            }

        }
        for (auto i = li.begin(); i != li.end() ; ++i) {
            cout<<*i<<" ";
        }
        cout<<endl;
    }


    return 0;
}

P236 小球下落

HINT

序号为k的小球左节点为2k+1,右节点为2k+2。如果树的节点之间建立了连接，则保存树节点的数组可以是无序的，一般的，都会遵从最开始的这个规则，即2k+1。。。这样的话，数 组保存的元素就是节点的数据，如此题使用bool amaxn).

代码

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
const int maxn = 20;

int main(){

    int D, I;

    while(cin>>D>>I){
        if (D == 0) break;

        int n = (1<<D) - 1;

        vector<bool> tre(n, false);
        int k = 0;
        for (int i = 0; i < I; ++i) {
            k = 0;

            while( k<=n-1 ){
                tre[k] = !tre[k];
                k = tre[k]?(2*k+1):(2*k+2);
            }
        }

        cout<<(k-1)/2<<endl;

    }

    return 0;
}

2018-3-29

P249 天平

HINT

递归输入

代码

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
bool solve(int& W){
    int W1, D1, W2, D2;
    bool b1 = true, b2 = true;
    cin>>W1>>D1>>W2>>D2;

    if (!W1) b1 = solve(W1);
    if (!W2) b2 = solve(W2);

    W = W1 + W2;

    return b1&&b2&&(W1*D1 == W2*D2);
}


int main()
{
    int T, W;

    cin>>T;

    while(T--){
        if (solve(W)) cout<<"yes\n"; else cout<<"no\n";
        if (T) cout<<endl;
    }
    return 0;
}

// 非递归输入版本
bool solve(int& W, int& i, vector<vector<int>>& vec, int n){


    int W1, D1, W2, D2;
    W1 = vec[i][0];D1 = vec[i][1];W2 = vec[i][2];D2 = vec[i][3];

    bool b1 = true, b2 = true;


    if (!W1) {
        ++i;
        b1 = solve(W1, i, vec, n);
    }
    if (!W2) {
        ++i;
        b2 = solve(W2, i, vec, n);
    }

    W = W1 + W2;

    return b1&&b2&&(W1*D1 == W2*D2);
}


int main()
{
    int T, W;

    int n;
    cin>>T>>n;

    vector<vector<int>> opr(n, vector<int>(4));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 4; ++j) {
            cin>>opr[i][j];
        }
    }

    while(T--){
        int i = 0;
        if (solve(W, i, opr, n)) cout<<"yes\n"; else cout<<"no\n";
        if (T) cout<<endl;
    }
    return 0;
}

2018-3-30

P251 下落的树叶

HINT

递归输入

代码

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
//输入并统计一棵子树，树根水平位置为p
void build(int p)
{
    int v; cin >> v;
    if(v == -1)
        return;
    sum[p] += v;
    build(p - 1);
    build(p + 1);
    // 如果是中序输入，则
    // build(p - 1);
    // int v; cin >> v;
    // if(v == -1)
    // return;
    // build(p+1);

}

//边读入边统计
bool init()
{
    int v; cin >> v;
    if(v == -1) return false;
    memset(sum, 0, sizeof(sum));
    int pos = maxn/2;
    sum[pos] = v;
    build(pos - 1);
    build(pos + 1);
}

int main( ) {
    int kase = 0;
    while(init( )) {
        int p = 0;
        while(sum[p] == 0) p++;
        cout << "Case " << ++kase << ":\n" << sum[p++];//因为要避免行末多余空格 while(sum[p] != 0) cout << " " << sum[p++];
        cout << "\n\n";
        }
    return 0;
}

2018-04-01

P253四分树

HINT

首先建树，然后为每一个可能的位置设置map二维矩阵，转化为染色问题

代码

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<cstdio>
#include<cstring>
const int len = 32;
const int maxn = 1024 + 10;
char s[maxn];
int buf[len][len], cnt;
//把字符串s[p..]导出到以(r,c)为左上角，边长为w的缓冲区中
//2 1
//3 4
void draw(const char* s, int& p, int r, int c, int w)
{
    char ch = s[p++];
    if(ch == 'p') {
        draw(s, p, r, c+w/2, w/2);  //1
        draw(s, p, r, c, w/2);      //2
        draw(s, p, r+w/2, c, w/2);  //3
        draw(s, p, r+w/2, c+w/2, w/2);//4
        }else if(ch == 'f'){//画黑像素（白像素不画
            for(int i = r; i < r+w; i++)
                for(int j = c; j < c+w; j++)
                    if(buf[i][j] == 0) { buf[i][j] = 1; cnt++; }
        }
}

int main( )
{
    int T;
    scanf("%d", &T);
    while(T--) {
        memset(buf, 0, sizeof(buf));
        cnt = 0;
        for(int i = 0; i < 2; i++)
        {
            scanf("%s", s);
            int p = 0;
            draw(s, p, 0, 0, len);
        }
        printf("There are %d black pixels.\n", cnt);
    }
    return 0;
}

2018-04-02

P268 看图写树

HINT

不用建树，采用DFS输出

代码

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
#include <cstdio>
#include <cctype>
#include <cstring>


using namespace std;

const int maxn = 200 + 10;
int n;
char buf[maxn][maxn];

void dfs(int r, int c){
    printf("%c(", buf[r][c]);

    if(r+1 < n && buf[r+1][c] == '|') { //有子树
        int i = c;
        while(i-1>=0 && buf[r+2][i-1] == '-') --i;
        while(buf[r+2][i] == '-' && buf[r+3][i] != '\0') {
            if(!isspace(buf[r+3][i])) dfs(r+3, i); //fgets读入的"\n"也满足isspace( )
            ++i;
        }
    }
    printf(")");
}

void solve( ) {
    n = 0;
    for(;;) {
        fgets(buf[n], maxn, stdin);
        if(buf[n][0] == '#') break;
        else n++;
    }
    printf("(");
    if(n) {
        for(int i = 0; i < strlen(buf[0]); i++)
            if(buf[0][i] != ' ') {
                dfs(0, i);
                break;
            }
    }
    printf(")\n");
}

int main( ) {
    int T;
    fgets(buf[0], maxn, stdin);
    sscanf(buf[0], "%d", &T);
    while (T--) solve();
    return 0;
}

2018-04-03

P270 雕塑

给出一些边平行于坐标轴的长方体，这些长方体可能相交，也可能相互嵌套，这些长方体形成了一个雕塑，求这个雕塑的总体积和表面积。(本题用到离散化，是5.2 5.3的拓展)

HINT

最容易想到直接进行bfs或者dfs统计，但此题的麻烦之处在于求整个雕塑的外表面积和雕塑内部可能出现四个长方体所搭成的空心，空心不能计算到表面积中，但是计算总体积却要计入，于是直接bfs或者dfs不好处理，于是，可以想到直接统计整个雕塑外围的所有小方块，即可很方便地求出雕塑地表面积和体积(雕塑地总体积＝＝整个空间地体积－外围想方块的体积），还有一点就是由于坐标范围达到1-1000， 整个空间的大小达到了100010001000 ＝ 1e9, 直接bfs明显会超时，由于长方体的个数最大只有50个，于是可以对原坐标进行离散化，把每一维的坐标离散化后，整个空间的大小缩小到了100＊100＊100 ＝ 1e6，于是这个问题就解决了。（详细参考代码，注释地很详细）。

代码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
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
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 50 + 5;
const int maxc = 1000 + 1;

int n;
int x0[maxn], y0[maxn], z0[maxn], x1[maxn], y1[maxn], z1[maxn];
int xs[maxn*2], ys[maxn*2], zs[maxn*2], nx, ny, nz;
int color[maxn*2][maxn*2][maxn*2];
int dx[] = {0, 0, 0, 0, -1, 1};
int dy[] = {0, 0, -1, 1, 0, 0};
int dz[] = {-1, 1, 0, 0, 0, 0};

struct Cell
{
    int x, y, z;
    Cell(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {}
    void setVis() const {
        color[x][y][z] = 2;
    }
    int volume() const {
        return (xs[x+1]-xs[x])*(ys[y+1]-ys[y])*(zs[z+1]-zs[z]);
    }
    Cell neighbor(int i) const {
        return Cell(x+dx[i], y+dy[i], z+dz[i]);
    }
    bool valid() const {
        return x>=0 && x<nx-1 && y>=0 && y<ny-1 && z>=0 && z<nz-1;
    }
    bool solid() const {
        return color[x][y][z] == 1;
    }
    int area(int i) const {
        if (dx[i] != 0) return (ys[y+1]-ys[y])*(zs[z+1]-zs[z]);
        else if(dy[i] != 0) return (xs[x+1]-xs[x])*(zs[z+1]-zs[z]);
        else return (xs[x+1]-xs[x])*(ys[y+1]-ys[y]);
    }
    bool getVis() const {
        return color[x][y][z] == 2;
    }
};

void discretize(int* x, int& n)     //对每一维进行离散化
{
    sort(x, x + n);
    n = (int)(unique(x, x+n) - x);
}
int ID(int* x, int n, int x0)   //找到原坐标离散化后的新坐标
{
    return (int)(lower_bound(x, x+n, x0) - x);
}
void floodfill(int& s, int& v)  //bfs 统计
{
    s = v = 0;
    Cell c; c.setVis();
    queue<Cell> Q; Q.push(c);

    while (!Q.empty())
    {
        Cell now = Q.front(); Q.pop();
        v += now.volume();      //统计雕塑外围的总体积
        for (int i = 0; i < 6; i++)
        {
            Cell nxt = now.neighbor(i);
            if (!nxt.valid()) continue;     //越界
            if (nxt.solid()) s += now.area(i);      //统计雕塑外围表面积
            else if(!nxt.getVis())
            {
                nxt.setVis();
                Q.push(nxt);
            }
        }
    }
    v = maxc*maxc*maxc - v;     //雕塑体积 ＝＝ 整个空间的体积－雕塑外围体积
}
int main()
{
//    freopen("/Users/apple/Desktop/in.txt", "r", stdin);

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

    while (t--)
    {
        scanf("%d", &n);
        nx = ny = nz = 2;
        xs[0] = ys[0] = zs[0] = 0;
        xs[1] = ys[1] = zs[1] = maxc;   //存入边界坐标
        for (int i = 0; i < n; i++)
        {
            scanf("%d%d%d", &x0[i], &y0[i], &z0[i]);
            scanf("%d%d%d", &x1[i], &y1[i], &z1[i]);
            x1[i] += x0[i], y1[i] += y0[i], z1[i] += z0[i];
            xs[nx++] = x0[i], xs[nx++] = x1[i];
            ys[ny++] = y0[i], ys[ny++] = y1[i];
            zs[nz++] = z0[i], zs[nz++] = z1[i];
        }
        discretize(xs, nx), discretize(ys, ny), discretize(zs, nz);
        memset(color, 0, sizeof(color));    //染色
        for (int i = 0; i < n; i++)
        {
            int X1 = ID(xs, nx, x0[i]), X2 = ID(xs, nx, x1[i]);
            int Y1 = ID(ys, ny, y0[i]), Y2 = ID(ys, ny, y1[i]);
            int Z1 = ID(zs, nz, z0[i]), Z2 = ID(zs, nz, z1[i]);
            for (int X = X1; X < X2; X++)       //对离散化后的坐标依次染色
            {
                for (int Y = Y1; Y < Y2; Y++)
                {
                    for (int Z = Z1; Z < Z2; Z++)
                    {
                        color[X][Y][Z] = 1;
                    }
                }
            }
        }
        int s, v;
        floodfill(s, v);
        printf("%d %d\n", s, v);
    }


    return 0;
}

代码2

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
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 50 + 5;
const long maxc = 1000 + 1;

int n;
vector<vector<long>> pos(6, vector<long>(maxn));
vector<long> uniqx, uniqy, uniqz;
int color[maxn*2][maxn*2][maxn*2];
int dx[] = {0, 0, 0, 0, -1, 1};
int dy[] = {0, 0, -1, 1, 0, 0};
int dz[] = {-1, 1, 0, 0, 0, 0};

struct Cell
{
    int x, y, z;// 序号
    Cell(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {}

    // color为2标记为立方体外围
    void setVis() const {
        color[x][y][z] = 2;
    }

    // 计算体积
    int volume() const {
        return (uniqx[x+1]-uniqx[x])*(uniqy[y+1]-uniqy[y])*(uniqz[z+1]-uniqz[z]);
    }

    // 下一步
    Cell neighbor(int i) const {
        return Cell(x+dx[i], y+dy[i], z+dz[i]);
    }

    // 是否越界
    bool valid() const {
        return x>=0 && x<uniqx.size()-1 && y>=0 && y<uniqx.size()-1 && z>=0 && z<uniqx.size()-1;
    }

    // 是否为立方体内部
    bool solid() const {
        return color[x][y][z] == 1;
    }

    // 计算表面积
    int area(int i) const {
        if (dx[i] != 0) return (uniqy[y+1]-uniqy[y])*(uniqz[z+1]-uniqz[z]);
        else if(dy[i] != 0) return (uniqx[x+1]-uniqx[x])*(uniqz[z+1]-uniqz[z]);
        else return (uniqx[x+1]-uniqx[x])*(uniqy[y+1]-uniqy[y]);
    }

    // 是否为外部
    bool getVis() const {
        return color[x][y][z] == 2;
    }
};

// 对每一维进行离散化
void discretize(vector<long>& vec)
{
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
}

// 找到原坐标离散化后的新坐标
int ID(vector<long> vec, int x0)
{
    return (int)(lower_bound(vec.begin(), vec.end(), x0) - vec.begin());
}

//bfs 统计
void floodfill(int& s, int& v)
{
    s = v = 0;
    Cell c; c.setVis();
    queue<Cell> Q; Q.push(c);

    while (!Q.empty())
    {
        Cell now = Q.front(); Q.pop();
        v += now.volume();      //统计雕塑外围的总体积
        for (int i = 0; i < 6; i++)
        {
            Cell nxt = now.neighbor(i);
            if (!nxt.valid()) continue;     //越界
            if (nxt.solid()) s += now.area(i);      //now肯定是外围，nxt为内部则统计雕塑外围表面积
            else if(!nxt.getVis())
            {
                nxt.setVis();
                Q.push(nxt);
            }
        }
    }
    v = maxc*maxc*maxc - v;     //雕塑体积 ＝＝ 整个空间的体积－雕塑外围体积
}

int main()
{
//    freopen("/Users/apple/Desktop/in.txt", "r", stdin);

    int t;
    cin>>t;

    while (t--)
    {
        cin>>n;
        //存入边界坐标
        uniqx.push_back(0);uniqx.push_back(maxc);
        uniqy.push_back(0);uniqy.push_back(maxc);
        uniqz.push_back(0);uniqz.push_back(maxc);

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < 6; ++j) {
                for (int k = 0; k < n; ++k) {
                    cin>>pos[j][k];
                    if ((j == 0)||(j == 3)) uniqx.push_back(pos[j][k]);
                    if ((j == 1)||(j == 4)) uniqy.push_back(pos[j][k]);
                    if ((j == 2)||(j == 5)) uniqz.push_back(pos[j][k]);
                }
            }
        }

        discretize(uniqx), discretize(uniqy), discretize(uniqz);

        memset(color, 0, sizeof(color));    //染色
        for (int i = 0; i < n; i++)
        {
            int X1 = ID(uniqx, pos[0][i]), X2 = ID(uniqx, pos[3][i]);
            int Y1 = ID(uniqy, pos[1][i]), Y2 = ID(uniqy, pos[4][i]);
            int Z1 = ID(uniqz, pos[2][i]), Z2 = ID(uniqz, pos[5][i]);
            for (int X = X1; X < X2; X++)       //对离散化后的坐标依次染色
            {
                for (int Y = Y1; Y < Y2; Y++)
                {
                    for (int Z = Z1; Z < Z2; Z++)
                    {
                        color[X][Y][Z] = 1;
                    }
                }
            }
        }

        int s, v;
        floodfill(s, v);
        cout<<s<<" "<<v<<endl;
    }

    return 0;
}

2018-4-4

理想路径

P273

HINT

  1. 若不考虑字典序问题，则显然可以直接bfs求解最短路。但是如何使得字典序最小呢？
  2. 显然要贪心选取每一步的col值最小，为了保证贪心选取时每一步都仍为最短路，从终点进行一次bfs的到各点dis。
  3. 取最小值的过程仍为bfs的过程，但是需要从多点出发访问下一层的bfs，用vector来实现，且访问层数即为最短距离。

代码

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
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cctype>
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define IN() freopen("in.txt", "r", stdin)
#define OUT() freopen("out.txt", "w", stdout)
#define LL long long
#define maxn 100005
#define maxm 200005
#define mod 1000000007
#define INF 1000000007
#define eps 1e-5
#define PI 3.1415926535898
#define N 26
using namespace std;
//-------------------------CHC------------------------------//
struct Edge {
    int to, col;
    Edge(int to = 0, int col = 0) : to(to), col(col) { }
};
vector<Edge> edges[maxn];
int d[maxn];
bool vis[maxn];
vector<int> col;

void get_dis(int n) {
    CLEAR(vis, 0);
    queue<int> q;
    q.push(n);
    vis[n] = true;
    d[n] = 0;

    while (q.size()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < edges[u].size(); ++i) {
            int v = edges[u][i].to;
            if (!vis[v]) {
                vis[v] = true;
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
}

void bfs(int n) {
    CLEAR(vis, 0);
    col.clear();
    vector<int> s;
    s.push_back(1);
    vis[1] = true;

    for (int i = 0; i < d[1]; ++i) {
        int mincol = INF;
        for (int j = 0; j < s.size(); ++j) {    //find the minimum col
            int u = s[j];
            for (int k = 0; k < edges[u].size(); ++k) {
                int v = edges[u][k].to, c = edges[u][k].col;
                if (!vis[v] && d[v] == d[u] - 1)
                    mincol = min(mincol, c);
            }
        }
        col.push_back(mincol);

        vector<int> temp;
        for (int j = 0; j < s.size(); ++j) {    //find out the next vertices of the next phase
            int u = s[j];
            for (int k = 0; k < edges[u].size(); ++k) {
                int v = edges[u][k].to, c = edges[u][k].col;
                if (!vis[v] && d[v] == d[u] - 1 && c == mincol) {
                    temp.push_back(v);
                    vis[v] = true;
                }
            }
        }
        s = temp;
    }
}

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        for (int i = 1; i <= n; ++i) edges[i].clear();
        CLEAR(d, -1);
        int u, v, w;
        for (int i = 0; i < m; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            edges[u].push_back(Edge(v, w));
            edges[v].push_back(Edge(u, w));
        }
        get_dis(n);
        bfs(n);
        printf("%d\n", d[1]);
        bool first = true;
        for (int i = 0; i < col.size(); ++i) {
            if (first) first = false;
            else putchar(' ');
            printf("%d", col[i]);
        }
        putchar('\n');
    }
    return 0;
}

2018-04-09

P278 平衡的括号

HINT

使用栈

代码

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
map<char, char> mp = {{'[', ']'}, {'(', ')'}};

bool judge(string str){

    stack<char> st;

    for (auto it = str.begin(); it != str.end(); ++it) {

        if (*it == '[' || *it == '(') st.push(*it);
        else{

            assert(*it == ']' || *it == ')');
            if (st.empty())
                return false;
            char cp = st.top();
            if (*it  == mp[cp]) {
                st.pop();
                continue;
            }
            else
                return false;

        }
    }
    return st.empty();
}

int main()
{
    int n;
    char buf[256];
    scanf("%d\n", &n);
    while(n--) {
        gets(buf);
        if(judge(buf)) puts("Yes");
        else puts("No");
    }
    return 0;
}

P279 骑士的移动

HINT

广度优先遍历

代码

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
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
int map[10][10];
int visit[10][10];
int dist[10][10];
int dx[8]={-2,-2,-1,-1,1,1,2,2};
int dy[8]={-1,1,-2,2,-2,2,-1,1};
char a[5];
int x2,y2;
int min = 999;
struct node
{
    int x,y;
};
queue<node>q;

void dfs(node T, int sum)
{
    if (sum>min) return;

    if (T.x==x2&&T.y==y2){
        if (sum < min){
            min = sum;
        }
        return;
    }

    for(int i=0; i<8; i++)
    {

        int xx = T.x+dx[i];
        int yy = T.y+dy[i];
        if(!visit[xx][yy]&&xx>0&&yy>0&&xx<=8&&yy<=8)
        {
            node n ;
            n.x = xx;
            n.y = yy;
            q.push(n);
            visit[xx][yy] = 1;
            dfs(n, sum+1);
            visit[xx][yy] = 0;
        }
    }
    return;

}

int bfs(node T)
{
    if(T.x==x2&&T.y==y2)
    {
        return dist[T.x][T.y];
    }
    else
    {
        while(!q.empty())
        {
            node m = q.front();
            q.pop();
            if(m.x==x2&&m.y==y2)
                return dist[m.x][m.y];
            for(int i=0; i<8; i++)
            {

                int xx = m.x+dx[i];
                int yy = m.y+dy[i];
                if(!visit[xx][yy]&&xx>0&&yy>0&&xx<=8&&yy<=8)
                {
                    node n ;
                    n.x = xx;
                    n.y = yy;
                    q.push(n);
                    dist[xx][yy] = dist[m.x][m.y]+1;
                    visit[xx][yy] = 1;
                }
            }
        }
    }
}
int main()
{
    int x1,y1,i,j;
    while(gets(a))
    {
        y1 = a[0]-'a'+1;
        x1 = a[1]-'0';
        y2 = a[3]-'a'+1;
        x2 = a[4]-'0';
        //printf("%d %d %d %d\n",x1,y1,x2,y2);
        node T;
        T.x = x1;
        T.y = y1;
        memset(dist,0,sizeof(dist));
        memset(visit,0,sizeof(visit));
        q.push(T);
        bfs(T);
        printf("To get from %c%c to %c%c takes %d knight moves.\n",a[0],a[1],a[3],a[4],dist[x2][y2]);
        while(!q.empty())
        {
            q.pop();
        }
    }
    return 0;
}

P280 巡逻机器人

HINT

bfs

代码

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
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
using namespace std;
int map[50][50],vis[50][50][50];//visit多一维来记录穿墙数
int m, n, k;
int d[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
struct node
{
    int x, y;
    int count;
    int layer;//用layer记录穿墙数
};

int bfs(int x,int y)
{
    memset(vis, 0, sizeof(vis));
    queue<node> q;
    node c;
    c.x = x; c.y = y;
    c.count = 0;c.layer=0;
    q.push(c);
    vis[x][y][0] = 1;
    while (!q.empty())
    {
        node c = q.front(); q.pop();
        if (c.x == m&&c.y == n)
            return c.count;
        for (int i = 0; i < 4; i++)
        {
            node v;
            v.x = c.x + d[i][0];
            v.y = c.y + d[i][1];
            v.layer = c.layer;
            if (map[v.x][v.y])
                v.layer++;     //遇到墙则穿墙数+1
            else
                v.layer = 0;    //如果不穿墙，穿墙数归零
            v.count = c.count + 1;
            if (v.layer<=k&&!vis[v.x][v.y][v.layer]&&v.x>=1&&v.x<=m&&v.y>=1&&v.y<=n)
            {
                vis[v.x][v.y][v.layer] = 1;//这里多一维的目的是有时候坐标相同但穿墙数不同也是能经过的
                q.push(v);
            }
        }
    }
    return -1;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int i,j;
        scanf("%d%d", &m, &n);
        scanf("%d", &k);
        for (i = 1; i <= m; i++)
            for (j = 1; j <= n; j++)
                scanf("%d", &map[i][j]);
        printf("%d\n", bfs(1,1));
    }
    return 0;
}

P280修改天平

HINT

本题利用dfs解决，不过思维上要发挥一些创造性。本题问至少要修改的砝码个数，那么首先可以想到要选一个基准砝码，其他所有的砝码都试图根据这个基准法吗而改变。不过本题的巧妙之处就在这里，只要以深度为depth（depth从0开始）重量为w的砝码为基准，那么就能求出整个天平的总重量，即w*2^(depth)，在代码中可以简洁地表示为w<<depth。这样，我们只用统计每个可能的总重量对应了多少不需要改动的砝码，设一共有sum个砝码，总重量为sumw的天平对应的砝码个数是base[sumw]，那么最终答案就是sum-max{base[i]}（i为所有可能的天平总重量）。本题在统计之前需要用dfs后序遍历该表达式。

本题的解法有点类似于找每个元素的某个贡献值的大小（在本题中贡献值就是以它为基准算出的天平总重量），同时统计该贡献值下元素有几个，那么最后取最优值即可。这种思维也是竞赛中的常见思维，应予以重视。

代码

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
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;
string line;
typedef long long LL;
map<LL, int>base;//统计重量为sumw的天平对应的砝码个数
int sum;

void dfs(int depth, int s, int e)
{
    if (line[s] == '[')
    {
        int p = 0;
        for (int i = s + 1; i != e; i++)
        {
            if (line[i] == '[')p++;
            if (line[i] == ']')p--;
            if (!p&&line[i] == ',')
            {
                dfs(depth + 1, s + 1, i - 1);//后序遍历表达式，直到找到砝码
                dfs(depth + 1, i + 1, e - 1);
            }
        }
    }
    else
    {
        LL w = 0;
        for (int i = s; i <= e; i++)
            w = w * 10 + line[i] - '0';
        ++sum, ++base[w << depth];//sum统计砝码总数量，base[w<<depth]统计该总重量对应的砝码个数
    }
}
int main()
{
    freopen("t.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while (T--)
    {
        cin >> line;
        base.clear();
        sum = 0;
        dfs(0, 0, line.size() - 1);
        int maxn = 0;
        for (auto it = base.begin(); it != base.end(); it++)//利用C++ 11的新关键字auto自动识别类型
            maxn = max(maxn, it->second);
        cout << sum - maxn << endl;
    }
    return 0;
}

2018-04-12

八皇后问题

HINT

回溯

代码

1
2
3
4
5
6
7
8
9
10
11
void search(int cur) {
    if(cur == n) tot++; //递归边界。只要走到了这里，所有皇后必然不冲突
    else for(int i = 0; i < n; i++) {
        int ok = 1;
        C[cur] = i; //尝试把第cur行的皇后放在第i列
        for(int j = 0; j < cur; j++) //检查是否和前面的皇后冲突
            if(C[cur] == C[j] || cur-C[cur] == j-C[j] || cur+C[cur] == j+C[j])
                { ok = 0; break; }
        if(ok) search(cur+1); //如果合法，则继续递归
    }
}

2018-04-13

P369 煎饼

HINT

贪心

代码

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
/** 翻转 */
void Action(vector<int>& vec, int target, int last){
    reverse(vec.begin(), vec.begin()+target+1);
    reverse(vec.begin(), vec.end()-last);
}

int main(){

    int n;

    while(cin>>n){
        vector<int> vec;
        for (int i = 0; i < n; ++i) {
            int j;
            cin>>j;
            vec.push_back(j);
        }

//        vector<int> sortvec = vec;
//
//        sort(sortvec.begin(), sortvec.end());

        for (int i = 0; i<n; ++i) {
            int maxt = 0;
            int index = 0;
            for (int k = 0; k < n-i; ++k) {
                if (vec[k] > maxt) {
                    maxt = vec[k];
                    index = k;
                }
            }
            Action(vec, index, i);
        }

        for (int l = 0; l < n; ++l) {
            cout<<vec[l]<<" ";
        }
    }

}
-------------本文结束感谢您的阅读-------------

本文标题:算法小计B1

文章作者:ChengXiao

发布时间:2018年03月20日 - 20:03

最后更新:2018年06月16日 - 18:06

原始链接:http://chengxiao19961022.github.io/2018/03/20/算法小计B1/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

你的鼓励是我前进的动力~