发表更新ICPC/CCPC / Contests / Codeforces10 分钟读完 (大约1450个字)

Codeforces Round #617 (Div.3)

比赛链接 / 官方题解链接

A. Array with Odd Sum

略

B. Food Buying

略

C. Yet Another Walking Robot

Solution

用 STL 的 map 记录上一次到达该位置的时间即可。

Code

>folded
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
#include<map>
#include<cstdio>
#include<algorithm>

using namespace std;

typedef pair<int, int> pii;
#define mp(x,y) make_pair(x,y)

const int N = 200005;

int T, n, ans = 1e9, ansl, ansr;
char s[N];

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        scanf("%s", s+1);
        map<pii, int> m;
        pii now = mp(0,0);
        m[now] = 1;
        ansl = ansr = 0, ans = 1e9;
        for(int i = 1; i <= n; i++){
            if(s[i] == 'U') now.second++;
            if(s[i] == 'D') now.second--;
            if(s[i] == 'L') now.first--;
            if(s[i] == 'R') now.first++;
            if(m[now] > 0)
                if(i + 1 - m[now] < ans)
                    ans = i + 1 - m[now], ansl = m[now], ansr = i;
            m[now] = i + 1;
        }
        if(ansl == ansr && ansl == 0)   puts("-1");
        else    printf("%d %d\n", ansl, ansr);
    }
    return 0;
}

D. Fight with Monsters

Solution

对于每个怪物都能 $O(1)$ 地获知要得分需要用多少次技能，根据技能消耗数从小到大依次取即可。

Code

>folded
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
#include<cstdio>
#include<queue>

using namespace std;

typedef long long LL;
const int N = 200005;
int n; LL a, b, k, h, ans, kk;
priority_queue<LL, vector<LL>, greater<LL> > q;

int main(){
    scanf("%d%lld%lld%lld", &n, &a, &b, &k);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &h);
        if(h % (a + b) <= a && h % (a + b) != 0)    ans++;
        else{
            LL m = h % (a + b); if(m == 0) m = a + b;
            LL tim = m / a + 1; if(m % a == 0) tim--;
            q.push(tim - 1);
        }
    }
    while(!q.empty()){
        if(kk + q.top() <= k){
            kk += q.top();
            q.pop();
            ans++;
        } else  break;
    }
    printf("%lld\n", ans);
    return 0;
}

E1. String Coloring (easy version)

Solution #1

首先有结论：只需所有逆序对的颜色不同即可，因为易知存在一种排序方式只交换逆序对。

于是我们可以给所有逆序对两两连边建图，然后二染色即可。

复杂度 $O(n^2)$

Solution #2

进一步思考，每个元素的颜色只需与在它之前出现的且大于它的所有元素的颜色不同即可。所以我们可以从颜色的角度出发，记录每个颜色染到的元素最大值，那么循环每个元素，若能染色为0，染为0；否则若能染色为1，染为1；否则无解。

复杂度 $O(n)$

Code —- $O(n^2)$

>folded
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>

using namespace std;

const int N = 205;

int n;
char s[N];
bool con[N];

struct Edge{
    int nxt, to;
}edge[N*N];
int head[N], edgeNum;
void addEdge(int from, int to){
    edge[++edgeNum] = (Edge){head[from], to};
    head[from] = edgeNum;
}

bool able;
int col[N];
void dfs(int x, int c){
    if(!able)   return;
    if(col[x] != -1){
        if(col[x] != c){
            col[x] = -1;
            able = false;
        }
        return;
    }
    col[x] = c;
    for(int i = head[x]; i; i = edge[i].nxt)
        dfs(edge[i].to, c ^ 1);
}

int main(){
    scanf("%d", &n);
    scanf("%s", s+1);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(s[j] > s[i]){
                addEdge(i, j);
                addEdge(j, i);
                con[j] = con[i] = true;
            }
        }
    }
    able = true;
    memset(col, -1, sizeof col);
    for(int i = 1; i <= n; i++){
        if(col[i] == -1){
            if(con[i])  dfs(i, 0);
            else    col[i] = 0;
        }
    }
    if(!able)   puts("NO");
    else{
        puts("YES");
        for(int i = 1; i <= n; i++)
            printf("%d", col[i]);
        puts("");
    }
    return 0;
}

Code —- $O(n)$

>folded
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<cstdio>

using namespace std;

const int N = 205;

int n, col[N];
char s[N], maxch[N];

int main(){
    scanf("%d", &n);
    scanf("%s", s+1);
    for(int i = 1; i <= n; i++){
        if(maxch[0] <= s[i])    maxch[col[i] = 0] = s[i];
        else if(maxch[1] <= s[i])   maxch[col[i] = 1] = s[i];
        else    return puts("NO"), 0;
    }
    puts("YES");
    for(int i = 1; i <= n; i++) printf("%d", col[i]);
    return 0;
}

