2020-02-18发表2020-12-20更新ICPC/CCPC / Contests / Codeforces22 分钟读完 (大约3230个字)

Codeforces Round #621 (Div.1+Div.2)

A. Cow and Haybales

Solution

尽可能地往 $a_1$ 放就行了。

Code

>folded

#include<algorithm>
#include<iostream>
#include<cstdio>

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, a[N], d;

int main(){
    read(T);
    while(T--){
        read(n, d);
        for(int i = 1; i <= n; i++){
            read(a[i]);
            if(i > 1){
                a[1] += min(d / (i - 1), a[i]);
                d -= (i - 1) * min(d / (i - 1), a[i]);
            }
        }
        printf("%d\n", a[1]);
    }
    return 0;
}

B. Cow and Friend

Solution

其实就是不断画圆，以两圆的情况说明：假设先走 $r_1$ 距离，再走 $r_2$，联想惠更斯原理里面的包络面，到原点距离为 $(r_1,r2]$ 之间的区域都可以通过这两步走到。

所以先走一个最大的小于 $x$ 的长度，再用最大的长度走即可。

Code

>folded

#include<algorithm>
#include<iostream>
#include<cstdio>

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, a, x, mx, mnx;

int main(){
    read(T);
    while(T--){
        mnx = mx = 0;
        read(n, x);
        for(int i = 1; i <= n; i++){
            read(a);
            if(a <= x && a > mnx)   mnx = a;
            if(a > mx)  mx = a;
        }
        int ans = (x - mnx) / mx + 1;
        if((x - mnx) % mx)   ans++;
        printf("%d\n", ans);
    }
}

C. Cow and Message

Solution

一定存在长度为 $1$ 或者 $2$ 的出现次数最多字符串，因为对于长度大于 $2$ 的字符串，取它的长度为 $2$ 的子串，出现次数至少和它一样多。

Code

>folded

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>

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;

char s[N];
int n, dp2, dp1;
LL cnt[200], ans;

int main(){
    scanf("%s", s+1);
    n = strlen(s+1);
    for(int i = 1; i <= n; i++){
        cnt[s[i]]++;
        ans = max(ans, max(cnt[s[i]], cnt[s[i]] * (cnt[s[i]] - 1) / 2));
    }
    for(int i = 'a'; i <= 'z'; i++){
        for(int j = 'a'; j <= 'z'; j++){
            LL res = 0;
            if(j == i)  continue;
            dp1 = dp2 = 0;
            for(int k = n; k >= 1; k--){
                dp1 = dp2;
                if(s[k] == j)   dp1++;
                if(s[k] == i)   res += dp1;
                dp2 = dp1;
            }
            ans = max(ans, res);
        }
    }
    printf("%lld\n", ans);
    return 0;
}

D. Cow and Fields

Solution

加上一条边后，从 $1$ 到 $n$ 的最短路有两种情况：经过了加的新边或未经过新边。

未经过新边：则最短路就是原来的最短路，$bfs$ 即可。

经过了新边：设新边是 $(u,v)$，则最短路就是 $\min(dis1_{u}+1+dis2_{v},dis1_{v}+1+dis2_{u})$，其中 $dis1_{i}$ 表示 $1$ 到 $i$ 的最短路，$dis2_{i}$ 表示 $i$ 到 $n$ 的最短路，二者都可以 $bfs$ 求得。

现在我们的问题转化为最大化 $\min(dis1_{i}+dis2_{j},dis1_{j}+dis2_{i})$，其中 $i,j$ 是 $a$ 中的数。我们想把讨厌的 $\min()$ 去掉，考虑贪心：按照 $dis1$ 从小到大排序，分类讨论（设 $i<j$ ）：

若 $dis1_i+dis2_j\leq dis1_j+dis2_i$，则 $\min(dis1_{i}+dis2_{j},dis1_{j}+dis2_{i})=dis1_i+dis2_j$，达到了去掉 $\min()$ 的目的；
若 $dis1_i+dis2_j>dis1_j+dis2_i$，又因为排序后 $dis1_i\leq dis1_j$，所以一定有 $dis2_i<dis2_j$，于是 $dis1_i+dis2_i<dis1_j+dis2_j$，也就是说我不经过新加的 $(i,j)$ 这条边就能走出更短的路径，那么最后计算答案与原最短路取 $\min$ 时，这个分类情况的存在不影响答案，不妨就按照第一种分类的情形计算罢了（反正结果不会影响最终答案）。

