Chengrui's Blog

0%

发表于 分类于 ， Disqus：

书上给了思路，水题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=20;
int a[maxn];
int main(){
    int n,t=0;
    while(cin>>n){
        for(int i=0;i<n;i++) cin>>a[i];
        long long x=0,y;
        for(int i=0;i<n;i++){
            y=1;
            for(int j=i;j<n;j++){
                y*=a[j];
                x=max(x,y);
            }
        }
        cout<<"Case #"<<++t<<": The maximum product is "<<x<<"."<<endl;
        cout<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

水

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
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
set<int>num[7];
int n,cnt,x,y[7];
bool z;
void judge(){
    x=n*y[1];
    if(x>98765){
        z=true;
        return;
    }
    num[1].insert(x/10000);
    num[1].insert(x%10000/1000);
    num[1].insert(x%1000/100);
    num[1].insert(x%100/10);
    num[1].insert(x%10);
    if(num[1].size()==10){
        printf("%05d / %05d = %d\n",x,y[1],n);
        cnt++;
    }
    num[1].clear();
    return;
}
void find(int k){
    for(int i=0;i<10;i++){
        y[k]=y[k+1];
        num[k]=num[k+1];
        while(num[k].find(i)!=num[k].end()&&i<9) i++;
        if(num[k].find(i)==num[k].end()){
            y[k]*=10;
            y[k]+=i;
            num[k].insert(i);
            if(k-1) find(k-1);
            else judge();
            if(z) return;
        }
    }
    return;
}
int main(){
    int t=0;
    while(cin>>n&&n){
        cnt=0;
        z=false;
        if(t++) cout<<endl;
        find(5);
        if(!cnt) cout<<"There are no solutions for "<<n<<"."<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

dfs类的题，感觉应该还能再优化，时间用了0.9s+，挺长的。。

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
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<vector>
using namespace std;
struct Node{
    string s;
    unsigned long long t;
    Node *left,*right;
    Node():t(0),left(NULL),right(NULL){}
};
Node *root;
int cnt1,cnt2,cnt;
vector<unsigned long long>heavy;
Node* newnode(){
    return new Node;
}
void build(Node* a,int n){
    int i,k=0;
    if(a->s.find("[")==string::npos){
        stringstream ss(a->s);
        ss>>a->t;
        cnt1++;
        heavy.push_back(a->t<<n);
        return;
    }
    a->left=newnode();
    for(i=1;i<a->s.length();i++){
        if(a->s[i]=='[') k++;
        if(a->s[i]==']') k--;
        if(!k&&a->s[i]==',') break;
        a->left->s+=a->s[i];
    }
    a->right=newnode();
    for(i++;i<a->s.length()-1;i++)
        a->right->s+=a->s[i];
    build(a->left,n+1);
    build(a->right,n+1);
    return;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        cnt1=0;
        cnt2=cnt=1;
        root=newnode();
        root->s=s;
        build(root,0);
        sort(heavy.begin(),heavy.end());
        for(int i=0;i<heavy.size()-1;i++){
            if(heavy[i]==heavy[i+1]) cnt++;
            else cnt=1;
            cnt2=max(cnt2,cnt);
        }
        cout<<cnt1-cnt2<<endl;
        heavy.clear();
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

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
67
68
69
70
71
72
73
74
75
76
77
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=25;
struct Node{
    int a,b,c;
    Node *p[4];
    Node(int a=0,int b=0,int c=0):a(a),b(b),c(c){}
};
int m,n,k,maze[maxn][maxn];
bool arrived[maxn][maxn];
int run[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
Node* root;
queue<Node*>ept;
queue<queue<Node*> >tree;
Node* newnode(int a,int b,int c){
    Node* temp;
    temp=new Node(a,b,c);
    for(int i=0;i<4;i++)
        temp->p[i]=NULL;
    return temp;
}
bool inmaze(int a,int b){
    if(a>=0&&a<m&&b>=0&&b<n)
        return true;
    return false;
}
void build(Node* a){
    int x=a->a,y=a->b,z=a->c,aa,bb;
    if(maze[x][y]) z--;
    else z=k;
    if(!maze[x][y]||(maze[x][y]&&z==k-1)) arrived[x][y]=true;
    for(int i=0;i<4;i++){
        aa=x+run[i][0],bb=y+run[i][1];
        if(inmaze(aa,bb)&&!arrived[aa][bb]&&(!maze[aa][bb]||z>0)){
            a->p[i]=newnode(aa,bb,z);
            tree.back().push(a->p[i]);
        }
    }
    return;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        int move=0;
        cin>>m>>n>>k;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                cin>>maze[i][j];
        root=newnode(0,0,k);
        tree.push(ept);
        tree.push(ept);
        tree.front().push(root);
        while(1){
            if(arrived[m-1][n-1]) break;
            if(tree.front().empty()&&tree.back().empty()){
                move=-1;
                break;
            }
            if(tree.front().empty()){
                tree.pop();
                tree.push(ept);
                move++;
            }
            build(tree.front().front());
            tree.front().pop();
        }
        cout<<move<<endl;
        memset(arrived,0,sizeof(arrived));
        memset(maze,0,sizeof(maze));
        tree.pop();
        tree.pop();
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

bfs类的题，加了内存处理之后自己运行一直不对，但不处理泄漏的内存，能出正确结果，注释掉之后一次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
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<map>
#include<queue>
#include<vector>
using namespace std;
struct Point{
    int a,b;
    Point(int a=0,int b=0):a(a),b(b){}
    Point operator + (const Point A) const {
        Point temp;
        temp=Point(a+A.a,b+A.b);
        return temp;
    }
    bool operator ==(const Point A) const{
        return a==A.a&&b==A.b;
    }
};
struct Node{
    Point a;
    Node *p[8];
    Node(Point a=Point()):a(a){}
};
int k[8][2]={{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1}};
bool arrived[8][8];
Point jump[8],sta,ed;
map<char,int>x;
queue<Node*>deep;
vector<queue<Node*> >tree;
bool should_jump(Point a,Point b){
    Point temp;
    temp=a+b;
    if(temp.a>=0&&temp.a<8&&temp.b>=0&&temp.b<8&&!arrived[temp.a][temp.b]) return true;
    return false;
}
Node* newnode(){
    Node *temp;
    temp=new Node();
    for(int i=0;i<8;i++)
        temp->p[i]=NULL;
    return temp;
}
Point read_point(string a){
    Point temp;
    temp.a=x[a[0]];
    temp.b=a[1]-'1';
    return temp;
}
void arrive(Point a){
    arrived[a.a][a.b]=true;
    return;
}
void build(Node* a,int k){
    for(int i=0;i<8;i++)
        if(should_jump(a->a,jump[i])){
            a->p[i]=new Node();
            a->p[i]->a=a->a+jump[i];
            arrive(a->p[i]->a);
            tree[k].push(a->p[i]);
        }
}
void remove_tree(Node* a){
    if(a==NULL) return;
    for(int i=0;i<8;i++)
        remove_tree(a->p[i]);
    delete a;
}
int main(){
    for(int i=0;i<8;i++){
        jump[i].a=k[i][0];
        jump[i].b=k[i][1];
        x['a'+i]=i;
    }
    string s0,s;
    while(cin>>s0>>s){
        int move;
        Node* root;
        memset(arrived,0,sizeof(arrived));
        sta=read_point(s0);
        arrive(sta);
        ed=read_point(s);
        if(sta==ed){
            move=0;
            goto END;
        }
        root=newnode();
        root->a=sta;
        tree.push_back(deep);
        tree.push_back(deep);
        tree[0].push(root);
        move=1;
        while(1){
            if(arrived[ed.a][ed.b]) break;
            if(tree[0].empty()){
                tree.erase(tree.begin());
                tree.push_back(deep);
                move++;
            }
            build(tree[0].front(),1);
            tree[0].pop();
        }
    END:
        cout<<"To get from "<<s0<<" to "<<s<<" takes "<<move<<" knight moves."<<endl;
        //remove_tree(root);
        tree.clear();
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 Disqus：

刷题40天了，紫书上刷了60道题了，终于做到数据结构了，据说这章挺难的。以后刷题节奏可能越来越慢。第五章有道题貌似建字典树过简单点，就一直没再去弄，等学完再 搞。

这十天感觉自己C++熟练多了，STL用起来更加自如了，结构体内重载运算符什么的也终于理解了，还写了高精度算法模版。以后准备边积累算法素材，边刷题。争取早日刷 够百题。

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

二叉树的题，建树之后代数就行。

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
#include<iostream>
#include<cstring>
#include<string>
#include<sstream>
#include<vector>
using namespace std;
int n,m,t,x[8];
struct Node{
    Node *left,*right;
    bool have_value;
    int v;
    Node():v(0),have_value(false),left(NULL),right(NULL){}
};
vector<Node*>tree[8];
Node* root;
void read_order(){
    string s;
    getline(cin,s);
    stringstream ss(s);
    for(int i=0;i<n;i++){
        ss.get();
        ss>>x[i];
        ss.get();
    }
}
Node* newnote(){
    return new Node();
}
void build(vector<Node*>a,int b){
    for(int i=0;i<a.size();i++){
        a[i]->left=newnote();
        a[i]->right=newnote();
        tree[b+1].push_back(a[i]->left);
        tree[b+1].push_back(a[i]->right);
    }
    return;
}
void remove_tree(Node* u){
    if(u==NULL) return;
    remove_tree(u->left);
    remove_tree(u->right);
    delete u;
}
int main(){
    while(cin>>n&&n){
        cin.get();
        string s,s0,sk,empty;
        read_order();
        cin>>s;
        root=newnote();
        tree[0].push_back(root);
        for(int i=0;i<n;i++){
            build(tree[i],i);
        }
        for(int i=0;i<tree[n].size();i++){
            tree[n][i]->v=s[i];
            tree[n][i]->have_value=true;
        }
        cin>>m;
        while(m--){
            cin>>s0;
            s=empty;
            Node *t=root;
            for(int i=0;i<n;i++)
                s+=s0[x[i]-1];
            s0=s;
            for(int i=0;i<n;i++){
                if(s0[i]=='0') t=t->left;
                else t=t->right;
            }
            sk+=t->v;
        }
        cout<<"S-Tree #"<<++t<<":"<<endl;
        cout<<sk<<endl;
        cout<<endl;
        for(int i=0;i<8;i++) tree[i].clear();
        remove_tree(root);
        memset(x,0,sizeof(x));
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

水的不得了，有种OJ作业题的感觉。。

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<string>
#include<sstream>
using namespace std;
const int maxv=30;
char pre_order[maxv],in_order[maxv];
int lch[maxv],rch[maxv];
int n;
bool read_list(char* a){
    string line;
    if(!(cin>>line)) return false;
    stringstream ss(line);
    n=0;
    char x;
    while(ss.get(x)) a[n++]=x;
    return true;
}
int build(int L1,int R1,int L2,int R2){
    if(L1>R1) return 0;
    int root=pre_order[L2]+1-'A';
    int p=L1;
    while((in_order[p]+1-'A')!=root) p++;
    int cnt=p-L1;
    lch[root]=build(L1,p-1,L2+1,L2+cnt);
    rch[root]=build(p+1,R1,L2+cnt+1,R2);
    return root;
}
void print(int x){
    char c=x+'A'-1;
    if(lch[x]) print(lch[x]);
    if(rch[x]) print(rch[x]);
    cout<<c;
    return;
}
int main(){
    while(read_list(pre_order)){
        read_list(in_order);
        build(0,n-1,0,n-1);
        print(pre_order[0]+1-'A');
        cout<<endl;
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 Disqus：

这次是高精度数运算。打好模版之后，很简单就过了。

一开始模版没做好，乘法多0，除法爆掉int，减法只能大减小。

经过修正乘法、加法、除法已经支持负数运算，减法懒得改了。。

幂运算和乘法差不多，加个运算小数点位置的步骤就过了。

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **

发表于 分类于 ， Disqus：

总算学到树了，是道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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=550;
const int root=1;
int cnt,left[maxn],right[maxn],value[maxn];
bool failed,have_value[maxn];
char s[maxn];
vector<int>a;
void new_tree(){
    left[root]=right[root]=0;
    have_value[root]=false;
    cnt=root;
    return;
}
int newnode(){
    int u=++cnt;
    left[u]=right[u]=0;
    have_value[u]=false;
    return u;
}
void addnote(int v,char* s){
    int n=(int)strlen(s);
    int u=root;
    for(int i=0;i<n;i++)
        if(s[i]=='L'){
            if(!left[u]) left[u]=newnode();
            u=left[u];
        }
        else if(s[i]=='R'){
            if(!right[u]) right[u]=newnode();
            u=right[u];
        }
    if(have_value[u]) failed=true;
    value[u]=v;
    have_value[u]=true;
    return;
}
bool read_input(){
    failed=false;
    for(;;){
        if(scanf("%s",s)!=1) return false;
        if(!strcmp(s,"()")) break;
        int v;
        sscanf(&s[1],"%d",&v);
        addnote(v,strchr(s,',')+1);
    }
    return true;
}
bool bfs(){
    if(failed) return false;
    queue<int>q;
    a.clear();
    q.push(root);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(!have_value[u]) return false;
        a.push_back(value[u]);
        if(left[u]) q.push(left[u]);
        if(right[u]) q.push(right[u]);
    }
    return true;
}
void print(){
    for(int i=0;i<a.size();i++){
        if(i) printf(" ");
        printf("%d",a[i]);
    }
    printf("\n");
    return;
}
int main(){
    while(1){
        new_tree();
        if(!read_input()) break;
        if(!bfs()) failed=true;
        if(failed) printf("not complete\n");
        else print();
    }
    return 0;
}

** 本文迁移自我的CSDN博客，格式可能有所偏差。 **