PTA

pta

1002 dp

给定一个任务的价格，持续的时间和截止的时间，挑选若干的任务，使得最后的价值最大。

dp:

$$
dp[i][j]表示前i个任务第j天完成的收益，\
转移方程：\
dp[i][j+node[i].last] = max(dp[i][j+node[i].last], dp[k][j]+node[i].price), j+node[i].last\le node[i].ddl
$$

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
int n;
struct Node{
    int price, last, ddl;
    Node(int _p, int _l, int _d):price(_p), last(_l), ddl(_d){};
    Node(){};
    bool operator < (const Node& b){
        return ddl<b.ddl;
    }
}node[100];
map<ll, map<ll, ll> > dp;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int p, l, d;
    for(int i=1; i<=n; i++){
        cin>>p>>l>>d;
        node[i] = Node(p, l, d);
    }
    node[0] = Node(0, 0, 0);
    sort(node+1, node+1+n);
    //cout<<node[1].price<<" "<<node[1].ddl<<" "<<node[1].last<<endl;
    dp.clear();
    ll ans = 0;
    for(int i=1; i<=n; i++){
        for(int j=0; j<=node[i-1].ddl; j++){
            if(j+node[i].last<=node[i].ddl){
                for(int k=0; k<i; k++){
                    //cout<<i<<" "<<j<<" "<<k<<endl;
                    dp[i][j+node[i].last] = max(dp[i][j+node[i].last], dp[k][j]+node[i].price);
                    ans = max(ans, dp[i][j+node[i].last]);
                    //cout<<ans<<endl;
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

1017

求两次上升子序列，这种写法比较的优秀，还不用排序。

看网上O（n^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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e4+10;
int n;
struct Node{
    int idx, num;
    bool operator < (const Node& b) const{
        if(num!=b.num)return num<b.num;
        else return idx<b.idx;
    }
}node[maxn];
int c[maxn<<1];
int dp1[maxn];
int dp2[maxn];
int lowbit(int x){
    return x&(-x);
}
void add(int x, int val){
    while(x<=20001){
        c[x] = max(c[x], val);
        x += lowbit(x);
    }
}
int query(int x){
    int ans = 0;
    while(x>0){
        ans = max(ans, c[x]);
        x -= lowbit(x);
    }
    return ans;
}
Node temp[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>node[i].num;
        node[i].num += 10001;
    }
    int mx = 0;
    for(int i=1; i<=n; i++){
        dp1[i] = query(node[i].num-1)+1;
        add(node[i].num, dp1[i]);
    }
    cls(c, 0);
    for(int i=n; i>=1; i--){
        dp2[i] = query(node[i].num-1)+1;
        add(node[i].num, dp2[i]);
    }
    int ans = 0;
    bool has = false;
    int idx = -1;
    int num = 0;
    int len2 = 0;
    for(int i=1; i<=n; i++){
        if(dp1[i]>=2 && dp2[i]>=2&&(dp1[i]+dp2[i]-1>ans||(dp1[i]+dp2[i]-1==ans&&abs(dp2[i]-dp1[i])<len2))){
            ans = max(ans, dp1[i]+dp2[i]-1);
            num = node[i].num;
            idx = i;
            has = true;
            len2 = abs(dp2[i]-dp1[i]);
        }
    }
    if(!has){
        cout<<"No peak shape"<<endl;
    }
    else cout<<ans<<" "<<idx<<" "<<num-10001<<endl;
    return 0;
}

1001 枚举点求最小生成树

注意当无法构成最小生成树的时候，该点必然是答案。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 500+10;
struct Edge{
    int u, v, weight;
    bool operator < (const Edge&b) const{
        return weight<b.weight;
    }
}edge[maxn*maxn];
int n, m;
vector<int> nd;
int ans = 0;
int fa[maxn];
int find_fa(int x){
    return fa[x] == x?x:fa[x] = find_fa(fa[x]);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int u, v, w, sta;
    for(int i=1; i<=m; i++){
        cin>>u>>v>>w>>sta;
        if(sta == 1) edge[i] = Edge{u, v, 0};
        else edge[i] = Edge{u, v, w};
    }
    sort(edge+1, edge+1+m);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) fa[j] = j;
        int cnt = 0;
        int temp = 0;
        for(int j=1; j<=m; j++){
            u = edge[j].u, v = edge[j].v, w = edge[j].weight;
            if(u == i||v == i) continue;
            int fau = find_fa(u);
            int fav = find_fa(v);
            if(fau != fav){
                fa[fau] = fav;
                cnt++;
                temp += w;
            }
            if(cnt == n-2) break;
        }
        if(cnt!=n-2){
            temp = inf;
        }
        if(temp>ans){
            ans = temp;
            nd.clear();
            nd.push_back(i);
        }
        else if(temp == ans&&temp!=0) {
            nd.push_back(i);
        }
    }
    int sz = nd.size();
    if(sz == 0){
        cout<<0<<endl;
        return 0;
    }
    for(int i=0; i<sz-1; i++){
        cout<<nd[i]<<" ";
    }
    cout<<nd[sz-1]<<endl;
    return 0;
}

1026 区间的滑窗

  1. 取一段连续的珠子，使得最长
  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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e4+10;
int val[maxn];
bool vis[maxn];
int kind[maxn];
int n;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>val[i];
    for(int i=1; i<=n; i++) cin>>kind[i];
    int l=1, r=1;
    int ans = 0;
    int temp  = 0;
    int ansl=1, ansr=1;
    int mxlen = 0;
    while(r<=n){
        while(!vis[kind[r]]&&r<=n){
            temp += val[kind[r]];
            vis[kind[r]] = true;
            r++;
        }
        if(r-l>mxlen||(ans<temp&&r-l == mxlen)){
            ans = temp;
            ansl=l, ansr = r-1;
            mxlen = r-l;
        }
        temp -= val[kind[l]];
        vis[kind[l]] = false;
        l++;
    }
    cout<<ans<<" "<<ansl-1<<" "<<ansr-1<<endl;
    return 0;
}

