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

Codeforces Round #620 (Div.2)

比赛链接 / 官方题解链接

A. Two Rabbits

Solution

$x+at=y-bt\Rightarrow (a+b)t=y-x$.

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

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int T;
LL x, y, a, b;

int main(){
    read(T);
    while(T--){
        read(x, y, a, b);
        if((y - x) % (a + b) == 0){
            printf("%lld\n", (y-x) / (a+b));
        } else  puts("-1");
    }
    return 0;
}

B. Longest Palindrome

Solution

设答案为 ans，则 ans 不断加上具有逆序串的字符串，输出 ans，如果有自身回文的串就任输出一个，然后 ans 翻转再输出即可。

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 105;
const int LEN = 55;

int n, m, mark;
char s[N][LEN];
bool vis[N];
string ans = "";

bool checkPalin(int a, int b){
    for(int i = 1; i <= m; i++)
        if(s[a][i] != s[b][m-i+1])
            return false;
    return true;
}

int main(){
    read(n, m);
    for(int i = 1; i <= n; i++){
        scanf("%s", s[i]+1);
        if(!mark && checkPalin(i, i)){
            vis[i] = 1;
            mark = i;
        }
    }
    for(int i = 1; i <= n; i++){
        if(vis[i])  continue;
        for(int j = 1; j < i; j++){
            if(vis[j])  continue;
            if(checkPalin(i, j)){
                vis[i] = vis[j] = 1;
                ans = ans + (s[i]+1);
            }
        }
    }
    if(mark)    printf("%d\n", 2 * (int)ans.size() + m);
    else    printf("%d\n", 2 * (int)ans.size());
    cout << ans;
    if(mark)    printf("%s", s[mark]+1);
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}

C. Air Conditioner

Solution

根据前一个人能调控到的温度范围，可以推知下一个人到来时能调控到的温度范围，与这个人的舒适温度范围取交，如此递推下去即可。

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 105;

int T, n;
LL m, t[N], l[N], h[N];

int main(){
    read(T);
    while(T--){
        read(n, m);
        for(int i = 1; i <= n; i++)
            read(t[i], l[i], h[i]);
        LL low = m, high = m;
        bool b = true;
        for(int i = 1; i <= n; i++){
            high += t[i] - t[i-1];
            low -= t[i] - t[i-1];
            high = min(high, h[i]);
            low = max(low, l[i]);
            if(low > high) {
                puts("NO");
                b = false;
                break;
            }
        }
        if(b)   puts("YES");
    }
    return 0;
}

D. Shortest and Longest LIS

Solution

最长 $LIS$ 的构造：只要上升，就上升到比当前最大值大 $1$ 处。

最短 $LIS$ 的构造：若某点后是一小段上升区间，那么保证上升幅度不要超过该点的前一个点。

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 200005;

int T, n, a[N], dp[N];
char s[N];

inline void getMax(){
    memset(a, 0, sizeof a);
    int curmax = 0, curmin = 0;
    a[1] = 0;
    for(int i = 1; i < n; i++){
        if(s[i] == '<') a[i+1] = ++curmax;
        else    a[i+1] = --curmin;
    }
    for(int i = 1; i <= n; i++)
        printf("%d ", a[i] - curmin + 1);
}
inline void getMin(){
    memset(dp, 0, sizeof dp);
    memset(a, 0, sizeof a);
    a[0] = 0; s[0] = '>';
    for(int i = n-1; i >= 0; i--){
        if(s[i] == '<') dp[i] = dp[i+1] + 1;
        else    dp[i] = 0;
    }
    int curmin = 0;
    for(int i = 0; i < n; i++){
        a[i+1] = curmin - dp[i+1] - 1;
        curmin = min(curmin, a[i+1]);
        for(int j = 1; j <= dp[i+1]; j++)
            a[i+j+1] = a[i+j] + 1;
        i += dp[i+1];
    }
    int mn = 1e9;
    for(int i = 1; i <= n; i++) mn = min(mn, a[i]);
    for(int i = 1; i <= n; i++)
        printf("%d ", a[i] - mn + 1);
}

int main(){
    read(T);
    while(T--){
        read(n);
        scanf("%s", s+1);
        getMin();
        putchar(10);
        getMax();
        putchar(10);
    }
    return 0;
}

E. 1-Trees and Queries

Solution

从 $a$ 到 $b$ 的路径可分为两种：经过了 $(x,y)$ 和未经过 $(x,y)$ 的：

  • 对于未经过 $(x,y)$ 的路径，$a,b$ 间的最短路径即原树上两点之间的简单路径，若该路径长度 $dis(a,b)$ 小于等于 $k$ 且奇偶性相同，则可达；

  • 对于经过了 $(x,y)$ 的路径，有两种可能：

    • $a\rightarrow x\rightarrow y\rightarrow b$，长 $dis(a,x)+1+dis(y,b)$.
    • $a\rightarrow y\rightarrow x\rightarrow b$，长 $dis(a,y)+1+dis(x,b)$.

    若其一长度小于等于 $k$ 且奇偶性相同，则可达。

