AtCoder AGC #2 Virtual Participation

在知乎上听zzx大佬说AGC练智商...于是试了一下

A.Range Product

给$a$，$b$，求$\prod^{b}_{i=a}i$是正数，负数还是$0$

。。。不写了

B.Box and Ball

有$n$个盒子，每个里面有一些小球，在$1$号盒子里有一个红球，现在给你若干次移动操作

每次移动是“从$x$中随机抽出一个球中放到$y$中”

最后询问有多少个盒子有可能有红球

。。。sb题吧，不写了口胡一下

发现一个盒子只要“有可能”被放过红球且未被拿光，就是“有可能”有红球，模拟即可

官方题解说的很好，考虑$1$号盒子里有一盒红墨水，其它盒子里有清水，每次移动操作可看做从$x$取出一杯溶液灌到$y$里

C.Knot Puzzle

有$n$个长度为$a_1,a_2,...,a_n$的绳子，第$i$个和第$i + 1$个绳子($1 \leq i \leq (n -1)$)通过打结连接起来

每次你可以选取一段还打着节的，且长度大于等于$L$的绳子，解开一个节

求最后能不能解开这$n-1$个节，如果可以输出操作序列

。。。sb题

首先因为最后所有节都要被打开，我们需要连续的两个绳子加起来大于等于$L$，没有直接就是Impossible

找到了这两个，考虑构造

因为他俩就已经大于等于$L$了，我们可以先从左到右把左边一个一个拆下来

这样每一步都大于等于$L$

然后从右到左拆右边

最后拆他俩就可以啦

D.Stamp Rally

给一个$n$个点$m$条边的无向图，$q$组询问

每次给出$x$,$y$,$z$表示一个人从$x$出发，一个人从$y$出发，同时走

总共经过$z$个不同的点，要经过的编号最大的边编号最小是多少

n,m,q 1e5

#include<bits/stdc++.h>

#define LL long long

using namespace std;

inline int read()

{

    int x = ,f = ;char ch = getchar();

    for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f;

    for(;isdigit(ch);ch = getchar())x =  * x + ch - '';

    return x * f;

}

const int maxn = 1e5 + ;

int n,m,q;

struct EDG{int u,v;}es[maxn];

stack<EDG> s;

struct Ques

{

    int u,v,z,id;

}qs[maxn],ts[maxn];

int ans[maxn];

int fa[maxn],size[maxn];

inline int find(int x){return x == fa[x] ? x : find(fa[x]);}

inline void divide(int l,int r,int ql,int qr)

{

    if(l == r)

    {

        for(int i=ql;i<=qr;i++)ans[qs[i].id] = l;

        int fx = find(es[l].u),fy = find(es[l].v);

        if(size[fx] > size[fy])swap(fx,fy);if(fx != fy)fa[fx] = fy,size[fy] += size[fx];

        return;

    }

    int mid = (l + r) >> ;

    for(int i=l;i<=mid;i++)

    {

        int fx = find(es[i].u),fy = find(es[i].v);

        if(size[fx] > size[fy])swap(fx,fy);if(fx != fy)fa[fx] = fy,size[fy] += size[fx],s.push((EDG){fx,fy});

    }

    int cnt1 = ql - ,cnt2 = ;

    int tot;

    for(int i=ql;i<=qr;i++)

    {

        int fx = find(qs[i].u),fy = find(qs[i].v);

        if(fx == fy)tot = size[fx];

        else tot = size[fx] + size[fy];

        if(tot >= qs[i].z)qs[++cnt1] = qs[i];

        else ts[++cnt2] = qs[i];

    }

    for(int i=;i<=cnt2;i++)qs[cnt1 + i] = ts[i];

    while(!s.empty())

    {

        EDG h = s.top();s.pop();

        fa[h.u] = h.u;size[h.v] -= size[h.u];

    }

    divide(l,mid,ql,cnt1);divide(mid + ,r,cnt1 + ,qr);

}

int main()

{

    n = read(),m = read();

    for(int i=;i<=m;i++){es[i].u = read(),es[i].v = read();}

    for(int i=;i<=n;i++)fa[i] = i,size[i] = ;

    q = read();

    for(int i=;i<=q;i++)

    {

        qs[i].u = read(),qs[i].v = read(),qs[i].z = read();

        qs[i].id = i;

    }

    divide(,m,,q);

    for(int i=;i<=q;i++)

        printf("%d\n",ans[i]);

}

先考虑暴力

显然就是每次二分一个最大编号，check就是搞一个并查集看$x$和$y$的$size$到没有到$z$

