考试包下载 >> 《Simple or Naive》

Simple or Naive - that is the question

一、题目概况

中文题目名称 折线 链表 最小直径生成树
英文题目与子目录名 polyline chain mdst
可执行文件名 polyline chain mdst
输入文件名 polyline.in chain.in mdst.in
输出文件名 polyline.out chain.out mdst.out
每个测试点时限 1s 1s 1s
测试点数目 10 10 10
每个测试点分值 10 10 10
结果比较方式 全文比较 SPJ 全文比较
题目类型 传统 传统 传统
运行内存上限 128M 128M 128M
题目来源 Codeforces 原创 ZOJ

二、提交源程序文件名

对于C++语言 polyline.cpp chain.cpp mdst.cpp
对于C语言 polyline.c chain.c mdst.c
对于pascal语言 polyline.pas chain.pas mdst.pas

三、编译命令（不包含任何优化开关）

对于C++语言 g++ -o polyline polyline.cpp -lm g++ -o chain chain.cpp -lm g++ -omdst mdst.cpp -lm
对于C语言 gcc -o polyline polyline.c -lm gcc -o chain chain.c -lm gcc -o mdst mdst.c -lmc
对于pascal语言 fpc polyline.pas fpc chain.pas fpc mdst.pas

四、注意事项

1、文件名（程序名和输入输出文件名）必须使用英文小写。

2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。

3、知识点保证都在NOIP范围内！

五、题面

1.折线 (polyline.cpp/c/pas)

[Description]

二维坐标平面上，我们称一条折线是畸形的，当且仅当它依次经过如下坐标:

(0,0)−>(x, x)–>(2x, 0)–>(3x, x)–>(4x, 0) … (0,0)->(x, x)–>(2x, 0)–>(3x, x)–>(4x, 0) … 

其中x称为这条折线的畸形值。

现给出一点(a,b)(a,b)，询问是存在一条或多条畸形的折线经过它。若存在，找出满足要求的折线中畸形值最小的一条。

[Input]

一行两个整数a,ba,b.
其中1≤a,b≤1091≤a,b≤10^9.

[Output]

若存在满足要求的直线，输出最小畸形值，答案用既约分数表示。
不存在则输出−1-1.

[Sample Input & Output]

polyline.in polyline.out
4 1 5/4

[Hint]

样例解释：

最小畸形值为1.25，如图所示：

2.链表 (chain.cpp/c/pas)

[Description]

笔者最近学了学块状链表…于是造了这道题

我们可以实力简化一下模型：

一个长度为nn的链表共有nn个“块”，编号1∼n1\sim n。每块中放置了一个长度为kk的数组，第i块中的数组0∼ai−10\sim a_{i-1}的单位空间内存储了长度为ai的有效信息。

这样，第i块中的数组就有k−aik-a_i的单位空间是没有使用的，这样造成了时间和空间效率的常数增加，所以需要合并一部分块来提高运行效率。

两个块i,ji,j能够合并，当且仅当i+1=ji+1=j，且ai+aj≤ka_i+a_j≤k.

操作为:将jj的有效信息紧接到i的有效信息后面，在ii的数组中0∼ai+aj−10\sim a_i+a_{j-1}的单位空间内形成长度为ai+aja_i+a_j的有效信息，并删除jj。

令表示第i∼ji\sim j块最少能合并到多少块，如当k=2k=2时{1,1,1}\{1,1,1\}最少合并到两块。

现给定一个长度为nn的链表，希望孙子们完成下列任务：

1.计算 f(i,j)f(i,j)

2.计算 ∑i=1n∑j=inf(i,j)\sum_{i=1}^{n}\sum_{j=i}^{n}f(i,j)

[Input]

第一行两个整数n,kn,k.
第二行n个整数表示a1 ana_1~a_n.
其中1≤n≤105,1≤k≤1091≤n≤10^5,1≤k≤10^9,所有aia_i小于等于kk.

[Output]

一行两个整数，空格隔开，分别为第一二个任务的值。
对于每个测试点，若第一问正确，获得30%的分数，若第二问正确，获得70%的分数。

[Sample Input&Output]

chain.in chain.out
3 2
1 1 1		 2 7

3.最小直径生成树 (mdst.cpp/c/pas)

[Description]

给出一个有nn个结点和mm条边的无向连通图GG，找出GG的所有生成树中直径最小的一棵，输出它的直径。

注：一棵树的直径指这棵树上任意两点间路径的最大值。

[Input]

第一行两个整数n,mn,m.
接下来mm行，每行三个整数x,y,wx,y,w，表示结点xx和yy间有一条长度ww的边。

其中x,y≤n≤200,n−1≤m≤10000,0≤w≤105x,y≤n≤200,n−1≤m≤10000,0≤w≤10^5.
输入保证没有自环和重边。

[Output]

一行一个整数，表示最小直径。

[Sample Input&Output]

mdst.in mdst.out
3 3
1 2 1
1 3 2
2 3 1		 2

[Hint]

样例解释：