两点之间的距离 $dis(a,b)$ 可由倍增法求 $lca$ 得到：$dis(a,b)=dep[a]+dep[b]-2*dep[lca(a,b)]$.

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
79
80
81
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 100005;

int n, u, v, q, qx, qy, qa, qb, qk;

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

int fa[N][25], dep[N];
void dfs(int x, int f, int depth){
    dep[x] = depth;
    fa[x][0] = f;
    for(int i = head[x]; i; i = edge[i].nxt){
        if(edge[i].to == f)	continue;
        dfs(edge[i].to, x, depth+1);
    }
}
void init(){
    for(int j = 1; (1 << j) <= n; j++)
        for(int i = 1; i <= n; i++)
            if(fa[i][j-1])
                fa[i][j] = fa[fa[i][j-1]][j-1];
}
int lca(int x, int y){
    if(dep[x] < dep[y])
        swap(x, y);
    for(int i = 20; i >= 0; i--)
        if(dep[x] - (1 << i) >= dep[y])
            x = fa[x][i];
    if(x == y)	return x;
    for(int i = 20; i >= 0; i--){
        if(fa[x][i] && fa[x][i] != fa[y][i]){
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    return fa[x][0];
}
inline int dis(int a, int b){ return dep[a] + dep[b] - 2 * dep[lca(a, b)]; }

int main(){
    read(n);
    for(int i = 1; i < n; i++){
        read(u, v);
        addEdge(u, v), addEdge(v, u);
    }
    dfs(1, 0, 1);
    init();
    read(q);
    while(q--){
        read(qx, qy, qa, qb, qk);
        int d = dis(qa, qb);
        if(d <= qk && (qk - d) % 2 == 0){ puts("YES"); continue; }
        d = dis(qa, qx) + 1 + dis(qy, qb);
        if(d <= qk && (qk - d) % 2 == 0){ puts("YES"); continue; }
        d = dis(qa, qy) + 1 + dis(qx, qb);
        if(d <= qk && (qk - d) % 2 == 0){ puts("YES"); continue; }
        puts("NO");
    }
    return 0;
}

F1. Animal Observation (easy version)

Solution

【参考官方题解】为方便阐述，设 $s[i][j]=\sum\limits_{i=1}^j a[i][j]$，即 $a[i][j]$ 的前缀和。又令 $Sum(i,j)$ 为第 $i$ 天在 $j\sim j+k-1$ 区域内放置摄像机能摄到的动物数量（利用 $s$ 数组 $O(1)$ 可求）

考虑 $dp$：

  • $dp$ 状态：$dp[i][j]$ 表示第 $i$ 天在 $j\sim j+k-1$ 的区域放置摄像机后，前 $i$ 天一共能摄到的最多动物数量。
  • 转移方程：分第 $i$ 天与第 $i-1$ 天无重叠和有重叠转移：
    • 无重叠之前一天在第 $i$ 天之前：$dp[i][j]=\max\limits_{l=1}^{j-k}dp[i-1][l]+Sum(i,j)$. 其中，$\max\limits_{l=1}^{j-k}dp[i-1][l]$ 可预处理前缀最大值 $O(1)$ 调用。
    • 无重叠之前一天在第 $i$ 天之后：$dp[i][j]=\max\limits_{l=j+k}^{m}dp[i-1][l]+Sum(i,j)$. 其中，$\max\limits_{l=j+k}^{m}dp[i-1][l]$ 可预处理后缀最大值 $O(1)$ 调用。
    • 两天有重叠部分：由于 $k$ 比较小，循环删去重复部分即可。
  • 转移顺序：由转移方程可知，依次循环即可。
  • 边界条件：$dp[i][j]=0$.

复杂度 $O(nmk)$

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 55;
const int M = 20005;

int n, m, k;
LL a[N][M], s[N][M], dp[N][M], pre[N][M], suf[N][M];

inline LL Sum(int i, int j){ return s[i][j+k-1] - s[i][j-1] + s[i+1][j+k-1] - s[i+1][j-1]; }

int main(){
    read(n, m, k);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            read(a[i][j]);
            s[i][j] = s[i][j-1] + a[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m-k+1; j++){
            if(j - k > 0)   dp[i][j] = max(dp[i][j], pre[i-1][j-k] + Sum(i, j));
            if(j + k <= m)  dp[i][j] = max(dp[i][j], suf[i-1][j+k] + Sum(i, j));
            for(int l = j-k+1; l <= j+k-1; l++){
                LL res = dp[i-1][l] + Sum(i, j);
                if(i > 1){
                    if(l < j)   res -= s[i][l+k-1] - s[i][j-1];
                    else        res -= s[i][j+k-1] - s[i][l-1];
                }
                dp[i][j] = max(dp[i][j], res);
            }
            pre[i][j] = max(pre[i][j-1], dp[i][j]);
        }
        for(int j = m-k+1; j >= 1; j--)
            suf[i][j] = max(suf[i][j+1], dp[i][j]);
    }
    LL ans = -1;
    for(int j = 1; j <= m; j++)
        ans = max(ans, dp[n][j]);
    printf("%lld\n", ans);
    return 0;
}

F2. Animal Observation (hard version)

Solution

【参考官方题解】需要把 easy version 中转移方程用数据结构维护。

三类转移方程其实可归为一个问题：求 $dp[i-1]$ 中减去重叠部分（可能为 $0$）后的最大值。对于每个 $i$，建立一颗以 $dp[i-1]$ 为基础的线段树，显然重叠部分不能循环 $j$，然后一个一个的暴力减，但我们可以用类似滑动窗口的做法做——首先减去 $dp[i][1]$ 的重叠部分，这 $k$ 个直接一个一个减就行了；然后假设我们已经减去了 $dp[i][j-1]$ 的重叠部分，在减 $dp[i][j]$ 的重叠部分时，窗口往右滑，只需要把不再覆盖 $a[i][j-1]$ 的区间 $[\max(1, j-k), j-1]$ 加回 $a[i][j-1]$，把新的覆盖了 $a[i][j+k-1]$ 的区间 $[j, \min(j+k-1, m-k+1)]$ 减去 $a[i][j+k-1]$ 即可。

复杂度 $O(nm\lg m)$

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
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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 55;
const int M = 20005;

int n, m, k;
LL a[N][M], s[N][M], dp[N][M];

inline LL Sum(int i, int j){ return s[i][j+k-1] - s[i][j-1] + s[i+1][j+k-1] - s[i+1][j-1]; }

struct segTree{
    int l, r;
    LL mx, lazy;
}tr[M<<2];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l+tr[id].r)>>1)
#define len(id) (tr[id].r - tr[id].l + 1)
inline void pushup(int id){
    tr[id].mx = max(tr[lid].mx, tr[rid].mx);
}
inline void pushdown(int id){
    if(tr[id].l == tr[id].r)    return;
    if(tr[id].lazy){
        tr[lid].lazy += tr[id].lazy;
        tr[lid].mx += tr[id].lazy;
        tr[rid].lazy += tr[id].lazy;
        tr[rid].mx += tr[id].lazy;
        tr[id].lazy = 0;
    }
}
void build(int id, int l, int r, LL v[]){
    tr[id].l = l, tr[id].r = r;
    tr[id].mx = tr[id].lazy = 0;
    if(tr[id].l == tr[id].r){
        tr[id].mx = v[l];
        tr[id].lazy = 0;
        return;
    }
    build(lid, l, mid, v);
    build(rid, mid+1, r, v);
    pushup(id);
}
void add(int id, int l, int r, LL v){
    pushdown(id);
    if(tr[id].l == l && tr[id].r == r){
        tr[id].lazy += v;
        tr[id].mx += v;
        return;
    }
    if(r <= mid)    add(lid, l, r, v);
    else if(l > mid)    add(rid, l, r, v);
    else    add(lid, l, mid, v), add(rid, mid+1, r, v);
    pushup(id);
}
LL queryMax(int id, int l, int r){
    pushdown(id);
    if(tr[id].l == l && tr[id].r == r)  return tr[id].mx;
    if(r <= mid)    return queryMax(lid, l, r);
    else if(l > mid)    return queryMax(rid, l, r);
    else    return max(queryMax(lid, l, mid), queryMax(rid, mid+1, r));
}

