hyz's blog
0%

发表于

训练赛套题链接：2018, XI Samara Regional Intercollegiate Programming Contest

感觉题目难度很友好，官方说是给蓝紫名选手做的。

A题

据说是水题，略。

B题

队友做的，留坑待填。

C题

这种区间求最优解的问题，一种套路就是排序+贪心。具体对这道题来说，即按照右边界、左边界从小到大排序，然后贪心地取右边界的点，同时跳过左边界在该点左边的那些区间，时间复杂度是O(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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok puts("ok");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=2e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

bool cmp(pii a, pii b) {
    if(a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

int mark, n, ans;
pii a[N];
vi v;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> n) {
        for(int i = 0; i < n; i++)
            scanf("%d%d", &a[i].x, &a[i].y);
        sort(a, a+n, cmp);
        ans = 0;
        v.clear();
        for(int i = 0; i < n; ) {
            mark = a[i].y;
            ans++;
            v.push_back(mark);
            while(i < n && a[i].x <= mark) i++;
        }
        printf("%d\n", ans);
        for(int i = 0; i < v.size(); i++)
            printf("%d%c", v[i], i==v.size()-1?'\n':' ');
    }
    return 0;
}

D题

不会，留坑。

E题

假如两个字符串相同，那么输出“YES”。

否则，从左往右找到第一个不同，然后从右往左找到第一个不同，翻转这个区间的字符串，判断是否能让两个字符串相同。可以输出”YES”，不可以输出”NO”。

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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok puts("ok");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

string s, t;
int l, r, len, j;
bool flag;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> s >> t) {
        len = s.length();
        l = r = -1;
        for(int i = 0; i < len; i++)
            if(s[i] != t[i]) {
                l = i;
                break;
            }
        for(int i = len; i > 0; i--)
            if(s[i] != t[i]) {
                r = i;
                break;
            }
        if(l == -1)
            printf("YES\n");
        else {
            flag = true;
            for(int i = l; i <= r; i++) {
                j = r - i + l;
                if(s[i] != t[j]) {
                    flag = false;
                    break;
                }
            }
            if(flag)
                printf("YES\n");
            else
                printf("NO\n");
        }

    }

    return 0;
}

F题

不会，留坑。

G题

不会，留坑。
传送门

H题

这道题主要的难题在于ban掉怪兽能攻击到的区域，赛后经大佬指点，学会了多源bfs这种操作，新技能get :)

由n*m<=200000，可得1 <= n <= 200000，1 <= ｍ <= 200000，所以不能开普通的二维数组，要开vector。比赛的时候没用vector，而是弄了个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
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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok puts("ok");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=2e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

int cnt, n, m, dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, vis[N], ban[N], sx, sy, gx, gy, d, dis[N], b[N];
string g[N];
vector<pii> v;

inline bool check(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

inline int id(pii t) {
    return t.x * m + t.y;
}

inline int id(int x, int y) {
    return x * m + y;
}

//多源bfs
void banbfs() {
    queue<pii> que;
    for(int i = 0; i < v.size(); i++) {
        que.push(pii(v[i].x, v[i].y));
        vis[id(v[i])] = 1;
        b[id(v[i])] = d;
    }
    while(que.size()) {
        pii u = que.front();
        que.pop();
        if(b[id(u)] == 0) break;
        for(int i = 0; i < 4; i++) {
            int nx = u.x + dx[i], ny = u.y + dy[i];
            if(check(nx, ny) && !vis[id(nx, ny)]) {
                vis[id(nx, ny)] = 1;
                ban[id(nx, ny)] = 1;
                b[id(nx, ny)] = b[id(u)] - 1;
                que.push(pii(nx, ny));
            }
        }
    }
}

void bfs() {
    banbfs();
    queue<pii> que;
    if(!ban[id(sx, sy)])
        que.push(pii(sx, sy));
    memset(dis, -1, sizeof dis);
    dis[id(pii(sx, sy))] = 0;
    vis[id(sx, sy)] = 1;
    while(que.size()) {
        pii u = que.front();
        que.pop();
        if(u.x == gx && u.y == gy) {
            break;
        }
        for(int i = 0; i < 4; i++) {
            int nx = u.x + dx[i], ny = u.y + dy[i];
            if(check(nx, ny) && !vis[id(nx, ny)] && !ban[id(nx, ny)]) {
                que.push(pii(nx, ny));
                vis[id(nx, ny)] = 1;
                dis[id(pii(nx, ny))] = dis[id(u)] + 1;
            }
        }
    }
    printf("%d\n", dis[id(pii(gx, gy))]);
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> n >> m >> d) {
        for(int i = 0; i < n; i++)
            cin >> g[i];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++) {
                if(g[i][j] == 'S')
                    sx = i, sy = j;
                else if(g[i][j] == 'M')
                    v.push_back(pii(i, j));
                else if(g[i][j] == 'F')
                    gx = i, gy = j;
            }
        bfs();
    }

    return 0;
}

