摘要：

NOIP2018复赛成绩查询，程序公布，成绩申诉，确定分数线及获奖名额以及分数线公示等时间表公布。

NOIP2018复赛解析及代码参考

声明：本解析来源于网络，仅供大家参考，最终答案及测试数据均以CCF官方公布为准！

根据目前同学们的反应，普及组题目比去年简单。关于题目的任何问题，欢迎留言给小编讨论。

普及组题目解析

1 标题统计

NOIP 罕见的考察了字符串。不过签到题/语法题难度。

考察 getline或gets 的用法。

或者是直接 getchar, cin char, scanf %c 一个一个字符读，

参考代码：

#include

int main() {

int ans = 0;

char ch;

while(ch = getchar(), ch != '\n') ans += (ch != ' ');

printf("%d\n", ans);

参考代码：

#include

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;

}

2 龙虎斗

这个题目目的是:

有一个长度为 n 个数组 a_i，下标从 1 开始。

其中 m 是中心，第 i 个位置的贡献是

设

输入 x，现在可以选择 1 到 n 的某个位置加上 x，希望操作后的 s 绝对值最小。问加在哪个位置最好，如果有多个最好的位置，输出标号最小的位置。

做法：

大概加在 -s/x 的位置。

其实直接枚举加在什么位置，更新答案，也ok。

#include

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;

}

3摆渡车

比较麻烦的动态规划。

大意：

有 n 个人到达，摆渡车往返一次需要 m 的时间。问所有人最少需要等待多久。

做法：

首先猜想，发车时间一定是人到达的时间，发现是错的。

其次猜想，如果 t_i 有人到，那么发车时间一定是 t_i 到 t_i + m - 1 之间。然后可以得到一个 nma_i 的 DP。

参考代码：

#include

#include

using namespace std;

const int N = 500 + 10;

const int M = 100 + 10;

const int inf = 1000000000;

int t[N], nt[N];

int f[100210], cnt[100210];

int main()

{

int res, n, m, s, d, i, j;

cin>>n>>m;

for (i=1; i<=n; i cin>>t[i];

sort(t + 1, t + n + 1);

nt[0] = 0;

nt[1] = m;

for (i=2; i<=n; i++)

if (t[i] - t[i-1] > 2 * m) nt[i] = nt[i-1] + 2 * m; else nt[i] = nt[i-1] + t[i] - t[i-1];

for (i=1; i<=n; i++) cnt[nt[i]] ++;

for (i=nt[n]-1; i>=0; i--)

{

f[i] = inf;

s = d = 0;

for (j=1; j<2*m; j++)

{

d += s;

if (j >= m && d + f[i+j] < f[i]) f[i] = d + f[i+j];

s += cnt[i+j];

}

}

cout<<f[0]<<endl;

return 0;

}

4 对称二叉树

这个题比去年第四题简单非常多。

并且 NOIP 考察了信仰一交技能。（即写一个暴力，其实就是对的，看敢不敢交） 考察了爆栈，但据陈俊锟说，NOIP 一直开栈，虽然并没有公开。

大意：

输入一个二叉树，问有多少个二叉树是对称的。

二叉树每个节点有权值，要求结构对称和权值对称。

做法:

对于每个节点直接判断即可。

通过提前返回（发现一个地方不对称，直接返回整体不对称，不继续做） 或者是提前比较大小（如果对称，那么要求子树大小整体对称）

不加任何优化，就是一个完全正确的做法。似乎 n ≤ 1000000 会爆栈。

如果避免爆栈，就是需要把深搜换成广搜，需要使用队列

参考代码：

#include<bits/stdc++.h>

using namespace std;

int v[1000005],ch[1000005][2],c[1000005],n,ans;

bool same(int a,int b)

{

if(a==b)return 1;

if(!a||!b)return 0;

return v[a]==v[b]&&same(ch[a][0],ch[b][1])&&same(ch[a][1],ch[b][0]);

}

void dfs(int i)

{

if(!i)return;

dfs(ch[i][0]);

dfs(ch[i][1]);

c[i]=1+c[ch[i][0]]+c[ch[i][1]];

v[i]=v[i]+v[ch[i][0]]+v[ch[i][1]];

if(ans<c[i]&&same(ch[i][0],ch[i][1]))ans=c[i];

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)scanf("%d",&v[i]);

v[0]=1005;

for(int i=1;i<=n;i++)

for(int k=0;k<2;++k){

scanf("%d",&ch[i][k]);

if(ch[i][k]==-1)ch[i][k]=0;

}

dfs(1);

printf("%d",ans);

return 0;

}

提高组

第一天题目总体来说是这些年中比较简单的。三个题目都被说是原题。

1 铺设道路

