5.13训练补题

ACM

心情不好


区域赛

A

暴力，用set维护T了，迭代的速度确实很慢。
遍历3e7个数字，数组和迭代器所用的时间相差的常数还是非常大的：
0.215s
1.045s

测试代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e7+10;
int num[maxn];
int main(){
    clock_t start, finish;
    start = clock();
    for(int i=0; i<maxn; i++){
        num[i] = i;
    }
    finish = clock();
    cout<<1.0*(finish-start)/CLOCKS_PER_SEC<<endl;
    set<int> s;
    s.clear();
    for(int i=0; i<maxn; i++){
        s.insert(i);
    }
    int temp;
    start = clock();
    for(set<int>::iterator it = s.begin(); it!=s.end(); it++){
        temp = *it;
    }
    finish = clock();
    cout<<1.0*(finish-start)/CLOCKS_PER_SEC<<endl;
    return 0;
}

AC code

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
#include <bits/stdc++.h>
using namespace std;
const int Mx = 5e4+10;
typedef long long ll;
const ll maxn = 1e9+7;
struct Node{
    ll x, y;
    bool tag;
}node[Mx];
int n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n&&n){
        ll a, b, c;
        int tot = 0;
        for(int i=0; i<n; i++){
            cin>>a>>b>>c;
            if(a == 1){
                node[tot].x = b;
                node[tot].y = c;
                node[tot++].tag = true;
            }
            else if(a == -1){
                for(int i=0; i<tot; i++){
                    if(node[i].x == b&&node[i].y == c&&node[i].tag){
                        node[i].tag = false;
                        break;
                    }
                }
            }
            else{
                ll ans = -maxn*maxn*2;
                for(int i=0; i<tot; i++){
                    if(node[i].tag == false) continue;
                    ll temp = node[i].x*b+node[i].y*c;
                    ans = max(ans, temp);
                }
                cout<<ans<<endl;
            }
        }
    }
    return 0;
}

B

用一条对角线表示一个矩形
注意会有回字形的情况！
注意两个矩形的边不能重叠