所以排序后维护一个 $dis2$ 的后缀最大值即可。

复杂度：$O(n\lg n+m)$

Code

>folded

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#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 long long LL;

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

int n, a[N], u, v, m, k;

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

int dis[3][N];
void bfs(int s, int kind){
    queue<int> q;
    for(int i = 1; i <= n; i++) dis[kind][i] = INF;
    dis[kind][s] = 0;
    q.push(s);
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(int i = head[cur]; i; i = edge[i].nxt){
            if(dis[kind][edge[i].to] != INF)    continue;
            dis[kind][edge[i].to] = dis[kind][cur] + 1;
            q.push(edge[i].to);
        }
    }
}

struct Special{
    int a, b;
    bool operator < (const Special A) const{
        return a < A.a;
    }
}d[N];
int mx[N];

int main(){
    read(n, m, k);
    for(int i = 1; i <= k; i++) read(a[i]);
    for(int i = 1; i <= m; i++){
        read(u, v);
        addEdge(u, v);
        addEdge(v, u);
    }
    bfs(1, 1);
    bfs(n, 2);
    for(int i = 1; i <= k; i++){
        d[i].a = dis[1][a[i]];
        d[i].b = dis[2][a[i]];
    }
    sort(d+1, d+k+1);
    for(int i = k; i >= 1; i--)
        mx[i] = max(mx[i+1], d[i].b);
    int res = 0;
    for(int i = 1; i < k; i++)
        res = max(res, d[i].a + mx[i+1]);
    printf("%d\n", min(dis[1][n], res + 1));
    return 0;
}

E. Cow and Treats

好诡异的题目背景呃……分分钟出戏啊～

Solution

【参考博客：1，2 】

首先我们需要发现一个重要的结论：

结论：$f_i$ 相同的牛必不在同一侧，否则一定会撞车（很好理解）
- 推论1：$f_i$ 相同的牛最多只能走两头，即分别从左右两端走
- 推论2：同一侧的牛的 $f_i$ 互不相同，因此只要草够吃，就一定可以找到一个顺序使得它们全都睡觉

现在同一侧的牛之间倒是不会冲突了，但是两侧的牛还是可能冲突的。于是我们可以枚举一个分割点，规定左右侧的牛都不能走过这个分割点。

由于 $f_i$ 相同与否起到至关重要的作用，我们把所有牛按照 $f_i$ 分类，依次考虑每一类：假设从左边出发能吃饱睡觉的有 $a$ 头牛，从右边出发能吃饱睡觉的有 $b$ 头牛，从两边出发都可以吃饱睡觉的有 $c$ 头牛，那么简单分类列式一下就知道方案数了。

可惜这么做会出现重复计算的情况——当分割点处没有牛睡觉时。于是我们可以枚举第一头从左往右走的牛，它睡下后自然而然形成了分割点，再按上述过程处理（不过特判一下和它同一类的牛只能从右往左且最多走一头）

但是这样做会导致漏一种情况：没有牛从左边出发的情况。所以最后再单独计算一下全部从右边出发的情况即可。

复杂度：$O(n^2)$

虽然至此这道题做完了，但是上述过程总还是有点不直观，然后搜到了 cz_xuyixuan dalao 的博客，把这个问题抽象成了数学语言：

每个元素有三个值 $f_i,l_i,r_i$，要求找到两个集合 $S,T$，满足同一集合中元素的 $f_i$ 互不相同且：$\max\limits_{i\in S}{l_i}+\max\limits_{i\in T}r_i\leq n$. 求 $|S|+|T|$ 的最大值及方案数。

于是乎，我们的做法对应为：枚举 $\max\limits_{i\in S}l_i$，对于一个元素 $j$，它能放在 $S$ 中需要满足：$l_j<l_i$，能放在 $T$ 中需要满足：$n-r_j\geq l_i$. 然后把元素按照 $f_i$ 分类后计数。

转化成数学模型之后就不用绕原来那个吃饱了睡觉的弯了，思维上直接一些。Orz…

Code

>folded

#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 5005;
const LL MOD = 1e9 + 7;

int n, m, s[N], ltot[N], rtot[N], maxx;
LL ans, ans0;
struct Cow{
    int f, h;
}cow[N];
vector<int> vec[N];