然后我们发现并不用二分...整体二分就可以了

整体二分的时候用可持久化并查集维护一下，每次多余的边弹掉就可以了

细节：当$x$，$y$在当前的图里处于同一个联通块的时候联通块大小是$size[x]$而不是$size[x] + size[y]$

wls：可持久化并查集都可以用Kruskal重构树来做

那这题的重构树做法显然就是二分一个高度暴力往上跳...两个复杂度和代码长度都比并查集优秀

然而..我的思维路径是：整体二分->重构树->重构个锤子直接并查集

成功错过正解

E.Candy Piles

有$n$堆糖，Alice和Bob轮流行动，每次可以选择吃掉最多的一堆或者从每个还有糖的堆吃一个

吃到最后一个的就输了，求谁赢

n 1e5 ai 1e9

#include<bits/stdc++.h>

#define LL long long

using namespace std;

inline int read()

{

    int x = ,f = ;char ch = getchar();

    for(;!isdigit(ch);ch = getchar())if(ch == '-')f = -f;

    for(;isdigit(ch);ch = getchar())x =  * x + ch - '';

    return x * f;

}

const int maxn = 1e5 + ;

int n;int a[maxn];

int main()

{

    n = read();

    for(int i=;i<=n;i++)a[i] = read();

    sort(a + ,a + n + );reverse(a + ,a + n + );

    int ans = ;

    for(int i=;i<=n;i++)

    {

        if(i +  > a[i + ])

        {

            for(int j=i+;a[j] == i;j++) ans ^= ;

            ans |= (a[i] - i) & ;

            if(ans)puts("First");

               else puts("Second");

            return ;

        }

    }

}

我们把每堆按糖数排序

然后就成了一个杨表

每次可以去掉这个杨表的左起第一列或者下起第一行

也就是相当于每次可以从杨表左下角画一个长度为$1$的向右（吃掉行）或者向上（吃掉列）的线

显然右边界全是必胜态

然后，往右往上至少有一个必败态的是必胜态，全是必胜态的是必败态

然后发现，一条斜线的状态是一样的，于是从左下画一条斜率为$1$的线，看必败还是必胜即可

F.Leftmost Ball

有$n$种颜色，每种颜色有恰好$k$个小球。现在把这$n \times k$个小球排成一排，然后把每种颜色最左边的小球染成颜色$0$。问总共有多少种不同的颜色序列。

神仙题不会

别人的题解 & 代码

<del>体验到了智商被碾压的感觉</del>

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

const int N=;

const int MOD=;

int n,k,f[N][N],jc[N*N+N*],ny[N*N+N*];

void updata(int &x,int y)

{

    x+=y,x-=x>=MOD?MOD:;

}

int C(int n,int m)

{

    return (LL)jc[n]*ny[m]%MOD*ny[n-m]%MOD;

}

int main()

{

    scanf("%d%d",&n,&k);k--;

    if (!k) {puts("");return ;}

    jc[]=jc[]=ny[]=ny[]=;

    for (int i=;i<=n*k+n+k;i++) jc[i]=(LL)jc[i-]*i%MOD,ny[i]=(LL)(MOD-MOD/i)*ny[MOD%i]%MOD;

    for (int i=;i<=n*k+n+k;i++) ny[i]=(LL)ny[i-]*ny[i]%MOD;

    f[][]=;

    for (int i=;i<=n;i++)

        for (int j=i;j<=n;j++)

        {

            if (i) updata(f[i][j],f[i-][j]);

            if (j) updata(f[i][j],(LL)f[i][j-]*C(i+(j-)*k+k-,k-)%MOD);

        }

    printf("%d",(LL)f[n][n]*jc[n]%MOD);

    return ;

}

我们可以看成每种颜色的小球都只有k-1个，然后就是要满足对于每个前缀，都有颜色为0的小球数量不能小于大于0的颜色数量。
考虑反过来计数。
设f[i,j]表示从后往前，已经放了i个颜色为0的小球和j种颜色的小球的方案，其中i必须不大于j。
一种转移是在当前位置放颜色为0的小球，也就是f[i,j]=f[i-1,j]。
一种转移是加入一种新的颜色，那么新颜色有k-1个小球，其中必须有一个放在最前面，然后后面已经放了的小球数是i+(j-1)*(k-1)。
那么系数就是一个简单的组合数了。
最后乘上一个n!即可。

巴特西

AtCoder AGC #2 Virtual Participation

最新文章

热门文章