做题笔记[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\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$。考虑转移：
- 若当前位置放一个有颜色的球。根据定义，我们一次安排一类 $k-1$ 个同颜色的球的位置，那么这个位置是一个没有出现过的颜色的球。因为是从 $f_{i,j-1}$ 转移过来，所以这个球的颜色有 $n-j+1$ 种。当前位置放一个，前面有一个此颜色转换成的白球，后面此种颜色共安排 $k-2$ 个，则可以安排在后面 $nk-i-(j-i)(k-1)-1$ 个空位种的 $k-2$ 个位置，则有转移方程：
边界：$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;
}
|