inline int calPos(int i){
    int cnt = 0, pos;
    for(pos = 1; pos <= n; pos++){ // calculate the position where the first cow sleeps
        if(s[pos] == cow[i].f){
            cnt++;
            if(cnt == cow[i].h) break;
        }
    }
    return pos;
}

inline void initTot(int pos){
    memset(ltot, 0, sizeof ltot);
    memset(rtot, 0, sizeof rtot);
    for(int j = 1; j <= pos - 1; j++)   ltot[s[j]]++;
    for(int j = pos + 1; j <= n; j++)   rtot[s[j]]++;
}

inline int calGoFromRight(int i){
    int cnt = 0;
    for(int k = 0; k < vec[cow[i].f].size(); k++)
        if(vec[cow[i].f][k] <= rtot[cow[i].f])
            cnt++;
    cnt -= rtot[cow[i].f] >= cow[i].h;
    return cnt;
}

void calOtherCow(int i, LL &res, LL &res0){
    for(int j = 1; j <= maxx; j++){
        if(j == cow[i].f)   continue;
        int a = 0, b = 0, c = 0;
        for(int k = 0; k < vec[j].size(); k++){
            if(vec[j][k] <= ltot[j] && vec[j][k] <= rtot[j])    c++;
            else if(vec[j][k] <= ltot[j])   a++;
            else if(vec[j][k] <= rtot[j])   b++;
        }
        if((!a && b && c) || (a && !b && c)){
            (res *= (a * b + a * c + b * c + c * (c - 1)) % MOD) %= MOD;
            res0 += 2;
        }
        else if(!a && !b && c){
            if(c == 1)  (res *= 2) %= MOD, res0++;
            else    (res *= c * (c - 1) % MOD) %= MOD, res0 += 2;
        }
        else if(a && !b && !c)   (res *= a) %= MOD, res0++;
        else if(!a && b && !c)   (res *= b) %= MOD, res0++;
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &s[i]);
        maxx = max(maxx, s[i]);
    }
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &cow[i].f, &cow[i].h);
        vec[cow[i].f].push_back(cow[i].h);
        maxx = max(maxx, cow[i].f);
    }

    for(int i = 1; i <= m; i++){ // iterate the first cow
        LL res = 0, res0 = 0;
        int pos = calPos(i);
        if(pos == n + 1)    continue;
        initTot(pos);
        int cnt = calGoFromRight(i);
        res = max(1, cnt);
        res0 = cnt == 0 ? 1 : 2;
        calOtherCow(i, res, res0);
        if(res0 > ans0) ans0 = res0, ans = res;
        else if(res0 == ans0)   (ans += res) %= MOD;
    }
    memset(rtot, 0, sizeof rtot);
    for(int i = 1; i <= n; i++) rtot[s[i]]++;
    LL onlyRight0 = 0, onlyRight = 1;
    for(int i = 1; i <= maxx; i++){
        if(!vec[i].empty()){
            int cnt = 0;
            for(int k = 0; k < vec[i].size(); k++)
                if(rtot[i] >= vec[i][k])
                    cnt++;
            if(cnt){
                onlyRight0++;
                (onlyRight *= cnt) %= MOD;
            }
        }
    }
    if(onlyRight0 > ans0)   ans0 = onlyRight0, ans = onlyRight;
    else if(onlyRight0 == ans0)  (ans += onlyRight) %= MOD;
    printf("%lld %lld\n", ans0, ans0 == 0 ? 1 : ans);
    return 0;
}

F. Cow and Vacation

Solution

对于每个询问，起点到终点在树上有唯一路径，我们要做的就是在路径的某个节点出去补充一下能量，然后回来继续沿着这条路径走。所以很容易地知道，假设我们在某个“路口”出去补充能量，那么补给站到路口的距离应小于 $\frac{k}{2}$，否则回来之后能量反而更少了。于是我们有了一个 $O(nv)$ 的做法：即对于每个询问，一步一步地从起点往终点走，并且不断更新能量，能更新多少能量可以 $O(n^2)$ 的预处理出来。

现在要优化这个做法，我们显然不能一步一步地走。注意到如果两个补给站之间的距离小于等于 $k$，那么这两个补给站可以看作传送门。由此，用 $bfs$ 和并查集将补给站分好类，同一类的补给站之间可以进行无消耗的传送。那么对于每个询问，如果起点与终点要么可以直接走到，要么能通过一系列的传送门传送到达，就输出 YES。再想一下，不难发现上述的“一系列传送门”其实就是“一种传送门”，因为两种传送门之间能走到的话，按我们的定义，它们其实就是一种传送门。