I题

给了一些边，每条边最多只能用一次，现在需要判断所有的边能最多能组成多少的平行四边形。根据平行四边形的性质，答案就是边长相等的边的对数除以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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok puts("ok");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=2e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

int a[N], n, ans, d;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> n) {
        memset(a, 0, sizeof a);
        for(int i = 0; i < n; i++) {
            scanf("%d", &d);
            a[d]++;
        }
        ans = 0;
        for(int i = 0; i < N; i++)
            ans += a[i]/2;
        printf("%d\n", ans/2);
    }

    return 0;
}

J题

不会，留坑。

K题

不会，留坑。

L题

首先开26个set，将相同字母的位置压进同一个set里面。

当push 某个字母时，就在这个字母的set里面查找第一个大于当前位置的位置。假如找不到，那么就是NO，假如找到了，那么就是YES。不管是YES还是NO，都要先把旧位置放进栈里面，然后更新当前位置（NO时就更新为INF）。

当pop某个字母时，就将当前位置更新为栈顶元素，判断栈顶元素是否为INF，假如为INF，那就是NO，否则为YES。

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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok puts("ok");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

string s;
char op[9], c;
int m, t;
set<int> se[29];
stack<int> sta;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> s) {
        for(int i = 0; i < s.length(); i++)
            se[s[i]-'a'].insert(i);
        scanf("%d", &m);
        int pp = -1;
        while(m--) {
            scanf("%s", op);
            getchar();
            if(op[1] == 'u') {
                c = getchar();
                t = c - 'a';
                set<int>::iterator it = se[t].upper_bound(pp);
                sta.push(pp);
                if(it != se[t].end()) {
                    pp = *it;
                    printf("YES\n");
                }
                else {
                    pp = INF;
                    printf("NO\n");
                }
            }
            else {
                pp = sta.top();
                sta.pop();
                if(pp == INF)
                    printf("NO\n");
                else
                    printf("YES\n");
            }
        }
    }
    return 0;
}

M题

这道题要分情况讨论。

  1. 三个字符串完全相同，Ambiguous。
  2. 存在两个字符串的差异值大于2，Impossible。
  3. 然后两两枚举不同的位置，再与剩余的另一个字符串diff，假如差异值大于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
#include<bits/stdc++.h>
#define x first
#define y second
#define ok puts("ok");
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const int shift=1e3+9;
const double Eps=1e-7;

string s1, s2, s3, t;
vi v[3];
set<string> se;
bool flag;
int len, cnt;

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(cin >> s1 >> s2 >> s3) {
        v[0].clear();
        v[1].clear();
        v[2].clear();
        len = s1.length();
        for(int i = 0; i < len; i++) {
            if(s1[i] != s2[i])
                v[0].push_back(i);
            if(s2[i] != s3[i])
                v[1].push_back(i);
            if(s1[i] != s3[i])
                v[2].push_back(i);
        }
        flag = true;
        for(int i = 0; i < 3; i++)
            if(v[i].size() > 2)
                flag = false;
        if(!flag)
            printf("Impossible\n");
        else if(v[0].size() == 0 && v[1].size() == 0 && v[2].size() == 0)
            printf("Ambiguous\n");
        else {
            se.clear();
            for(int i = 0; i < v[0].size(); i++) {
                t = s1;
                t[v[0][i]] = s2[v[0][i]];
                cnt = 0;
                for(int j = 0; j < len; j++)
                    if(t[j] != s3[j])
                        cnt++;
                if(cnt <= 1)
                    se.insert(t);
            }
            for(int i = 0; i < v[1].size(); i++) {
                t = s2;
                t[v[1][i]] = s3[v[1][i]];
                cnt = 0;
                for(int j = 0; j < len; j++)
                    if(t[j] != s1[j])
                        cnt++;
                if(cnt <= 1)
                    se.insert(t);
            }
            for(int i = 0; i < v[2].size(); i++) {
                t = s3;
                t[v[2][i]] = s1[v[2][i]];
                cnt = 0;
                for(int j = 0; j < len; j++)
                    if(t[j] != s2[j])
                        cnt++;
                if(cnt <= 1)
                    se.insert(t);
            }
            if(se.size() == 1)
                cout << *se.begin() << endl;
            else if(se.size() == 0)
                printf("Impossible\n");
            else
                printf("Ambiguous\n");
        }

    }

    return 0;
}