做题笔记[AGC002]

A - Range Product

标签：数学

难度：★☆☆☆☆

题目大意

给你两个整数 \(a\) 和 \(b\) (\(a≤b\))。

判断 \(\prod\limits_{i=a}^b i\) 是正、负还是零。

数据范围

\(-10^9\le a\le b\le 10^9\)。

解题思路

判断正负性，经过 \(0\) 的乘积为 \(0\)，再判断负数个数即可。

参考代码

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int a,b;
int main(){
    cin>>a>>b;
    if(a<=0&&b>=0) cout<<"Zero";
    else if(a>0||(b-a+1)%2==0) cout<<"Positive";
    else cout<<"Negative";
    return 0;
}

B - Box and Ball

标签：思维

难度：★★☆☆☆

题目大意

我们有\(N\)个盒子，一开始，\(1\) 号盒子里有一个红球，其他每个盒子里都有一个白球。

逐一执行给定的 \(M\) 操作。在第 \(i\) 次操作中，他会从 \(x_i\) 盒子中随机选取一个球，然后将其放入 \(y_i\) 盒子中。

求所有操作完成后，可能装有红球的盒子数。

数据范围

\(2\le N,M\le 10^5,1\le x_i,y_i\le N\)。

解题思路

判断 \(1\) 号球可能到达的位置，每次移动将 \(y\) 盒子打上“可能”的标记，如果 \(x\) 盒子空了，就撤销 \(x\) 的“可能”标记即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
#define MAXN 100005
int n,m,sz[MAXN];
bool f[MAXN];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) sz[i]=1;
    f[1]=1;
    for(int x,y,i=1;i<=m;i++){
        cin>>x>>y;
        sz[x]--;
        sz[y]++;
        f[y]|=f[x];
        if(!sz[x]) f[x]=0;
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans+=f[i];
    cout<<ans;
    return 0;
}

C - Knot Puzzle

标签：贪心、构造

难度：★★★☆☆

题目大意

我们有 \(N\) 根绳子，第 \(i\) 段的长度是 \(a_i\)。起初，每条和相邻的绳子打上结，形成一条有 \(N-1\) 个结的长绳。尝试通过重复执行以下操作来解开所有绳结：

  • 选择一条总长度至少为 \(L\) 的（相连）绳子，然后解开其中一个绳结。

通过正确的操作是否可以解开所有的 \(N-1\) 个绳结？如果答案是肯定的，请找出一种可能的解结顺序。

数据范围

\(2\le N\le 10^5,1\le L,a_i\le 10^9\)。

解题思路

考虑贪心。如果全部能解开，则最后解开的那一对相邻的绳子长度一定大于等于 \(L\)。我们找到这对绳子，从两边开始解开所有的绳子。

如果没有这样一对相邻的绳子，则判断无解。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;
#define MAXN 100005
int n,len,a[MAXN];
int main(){
    cin>>n>>len;
    int s=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]+a[i-1]>=a[s]+a[s-1]) s=i;
    }
    if(a[s]+a[s-1]<len){
        cout<<"Impossible";
        return 0;
    }
    cout<<"Possible"<<endl;
    for(int i=1;i<s-1;i++) cout<<i<<endl;
    for(int i=n-1;i>=s;i--) cout<<i<<endl;
    cout<<s-1<<endl;
    return 0;
}

D - Stamp Rally

标签：图论、kruskal 重构树

难度：★★★★☆

题目大意

有一个 \(N\) 个顶点和 \(M\) 条边的无向连通图。一共有 \(Q\) 此询问，每次询问给定两个点 \(x,y\)，要求是同这两个点开始走，一共走 \(z\) 个点，最小化所经过的边的权值最大值。

数据范围

\(3\le N,Q\le 10^5,N−1\le M\le 10^5,1\le a_i<b_i\le N\)。

解题思路

因为要最小化路径最大权值，想到构建最小生成树，这样能保证连通图的最大边权最小。

