NOIP2018普及组复赛题解

发布时间:2018-11-22 18:05:09 作者:ex_jason 阅读量:302

标题统计

分析

使用 scanfcin

读入每个字符串(不包含空格),然后统计字符串的长度之和即可。

时间复杂度O(|s|)

代码

#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;
}

龙虎斗

分析

首先,我们直接把 s1

位工兵增加到第 p1 号兵营,设 s=ni=1ai(im)

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

时间复杂度O(n)

代码

#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;
}

摆渡车

分析

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

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

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

f[i][j]=min0k<i,0p<m{f[k][p]+cost(k+1,i,ti+j)}

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

这个式子直接计算是 O(n3m2)的,接下来考虑转移如何优化。上述式子中,我们通过对 ti 做前缀和可以 O(1) 计算出 cost 的值。我们再记 g[i][j]=min0j<mf[i][j](这个前缀 min 可以在转移过程中维护),转移方程化为

f[i][j]=min0k<i{g[k][x]+cost},其中 x=min(m1,ti+jtkm)  且 x0,时间复杂度优化为 O(n2m)

时间复杂度O(n2m)

代码

#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;
}

对称二叉树

分析

u的左右儿子分别为 lsonursonu。对于以 u 为根的一棵子树,如果它是对称的那么必须满足:

  1. 是对称的。
  2. 对于每一对左右儿子x,y必须满足 lsonxrsony 是对称的、rsonxlsony 是对称的。


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

复杂度证明:每次判断子树 x

y 是否对称时,复杂度为 O(min(sizex,sizey)),如果一个点能往上继续产生贡献,那么大小至少乘以 2,总复杂度即为 O(nlogn)

时间复杂度O(nlogn)

代码

#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;
}

我要评论 登录后才能发布评论

推荐阅读

 2018-12-14 20:44:05   ex_jason

我是我吗

 2018-11-24 08:54:16   ex_jason

题解洛谷 P1063 【能量项链...

 2018-11-24 08:53:32   ex_jason

关于NOIP的注意事项?CCF官...

 2018-11-24 08:52:31   ex_jason

最小生成树

 2018-11-22 18:05:09   ex_jason

NOIP2018普及组复赛题解

 2018-11-10 20:40:14   ex_jason

LOL S8 决赛视频

  文章归档

ex_jason的博客"    我要留言
Catfish(鲶鱼) CMS V 4.8.51