AC code

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 35;
int x[maxn];
int y[maxn];
int a[10];
int b[10];
int n;
bool exist(){
    int tot = 0;
    bool vis[10];
    memset(vis, 0, sizeof(vis));
    for(int i=1; i<=n; i++){
        int x1 = x[i];
        int y1 = y[i];
        for(int j=1; j<=8; j++){
            if(x1 == a[j]&&y1 == b[j]){
                vis[j] = true;
            }
        }
    }
    for(int i=1; i<=8; i++){
        if(!vis[i]) return false;
    }
    return true;
}
bool cross(){
    int x_mi = min(a[5], a[7]);
    int x_mx = max(a[5], a[7]);
    int y_mi = min(b[5], b[7]);
    int y_mx = max(b[5], b[7]);
    bool flag1 = false;
    for(int i=1; i<=4; i++){
        if(a[i]>x_mi&&a[i]<x_mx&&b[i]>y_mi&&b[i]<y_mx){
            flag1 = true;
            break;
        }
    }
    bool flag2 = false;
    for(int i=1; i<=4; i++){
        if(a[i]<x_mi||a[i]>x_mx||b[i]<y_mi||b[i]>y_mx){
            flag2 = true;
            break;
        }
    }
    if(flag1&&flag2) return true;
    return false;
}
bool touch(){
    int x_mi = min(a[5], a[7]);
    int x_mx = max(a[5], a[7]);
    int y_mi = min(b[5], b[7]);
    int y_mx = max(b[5], b[7]);
    for(int i=1; i<=4; i++){
        if(b[i] == y_mi||b[i] == y_mx){
            if(a[i]>=x_mi&&a[i]<=x_mx) return true;
        }
        if(a[i] == x_mi||a[i] == x_mx){
            if(b[i]>=y_mi&&b[i]<=y_mx) return true;
        }
    }
    return false;
}
bool in(){
    int x_mi = min(a[5], a[7]);
    int x_mx = max(a[5], a[7]);
    int y_mi = min(b[5], b[7]);
    int y_mx = max(b[5], b[7]);
    int x_mi1 = min(a[1], a[3]);
    int x_mx1 = max(a[1], a[3]);
    int y_mi1 = min(b[1], b[3]);
    int y_mx1 = max(b[1], b[3]);
    if(x_mi<x_mi1&&x_mx>x_mx1){
        for(int i=1; i<=4; i++){
            if(a[i]<=x_mi||a[i]>=x_mx||b[i]<=y_mi||b[i]>=y_mx){
                return false;
            }
        }
        return true;
    }
    else if(x_mi>x_mi1&&x_mx<x_mx1){
        for(int i=5; i<=8; i++){
            if(a[i]<=x_mi1||a[i]>=x_mx1||b[i]<=y_mi1||b[i]>=y_mx1){
                return false;
            }
        }
        return true;
    }
}
bool judge(){
    if(a[1] == a[3]||b[1] == b[3]||a[5] == a[7]||b[5] == b[7])
        return false;
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(cin>>n&&n){
        for(int i=1; i<=n; i++){
            cin>>x[i]>>y[i];
        }
        int ans = -1;
        for(int i=1; i<=n; i++){
            for(int j=i+1; j<=n; j++){
                for(int k=j+1; k<=n; k++){
                    for(int m = k+1; m<=n; m++){
                        a[1] = x[i], b[1] = y[i];
                        a[2] = x[i], b[2] = y[j];
                        a[3] = x[j], b[3] = y[j];
                        a[4] = x[j], b[4] = y[i];
                        a[5] = x[k], b[5] = y[k];
                        a[6] = x[k], b[6] = y[m];
                        a[7] = x[m], b[7] = y[m];
                        a[8] = x[m], b[8] = y[k];
                        if(!judge()) continue;
                        if(!exist()) continue;
                        if(cross()) continue;
                        if(touch()) continue;
                        if(in()){
                            int area1 = abs(a[1]-a[3])*abs(b[1]-b[3]);
                            int area2 = abs(a[5]-a[7])*abs(b[5]-b[7]);
                            area1 = max(area1, area2);
                            ans = max(ans, area1);
                            //cout<<"haha"<<endl;
                            continue;
                        }
                        int area1 = abs(a[1]-a[3])*abs(b[1]-b[3]);
                        int area2 = abs(a[5]-a[7])*abs(b[5]-b[7]);
                        //cout<<ans<<"---"<<endl;
                        ans = max(ans, area1+area2);
                        //cout<<ans<<"---"<<endl;
                    }
                }
            }
        }
        if(ans == -1){
            printf("imp\n");
        }
        else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

D

计算几何，求一个圆和一个多边形面积的交
并不会
模板题

I

大霸用了状压dp,我看题解直接先对边进行排序，然后从小边向后面不断的组成三角就行了。虽然并不懂原理

K

最短路的模板题，我第三个小时才签出来。。。
面壁思过

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 35;
int G[maxn][maxn];
int G1[maxn][maxn];
int dis[maxn];
bool vis[maxn];
int n, m;
const int INF = 1e9+7;
void init(){
    for(int i=0; i<maxn; i++){
        for(int j=0; j<maxn; j++){
            G[i][j] = -1;
        }
    }
}
int dij(){
    for(int i=0; i<maxn; i++) dis[i] = INF;
    memset(vis, 0, sizeof(vis));
    dis[1] = 0;
    for(int i=0; i<n-1; i++){
        int u = -1;
        int Min_dis = INF;
        for(int j=1; j<=n; j++){
            if(!vis[j] &&Min_dis>dis[j]){
                u = j;
                Min_dis = dis[j];
            }
        }
        if(u == -1) return -1;
        if(u == n) return dis[n];
        vis[u] = true;
        for(int j=1; j<=n; j++){
            if(!vis[j]&&G1[u][j]!=-1){
                dis[j] = min(dis[j], dis[u]+G1[u][j]);
            }
        }
    }
    if(dis[n] == INF) return -1;
    else return dis[n];
}
int main(){
    while(cin>>n>>m&&n+m!=0){
        init();
        int u, v,weight;
        for(int i=0; i<m; i++){
            cin>>u>>v>>weight;
            G[u][v] = weight;
            G[v][u] = weight;
        }
        int ans = -1;
        bool flag = false;
        for(int i=2; i<n; i++){
            for(int j=1; j<=n; j++){
                for(int k=1; k<=n; k++){
                    G1[j][k] = G[j][k];
                }
            }
            for(int j=1; j<=n; j++){
                G1[i][j] = -1;
            }
            for(int j=1; j<=n; j++){
                G1[j][i] = -1;
            }
            int temp = dij();
            if(temp == -1){
                flag = true;
            }
            else{
                ans = max(ans, temp);
            }
        }
        if(flag){
            cout<<"Inf"<<endl;
        }
        else if(ans == -1){
            cout<<"Inf"<<endl;
        }
        else cout<<ans<<endl;
    }
    return 0;
}

未解决的问题

本文标题:5.13训练补题

文章作者:Babydragon

发布时间:2018-05-13, 18:47:43

最后更新:2018-05-13, 22:49:26

原始链接:http://baolintian.github.io/2018/05/13/5-13训练补题/

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

文章目录
  1. 1. A
    1. 1.1. 测试代码
    2. 1.2. AC code
  2. 2. B
    1. 2.1. AC code
  3. 3. D
  4. 4. I
  5. 5. K
    1. 5.1. AC代码
  6. 6. 未解决的问题
{{ live2d() }}