NOIP 2018 普及组题解

退役选手的 NOIP 2018 普及组题解 QAQ

题面


数据

下载地址:NOIP 2018 普及组测试数据


标题统计

Description

输入一行可能带空格的字符串,求除空格外有多少个字符。

Solution

使用 $\text{scanf}$ 或 $\text{cin}$ 读入每个字符串(不包含空格),然后统计字符串的长度之和即可。

时间复杂度:$O(|s|)$

Code

1
2
3
4
5
6
7
8
9
10
#include <cstdio>
#include <cstring>

int main() {
char s[6];
int ans=0;
while(~scanf("%s",s+1)) ans+=strlen(s+1);
printf("%d\n",ans);
return 0;
}

龙虎斗

Description

在数轴上有 $n$ 个点,第 $i$ 个点的位置为 $i$,权值为 $c_i$。现在给第 $p_1$ 个点的权值增加 $s_1$,你必须再给一个点的权值增加 $s_2$ 满足对于给定的一个坐标为 $m$ 的点,使得 $\sum_{i=1}^n c_i(i-m)$ 的绝对值最小。

Solution

首先,我们直接把 $s_1$ 位工兵增加到第 $p_1$ 号兵营,设 $s=\sum_{i=1}^n c_i(i-m)$

我们考虑如果在第 $p_2$ 的位置增加 $s_2$ 位工兵,那么可以得到 $s’=s+s_2(p_2-m)$。我们只需要求出使得 $s’$ 的绝对值最小的 $p_2$。我们可以直接枚举 $p_2$,在 $O(1)$ 的时间内计算出 $s_2$,更新答案的过程中要注意字典序最小的要求。

时间复杂度:$O(n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>

const int N=1e5+5;
int n,m,p1;
long long c[N],s1,s2;

int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld",&c[i]);
scanf("%d%d%lld%lld",&m,&p1,&s1,&s2);
c[p1]+=s1;
long long sum=0,mn=1LL<<62;
for(int i=1;i<=n;++i) sum+=1LL*(i-m)*c[i];
int ans;
for(int i=1;i<=n;++i) {
long long now=sum+1LL*(i-m)*s2;
if(now<0) now=-now;
if(now<mn) mn=now,ans=i;
}
printf("%d\n",ans);
return 0;
}

摆渡车

Description

有 $n$ 名同学在同一地点等车去同一目的地,第 $i$ 个人在第 $t_i$ 分钟开始等车。现在只有一辆车可以载人(车的容量可以视为无限大),往返一趟需要的时间为 $m$ 分钟。这辆车需要把所有同学都送到目的地。如果这辆车能在任何时间出发,回到等车地点后又可以即刻出发,求出这些同学的等车时间之和最小为多少。

Solution

引理:对于每个乘客,如果他开始等待的时刻为 $t$,那么搭载他的车的发车时间 $t_0\in [t,t+m)$。

证明:如果存在一种发车时间 $\geqslant t+m$,那么发车时间一定可以提早若干个 $m$ 使得 $t_0$ 到达 $[t,t+m)$。这样不会影响其他 $\geqslant t+m$ 的发车时间,不会干扰后面的人等车。

我们考虑 $\text{DP}$ 状态设计:$f[i][j]$ 表示搭载了前 $i$ 个人,搭载第 $i$ 个人的摆渡车的发车时间为 $t_i+j$ 的最小等候时间总和。朴素的转移方程为:

其中 $\text{cost}(i,j,k)$ 表示第 $i\sim j$ 个人在 $k$ 时间乘车的等候时间总和。注意转移过程中有 $t_i+j\geqslant t_k+p+m$(当前这趟车比上一趟车至少晚 $m$)的限制!

这个式子直接计算是 $O(n^3m^2)$的,接下来考虑转移如何优化。上述式子中,我们通过对 $t_i$ 做前缀和可以 $O(1)$ 计算出 $cost$ 的值。我们再记 $g[i][j]=\min_{0\le j<m}f[i][j]$(这个前缀 $\min$ 可以在转移过程中维护),转移方程化为 $f[i][j]=\min_{0\le k<i}\{g[k][x]+\text{cost}\}$,其中 $x=\min(m-1,t_i+j-t_k-m)$ 且 $x\geqslant 0$,时间复杂度优化为 $O(n^2m)$ 。

时间复杂度:$O(n^2m)$

Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=505,M=105;
int n,m,a[N];
long long sum[N],f[N][M];

long long query(int l,int r) {
return sum[r]-sum[l-1];
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
std::sort(a+1,a+n+1);
for(int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;++i) {
f[i][0]=1LL*i*a[i]-query(1,i);
for(int j=0;j<m;++j) {
for(int k=1;k<i;++k) {
int x=std::min(m-1,a[i]+j-m-a[k]);
if(x<0) continue;
f[i][j]=std::min(f[i][j],f[k][x]+1LL*(i-k)*(a[i]+j)-query(k+1,i));
}
}
for(int j=1;j<m;++j) {
f[i][j]=std::min(f[i][j],f[i][j-1]);
}
}
printf("%lld\n",f[n][m-1]);
return 0;
}

对称二叉树

Description

一棵二叉树被称为对称二叉树当且仅当:这是一棵二叉树,将这棵树所有节点的左右子树交换,新树和原树的结构和点权完全相同。

现在给定一棵二叉树,希望找出它的一棵子树,使得该子树为对称二叉树,且节点数最多。

Solution

记 $u$ 的左右儿子分别为 $\text{lson}_u$ 和 $\text{rson}_u$。对于以 $u$ 为根的一棵子树,如果它是对称的那么必须满足:

  1. $\text{lson}_u$ 和 $\text{rson}_u$ 是对称的。
  2. 对于每一对左右儿子 $x,y$,必须满足 $\text{lson}_x$ 和 $\text{rson}_y$ 是对称的、$\text{rson}_x$ 和 $\text{lson}_y$ 是对称的。

我们可以对于每个节点暴力判断是否满足条件。判断的过程中,我们可以使用一些剪枝:左右儿子的大小、权值和等必须相同。

复杂度证明:每次判断子树 $x$ 和 $y$ 是否对称时,复杂度为 $O(\min(\text{size}_x,\text{size}_y))$,如果一个点能往上继续产生贡献,那么大小至少乘以 $2$,总复杂度即为 $O(n\log n)$

时间复杂度:$O(n\log n)$

Code

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 <cstdio>

const int N=1e6+5;
int n,val[N],ch[N][2],sz[N];

void dfs(int u) {
if(!u) return;
dfs(ch[u][0]),dfs(ch[u][1]);
sz[u]=1+sz[ch[u][0]]+sz[ch[u][1]];
}
bool same(int x,int y) {
if(!x&&!y) return 1;
if(!x||!y||sz[x]!=sz[y]||val[x]!=val[y]) return 0;
return same(ch[x][0],ch[y][1])&&same(ch[x][1],ch[y][0]);
}
bool check(int u) {
return same(ch[u][0],ch[u][1]);
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&val[i]);
for(int i=1;i<=n;++i) for(int j=0;j<2;++j) {
scanf("%d",&ch[i][j]);
if(ch[i][j]<0) ch[i][j]=0;
}
dfs(1);
int ans=0;
for(int i=1;i<=n;++i) if(sz[i]>ans&&check(i)) ans=sz[i];
printf("%d\n",ans);
return 0;
}
0%