E2. String Coloring (hard version)

Solution

沿袭 E1 的 Solution #2 的思路，只不过 E2 的颜色数增加了而已，于是我们可以以颜色为下标建立线段树，像值域线段树那样查找最小的值不比当前元素大的颜色。

复杂度 $O(n\lg n)$

Code

>folded
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
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 200005;
const int INF = 1e9;

int n;
char s[N];

struct segTree{
    int l, r, mn;
}tr[N<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
inline void pushup(int id){
    tr[id].mn = min(tr[lid].mn, tr[rid].mn);
}
void build(int id, int l, int r){
    tr[id].l = l, tr[id].r = r;
    tr[id].mn = 0;
    if(tr[id].l == tr[id].r)    return;
    build(lid, l, mid);
    build(rid, mid+1, r);
    pushup(id);
}
void modify(int id, int x, int val){
    if(tr[id].l == tr[id].r){
        tr[id].mn = val;
        return;
    }
    if(x <= mid)    modify(lid, x, val);
    else    modify(rid, x, val);
    pushup(id);
}
int query(int id, int val){
    if(tr[id].l == tr[id].r)    return tr[id].l;
    if(tr[lid].mn <= val)  return query(lid, val);
    else    return query(rid, val);
}

int col[N], cnt;
bool appeared[N];

int main(){
    scanf("%d", &n);
    scanf("%s", s+1);
    build(1, 1, n);
    for(int i = 1; i <= n; i++){
        int q = query(1, s[i]-'a'+1);
        modify(1, q, s[i]-'a'+1);
        col[i] = q;
        if(!appeared[q])    cnt++, appeared[q] = true;
    }
    printf("%d\n", cnt);
    for(int i = 1; i <= n; i++)
        printf("%d ", col[i]);
    return 0;
}

F. Berland Beauty

Solution

根据 $g_i$ 的值从大到小排序，依次拿到路径上赋值，一条边的值为当前值和 $g_i$ 的最大值，赋值结束后还没值的边赋为1e6，随后把所有条件验证一遍，验证不过输出 -1，验证通过输出答案。

复杂度 $O(n^2)$

Code

>folded
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
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 5005;
const int INF = 1e9;

int n, u[N], v[N], m, val[N][N];
vector<int> edge[N];
struct Node{
    int u, v, g;
    bool operator < (const Node &A) const{
        return g > A.g;
    }
}q[N];

vector<int> vec;
bool found, vis[N], check;
void dfs(int x, int y, int minval, int kind){
    if(found)   return;
    vis[x] = true;
    vec.push_back(x);
    if(x == y){
        int minn = INF;
        for(int i = 1; i < vec.size(); i++){
            if(kind == 0)   val[vec[i]][vec[i-1]] = val[vec[i-1]][vec[i]] = max(val[vec[i-1]][vec[i]], minval);
            else    minn = min(minn, val[vec[i]][vec[i-1]]);
        }
        found = true;
        if(kind == 1 && minn != minval){
            puts("-1");
            exit(0);
        }
        return;
    }
    for(int i = 0; i < edge[x].size(); i++)
        if(!vis[edge[x][i]])
            dfs(edge[x][i], y, minval, kind);
    vec.pop_back();
    vis[x] = false;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u[i], &v[i]);
        edge[u[i]].push_back(v[i]);
        edge[v[i]].push_back(u[i]);
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; i++){
        scanf("%d%d%d", &q[i].u, &q[i].v, &q[i].g);
        if(q[i].u > q[i].v) swap(q[i].u, q[i].v);
    }
    sort(q+1, q+m+1);
    for(int i = 1; i <= m; i++){
        vec.clear();
        found = false;
        memset(vis, 0, sizeof vis);
        dfs(q[i].u, q[i].v, q[i].g, 0);
    }
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(val[i][j] == 0)
                val[i][j] = 1e6;
    for(int i = 1; i <= m; i++){
        vec.clear();
        found = false;
        memset(vis, 0, sizeof vis);
        dfs(q[i].u, q[i].v, q[i].g, 1);
    }
    for(int i = 1; i < n; i++)
        printf("%d ", val[u[i]][v[i]] > 1000000 ? 1000000 : val[u[i]][v[i]]);
    return 0;
}

Codeforces Round #617 (Div.3)

http://xyfjason.github.io/blog-xcpc/2020/02/05/Codeforces-Round-617-Div-3/

作者

xyfJASON

发布于

2020-02-05

更新于

2020-12-20

许可协议

#

评论

关注我

分类

最新文章

标签

AtCoder2
CCPC2
Codeforces57
EOJ1
GMCPC1
HDU11
ICPC3
Nowcoder12
POI1
hihoCoder1
学习笔记17
随笔1
×