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

Codeforces Round #619 (Div.2)

比赛链接 / 官方题解链接

A. Three Strings

Solution

$a_i,b_i$ 相同则 $c_i$ 必须也相同，$a_i,b_i$ 不同则 $c_i$ 必须与其中一个相同。

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>

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 = 205;

int T;
char a[N], b[N], c[N];

int main(){
    read(T);
    while(T--){
        scanf("%s", a+1);
        scanf("%s", b+1);
        scanf("%s", c+1);
        int n = strlen(a+1);
        bool ok = true;
        for(int i = 1; i <= n; i++){
            if(a[i] == b[i]){
                if(c[i] != a[i]){
                    ok = false;
                    break;
                }
            }
            else{
                if(!(c[i] == a[i] || c[i] == b[i])){
                    ok = false;
                    break;
                }
            }
        }
        if(!ok) puts("NO");
        else    puts("YES");
    }
    return 0;
}

B. Motarack’s Birthday

Solution

二分最小差值 $m$，check 时，对于每一个 $?$，设其旁边的数为 $x$，则 $?$ 的取值范围为 $[x-m,x+m]$，判断所有这样的区间交集是否为空。

Better Solution

可以 $O(n)$ 的…… $k$ 取 $\frac{min+max}{2}$ 就好……

Code

$O(n\lg n)$:

>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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>

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 T, n;
LL a[N], k;

bool check(LL m){
    LL l = -1e14, r = 1e14;
    for(int i = 1; i <= n; i++){
        if(a[i] == -1){
            if(i != 1 && a[i-1] != -1)
                l = max(l, a[i-1] - m), r = min(r, a[i-1] + m);
            if(i != n && a[i+1] != -1)
                l = max(l, a[i+1] - m), r = min(r, a[i+1] + m);
        }
    }
    if(l <= r)  k = l;
    return l <= r;
}

int main(){
    read(T);
    while(T--){
        read(n);
        LL gap = -1e16;
        for(int i = 1; i <= n; i++){
            read(a[i]);
            if(i != 1 && a[i] != -1 && a[i-1] != -1)
                gap = max(gap, max(a[i] - a[i-1], a[i-1] - a[i]));
        }
        LL l = 0, r = 1e9;
        while(l < r){
            LL mid = (l + r) >> 1;
            if(check(mid))  r = mid;
            else    l = mid + 1;
        }
        if(k < 0 || k > 1e9)    k = 1;
        printf("%lld %lld\n", max(gap, l), k);
    }
    return 0;
}

C. Ayoub’s function

Solution

直觉告诉我们，把 $1$ 尽可能均分是最优的，事实上可以严谨证明。

证：设序列为 $\underbrace{00\cdots0}_{a_1个0}1\underbrace{00\cdots0}_{a_2个0}1\cdots1\underbrace{00\cdots0}_{a_l个0}$，且 $\sum\limits_{i=1}^l a_i=n-m$. 要求的 $f(s)$ 可以看作所有区间个数减去不含 $1$ 的区间个数，即

恒等变形：

根据均值不等式，上式后一项在 $a_1=a_2=\cdots=a_l$ 时最小，$f(s)$ 最大，证毕.

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>

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 T;
LL n, m, ans;

int main(){
    read(T);
    while(T--){
        read(n, m);
        ans = n * (n + 1) / 2;
        LL C = n - m;
        LL bs = C / (m + 1), res = C - bs * (m + 1);
        ans -= (m + 1 - res) * bs * (bs + 1) / 2 + res * (bs + 1) * (bs + 2) / 2;
        printf("%lld\n", ans);
    }
    return 0;
}

D. Time to Run

Solution

可以找到一条路径经过所有 $4nm-2n-2m$ 条边，我找的是形如下图的路径：

然后就是模拟了……

Code

【以下代码参考了 MiFaFaOvO 的代码，因为我的模拟实在是太丑了……】

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

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;
typedef pair<int, string> pis;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

int n, m, k;
vector< pis > steps, ans;