背景

本题主要考察了数学。

本题和 NOIP2013 第一天第一题一模一样，数据范围，输入输出格式，标程做法，题目主人公。

只是题意有微小的差别。

大意：

输入一个数组 a_i，每次可以选择一个区间，使区间内的数字都减少 1。希望把所有数字都变成 0，问最少需要几次操作。

据说本题是 NOIP2013原题。数据范围，输入输出格式果然完全一样。见下图：

求差分，考虑差分中所有正数的和。（同时也是所有负数和的相反数）

#include

int main() {

int n, h1 = 0, h, ans = 0;

scanf("%d", &n);

while(n--) {

scanf("%d", &h);

h > h1 ? ans += h - h1 : 0;

h1 = h;

}

printf("%d", ans);

return 0;

}

2 货币系统

背景：

主要考察完全背包和动态规划

大意：

输入 n 个面值 ai 这些面值可以凑出一些金额。问能凑出这样的金额至少需要几个面值。

n ≤ 100, a_i ≤ 25000

做法：

将所有面值排序。

面值最小的一定要选。

如果用面值最小的凑不出面值第二小的，那么要选第二小的。（如果凑的出，就不用选） 对于面值 x，如果用比 x 小的面值凑不出 x，就需要选 x（如果凑的出，就不用选）

凑得出凑不出，这是一个完全背包问题，时间复杂度是 O(n × a_i)。

#include<bits/stdc++.h>

using namespace std;

int T,n,ans;

int a[103],f[300003];

int main(){

scanf("%d",&T);

while (T--){

scanf("%d",&n);

for (int i=1;i<=n;i++)

scanf("%d",&a[i]);

sort(a+1,a+1+n);

ans=n;

memset(f,0,sizeof(f));

f[0]=1;

for (int i=1;i<=n;i++){

if (f[a[i]]) ans--;

for (int j=0;j+a[i]<=30000;j++)

if (f[j]) f[j+a[i]]=1;

}

printf("%d\n",ans);

}

return 0;

}

3 赛道修建

背景：

本题主要考察了二分和树形动态规划。

这个题被说 BZOJ 2067 一样，我觉得这个题比 BZOJ 2067 非常类似。都是先二分，再树形 DP，每个点再需要二分更新。

大意：

输入一棵 n 个点的树，有边权，从中找出 m 个边不相交的链（点可以相交），使得最短的链最长。

做法：

首先看到最短的链最长，显然想到是一个二分。

然后看到 n 的范围，每个点应该只有常数个状态。

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;

int n,m,K,ans;

int hd[N],nxt[N],to[N],w[N],tot;

void add(int a,int b,int c) {

to[++tot]=b,w[tot]=c,nxt[tot]=hd[a],hd[a]=tot;

}

int dfs(int u,int f) {

multiset st;

for (int i=hd[u];i;i=nxt[i]) {

if (to[i]!=f) st.insert(dfs(to[i],u)+w[i]);

}

multiset::iterator p1,p2;

while ((p1=st.end())!=st.begin()&&*--p1>=K) {

++ans;

st.erase(p1);

}

int re=0;

while ((p1=st.begin())!=st.end()) {

int tmp=*p1;

st.erase(p1);

if ((p2=st.lower_bound(K-tmp))!=st.end()) {

++ans;

st.erase(p2);

}

else re=tmp;

}

return re;

}

bool check() {

ans=0;

dfs(1,0);

return ans>=m;

}

int main() {

scanf("%d%d",&n,&m);

for (int i=1,x,y,z;i<n;++i) {

scanf("%d%d%d",&x,&y,&z);

add(x,y,z);

add(y,x,z);

}

int L=0,R=5e8;

while (L<R) {

K=L+R+1>>1;

if (check()) L=K;

else R=K-1;

}

printf("%d\n",L);

}

提高组day2

第一题是一个简单的图论。

第二题是一个搜索找规律。

第三题又是树形 DP

5 旅行

大意

输入一棵树，n 个点，n - 1 条边，找到一个 DFS 序最小的 DFS 序列。

输入一棵带环树，n 个点，n - 1 条边，找到一个 DFS 序最小的 DFS 序列。对于所有数据 n ≤ 5000。

做法

对于一个树的情况大概是每次 DFS 标号最小的孩子。

参考代码：

#include

#include

#include

int *E[5005], D[5005];

int e[5005][2], dx, dy;

int cur[5005], ans[5005];

bool v[5005];

void dfs(int i) {

v[i] = 1;

cur[++*cur] = i;

for(int k = D[i]; k--; )

if(!v[E[i][k]] && !(i == dx && E[i][k] == dy) && !(i == dy && E[i][k] == dx))

dfs(E[i][k]);

// v[i] = 0;

}

