Team Round #8:2019 ICPC Malaysia National

发表于 更新于 分类于 阅读次数： 评论数：
本文字数： 1k 阅读时长 ≈ 3 分钟
本文记录了Daenerys Stormborn of the House Targaryen.的第08场训练

这一场是在 2019-11-17 13:39 CST 打的

是打完南京南昌回来后的第一场Team Round,当然了,选题性质是恢复信心训练。

一共解了BKICJAEFH九道题。

有一个小插曲就是我a了第一个水题的时候wqr_和dqy已经切了四道题😭(我神经病了用scanf输入字符,ljlct不会)

B - SpongeBob SquarePants

签到

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
/*   _ _ _                     
    | | | | ___  ___           
    | | | || . ||  _|          
    |_____||_  ||_|  _____     
             |_|    |_____|  */
// Time : 19/11/17
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
int main(){
#ifdef Wqr_
    freopen("in.txt","r",stdin);/*   _ _ _                     
    | | | | ___  ___           
    | | | || . ||  _|          
    |_____||_  ||_|  _____     
             |_|    |_____|  */
// Time : 19/11/17
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
int main(){
#ifdef Wqr_
    freopen("in.txt","r",stdin);
#endif
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int a, b;
        cin >> a >> b;
        if(a == b) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}
#endif
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int a, b;
        cin >> a >> b;
        if(a == b) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

K - Help The Support Lady

思路：dqy写的

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
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
struct rbtree: tree<T,null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>{};
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define mp make_pair
#define pb push_back
#define lowb lower_bound
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mem0(a) memset((a), 0, sizeof(a))
#define mem(a, b) memset((a), (b), sizeof(a))
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int N = 1e5+10;

ll a[N];

int main(){
    //IOS;
    int t;
    int z = 1;
    scanf("%d", &t);
    while(t--){
        int n;
        scanf("%d", &n);
        ll sum = 0;
        for(int i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        int cnt = 0;
        sort(a+1, a+1+n);
        for(int i = 1; i <= n; i++){
            if(sum <= a[i]){
                cnt++;
                sum += a[i];
            }else continue;
        }
        printf("Case #%d: %d\n", z++, cnt);
    }




    return 0;
}

I - To Crash Or Not To Crash

思路：wqr写的

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
/*   _ _ _                     
    | | | | ___  ___           
    | | | || . ||  _|          
    |_____||_  ||_|  _____     
             |_|    |_____|  */
// Time : 19/11/17
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
int main(){
#ifdef Wqr_
    freopen("in.txt","r",stdin);
#endif
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    string a[3];
    cin >> a[0] >> a[1] >> a[2];
    for(auto str : a){
        bool flag = 0;
        for(auto i : str){
            if(flag){
                if(i != '.'){
                    cout << i << endl;
                    return 0;
                }
            }
            if(i == '='){
                flag = 1;
            }
        }
        if(flag){
            cout << "You shall pass!!!" << endl;
            return 0;
        }
    }
    return 0;
}

C - I Don’t Want To Pay For The Late Jar!

dqy写的

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
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
struct rbtree: tree<T,null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>{};
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define mp make_pair
#define pb push_back
#define lowb lower_bound
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mem0(a) memset((a), 0, sizeof(a))
#define mem(a, b) memset((a), (b), sizeof(a))
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;

int main(){
    //IOS;
    int t;
    cin>>t;
    int cnt=1;
    while(t--){
        int n, s;
        cin>>n>>s;
        int ans = -INF;
        for(int i = 0; i < n; i++){
            int x, y;
            cin>>x>>y;
            if(y <= s)ans = max(ans, x);
            else ans = max(ans, x-(y-s));
        }
        printf("Case #%d: %d\n", cnt++, ans);
    }


    return 0;
}

J - Kitchen Plates

题意：

给你abcde五个盘子，给你五个关系，根据给的关系依此输出盘子（从小到大）

思路：

确实可以暴力，然而我第一反应就是拓扑排序，然后敲完之后很长很长一段时间陷入很迷的状态，后来才发现是我用scanf用不对？？。。在我低迷的时候dqy和wqr说杀鸡焉用牛刀这不随便乱搞。。。btw，判断impossible就是有无环，检查序列a长度即可

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
#include <bits/stdc++.h>

using namespace std;
const int maxn = 6;
int ver[maxn], nxt[maxn], head[maxn], deg[maxn], a[maxn];
int tot , cnt, n, m;
char c[3];
void add(int x, int y){
    ver[++tot] = y,nxt[tot] = head[x],head[x] = tot;
    deg[y]++;
}
void topo(){
    queue<int >q;
    for(int i = 1; i <= n;i++){
        if(deg[i] == 0)q.push(i);
    }
    while(q.size()){
        int x = q.front();
        q.pop();
        a[++cnt] = x;
        //cout << "x ==== " << x << "     a["<< cnt <<  "] ===== " <<a[cnt] << endl;
        for(int i  = head[x]; i ; i = nxt[i]){
            int y = ver[i];
            if(--deg[y] == 0)q.push(y);
        }
    }
}
int main(){
    n = 5;
    m = 5;
    for(int i = 0; i < m;i++){
            scanf("%s", c);
        if(c[1] == '<')add(c[0] - 'A' + 1, c[2] - 'A'+1);
        else add(c[2] - 'A'+1,c[0]-'A'+1);
        /*int x, y;
        cin >> x >> y;
        add(x,y);*/
    }
    topo();
   // cout << cnt << endl;
    if(cnt < 5)cout << "impossible\n";
    else {
        for(int i = 1; i <= cnt;i++)
            cout << (char)('A'+a[i]-1);
    }
}

A - Mental Rotation

题意：

给你一个方形图案，给一系列右旋转或者左旋转操作，要求输出操作后的图案

思路：

模拟，模拟带师wqr写的。观察到最多只有右旋90，180，270度这三种，处理完所有的操作后模拟旋转就行。

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
/*   _ _ _                     
    | | | | ___  ___           
    | | | || . ||  _|          
    |_____||_  ||_|  _____     
             |_|    |_____|  */
// Time : 19/11/17
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
const int maxn = 1000 + 10;
int n;
int l = 0, r = 0;
char tu[maxn][maxn];
char vs[4] = {'^', '>', 'v', '<'};
unordered_map<char, int> vsmap;
char ch(char in){
    if(in == '.') return '.';
    return vs[(vsmap[in] + 1) % 4];
}
void ror(){
    char tmp[maxn][maxn];
    for (int j = 0; j < n; j++) {
        for (int i = n - 1; i >= 0; i--) {
            tmp[j][n - 1 - i] = ch(tu[i][j]);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            tu[i][j] = tmp[i][j];
        }
    }
}
void rol(){
    ror();
    ror();
    ror();
}
int main(){
#ifdef Wqr_
    freopen("in.txt","r",stdin);
#endif
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    vsmap['^'] = 0;
    vsmap['>'] = 1;
    vsmap['v'] = 2;
    vsmap['<'] = 3;
    /*
    cout << vs[(vsmap['^'] + 1) % 4] << endl;
    cout << vs[(vsmap['>'] + 1) % 4] << endl;
    cout << vs[(vsmap['v'] + 1) % 4] << endl;
    cout << vs[(vsmap['<'] + 1) % 4] << endl;
    */
    cin >> n;
    string o;
    cin >> o;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> tu[i][j];
        }
    }
    for(auto i : o){
        if(i == 'L') l++;
        if(i == 'R') r++;
    }
    l %= 4;
    r %= 4;
    int tmpl = l, tmpr = r;
    r = max(tmpl, tmpr) - tmpl;
    l = max(tmpl, tmpr) - tmpr;
    for(int i = 0; i < l; i++){
        rol();
    }
    for(int i = 0; i < r; i++){
        ror();
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << tu[i][j];
        }
        cout << endl;
    }
    return 0;
}