所以现在只需要考虑如何判断起点与终点是否可以到达同一类补给站。又由第一段的叙述，不妨定义距离一个补给站小于 $\frac{k}{2}$ 的所有点都是同一类传送门，于是同一类传送门之间可以进行传送且能量消耗小于 $\frac{k}{2}$. 对于每个询问，特判掉可以直接走到的情况，然后从起点往终点走 $\frac{k}{2}$ 的距离，从终点到起点走 $\frac{k}{2}$ 的距离，判断新到的这两个点是否属于同一类传送门即可。

一个 trick：在每条边中间插一个点，即把边扩倍，然后 $k$ 也相应的乘 $2$，变成偶数便于处理。

复杂度：$O((n+v)\lg n)$

Code

>folded

#include<algorithm>
#include<cstdio>
#include<queue>

using namespace std;

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

const int N = 400005;

int n, k, r, u, v, q, rest[N];

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;
}

struct LCA{
    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 up(int x, int d){
        for(int i = 20; i >= 0; i--){
            if((1 << i) <= d){
                d -= (1 << i);
                x = fa[x][i];
            }
        }
        return x;
    }
}lca;

struct DSU{
    int fa[N];
    inline void init(){ for(int i = 1; i <= n; i++) fa[i] = i; }
    int findfa(int x){ return fa[x] == x ? x : fa[x] = findfa(fa[x]); }
    inline void unionn(int x, int y){ fa[findfa(y)] = findfa(x); }
}dsu;

int dis[N];
queue<int> que;
inline void bfs(){
    for(int i = 1; i <= n; i++) dis[i] = -1;
    for(int i = 1; i <= r; i++){
        que.push(rest[i]);
        dis[rest[i]] = 0;
    }
    while(!que.empty()){
        int cur = que.front(); que.pop();
        if(dis[cur] == k)   continue;
        for(int i = head[cur]; i; i = edge[i].nxt){
            if(dis[edge[i].to] == -1){
                que.push(edge[i].to);
                dis[edge[i].to] = dis[cur] + 1;
            }
            dsu.unionn(cur, edge[i].to);
        }
    }
}

int main(){
    scanf("%d%d%d", &n, &k, &r);
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        addEdge(u, n+i), addEdge(n+i, u);
        addEdge(n+i, v), addEdge(v, n+i);
    }
    n += n - 1;
    dsu.init();
    for(int i = 1; i <= r; i++) scanf("%d", &rest[i]);
    bfs();
    lca.dfs(1, 0, 1);
    lca.init();
    scanf("%d", &q);
    while(q--){
        scanf("%d%d", &u, &v);
        int uvlca = lca.lca(u, v);
        if(lca.dep[u] + lca.dep[v] - 2 * lca.dep[uvlca] <= 2 * k){
            puts("YES");
            continue;
        }
        if(lca.dep[u] - lca.dep[uvlca] >= k)    u = lca.up(u, k);
        else    u = lca.up(v, lca.dep[v] + lca.dep[u] - 2 * lca.dep[uvlca] - k);
        if(lca.dep[v] - lca.dep[uvlca] >= k)    v = lca.up(v, k);
        else    v = lca.up(u, lca.dep[v] + lca.dep[u] - 2 * lca.dep[uvlca] - k);
        if(dsu.findfa(u) == dsu.findfa(v))  puts("YES");
        else    puts("NO");
    }
    return 0;
}

Codeforces Round #621 (Div.1+Div.2)

http://xyfjason.github.io/blog-xcpc/2020/02/18/Codeforces-Round-621-Div-1-Div-2/

作者

xyfJASON

发布于

2020-02-18

更新于

2020-12-20

许可协议

#Codeforces

Codeforces Round #621 (Div.1+Div.2)

A. Cow and Haybales

Solution

Code

B. Cow and Friend

Solution

Code

C. Cow and Message

Solution

Code

D. Cow and Fields

Solution

Code

E. Cow and Treats

Solution

Code

F. Cow and Vacation

Solution

Code

作者

发布于

更新于

许可协议

评论

分类

最新文章

标签