因为要从两个顶点开始，一共走 \(z\) 条边，考虑构建 kruskal 重构树，利用其一条路径的最大边权在两点的 LCA 位置处的性质，找到 \(x,y\) 的最近公共祖先，再判断 \(z\) 是否满足即可。

判断 \(z\) 是否满足，只需要再重构树上往祖先走的时候判断子树叶子节点个数即可。可利用倍增加速。时间复杂度 \(O(Q\log n)\)。

参考代码

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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define MAXN 200005
int n,m,dsu[MAXN],w[MAXN],f[MAXN][30],tot,root,lim,dep[MAXN],sz[MAXN];
vector<int> g[MAXN];
struct node{
    int x,y,z;
}edge[MAXN];
bool cmp(node x,node y){
    return x.z<y.z;
}
int find(int x){
    if(dsu[x]==x) return x;
    return dsu[x]=find(dsu[x]);
}
void dfs(int u,int fa){
    f[u][0]=fa;
    dep[u]=dep[fa]+1;
    if(g[u].size()==1) sz[u]=1;
    for(auto v:g[u]){
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
    }
}
int check(int x,int y,int c){
    for(int i=lim;i>=0;i--){
        if(w[f[x][i]]<=c) x=f[x][i];
        if(w[f[y][i]]<=c) y=f[y][i];
    }
    if(x==y) return sz[x];
    else return sz[x]+sz[y];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>edge[i].x>>edge[i].y;
        edge[i].z=i;
    }
    sort(edge+1,edge+1+m,cmp);
    for(int i=1;i<=n*2;i++) dsu[i]=i;
    tot=n;
    for(int t=1,i=1;t<n;i++){
        int x=edge[i].x,y=edge[i].y;
        if(find(x)!=find(y)){
            t++,tot++;
            g[find(x)].push_back(tot);
            g[tot].push_back(find(x));
            g[find(y)].push_back(tot);
            g[tot].push_back(find(y));
            w[tot]=edge[i].z;
            dsu[find(x)]=tot;
            dsu[find(y)]=tot;
        }
    }
    root=tot;
    dfs(root,0);
    lim=log2(n*2);
    for(int j=1;j<=lim;j++){
        for(int i=1;i<=n*2;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
    int Q;
    cin>>Q;
    w[0]=0x3f3f3f3f;
    while(Q--){
        int x,y,z;
        cin>>x>>y>>z;
        int l=1,r=m;
        while(l<r){
            int mid=(l+r)>>1;
            if(check(x,y,mid)>=z) r=mid;
            else l=mid+1;
        }
        cout<<l<<endl;
    }
    return 0;
}

E - Candy Piles

标签：博弈论、思维

难度：★★★★★

题目大意

桌子上有 \(N\) 堆糖果，第 \(i\) 堆里有 \(a_i\) 颗糖果。

两个人轮流玩游戏，在每个回合中，当前玩家必须执行以下两个操作中的一个：

  1. 选择剩余糖果数量最多的一堆，然后吃掉这一堆中的所有糖果。
  2. 从每堆糖果中吃掉一颗或多颗糖果。

吃掉桌上最后一颗糖果的玩家输掉游戏。如果双方都以最佳方式玩游戏，请确定哪一方会获胜。

数据范围

\(1\le N\le 10^5,1\le a_i\le 10^9\)。

解题思路

很巧妙的人类智慧题！

我们考虑将这个棋局表示为一个二维平面，第 \(i\) 列表示第 \(i\) 堆糖果，每列从下到上有 \(j\) 个添上的格子，表示第 \(i\) 堆糖果有 \(j\) 个。如下图：左图表示拿走最多的一堆（操作 1），右图表示每堆拿走一颗（操作 2）。

实际上，我们将问题转化成了：每次从左或下消除一列或一行，直到无法消去。问谁会赢。

将消去一列操作视为向右走一格，消去一行操作视为向上走一格，可以表示成下图。双方交替进行，红色表示先手，蓝色表示后手。

可以看到，只要走到边界，就会失败，所以给边界上的点一个“必败”的标记，考虑其他的点：

  • 如果这个点上方或右方有必胜点，则此点必胜（对于先手而言，下同）；
  • 否则此点必败。

如下图所示，红点为必败点，蓝点为必胜点。

不难发发现，一个点和其右上方的点属性相同。利用这个性质，我们可以从起点一直向右上方走，直到不能走，判断这个点的胜负性。

发现，对于靠近边界，不能向右上方走的点，如果其上方或右方能延伸的格子数有一个为奇数，则为必胜点，否则先手必败。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
int n,a[MAXN];
bool cmp(int x,int y){
    return x>y;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+1+n,cmp);
    int p=1;
    while(a[p+1]>=p+1) p++;
    int p1=0,p2=a[p]-p;
    while(a[p+p1+1]>=p) p1++;
    if((p1|p2)&1) cout<<"First";
    else cout<<"Second";
    return 0;
}