E - Optimal Slots

题意：

给一个总时间T，再给N个时间，要求选取一些时间ti，使得总和sum不超过T且尽量接近T，如果有多种方案，就输出输入顺序早的方案。

思路：

dqy 写的 倒着遍历 set 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
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
struct rbtree: tree<T,null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>{};
#define IN freopen("in.txt", "r", stdin);
#define endl '\n'
#define mp make_pair
#define pb push_back
#define lowb lower_bound
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define mem0(a) memset((a), 0, sizeof(a))
#define mem(a, b) memset((a), (b), sizeof(a))
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;

const int N = 55;
int a[N];
set<int> s, s1;
VI v[3000], vv[3000];

int main(){
    IOS;
    //IN;
    int t, n;
    while(cin>>t && t){
        s.clear();
        cin>>n;
        int ans=0;
        for(int i = 0; i < 2600; i++)v[i].clear();
        for(int i = 0; i < n; i++)cin>>a[i];
        for(int i = n-1; i >= 0; i--){
            s1.clear();
            for(auto it : s){
                if(it + a[i] <= t){
                    s1.insert(it+a[i]);
                    ans = max(ans, it+a[i]);
                    vv[it+a[i]] = v[it];
                    vv[it+a[i]].pb(a[i]);
                }
            }
            for(auto it : s1){
                s.insert(it);
                v[it] = vv[it];
                vv[it].clear();
            }
            if(a[i] <= t) {
                s.insert(a[i]);
                ans = max(ans, a[i]);
                v[a[i]].clear();
                v[a[i]].pb(a[i]);
            }
        }
        while(!v[ans].empty()){
            cout<<v[ans].back()<<' ';
            v[ans].pop_back();
        }
        cout<<ans<<endl;
    }
    return 0;
}