int main(){
    read(n, m, k);
    if(4 * n * m - 2 * n - 2 * m < k)   return puts("NO"), 0;
    puts("YES");
    if(m == 1){
        if(k <= m - 1)  return printf("1\n%d D\n", k), 0;
        return printf("2\n%d D\n%d U\n", n - 1, k - n + 1), 0;
    }
    steps.pb( mp(m-1, "R") );
    steps.pb( mp(m-1, "L") );
    for(int i = 1; i < n; i++){
        steps.pb( mp(m-1, "DRU") );
        steps.pb( mp(1, "D") );
        steps.pb( mp(m-1, "L") );
    }
    steps.pb( mp(n-1, "U") );
    int size = steps.size(), x;
    for(x = 0; x < size; x++){
        if(k >= steps[x].first * (steps[x].second.size())){
            k -= steps[x].first * (steps[x].second.size());
            if(steps[x].first)  ans.pb(steps[x]);
        }
        else{
            int len = steps[x].second.size();
            if(k / len) ans.pb( mp(k / len, steps[x].second) );
            if(k % len) ans.pb( mp(1, steps[x].second.substr(0, k % len)) );
            k = 0;
        }
    }
    printf("%d\n", (int)ans.size());
    for(int i = 0; i < ans.size(); i++)
        printf("%d %s\n", ans[i].first, ans[i].second.c_str());
    return 0;
}

E. Nanosoft

Solution

【参考官方题解】先用 $O(n^2)$ 的 $dp$ 得到每个方块作为红色右下角、黄色右上角、绿色左下角、蓝色左上角的最大色块边长，再用这些信息得到每个方块作为红色右下角能扩展出来的最大 $logo$ 大小。也即每个 $logo$ 都可以用红色右下角的方块的数值表示。

对于每次询问，二分答案（实际上二分的是 $logo$ 的半边长），check 时找到对应的区域（区域由可作为红色右下角的方块构成），判断区域内最大值是否大于等于二分的半边长。

区域内最大值用二维 ST 表维护。