int main() {

int n, m; scanf("%d%d", &n, &m);

for(int i = 1; i <= m; ++i) {

int x, y;

scanf("%d%d", &x, &y);

e[i][0] = x;

e[i][1] = y;

D[x]++;

D[y]++;

}

for(int i = 1; i <= n; ++i) { E[i] = new int[D[i] + 1]; D[i] = 0; }

for(int i = 1; i <= m; ++i) {

int x = e[i][0], y = e[i][1];

E[x][D[x]++] = y;

E[y][D[y]++] = x;

}

for(int i = 1; i <= n; ++i) {std::sort(E[i], E[i] + D[i]); std::reverse(E[i], E[i] + D[i]);}

if(m == n - 1) {

dfs(1);

memcpy(ans + 1, cur + 1, n << 2);

} else {

ans[1] = n + 1;

for(int i = 1; i <= m; ++i) {

dx = e[i][0];

dy = e[i][1];

*cur = 0;

memset(v + 1, 0, n);

dfs(1);

if(*cur == n) {

bool copy = 1;

for(int i = 1; i <= n; ++i) {

if(cur[i] > ans[i]) copy = 0;

if(cur[i] != ans[i]) break;

}

if(copy) memcpy(ans + 1, cur + 1, n << 2);

}

}

}

for(int i = 1; i <= n; ++i) printf("%d%c", ans[i], " \n"[i == n]);

}

6 填数游戏

背景

NOIP 罕见的考了计数问题。

大意

填一个 n × m 的

对于所有数据 n ≤ 8, m ≤ 1000000。

目做法：

n 很小，猜测应该是状态压缩 DP，首先暴力。设 F (n, m) 是 n, m 的答案。

发现 n 确定的情况下，当 m ≥ n + 2 时，F (n, m) = 3F (n, m - 1)。所以难点在于暴力比较小的部分。

暴力主要分为两部分，枚举和验证。

枚举部分，注意到右上到左下斜线上一定是单调不降的（先一些 0 再一些 1。） 利用这个可以极大的减少需要计算的状态。

然后考虑验证的问题，一共走的步数很少（比如 20 步） 可以用一个 int 类型来存这个 01 串。

对于每个点计算，从当前点到终点，字串最大是多少，最小是多少。

对于不在最后一行最后一列的点，都要保证右边的最大小于等于下边的最小。

参考代码：

#include

#include

#include

#include

using namespace std;

const int mo=1e9+7;

int n,m,d[100][100];

int f[10001][50],g[10001][50];

int Solve() {

for (int i=0;i<(1<<n);i++) f[i][n]=1;

for (int i=2;i<=m;i++) {

for (int j=0;j<(1<<n);j++)

for (int k=1;k<=n;k++) g[j][k]=0;

for (int j=0;j<(1<<n);j++) {

for (int k=1;k<=n;k++) {

if (f[j][k]==0) continue;

for (int k2=0;k2<(1<<n);k2++) {

bool judge=1;

for (int k3=1;k3<n;k3++) {

bool j1=(k2&(1<<(k3-1)));

bool j2=(j&(1<<k3));

if (j1>j2) {

judge=0;

break;

}

if (j1==j2&&k3>k) {

judge=0;

break;

}

}

if (!judge) continue;

int max0=1;

for (int k3=1;k3<n;k3++) {

bool j1=(k2&(1<<(k3-1)));

bool j2=(j&(1<<k3));

if (j1!=j2) break;

max0=k3+1;

if (k3+1>=k) break;

}

max0=min(max0,k);

g[k2][max0]=(g[k2][max0]+f[j][k])%mo;

}

}

}

for (int j=0;j<(1<<n);j++)

for (int k=1;k<=n;k++) f[j][k]=g[j][k];

}

int ans=0;

for (int i=0;i<(1<<n);i++)

for (int j=1;j<=n;j++) ans=(ans+f[i][j])%mo;

return ans;

}

int main() {

scanf("%d%d",&n,&m);

if (n>m) swap(n,m);

if (n==1) {

int now=1;

for (int i=1;i<=m;i++) now=now*2%mo;

cout<<now<<endl;

return 0;

}

if (n==m) {

int ans=Solve();

cout<<ans<<endl;

return 0;

}

int km=m;

m=n+1;

int ans=Solve();

for (int i=n+2;i<=km;i++) ans=(ans*2%mo+ans)%mo;

cout<<ans<<endl;

return 0;

}

7保卫王国

本题是一个树形dp问题。参考代码：

#include

#include<set>

#include

#include

#define maxn 100010

#define maxm 200010

#define ll long long

#define mp make_pair

#define pii pair

using namespace std;