题解2：

转化成01背包的思想

过程：

设d[i][j] 为能否从i到N这段中选取一些组成j,为1可行，为零不可行。考虑转移方程，从大到小枚举j,d[i][j] |= d[i+1][j-t[i]],找到一个最大的j，使得d[1][j] = 1, 那么ans = j。然后从大到小枚举i,如果由d[i+1][sum-t[i]] == 1,那么选取ti。

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<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 24 * 8;
int d[52][maxn], a[51];
int main() {
    int T, n;
    for (int i = 1; i <= 51; i++)
        d[i][0] = 1;
    while (cin>>T && T) {
        cin>>n;
        for (int i = 1; i<= n; i++) {
            cin>>a[i];
            for (int j = 1; j <= T; j++)
            d[i][j] = 0;
        }
        for (int j = 1; j <= T; j++)
            d[n + 1][j] = 0;
        for (int i = n; i; i--) {
            for (int j = T; j >= a[i]; j--)
                d[i][j] |= d[i + 1][j - a[i]];
            for (int j = T; j; j--)
                d[i][j] |= d[i + 1][j];
        }
        int sum = T;
        while (!d[1][sum])
            sum--;
        int ans = sum;
        int p = 1;
        queue<int> q;
        while (sum > 0) {
            if (a[p] <= sum) {
                if (d[p + 1][sum - a[p]])
                    q.push(a[p]), sum -= a[p];
            }
            p++;
        }
        while (!q.empty()) {
            printf("%d ", q.front());
            q.pop();
        }
        printf("%d\n", ans);
    }
}
//others：https://blog.csdn.net/ccsu_cat/article/details/93400147

F - Military Class

题意：

有2N个士兵站成两排，现在要求上面一排的士兵和下面一排的士兵一一配对组成N队，要求配对的两个士兵，他们的位置相差不能超过e，而且有K队士兵互相讨厌，他们不能配对在一起。要求输出配对总方案数。

解法：

观察到e很小，2e+1最大也就是9。考虑用状压dp。

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
#include <bits/stdc++.h>

#define int long long
using namespace std;
using ll = long long;
const int maxn = 2005;
const int mod = 1e9+7;
int n , e, kk , ans;
typedef pair <int , int > P;
set<P> s;
int dp[maxn][maxn];
/*int mul(int a , int b){
    int ret = 0;
    while(b){
        if(b & 1)
            ret = (ret+a)%mod;
        a=(a << 1)%mod;
        b = b >> 1;
    }
    return ret;
}*/
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> e >> kk;
    int ee = 2*e+1;
    int all = (ll(1) << ee);
    for(int i = 0; i < kk;i++) {
        int a, b;
        cin >> a >> b;
        //s.insert(make_pair(a, b));
        if(abs(a - b) <= e)s.insert(make_pair(a, b));
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n;i++){
        for(int j = 0; j < all; j++){
            for(int k = 0; k < ee;k++){
                if(i + k - e <= 0)continue;
                if(i + k - e > n)continue;
                if(s.find(P{i, i+k-e}) != s.end())continue;
                int t = j >> 1;
                if(t & (1ll << k))continue;
                dp[i][t | (1ll << k)] = (dp[i][t | (1ll << k)] + dp[i-1][j] ) % mod;
            }
        }
    }
    for(int i = 0; i < all;i++){
        //cout << "dp[n][" << i << "] ===== "<< dp[n][i] << endl;
        ans += dp[n][i];
        ans %= mod;
    }
    cout << ans << endl;
}

H - Are You Safe?

题意：

给定n个点，求出这些点构成的凸包，然后逆时针输出，另外还有q次询问，每次询问一个点是否在凸包里

