@Dmaxiya 2019-01-16T16:47:11.000000Z 字数 7550 阅读 1156

Educational Codeforces Round 58

Codeforces

Contests 链接：Educational Codeforces Round 58
过题数：4
排名：985/6146

A. Minimum Integer

题意

输出不在范围 $[l,r]$ 内的最小的正整数 $x$ ，要求 $x$ 是 $d$ 的整数倍。

输入

第一行为一个整数 $q~(1\leq q\leq500)$ ，接下去有 $q$ 行，第 $i$ 行的三个整数分别为 $l_i,r_i,d_i~(1\leq l_i\leq r_i\leq10^9,1\leq d_i\leq10^9)$ 。

输出

对于每一行询问，输出对应的答案。

样例

输入
5 2 4 2 5 10 4 3 10 1 1 2 3 4 6 5
输出
6 4 1 3 10

题解

若 $d$ 在 $[l,r]$ 范围内，则输出 $(\lfloor\frac{r}{d}\rfloor+1)\times d$ ，否则输出 $d$ 。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
int T;
int l, r, x;
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &l, &r, &x);
        if(x >= l && x <= r) {
            printf("%d\n", r / x * x + x);
        } else {
            printf("%d\n", x);
        }
    }
    return 0;
}

B. Accordion

题意

用一个字符串来表示一个手风琴，其必须要满足的格式为：由 [ 开头，接着是一个 :，往后是连续的多个或零个 |，接着是一个 : 和 ]。给定一个字符串，问能否通过删除一些字符，使得最终剩下的字符串可以表示成一个手风琴，若能，求最长剩余字符串长度。

输入

输入仅包含一个字符串 $s~(1\leq|s|\leq5\times10^5)$ ，其中只包含小写字母以及 [、]、:、| 这几种符号。

输出

如果无法满足题意，则输出 $-1$ ，否则输出能表示成手风琴的最长的字符串。

样例

输入
`\|[a:b:\|]`
输出
4

输入
`\|]:[\|:]`
输出
-1

题解