F - Leftmost Ball

标签：组合数学、动态规划

难度：★★★★★

题目大意

一共有 \(N×K\) 个球，每种他喜欢的 \(N\) 种颜色有\(K\)个。他会把所有的球从左到右任意排成一排。然后，对于每种颜色的球，他都会把最左边的那个颜色的球涂成 \(0\) 号颜色（一种不同于 \(N\) 种原始颜色的颜色）。

求涂色后，球的颜色可能有多少个序列（取模）。

数据范围

\(1\le N,K\le 000\)。

解题思路

组合问题考虑动态规划。我们设状态 \(f_{i,j}\) 表示我们放置了 \(i\) 个白球和 \(j\) 个类颜色的球，显然 \(i\ge j\)。考虑转移：

  • 若当前位置放一个白球，则有转移方程：

\[ f_{i-1,j} \to f_{i,j} \]

  • 若当前位置放一个有颜色的球。根据定义，我们一次安排一类 \(k-1\) 个同颜色的球的位置，那么这个位置是一个没有出现过的颜色的球。因为是从 \(f_{i,j-1}\) 转移过来，所以这个球的颜色有 \(n-j+1\) 种。当前位置放一个，前面有一个此颜色转换成的白球，后面此种颜色共安排 \(k-2\) 个，则可以安排在后面 \(nk-i-(j-i)(k-1)-1\) 个空位种的 \(k-2\) 个位置，则有转移方程：

\[ f_{i,j-1}\times (n-j+1)\times {nk-i-(j-1)(k-1)-1\choose k-2}\to f_{i,j} \]

边界：\(f_{0,0}=1\)，答案：\(f_{n,n}\)。

时间复杂度 \(O(nk)\)。

参考代码

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
#include<iostream>
using namespace std;
#define MAXN 2005
#define mod 1000000007
typedef long long ll;
int n,k;
ll f[MAXN][MAXN],mul[MAXN*MAXN],inv[MAXN*MAXN];
ll qpow(ll a,ll b){
    ll w=1;
    while(b){
        if(b&1) w=w*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return w;
}
ll C(int n,int m){
    if(m<0||n<0) return 0;
    return mul[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
    cin>>n>>k;
    if(k==1){
        cout<<1;
        return 0;
    }
    mul[0]=1;
    for(int i=1;i<=k*n;i++) mul[i]=mul[i-1]*i%mod;
    inv[n*k]=qpow(mul[n*k],mod-2);
    for(int i=k*n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            if(i-1>=j) f[i][j]+=f[i-1][j];
            if(j) f[i][j]+=f[i][j-1]*(n-j+1)%mod*C(n*k-i-(j-1)*(k-1)-1,k-2)%mod;
            f[i][j]%=mod;
        }
    }
    cout<<f[n][n];
    return 0;
}