思路：wqr现学现卖，orz！

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
#include <bits/stdc++.h>
using namespace std;
#define eps 1e-8
class Point {
   public:
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    Point operator+(Point a) {
        return Point(a.x + x, a.y + y);
    }
    Point operator-(Point a) {
        return Point(x - a.x, y - a.y);
    }
    bool operator<(const Point &a) const {
        if (x == a.x)
            return y < a.y;
        return x < a.x;
    }
};
typedef Point Vector;
double cross(Vector a, Vector b) {
    return a.x * b.y - a.y * b.x;
}
double dot(Vector a, Vector b) {
    return a.x * b.x + a.y * b.y;
}
bool isclock(Point p0, Point p1, Point p2) {
    Vector a = p1 - p0;
    Vector b = p2 - p0;
    if (cross(a, b) < -eps) return true;
    return false;
}
double getDistance(Point a, Point b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
typedef vector<Point> Polygon;
Polygon andrewScan(Polygon s) {
    Polygon u, l;
    if (s.size() < 3) return s;
    sort(s.begin(), s.end());
    u.push_back(s[0]);
    u.push_back(s[1]);
    l.push_back(s[s.size() - 1]);
    l.push_back(s[s.size() - 2]);
    for (int i = 2; i < s.size(); i++) {
        for (int n = u.size(); n >= 2 && isclock(u[n - 2], u[n - 1], s[i]) != true; n--) {
            u.pop_back();
        }
        u.push_back(s[i]);
    }
    for (int i = s.size() - 3; i >= 0; i--) {
        for (int n = l.size(); n >= 2 && isclock(l[n - 2], l[n - 1], s[i]) != true; n--) {
            l.pop_back();
        }
        l.push_back(s[i]);
    }
    for (int i = 1; i < u.size() - 1; i++) l.push_back(u[i]);
    return l;
}
int cmp(double x){
    if(fabs(x) < eps) return 0;
    if(x > 0) return 1;
    return -1;
}
bool PointOnSegment(Point p, Point s, Point t){
    return cmp(cross(p-s, t-s)) == 0 && cmp(dot(p-s,p-t)) <= 0;
}
struct polygon{
    int n;
    vector<Point> a;
    polygon(vector<Point> in){
        for(auto i : in){
            a.push_back(i);
        }
        a.push_back(in.front());
        n = in.size();
    }
    bool Point_In(Point t){
        int num = 0, i, d1, d2, k;
        for(int i = 0; i < n; i++){
            if(PointOnSegment(t, a[i], a[i+1])) return 0;
            k = cmp(cross(a[i+1]-a[i], t-a[i]));
            d1 = cmp(a[i].y-t.y);
            d2 = cmp(a[i+1].y-t.y);
            if(k > 0 && d1 <= 0 && d2 > 0) num++;
            if(k < 0 && d2 <= 0 && d1 > 0) num--;
        }
        return num != 0;
    }
};
int main() {
#ifdef Wqr_
    freopen("in.txt", "r", stdin);
#endif
    std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    for(int kase = 1; kase <= t; kase++){
        cout << "Case " << kase << endl;
        int c, p;
        cin >> c >> p;
        double a, b;
        vector<Point> ps;
        for (int i = 0; i < c; i++) {
            cin >> a >> b;
            ps.push_back(Point(a, b));
        }
        vector<Point> anstmp = andrewScan(ps);
        vector<Point> ans;
        for(int i = anstmp.size() - 1; i >= 0; i--){
            ans.push_back(anstmp[i]);
        }
        int minit = 0;
        Point minP(1e5, 1e5);
        for(int i = 0; i < ans.size(); i++){
            if(ans[i] < minP){
                minit = i;
                minP = ans[i];
            }
        }
        for(int i = 0; i < ans.size(); i++){
            int cur = (i + minit) % ans.size();
            cout << ans[cur].x << " " << ans[cur].y << endl;
        }
        cout << ans[minit].x << " " << ans[minit].y << endl;
        polygon pol(ans);
        for (int i = 0; i < p; i++) {
            cin >> a >> b;
            if(pol.Point_In(Point(a, b))){
                cout << a << " " << b << " is unsafe!" << endl;
            }else{
                cout << a << " " << b << " is safe!" << endl;
            }
        }
        if(kase != t) cout << endl;
    }
    return 0;
}
-------------本文结束感谢您的阅读-------------
Powered By Valine
v1.5.2