1009 triple inversion

该序列是一个排列，所以不用离散化。

可以用树状数组来统计

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
int a[maxn];
int n;
ll ans[maxn];
int c[maxn];
ll l[maxn], r[maxn];
int lowbit(int x){
    return x&(-x);
}
void add(int x, int val){
    while(x<=n){
        c[x] += val;
        x += lowbit(x);
    }
}
int get(int x){
    int ans = 0;
    while(x>0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++){
        l[i] = i-1-get(a[i]);
        add(a[i], 1);
    }
    cls(c, 0);
    for(int i=1; i<=n; i++){
        r[i] = a[i]-1-get(a[i]);
        add(a[i], 1);
    }
    ll tot = 0;
    for(int i=1; i<=n; i++){
        tot += l[i]*r[i];
    }
    cout<<tot<<endl;
    return 0;
}

1015

非常巧妙的一个思路。

题解

l3-015 食物链

  1. 点的顺序原来没有排序
  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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 20+10;
char mp[maxn][maxn];
vector<int> G[maxn];
bool vis[maxn];
int n;
bool vis1[maxn][maxn];
stack<int> ans;
bool dfs(int x, int u){
    if(x == n+1){
        return true;
    }
    //cout<<" "<<x<<" "<<u<<endl;
    bool flag = false;
    if(x<n){
        for(int i=1; i<=n; i++){
            if((!vis[i])&&(mp[i][1] == 'W'||mp[1][i] == 'L')){
                flag = true;
                break;
            }
        }
        if(!flag) return false;
    }
    for(int i=0; i<G[u].size(); i++){
        int v = G[u][i];
        if(!vis[v]||(x==n&&v==1)){
            vis[v] = true;
            ans.push(v);
            if(dfs(x+1, v)) return true;
            vis[v] = false;
            ans.pop();
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin>>mp[i][j];
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(mp[i][j] == 'W'&&!vis1[i][j]) G[i].push_back(j), vis1[i][j] = true;
            else if(mp[i][j] == 'L'&&!vis1[j][i]) G[j].push_back(i), vis1[j][i] = true;
        }
    }
    for(int i=1; i<=n; i++) sort(G[i].begin(), G[i].end());
    vis[1] = true;
    ans.push(1);
    if(!dfs(1, 1)){
        cout<<"No Solution"<<endl;
    }
    else{
        ans.pop();
        vector<int> temp;
        while(!ans.empty()){
            int now = ans.top();
            ans.pop();
            temp.push_back(now);
        }
        for(int i=temp.size()-1; i>=1; i--){
            cout<<temp[i]<<" ";
        }
        cout<<temp[0]<<endl;
    }
    return 0;
}

极角排序

题目要求选择三个点，使得三角形的面积最小。