先找出最左边的 [ 下标 $l$ 以及最右边的 ] 的下标 $r$ ，要求 $l<r$ ，接着找在 [l,r] 范围内最左边的 : 以及最右边的 :，最后将这两个冒号间所有的 | 个数统计出来，答案就是 | 的个数 $+4$ 。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 500000 + 100;
int len;
char str[maxn];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%s", str + 1) != EOF) {
        len = strlen(str + 1);
        int l = -1;
        int r = -1;
        for(int i = 1; i <= len; ++i) {
            if(str[i] == '[') {
                l = i;
                break;
            }
        }
        for(int i = len; i >= 1; --i) {
            if(str[i] == ']') {
                r = i;
                break;
            }
        }
        if(l == -1 || r == -1 || r <= l) {
            printf("-1\n");
            continue;
        }
        int ll = -1;
        int rr = -1;
        for(int i = l + 1; i < r; ++i) {
            if(str[i] == ':') {
                if(ll == -1) {
                    ll = i;
                }
                rr = i;
            }
        }
        if(ll == -1 || rr == -1 || ll >= rr) {
            printf("-1\n");
            continue;
        }
        int ans = 4;
        for(int i = ll + 1; i < rr; ++i) {
            if(str[i] == '|') {
                ++ans;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

C. Division and Union

题意

给定 $n$ 条线段，第 $i$ 条线段的两个端点分别为 $[l_i,r_i]$ ，将这 $n$ 条线段分别放入两个非空集合中，要求从这两个集合中分别任意取一条线段出来，这两条线段没有任何公共部分。

输入

第一行为一个整数 $T~(1\leq T\leq5\times10^4)$ ，接下去有 $T$ 组数据，每组数据第一行为一个整数 $n~(2\leq n\leq10^5)$ ，数据保证所有数据的 $n$ 的总和不超过 $10^5$ ，接下去 $n$ 行每行两个整数 $l_i,r_i~(1\leq l_i\leq r_i\leq2\times10^5)$ 。

输出

对于每组数据输出一行，若某组数据无解，则输出 $-1$ ，否则输出 $n$ 个整数 $t_1,t_2,\cdots,t_n~(t_i\in\{1,2\})$ ， $t_i=1$ 表示第 $i$ 条线段被分到第 $1$ 个集合中， $t_i=2$ 表示第 $i$ 条线段被分到第 $2$ 个集合中，若有多解则输出任意一个。

样例

输入
3 2 5 5 2 3 3 3 5 2 3 2 3 3 3 3 4 4 5 5
输出
2 1 -1 1 1 2
提示
在第一组数据中，两条线段应被放到不同的集合中，但答案并不一定必须是 2 1，也可以是 1 2。在第二组数据中，第三条线段与前两条线段相交，因此它们应该被分在同一个集合中，这样另一个集合就会为空，不满足题意，因此答案为 $-1$ 。在第三组数据中，我们可以以任意方式将三条线段分配到两个不同的集合中，只要这两个集合非空就是合法的，因此总共有 $6$ 种合法的答案。

题解

将每条线段的两个端点拆开，左区间 $l_i$ 标为 $+i$ ，右区间 $r_i+1$ 标为 $-i$ ，以端点大小为主关键字从小到大、以下标为此关键词从小到大排序，最后对整个数组扫一遍，遇到左端点则放入集合中，遇到右端点则从集合中删除，最后用并查集维护相互覆盖的线段，只要存在至少两个连通块，就存在答案，将其中一个连通块中的线段放到集合 $1$ 中，其他的连通块放入集合 $2$ 中。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 100000 + 100;
struct Node {
    int Index, x;
};
bool operator<(const Node &a, const Node &b) {
    return a.x == b.x? a.Index < b.Index: a.x < b.x;
}
int T, n, l, r;
Node node[maxn << 1];
set<int> st;
int fa[maxn], ans[maxn];
void Init() {
    for(int i = 1; i <= n; ++i) {
        fa[i] = i;
    }
}
int Find(int x) {
    return x == fa[x]? x: fa[x] = Find(fa[x]);
}
void unit(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    fa[xx] = yy;
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        st.clear();
        Init();
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d", &l, &r);
            node[i].Index = i;
            node[i].x = l;
            node[i + n].Index = -i;
            node[i + n].x = r + 1;
        }
        sort(node + 1, node + 1 + 2 * n);
        for(int i = 1; i <= 2 * n; ) {
            while(i <= 2 * n && node[i].Index < 0) {
                st.erase(-node[i].Index);
                ++i;
            }
            if(i == 2 * n + 1) {
                break;
            }
            int f;
            if(st.empty()) {
                f = node[i].Index;
            } else {
                f = *st.begin();
            }
            while(i <= 2 * n && node[i].Index > 0) {
                st.insert(node[i].Index);
                unit(node[i].Index, f);
                ++i;
            }
        }
        bool flag = false;
        int f = Find(1);
        for(int i = 1; i <= n; ++i) {
            if(Find(i) == f) {
                ans[i] = 1;
            } else {
                flag = true;
                ans[i] = 2;
            }
        }
        if(!flag) {
            printf("-1\n");
            continue;
        }
        for(int i = 1; i <= n; ++i) {
            if(i != 1) {
                printf(" ");
            }
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

D. GCD Counting

题意

给定一棵 $n$ 个节点的树，树上的每个点都有一个权值 $a_i$ ，定义 $g(x,y)$ 表示从节点 $x$ 到节点 $y$ 的路径上所有节点（包括 $x,y$ 两点）权值的 $\gcd$ ，定义 $dist(x,y)$ 表示从节点 $x$ 到节点 $y$ 的路径上所有节点的数量，对于任意一个节点有 $dist(x,x)=1$ 。求在 $g(x,y)>1$ 的 $x,y$ 对中， $dist(x,y)$ 的最大值。

输入

第一行为一个整数 $n~(1\leq n\leq2\times10^5)$ ，第二行为 $n$ 个整数 $a_1,a_2,\cdots,a_n~(1\leq a_i\leq2\times10^5)$ ，接下去 $n-1$ 行每行两个整数 $x,y~(1\leq x,y\leq n,x\neq y)$ ，表示节点 $x$ 与节点 $y$ 之间有一条连边，数据保证所有的边可以构成一棵树。

输出

如果不存在满足条件的答案，输出 $0$ ，否则输出满足条件的 $dist(x,y)$ 的最大值。

样例

输入
3 2 3 4 1 2 2 3
输出
1

输入
3 2 3 4 1 3 2 3
输出
2

输入
3 1 1 1 1 2 2 3
输出
0

题解

定义 $dp[i][j]$ 表示以第 $i$ 个节点为根，从其任意一个子节点往下的一条链，这条链上所有节点权值的 $\gcd$ 为 $j$ 的倍数的最长长度，则可以得到 $dp$ 递推式：

$dp[i][j]=\max(dp[son_i][j])+1$

其中 $son_i$ 为节点 $i$ 的所有子节点， $j$ 为 $i$ 的所有质因子，答案为：

$ans=\max(\max(dp[son_i][j])+next\_max(dp[son_i][j])+1)$

其中 $next\_max$ 表示序列中的次大值。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
const int maxn = 200000 + 100;
int n, ans, u, v;
int num[maxn];
vector<int> G[maxn];
vector<int> fac[maxn];
map<int, int> dp[maxn];
map<int, int>::iterator it;
int cnt;
int prime[maxn];
bool vis[maxn];
void Prime(int n) {
    for(int i = 2; i <= n; ++i) {
        if(!vis[i]) {
            prime[cnt++] = i;
        }
        for(int j = 0; j < cnt && i <= n / prime[j]; ++j) {
            int k = i * prime[j];
            vis[k] = true;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}
void dfs(int f, int x) {
    int len = G[x].size();
    for(int i = 0; i < len; ++i) {
        int pos = G[x][i];
        if(pos == f) {
            continue;
        }
        dfs(x, pos);
    }
    len = fac[num[x]].size();
    for(int i = 0; i < len; ++i) {
        int ffac = fac[num[x]][i];
        int MMax = 0;
        int Max = 0;
        int llen = G[x].size();
        for(int j = 0; j < llen; ++j) {
            int pos = G[x][j];
            if(pos == f) {
                continue;
            }
            it = dp[pos].find(ffac);
            if(it == dp[pos].end()) {
                continue;
            }
            if(it->second >= Max) {
                MMax = Max;
                Max = it->second;
            } else if(it->second > MMax) {
                MMax = it->second;
            }
        }
        ans = max(ans, 1 + Max + MMax);
        dp[x][ffac] = 1 + Max;
    }
}
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    Prime(maxn - 1);
    for(int i = 0; i < cnt; ++i) {
        for(int j = prime[i]; j < maxn; j += prime[i]) {
            fac[j].push_back(prime[i]);
        }
    }
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &num[i]);
    }
    for(int i = 1; i < n; ++i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 1);
    printf("%d\n", ans);
    return 0;
}

E. Polycarp's New Job

题意

给定两种操作：

从一个初始为空的集合中加入一张大小为 $x\times y$ 的票据；

询问大小为 $h\times w$ 的钱包是否能装下所有票据。

对于所有已经被加入集合的票据，满足以下任意一个条件，则钱包能够装下所有票据：

$x_i\leq h$ 且 $y_i\leq w$ ；

$x_i\leq w$ 且 $y_i\leq h$ 。

对于每次询问，输出钱包是否能够装下集合中所有的票据。

输入

第一行包含一个整数 $n~(2\leq n\leq5\times10^5)$ ，接下去有 $n$ 次操作，每次操作格式为以下两个之一：

$+~x~y~(1\leq x,y\leq10^9)$ ，表示加入一张大小为 $x\times y$ 的票据；

$?~h~w~(1\leq h,w\leq10^9)$ ，询问大小为 $h\times w$ 的钱包能否放下集合中的所有票据。

数据保证在第一个询问 $2$ 之前至少存在一个询问 $1$ ，并且至少存在一个询问 $2$ 。

输出

对于每次询问，输出 $YES$ 或 $NO$ ，表示答案。

样例

输入
9 + 3 2 + 2 3 ? 1 20 ? 3 3 ? 2 3 + 1 5 ? 10 10 ? 1 5 + 1 1
输出
NO YES YES YES NO

题解

对于每次放入的票据，每次取短边的最大值和长边的最大值，对于每次询问，只要短边的最大值小于等于钱包的短边，长边的最大值小于等于钱包的长边即可。

过题代码

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <climits>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <bitset>
#include <sstream>
using namespace std;
#define LL long long
int n, l, r, maxl, maxr;
char ch[2];
int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);
    while(scanf("%d", &n) != EOF) {
        maxl = 0;
        maxr = 0;
        for(int i = 0; i < n; ++i) {
            scanf("%s%d%d", ch, &l, &r);
            if(l > r) {
                swap(l, r);
            }
            if(ch[0] == '+') {
                maxl = max(maxl, l);
                maxr = max(maxr, r);
            } else {
                if(l >= maxl && r >= maxr) {
                    printf("YES\n");
                } else {
                    printf("NO\n");
                }
            }
        }
    }
    return 0;
}

Educational Codeforces Round 58

A. Minimum Integer

题意

输入

输出

样例

题解

过题代码

B. Accordion

题意

输入

输出

样例

题解

过题代码

C. Division and Union

题意

输入

输出

样例

题解

过题代码

D. GCD Counting

题意

输入

输出

样例

题解

过题代码

E. Polycarp's New Job

题意

输入

输出

样例

题解

过题代码

内容目录