NOIP 2018 普及组题解

发表于 | | 阅读次数:
字数统计: 756 字
退役选手的 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%