int hd[maxn],nxt[maxm],pnt[maxm],tot=0;

int fa[maxn][20],val[maxn],dep[maxn],n,q;

ll f[maxn][2],g[maxn][2],fh[maxn][20][2][2];

const ll INF=1LL<<60;

char Type[10];

set st;

void read(int &x){

char ch=x=0;

while(!isdigit(ch))

ch=getchar();

while(isdigit(ch))

x=x*10+ch-'0',ch=getchar();

}

void add(int x,int y){

pnt[++tot]=y,nxt[tot]=hd[x],hd[x]=tot;

}

void dfs(int x,int FA,int d){

fa[x][0]=FA,dep[x]=d;

f[x][1]=val[x];

for(int i=hd[x];i;i=nxt[i]){

int v=pnt[i];

if(v==FA)

continue;

dfs(v,x,d+1);

f[x][0]+=f[v][1],f[x][1]+=min(f[v][0],f[v][1]);

}

}

void dfs_2(int x){

for(int i=hd[x];i;i=nxt[i]){

int v=pnt[i];

if(v==fa[x][0])

continue;

g[v][0]=g[x][1]+f[x][1]-min(f[v][0],f[v][1]);

g[v][1]=min(g[x][0]+f[x][0]-f[v][1],g[v][0]);

dfs_2(v);

}

}

ll solve(int x,int a,int y,int b){// x <---> a , y <---> b

if(dep[x]<dep[y])

swap(x,y),swap(a,b);

ll tx[2]={INF,INF},ty[2]={INF,INF};

ll nx[2],ny[2];

tx[a]=f[x][a],ty[b]=f[y][b];

for(int i=19;~i;i--){

if(dep[fa[x][i]]>=dep[y]){

nx[0]=nx[1]=INF;

for(int j=0;j<2;j++){

for(int k=0;k<2;k++)

nx[j]=min(nx[j],tx[k]+fh[x][i][k][j]);

}

tx[0]=nx[0],tx[1]=nx[1],x=fa[x][i];

}

}

if(x==y)

return tx[b]+g[x][b];

for(int i=19;~i;i--){

if(fa[x][i]!=fa[y][i]){

nx[0]=nx[1]=ny[0]=ny[1]=INF;

for(int j=0;j<2;j++){

for(int k=0;k<2;k++){

nx[j]=min(nx[j],tx[k]+fh[x][i][k][j]);

ny[j]=min(ny[j],ty[k]+fh[y][i][k][j]);

}

}

tx[0]=nx[0],tx[1]=nx[1],x=fa[x][i];

ty[0]=ny[0],ty[1]=ny[1],y=fa[y][i];

}

}

int lca=fa[x][0];

ll ans0=f[lca][0]-f[x][1]-f[y][1]+tx[1]+ty[1]+g[lca][0];

ll ans1=f[lca][1]-min(f[x][0],f[x][1])-min(f[y][0],f[y][1])+min(tx[0],tx[1])+min(ty[0],ty[1])+g[lca][1];

return min(ans0,ans1);

}

int main(){

read(n),read(q),scanf("%s",Type);

for(int i=1;i<=n;i++)

read(val[i]);

for(int i=1,u,v;i<=n-1;i++){

read(u),read(v);

add(u,v),add(v,u);

st.insert(mp(u,v)),st.insert(mp(v,u));

}

dfs(1,0,1),dfs_2(1);

for(int i=1;i<=n;i++){

fh[i][0][0][0]=INF;

fh[i][0][0][1]=f[fa[i][0]][1]-min(f[i][0],f[i][1]);

fh[i][0][1][0]=f[fa[i][0]][0]-f[i][1];

fh[i][0][1][1]=f[fa[i][0]][1]-min(f[i][0],f[i][1]);

}

for(int j=1;j<=19;j++){

for(int i=1;i<=n;i++){

int tmp=fa[i][j-1];

fa[i][j]=fa[tmp][j-1];

for(int u=0;u<2;u++){

for(int v=0;v<2;v++){

fh[i][j][u][v]=INF;

for(int w=0;w<2;w++)

fh[i][j][u][v]=min(fh[i][j][u][v],fh[i][j-1][u][w]+fh[tmp][j-1][w][v]);

}

}

}

}

for(int i=1,a,b,x,y;i<=q;i++){

read(a),read(x),read(b),read(y);

if(!x&&!y&&st.find(mp(a,b))!=st.end()){

puts("-1");

continue;

}

printf("%lld\n",solve(a,x,b,y));

}

return 0;

}

咨询方式：

司老师 18610112920 赵老师 18610112915 高老师18611056259 老师 18611083835 张老师 18610150289

定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，信息学训练营信息等诸多优质内容的wx公众平台noipnoi