noone___'s blog
0%

40801202-AGC002

发表于 更新于 分类于
AGC002

D

给一张图，多次询问，每次 $u\leftarrow v$ 中经过的不重复点数量 $=z$ ，求经过边最大编号最小值

边权问题想到 $Kruskal$ 重构树

重构树上倍增二分即可

这道题还有一种整体二分+并查集做法，但我不会

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
const int N=1e5+100;
struct node{
    int x,y,w;
    friend bool operator <(const node &a,const node &b){ return a.w<b.w;}
}edge[N<<1];
int anc[20][N<<1],fa[N<<1],Size[N<<1],edge_val[N<<1];
int n,m,root;

int find_fa(int x){ return x==fa[x] ? x : fa[x]=find_fa(fa[x]);}
inline int find_anc(int x,int d){
    for(rei i=19;~i;--i) if(edge_val[ anc[i][x] ]<=d) x=anc[i][x];
    return x;
}

inline bool check(int x,int y,int z,int d){
    x=find_anc(x,d),y=find_anc(y,d);
    return x==y ? Size[x]>=z : Size[x]+Size[y]>=z;
}

int main(){
    scanf("%d%d",&n,&m);
    edge_val[0]=m+1; root=n;
    for(rei i=1;i<=n;++i) fa[i]=i,Size[i]=1;
    for(rei i=1;i<=m;++i){
        rei u,v; scanf("%d%d",&u,&v);
        u=find_fa(u),v=find_fa(v);
        if(u==v) continue;
        fa[u]=fa[v]=++root;Size[root]=Size[u]+Size[v];
        fa[root]=root; anc[0][u]=anc[0][v]=root; edge_val[root]=i;
    }
    for(rei i=root;i;--i) for(rei j=1;j<20;++j) anc[j][i]=anc[j-1][ anc[j-1][i] ];
    rei Q;scanf("%d",&Q);
    while(Q--){
        rei x,y,z; scanf("%d%d%d",&x,&y,&z);
        rei l=1,r=m,ans=0;
        while(l<=r){
            rei mid=l+r>>1;
            check(x,y,z,mid) ? ans=mid,r=mid-1 : l=mid+1;
        }
        printf("%d\n",ans);
    }
    getchar(),getchar();
    return 0;
}

E

博弈论 每次操作将当前最大堆的糖果全部吃完或将每堆糖果吃掉一个，吃完的人输

GreenDay学长之前讲过

将每堆小石子的数量看成柱状图并排序，问题转化为从 $(1,1)$ 出发，每次只能向上或向右走一格，到边界者输

显然棱角处均为必败点，且打表得 $y=-k\times x$ 直线上的格子性质相同

找最大的 $(i,i)$ 再简单判断即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int N=1e5+100;
int a[N],n;

int main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
    sort(a+1,a+1+n,greater<int>());
    for(rei i=1;i<=n;++i)
        if(i+1>a[i+1]){//最大正方形
            if((a[i]-i)&1){ puts("First"); break;}
            rei right=i;
            while(a[right+1]==i) ++right;
            if((right-i)&1){ puts("First"); break;}
            puts("Second"); break;
        }
    getchar(),getchar();
    return 0;
}

F

给你 $n$ 种不含白色颜色的球，每个球有 $m$ 个，把这 $n\times m$ 个球排成一排，把每一种颜色的最左边出现的球涂成白色，求有多少种不同的颜色序列

有 $m$ 个白球，$n$ 种其他颜色的球各 $m-1$ 个 只有任意前缀中白球的个数均大于其他颜色种类数时合法

考虑序列计数 $dp$: 枚举位置或元素，这里枚举元素

设状态 $f_{i,j}$ 表示在 $n\times m$ 个位置上填了 $i$ 个白球和 $j$ 个其他球

考虑合法序列的从左到右的第一个格子如何转移

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N=2e3+5,M=4e6+5;
const int mod=1e9+7;
int n,m,f[N][N],fac[M],ifac[M],inv[M],ans;
inline int C(int n,int m){ return (ll) fac[n]*ifac[n-m]%mod*ifac[m]%mod;}

int main(){
    scanf("%d%d",&n,&m); inv[1]=ifac[0]=fac[0]=1; f[0][0]=1;
    for(rei i=2;i<=n*m;++i) inv[i]=(ll) (mod-mod/i)*inv[mod%i]%mod;
    for(rei i=1;i<=n*m;++i) fac[i]=(ll) i*fac[i-1]%mod,ifac[i]=(ll) inv[i]*ifac[i-1]%mod;
    for(rei i=1;i<=n;++i) for(rei j=0;j<=i;++j){
            f[i][j]=f[i-1][j];
            if(j) f[i][j]=(f[i][j]+(ll) f[i][j-1]*(n-j+1)%mod *C(n*m-i-(j-1)*(m-1)-1,m-2)%mod)%mod;
        }
    printf("%d\n",m==1 ? 1 : f[n][n]);
    return 0;
}