复杂度 $O(n^2+n^2\lg^2n+q\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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<algorithm>
#include<cstdio>
#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...);}

const int N = 505;

int n, m, q, r1, c1, r2, c2;
char g[N][N];
int R[N][N], a[N][N];
int Y[N][N], G[N][N], B[N][N];

int lg[N], rmq[N][N][10][10];
void pre(){
    lg[1] = 0, lg[2] = 1;
    for(int i = 3; i <= max(n, m); i++) lg[i] = lg[i/2] + 1;
}
void init(){
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            rmq[i][j][0][0] = a[i][j];
    for(int ki = 0; (1 << ki) <= n; ki++){
        for(int kj = 0; (1 << kj) <= m; kj++){
            if(!ki && !kj)  continue;
            for(int i = 1; i + (1 << ki) - 1 <= n; i++){
                for(int j = 1; j + (1 << kj) - 1 <= m; j++){
                    if(!ki) rmq[i][j][ki][kj] = max(rmq[i][j][ki][kj-1], rmq[i][j+(1<<(kj-1))][ki][kj-1]);
                    else    rmq[i][j][ki][kj] = max(rmq[i][j][ki-1][kj], rmq[i+(1<<(ki-1))][j][ki-1][kj]);
                }
            }
        }
    }
}
int query(int u, int l, int d, int r){
    int k1 = lg[d - u + 1], k2 = lg[r - l + 1];
    return max(max(rmq[u][l][k1][k2], rmq[d-(1<<k1)+1][r-(1<<k2)+1][k1][k2]),
               max(rmq[d-(1<<k1)+1][l][k1][k2], rmq[u][r-(1<<k2)+1][k1][k2]));
}
bool check(int mid, int u, int l, int d, int r){
    return query(u, l, d, r) >= mid;
}

int main(){
    read(n, m, q);
    for(int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(g[i][j] == 'R')
                R[i][j] = 1 + min(R[i-1][j-1], min(R[i-1][j], R[i][j-1]));
    for(int i = n; i >= 1; i--)
        for(int j = 1; j <= m; j++)
            if(g[i][j] == 'Y')
                Y[i][j] = 1 + min(Y[i+1][j-1], min(Y[i][j-1], Y[i+1][j]));
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 1; j--)
            if(g[i][j] == 'G')
                G[i][j] = 1 + min(G[i-1][j+1], min(G[i][j+1], G[i-1][j]));
    for(int i = n; i >= 1; i--)
        for(int j = m; j >= 1; j--)
            if(g[i][j] == 'B')
                B[i][j] = 1 + min(B[i+1][j+1], min(B[i][j+1], B[i+1][j]));
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(g[i][j] == 'R' && g[i+1][j] == 'Y' && g[i][j+1] == 'G' && g[i+1][j+1] == 'B')
                a[i][j] = min(min(R[i][j], Y[i+1][j]), min(G[i][j+1], B[i+1][j+1]));
    pre();
    init();
    while(q--){
        read(r1, c1, r2, c2);
        int l = 0, r = min((r2 - r1 + 1) / 2, (c2 - c1 + 1) / 2);
        while(l < r){
            int mid = (l + r + 1) >> 1;
            if(check(mid, r1 + mid - 1, c1 + mid - 1, r2 - mid, c2 - mid))  l = mid;
            else    r = mid - 1;
        }
        printf("%d\n", 4 * l * l);
    }
    return 0;
}

F. Super Jaber

Solution

【参考官方题解】设 $d[color][i][j]$ 为从 $i$ 行 $j$ 列的格子到一个颜色为 $color$ 的格子的最小步数，于是枚举颜色，以所有该颜色的格子为起点，bfs 求之。求答案时，枚举中间的桥梁颜色 $c$，则 ans=min(ans, d[c][r1][c1] + d[c][r2][c2] + 1)（+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
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
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>

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 pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

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

int n, m, k, a[N][N], q, r1, r2, c1, c2;
int d[45][N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
bool vis[45];
vector<pii> v[45];

inline void bfs(int col){
    queue< pii > que;
    memset(vis, 0, sizeof vis);
    for(int i = 0; i < v[col].size(); i++){
        que.push(v[col][i]);
        d[col][v[col][i].first][v[col][i].second] = 0;
    }
    vis[col] = 1;
    while(!que.empty()){
        int x = que.front().first, y = que.front().second;
        que.pop();
        if(!vis[a[x][y]]){
            vis[a[x][y]] = true;
            for(int i = 0; i < v[a[x][y]].size(); i++){
                int tx = v[a[x][y]][i].first, ty = v[a[x][y]][i].second;
                if(d[col][tx][ty] == -1){
                    d[col][tx][ty] = d[col][x][y] + 1;
                    que.push( mp(tx, ty) );
                }
            }
        }
        for(int i = 0; i < 4; i++){
            int tx = x + dx[i], ty = y + dy[i];
            if(tx > 0 && tx <= n && ty > 0 && ty <= m && d[col][tx][ty] == -1){
                d[col][tx][ty] = d[col][x][y] + 1;
                que.push( mp(tx, ty) );
            }
        }
    }
}

int main(){
    read(n, m, k);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            read(a[i][j]);
            v[a[i][j]].pb( mp(i, j) );
        }
    memset(d, -1, sizeof d);
    for(int i = 1; i <= k; i++) bfs(i);
    read(q);
    while(q--){
        read(r1, c1, r2, c2);
        int ans = abs(r1 - r2) + abs(c1 - c2);
        for(int kk = 1; kk <= k; kk++)
            ans = min(ans, d[kk][r1][c1] + d[kk][r2][c2] + 1);
        printf("%d\n", ans);
    }
    return 0;
}

Codeforces Round #619 (Div.2)

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

作者

xyfJASON

发布于

2020-02-14

更新于

2020-12-20

许可协议

#

评论

关注我

分类

最新文章

标签

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