int main(){
    read(n, m, k);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            read(a[i][j]);
            s[i][j] = s[i][j-1] + a[i][j];
        }
    }
    for(int j = 1; j <= m-k+1; j++)
        dp[1][j] = Sum(1, j);
    for(int i = 2; i <= n; i++){
        build(1, 1, m, dp[i-1]);
        for(int j = 1; j <= k; j++)
            add(1, j, j, -(s[i][k] - s[i][j-1]));
        dp[i][1] = queryMax(1, 1, m-k+1) + Sum(i, 1);
        for(int j = 2; j <= m-k+1; j++){
            add(1, max(1, j-k), j-1, a[i][j-1]);
            add(1, j, min(j+k-1, m-k+1), -a[i][j+k-1]);
            dp[i][j] = queryMax(1, 1, m-k+1) + Sum(i, j);
        }
    }
    LL ans = -1;
    for(int j = 1; j <= m; j++)
        ans = max(ans, dp[n][j]);
    printf("%lld\n", ans);
    return 0;
}

Codeforces Round #620 (Div.2)

http://xyfjason.github.io/blog-xcpc/2020/02/15/Codeforces-Round-620-Div-2/

作者

xyfJASON

发布于

2020-02-15

更新于

2020-12-20

许可协议

#

评论

关注我

分类

最新文章

标签

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