枚举每一个三角形的顶点，然后算面积

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<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 5000+10;
struct Node{
    ll x, y;
}node[maxn], a[maxn];
int n;
bool cmp(Node a, Node b){
    return b.y*a.x>a.y*b.x;
}
int main(){
    ios::sync_with_stdio(false);
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%lld%lld", &node[i].x, &node[i].y);
    }
    int idx = 0;
    ll ans = 1e18;
    for(int i=1; i<=n; i++){
        idx = 0;
        for(int j=1; j<=n; j++){
            if(i == j) continue;
            a[idx].x = node[i].x-node[j].x;
            a[idx].y = node[i].y-node[j].y;
            idx++;
        }
        sort(a, a+idx, cmp);
        for(int j=1; j<idx; j++){
            ans = min(ans, abs(a[j].x*a[j-1].y-a[j].y*a[j-1].x));
        }
    }
    printf("%.3lf\n", 1.0*ans/2);
    return 0;
}

l3-016 二叉树的形态

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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = (10000)+10;
int tr[maxn];
int n;
int a, b;
int xid, yid;
void build(int rt, int val){
    if(tr[rt] == -1) tr[rt] = val;
    else if(val<tr[rt]) build(rt<<1, val);
    else build(rt<<1|1, val);
    return ;
}
bool judge1(){
    for(int i=1; i<maxn; i++){
        if(tr[i] == a){
            xid = i;
            break;
        }
    }
    if(xid!=1) return false;
    return true;
}
bool judge2(){
    for(int i=1; i<maxn; i++){
        if(tr[i] == a){
            xid = i;
        }
        if(tr[i] == b){
            yid = i;
        }
    }
    if(xid/2!=yid/2) return false;
    return true;
}
bool judge3(){
    for(int i=1; i<maxn; i++){
        if(tr[i] == a){
            xid = i;
        }
        if(tr[i] == b){
            yid = i;
        }
    }
    if(xid !=yid/2) return false;
    return true;
}
bool judge4(){
    for(int i=1; i<maxn; i++){
        if(tr[i] == a){
            xid = i;
        }
        if(tr[i] == b){
            yid = i;
        }
    }
    if(xid !=yid*2) return false;
    return true;
}
bool judge5(){
    for(int i=1; i<maxn; i++){
        if(tr[i] == a){
            xid = i;
        }
        if(tr[i] == b){
            yid = i;
        }
    }
    if(xid !=yid*2+1) return false;
    return true;
}
bool judge6(){
    for(int i=1; i<maxn; i++){
        if(tr[i] == a){
            xid = i;
        }
        if(tr[i] == b){
            yid = i;
        }
    }
    int depth1=0;
    while(xid!=1&&xid!=-1){
        depth1++;
        xid/=2;
    }
    while(yid!=1&&yid!=-1){
        depth1--;
        yid/=2;
    }
    if(depth1) return false;
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cls(tr, -1);
    cin>>n;
    int temp;
    for(int i=1; i<=n; i++){
        cin>>temp;
        build(1, temp);
    }
    int q;
    cin>>q;
    string s[10];
    bool flag = false;
    while(q--){
        cin>>a>>s[0];
        xid = yid = -1;
        flag = false;
        if(s[0] == "and"){
            cin>>b;
            for(int i=1; i<=2; i++){
                cin>>s[i];
            }
            if(s[2] == "siblings"){
                if(judge2())flag = true;
            }
            else{
                for(int i=3; i<6; i++) cin>>s[i];
                if(judge6())flag = true;
            }
        }
        else{
            for(int i=1; i<=2; i++) cin>>s[i];
            if(s[2] == "root"){
                yid=1;
                if(judge1()) flag= true;
            }
            else if(s[2] == "parent"){
                for(int i=3; i<=3; i++) cin>>s[i];
                cin>>b;
                if(judge3())flag = true;
            }
            else if(s[2] == "left"){
                for(int i=3; i<=4; i++) cin>>s[i];
                cin>>b;
                if(judge4())flag = true;
            }
            else if(s[2] == "right"){
                for(int i=3; i<=4; i++) cin>>s[i];
                cin>>b;
                if(judge5())flag = true;
            }
        }
        //cout<<xid<<" "<<yid<<endl;
        if(xid==-1||yid==-1){//必须要加一个这个判断！因为有的数字不在原来的队列里。
            flag = false;
        }
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

l3-010 是否为满二叉树

把满二叉树的定义弄错了。。

  1. 值大的在右边，值小的在左边，不是优先填满某一层
  2. 满二叉树是1~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
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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 1048575*2+10;
struct Node{
    int data;
    int lchild, rchild;
}node[maxn];
int a[22];
int n;
void bfs(int rt, int val){
    queue<int> q;
    while(!q.empty()) q.pop();
    q.push(rt);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        if(node[now].data == -1){
            //cout<<now<<" "<<val<<endl;
            node[now].data = val;
            return ;
        }
        if(node[now].data<val)q.push(now*2);
        if(node[now].data>val)q.push(now*2+1);
    }
}
bool judge(int rt){
    for(int i=1; i<=n; i++){
        if(i*2+1<=n&&(node[i*2].data!=-1&&node[i*2+1].data==-1||node[i*2+1].data!=-1&&node[i*2].data==-1)){
            //cout<<"what "<<i<<endl;
            return false;
        }
        if(i*2<=n&&node[i*2].data == -1) return false;
        if(i*2+1<=n&&node[i*2].data == -1&&node[i*2+1].data == -1) return false;
    }
    return true;
}
vector<int> ans;
void layer(){
    queue<int> q;
    q.push(1);
    while(!q.empty()){
        int now = q.front();
        q.pop();
        //cout<<now<<endl;
        ans.push_back(node[now].data);
        if(now*2<maxn&&node[now*2].data!=-1){
            q.push(now*2);
        }
        if(now*2+1<maxn&&node[now*2+1].data!=-1){
            q.push(now*2+1);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1; i<maxn; i++) node[i].data = node[i].lchild = node[i].rchild = -1;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    bool flag = false;
    for(int i=1; i<=n; i++){
        bfs(1, a[i]);
    }
    //cout<<"haha"<<endl;
    layer();
    //cout<<ans.size()<<endl;
    for(int i=0; i<ans.size()-1; i++){
        cout<<ans[i]<<" ";
    }
    cout<<ans[ans.size()-1]<<endl;
    flag = judge(1);
    if(!flag) cout<<"NO"<<endl;
    else{
        cout<<"YES"<<endl;
    }
    return 0;
}

简单计算器

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<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define inc(i, l, r) for(int i=l; i<=r; i++)
const int inf = 0x3f3f3f3f;
const int maxn = 2000+10;
struct Node{
    double data;
    char op;
    bool flag;
};
queue<Node> q;
stack<Node> s;
string str;
map<char, int> pri;
void change(){
    for(int i=0; i<str.length(); i++){
        Node temp;
        temp.flag = false;
        if(str[i]>='0'&&str[i]<='9'){
            temp.flag = true;
            temp.data = str[i]-'0';
            i++;
            while(i<str.length()&&str[i]>='0'&&str[i]<='9'){
                temp.data = temp.data*10+str[i]-'0';
                i++;
            }
            q.push(temp);
            i--;
        }
        else{
            temp.op = str[i];
            while(!s.empty()&&pri[s.top().op]>=pri[str[i]]){
                q.push(s.top());
                s.pop();
            }
            s.push(temp);
        }
    }
    while(!s.empty()) {
        q.push(s.top());
        s.pop();
    }
//    while(!q.empty()){
//        Node temp = q.front();
//        q.pop();
//        if(temp.flag) cout<<temp.data<<" ";
//        else cout<<temp.op<<" ";
//    }
//    cout<<endl;
}
double cal(){
    double ans = 0;
    Node cur;
    while(!q.empty()){
        cur = q.front();
        q.pop();
        if(cur.flag) s.push(cur);
        else{
            Node temp2 = s.top();
            s.pop();
            Node temp1 = s.top();
            s.pop();
            Node t;
            t.flag = true;
            if(cur.op == '+') t.data = temp1.data+temp2.data;
            else if(cur.op == '-') t.data = temp1.data-temp2.data;
            else if(cur.op == '*') t.data = temp1.data*temp2.data;
            else if(cur.op == '/') t.data = temp1.data/temp2.data;
            //cout<<t.data<<endl;
            s.push(t);
        }
    }
    return s.top().data;
}
int main(){
    pri['+'] = pri['-'] = 1;
    pri['*'] = pri['/'] = 2;
    string str1;
    while(getline(cin, str1)){
        if(str1[0] == "0") break;//坑爹的判断，有可能为0+0...
        while(!s.empty()) s.pop();
        str = "";
        for(int i=0; i<str1.length(); i++){
            if(str1[i] != ' ') str+=str1[i];
        }
        //cout<<str<<endl;
        change();
        double ans = cal();
        printf("%.2lf\n", ans);
    }
    return 0;
}

未解决的问题

本文标题:PTA

文章作者:Babydragon

发布时间:2019-07-30, 16:51:10

最后更新:2019-08-06, 16:08:40

原始链接:http://baolintian.github.io/2019/07/30/PTA/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 1002 dp
  2. 2. 1017
  3. 3. 1001 枚举点求最小生成树
  4. 4. 1026 区间的滑窗
  5. 5. 1009 triple inversion
  6. 6. 1015
  7. 7. 极角排序
  8. 8. l3-016 二叉树的形态
  9. 9. l3-010 是否为满二叉树
  10. 10. 简单计算器
  11. 11. 未解决的问题
{{ live2d() }}