Round 1的题目总体而言不难，对19级新生区分度较好，E题略难，C题区间动规无人攻破实属遗憾。
题目难度系数：
- A : 1
- B : 1
- C : 4
- D : 2
- E : 6
- F : 2
题目分析
使用Bfs扩展马的路径即可。
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
#define pii pair<int,int>
#define mp make_pair
const int dx[]= {0,1,1,2,2,-1,-1,-2,-2},dy[]= {0,2,-2,1,-1,2,-2,1,-1};
int n,m,x,y,f[505][505];
bool vst[505][505];
void Bfs() {
queue<pii> Q;
Q.push(mp(x,y));
vst[x][y]=1;
while(!Q.empty()) {
pii Now=Q.front();
Q.pop();
for(int i=1; i<=8; i++) {
pii Next=mp(Now.first+dx[i],Now.second+dy[i]);
if(Next.first<1||Next.first>n||Next.second<1||Next.second>m||vst[Next.first][Next.second])continue;
Q.push(Next);
vst[Next.first][Next.second]=1;
f[Next.first][Next.second]=f[Now.first][Now.second]+1;
}
}
}
int main() {
n=Get_Int();
m=Get_Int();
x=Get_Int();
y=Get_Int();
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)f[i][j]=-1;
f[x][y]=0;
Bfs();
for(int i=1; i<=n; i++) {
for(int j=1; j<m; j++)printf("%d\t",f[i][j]);
printf("%d\n",f[i][m]);
}
return 0;
}
|
题目大意
给一个区间和宽度W，求区间中宽度为W子区间的最大权值和。
题目分析
做一个前缀和，扫描一遍即可。
甚至有条件$P_i\le100000$，双指针都免了。
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=100005;
int n,w,a[maxn],sum[maxn];
int main() {
n=Get_Int();
w=Get_Int();
int m=0;
for(int i=1; i<=n; i++) {
int x=Get_Int(),y=Get_Int();
a[x]+=y;
m=max(m,x);
}
for(int i=1; i<=m; i++)sum[i]=sum[i-1]+a[i];
int ans=0;
for(int i=1; i+w-1<=m; i++)ans=max(ans,sum[i+w-1]-sum[i-1]);
printf("%d\n",ans);
return 0;
}
|
题目分析
这题竟然成了防AK题。（然而我写着写着就忘了自己的状态定义，似乎没资格说这句话）
首先，有几个结论是显然错误的，比如：
- 浇水过程中，浇水的区间一定连续
- 每次选一个代价最小的浇水（局部贪心）
常见的反例有：
1
2
3
4
| 3 1
1 1000 1
1 1 1
1 1000 1
|
那怎么办呢？虽然浇水的区间不一定连续，但总可以划分成若干个区间，我们不妨想到区间DP：
设置状态$f(i,j)$表示浇完区间$[i,j]$的花的最小代价。
现在考虑将两个区间合并在一起进行转移。
枚举断点$k$，给$k$浇水，将区间$[i,k-1]和[k+1,j]$合并起来。
其中$w_{i,j,k}$表示当前区间$[i,j]$，给$k$浇水的代价。
时间复杂度$O(n^3)$
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
int n,w,a[405],b[405],t[405],f[405][405];
int main() {
n=Get_Int();
w=Get_Int();
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
b[i]=Get_Int();
t[i]=ceil(double(Get_Int())/w);
}
for(int len=1; len<=n; len++) {
for(int i=1; i+len-1<=n; i++) {
int j=i+len-1;
f[i][j]=INT_MAX/2;
for(int k=i; k<=j; k++) {
int l_cost=k-1>=i?f[i][k-1]:0;
int r_cost=k+1<=j?f[k+1][j]:0;
f[i][j]=min(f[i][j],l_cost+r_cost+t[k]*(a[k]+b[i-1]+b[j+1]));
}
}
}
printf("%d\n",f[1][n]);
return 0;
}
|
题目分析
如果两个三角形相交，他们的结果一定相同，可以把它们合并起来，并集又可以和其他三角形相交。
因此想到并查集，于是这道题就很简单了。
枚举两两三角形，利用并查集合并，并查集内维护一个最右端点即可。
代码
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
| #include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=1005;
int n,L[maxn],R[maxn],father[maxn],f[maxn];
bool Check(int x,int y) {return (L[x]<=L[y]&&R[x]>=L[y]&&R[x]<=R[y]);}
int Get(int x) {return father[x]==x?x:father[x]=Get(father[x]);}
void Union(int x,int y) {
int fx=Get(x),fy=Get(y);
if(fx!=fy) {
father[fx]=fy;
f[fy]=max(f[fy],f[fx]);
}
}
int main() {
n=Get_Int();
for(int i=1; i<=n; i++) {
L[i]=Get_Int();
R[i]=Get_Int();
f[i]=R[i];
father[i]=i;
}
for(int i=1; i<=n; i++)
for(int j=i+1; j<=n; j++)
if(Check(i,j)||Check(j,i))Union(i,j);
for(int i=1; i<=n; i++)printf("%d\n",f[Get(i)]);
return 0;
}
|
题目大意
有一颗有$n$个节点的树，树的根节点固定为$1$，节点$i$的父节点为$P_i$，并且节点上带有权值$c_i$。
现在需要对于每一个$1$到$m$中的数$x$求出：树中有多少个连通块的乘积为$x$
因为答案过大，只需要输出$\mod 998244353$之后的数即可
题目分析
这是六道题中最难的一道题。
值得一提的是，数据太水了只判链也可以过。
首先这道题求连通块的信息，有点分治，点分树，边分治等经典做法。
在这里讲点分治的做法。
按照点分治的思路，提取出树的重心，考虑经过当前重心的连通块。
现在我们考虑乘积为$x$，这类似一个背包问题，有两种处理思路：
- 自下而上统计信息，然后在重心处暴力合并或者启发式合并。
- 自上而下传递信息，然后再自下而上更新信息。
对于连通块，一般采用第2种方式更为容易，第1种方式一般用于处理路径问题。
于是我们从重心向下访问子结点，每一个结点考虑转移子结点的方案数，这就类似一个背包问题。
预处理出每个数的约数表，这样我们可以在$O(nm\log n\log m)$的时间内完成本题。
代码
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
83
84
85
86
87
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=1005,maxm=4005,mod=998244353;
int n,m,Core,Min,Size[maxn],Maxson[maxn],a[maxn];
LL f[maxn][maxm],ans[maxm];
bool vst[maxn];
vector<int> edges[maxn],d[maxm];
void Get_Size(int Now,int father) {
Size[Now]=1;
Maxson[Now]=0;
for(int Next:edges[Now]) {
if(Next==father||vst[Next])continue;
Get_Size(Next,Now);
Size[Now]+=Size[Next];
Maxson[Now]=max(Maxson[Now],Size[Next]);
}
}
void Get_Core(int Now,int father,int num) {
Maxson[Now]=max(Maxson[Now],Size[num]-Size[Now]);
if(Maxson[Now]<Min) {
Min=Maxson[Now];
Core=Now;
}
for(int Next:edges[Now]) {
if(Next==father||vst[Next])continue;
Get_Core(Next,Now,num);
}
}
int tmp[maxm];
void Dfs(int Now,int fa,int v) {
if(v>m)return;
for(int i=1; i<=m; i++)f[Now][i]=0;
f[Now][a[Now]]=1;
for(int Next:edges[Now]) {
if(vst[Next]||Next==fa)continue;
Dfs(Next,Now,v*a[Next]);
for(int j=1; j<=m; j++)tmp[j]=f[Now][j];
for(int j=a[Now]; j<=m; j+=a[Now])
for(int k:d[j/a[Now]])tmp[j]=(tmp[j]+f[Now][j/k]*f[Next][k]%mod)%mod;
for(int j=1; j<=m; j++)f[Now][j]=tmp[j];
}
}
void Solve(int Now) {
Min=n;
Get_Size(Now,0);
Get_Core(Now,0,Now);
Now=Core;
vst[Now]=1;
Dfs(Now,0,a[Now]);
for(int i=1; i<=m; i++)ans[i]=(ans[i]+f[Now][i])%mod;
for(int Next:edges[Now]) {
if(vst[Next])continue;
Solve(Next);
}
}
void AddEdge(int x,int y) {edges[x].push_back(y);edges[y].push_back(x);}
int main() {
n=Get_Int();
m=Get_Int();
for(int i=2; i<=n; i++)AddEdge(Get_Int(),i);
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=m; i++)
for(int j=1; j<=i; j++)if(i%j==0)d[i].push_back(j);
Solve(1);
for(int i=1; i<=m; i++)printf("%lld\n",ans[i]);
return 0;
}
|
题目大意
将分数转化为连分数
题目分析
题目竟然没给出$n$的范围！连分数表示会不会停不下来导致$n$很大呢？
不会，考虑一下，我们每一次的操作：除法，取模，交换分子分母
这一个过程是不是类似辗转相除？
其实这就是辗转相除，因此连分数永远有有限解，并且时间复杂度与求$\gcd$一样都是$\log$级别。
代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL Get_Int() {
LL num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
vector<LL> ans;
void Cal(LL x,LL y) {
LL gcd=__gcd(x,y);
x/=gcd;
y/=gcd;
ans.push_back(x/y);
if(x%y==1) {
ans.push_back(y);
return;
}
Cal(y,x%y);
}
int main() {
int t=Get_Int();
while(t--) {
ans.clear();
LL a=Get_Int(),b=Get_Int();
Cal(a,b);
for(int i=0; i<ans.size()-1; i++)printf("%lld ",ans[i]);
printf("%lld\n",ans.back());
}
return 0;
}
|