原图及其最小直径生成树。

Solutions - it is supercalifragilisticexpialidocious!

随便扯扯
第一次出题，好紧张><
各种纠结题意讲清楚了没/标程写对了没/数据强不强/难度适不适中/balabala…还有…这篇题解写得好不好qwq

还是从头说起…
出题过程是这样的…
大概一个月前接到要出模拟题的消息…
当时脑中浮现的是一道去年寒假脑补的题…当时并没做出来，以为自己太弱了。现在又想了想，还是不会做啊…但立志要把er这道题放上去。于是跑去问zty，十分敷衍；问lxy，觉得不可做；问vfk，也不会做…于是还是弃掉这道题吧qwq
不过不着急，还有时间
期间打了次cf，当时没人跟我一起打，于是我就偷偷将一题kuǎi了过来2333（就是第一题），然后帮助大家复习欧几里得，修改了答案的表示方法。
有次随便点开一道BZOJ的题，被标题深深吸引(smg- -)，然后就有了今天的第三题= =，只是增强了下数据范围（小数据都是OJ上的源数据）。
有了数学和数据结构，还差贪心/二分/动态规划啊！
在学块状链表的时候有合并操作，当时脑补了些奇怪的东西，就成了第二题的第一问。本来设计了个DP解决，后来一想这TM就是个贪心= =（当时一身冷汗，还好没这样就放出来），然后整张卷子难度就十分不乐观了啊，怎么办呢…还是稍微改改题吧er…于是想了很多种改法（在下面可以见到一些），发现这样能考到DP，且复杂度跟第一问相吻，就喜闻乐见的出出第二问啦~
在这里还要特别感谢lxy神犇提供的帮助~

总结来说，认真出一张卷子过程还是非常锻炼的~
然后我觉得我出得非常好- -
难度达到了，而且知识点并没有超过范围…
然后考点设计的比较全面，都是些常考的…
然后题面也没有那么冗杂了…
缺陷就是代码量偏小吧…应该大家能感知得到，然后数据结构考察也比较弱。
总之自己比较满意…
就不扯淡了，下面有三道题题解，同时拓展了一些内容。

Written by Codeplay0314 on 2015/10/01

1.折线

显然问题有解当且仅当a≤ba≤b.下面讨论有解的情况:

可以证明最优解下点一定在折线的右边一支，否则存在更优（证明略）。

过(0,0)，(a,b)(0,0)，(a,b)以x轴为斜边画出一个直角等腰三角形（深绿）

我们即要在这个三角形底上切出尽量多的全等直角三角形（草绿），且(x,y)(x,y)要在最后一个三角形的边上。可以看出，三角形切得越多，xx就越小。

最多切多少个呢？(a+b)/(2∗b)(a+b)/(2*b).所以ans=0.5∗(a+b)/((a+b)/(2∗b))ans=0.5*(a+b)/((a+b)/(2*b)).
再用下欧几里得就能表示答案了！注意特判分母=1的情况。

其实原题二分是可做的（我当时就是这样做），这一题就实力做不到了23333

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

inline int gcd(int x,int y){ return !y?x:gcd(y,x%y); }

int main(){
  freopen("polyline.in","r",stdin);
  freopen("polyline.out","w",stdout);
  int a,b; scanf("%d%d",&a,&b);
  if(a<b) printf("-1");
  else{
    int x=a+b,y=x/(2*b)*2;
	int GCD=gcd(x,y); x/=GCD,y/=GCD;
    if(y==1) printf("%d",x);
	else printf("%d/%d",x,y);
  }
  return 0;
}

2.链表

深切感知造题过程充满艰辛qwq

第一问是一个很简单的贪心，每个元素尽量往前放，放不下就形成一个新块。一定是最优解。至于正确性…自己感受感受。

第二问DP，设f(i)f(i)表示以i开始的所有区间的值，假设j为最大的数使得a[i]+a[i+1]…a[j]≤ka[i]+a[i+1]…a[j]≤k，于是我们得到转移方程：

f(i)=f(j)+n−i+1f(i)=f(j)+n−i+1

正确性也是基于第一问的贪心。
每个j的计算用双端队列就能O(n)O(n)算出了！
所以总时间复杂度为O(n)O(n).

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

typedef long long ll;
const int maxn=1e5+1;
int a[maxn],g[maxn];
ll f[maxn];

int main(){
  freopen("chain.in","r",stdin);
  freopen("chain.out","w",stdout);
  int n,k; scanf("%d%d",&n,&k);
  int ans1=1; ll ans2=0;
  for(int i=0;i<n;i++) scanf("%d",&a[i]);
  for(int i=0,now=0;i<n;i++)
    if((ll)now+a[i]<=k) now+=a[i];
    else now=a[i],ans1++;
  for(int i=0,r=0,now=0;i<n;i++){
    while(r<=n && (ll)now+a[r]<=k) now+=a[r++];
    g[i]=r; now-=a[i];
  }
  for(int i=n-1;i>=0;i--)
    ans2+=f[i]=f[g[i]]+n-i;
  printf("%d %lld",ans1,ans2);
  return 0;
}

拓展延伸：

  • 多个查询区间[l,r][l,r] —— 应该是某种数据结构
  • ai随机，询问查询[1, n][1,\ n]的期望值 —— O(n∗k2)O(n∗k^2)的DP?!

3.最小直径生成树

涉及：图的绝对中心，最短路树。

实现及技巧：枚举，Floyd,分段函数。

（其实下面写这么多都是一句话能讲清的事…）

一棵树有如下性质：

  • 树的中心（树的直径的中点）为树上所有点（包括边上的点）到其最远点距离的最大值最小的点。
  • 树上所有点中到其最远点距离的最大值最小的点为树的中心。
    对于此题，我们要找到一棵生成树使得直径最小，就要在图里找到一个中心使它到其他所有点的最远距离最小，我们把这个点称为图的绝对中心。
    显然与这个点的距离为最远的点至少有两个（不然可调整至更优），若以这三点的连线作为最小直径生成树的直径，答案就一定是最优的的了。然而不可行呢？
    当然。我们建一棵以绝对中心为根的最短路树（指根结点到其他结点的边都是原图中根结点到其他结点最短路上的边的树）就可以了，这样保证了直径的长度就为2∗绝对中心到最远点的距离2*绝对中心到最远点的距离，达到最优。
    那么怎么找出图的绝对中心呢？枚举。
    我们枚举每条边，看看绝对中心放在这条边的哪个位置更优。
    下面单独讨论一条边(u,v)(u,v)。
    我们假设(u,v)(u,v)长Wu,vW_{u,v}，把绝对中心放在距uu 结点γeγe的位置，那么绝对中心到其他点wiw_i的为距离awiawi关于γeγe满足函数关系awi=min(dis[u][wi]+γe,dis[v][wi]+Wu,v−γe)awi=min(dis[u][wi]+γe,dis[v][wi]+Wu,v-γe)，画出绝对中心与所有点的距离函数，最上方的一只则代表绝对中心与最远点的距离与γe的关系（如下图所示），而这段折线的最低点即为最优的放置方案，所有边的最小值即为所求直径的一半了。

观察发现，若条边上(u,v)(u,v)存在绝对中心，则直径的两个端点x, yx,\ y中，若离uu为xx较近，则离vv为yy较，所以我们将点按dis[u]，dis[v]dis[u]，dis[v]排好序，就可以O(n)O(n)计算出这条直线上的所有折点，就很容易设计一个O(n3)O(n^3)的算法了（详见代码）。

拓展延伸：

  • 若要你输出这棵树（怎么求最短路树）呢？ ——SPOJ1479
  • 求最小直径最小生成树（直径最小的同时保证边权最小）？
    有兴趣的同学可以自行学习《最短路树的计数、产生和优化问题》
    戳 >> http://www.docin.com/p-624656262.html
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
#include<cstdio>
#include<cctype>

inline int read(){
  int x=0; char c=getchar();
  while(!isdigit(c)) c=getchar();
  while(isdigit(c)) x=x*10+c-'0',c=getchar();
  return x;
}
inline int min(int x,int y){ return x<y?x:y; }
inline int swap(int&x,int&y){ int t=x;x=y;y=t; }

const int inf=~0u>>2;
const int maxn=200;
int e[maxn][maxn],d[maxn][maxn];
int rk[maxn][maxn];

int main(){
  freopen("mdst.in","r",stdin);
  freopen("mdst.out","w",stdout);
  int n=read(),m=read(),ans=inf;
  for(int i=0;i<n;i++){
	e[i][i]=d[i][i]=0;
	for(int j=i+1;j<n;j++)
	  e[i][j]=e[j][i]=d[i][j]=d[j][i]=inf;
  }
  for(int i=0;i<m;i++){
	int x=read()-1,y=read()-1,w=read();
	e[x][y]=e[y][x]=d[x][y]=d[y][x]=w;
  }
  for(int k=0;k<n;k++)
	for(int i=0;i<n;i++)
	  for(int j=0;j<n;j++)
		d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  for(int i=0;i<n;i++){
	for(int j=0;j<n;j++) rk[i][j]=j;
	for(int j=0;j<n;j++)
	  for(int k=j+1;k<n;k++)
		if(d[i][rk[i][j]]>d[i][rk[i][k]])
		  swap(rk[i][j],rk[i][k]);
  }
  for(int u=0;u<n;u++)
	for(int v=0;v<n;v++){
	  ans=min(ans,d[u][rk[u][n-1]]<<1);
	  ans=min(ans,d[v][rk[v][n-1]]<<1);
	  for(int cmp=n-1,i=cmp-1;i>=0;i--)
		if(d[v][rk[u][i]]>d[v][rk[u][cmp]])
		  ans=min(ans,d[u][rk[u][i]]+d[v][rk[u][cmp]]+e[u][v]),cmp=i;
	}
  printf("%d",ans);
  return 0;
}

祝大家NOIP顺利~