NOIP2017模拟赛（四）解题报告
T1：
约数
题目描述
设K是一个正整数，设X是K的约数，且X不等于1也不等于K.
加了X后，K的值就变大了，你可以重复上面的步骤。例如K= 4,我们可以用上面的规则产生所有的非素数. 可以通过5次变化得到
24: 4->6->8->12->18->24.
现在给你两个整数N 和 M, 求最少需要多少次变化才能到从 N 变到 M. 如果没法从N变到M,输出-1.
输入格式 1862.in
多组测试数据。
第一行：一个整数1<=ng<=5,表示有ng组测试数据。
每组测试数据格式如下：
一行：两个整数,N、M，空格分开。 4 <= N<=100000, N<=M<=100000.
输出格式 1862.out
一个整数。求最少需要多少次变化才能到从 N变到 M. 如果没法从N变到M,输出-1.
ng行，每行对应一组测试数据。
输入样例 1862.in
2
4 24
4 576
输出样例 1862.out
5（题目的例子）
14（4->6->8->12->18->27->36->54->81->108->162->243->324->432->576）
题目分析：这题应该算是本次比赛的签到题吧。考虑到数据只有10^5，我们用一个BFS，暴力枚举每一个i，再用sqrt(i)的时间枚举i的因数d，更新i+d，时间O(T*n*sqrt(n))。考场上就1A了，没什么好说下去的吧……
CODE：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100010;
bool vis[maxn];
int num[maxn];
int que[maxn];
int head,tail;
int ng,N,M;
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&ng);
while (ng--)
{
scanf("%d%d",&N,&M);
if (M<N)
{
printf("-1\n");
continue;
}
for (int i=N+1; i<=M; i++) vis[i]=false;
vis[N]=true,num[N]=0;
head=0,tail=1;
que[1]=N;
while (head<tail)
{
head++;
int x=que[head];
int sx=(int)floor( sqrt( (long double)x )+1e-8 );
bool sol=false;
for (int i=2; i<=sx; i++) if (x%i==0)
{
int y=x+i;
if ( y<=M && !vis[y] ) vis[y]=true,num[y]=num[x]+1,que[++tail]=y;
if (y==M)
{
sol=true;
break;
}
y=x+x/i;
if ( y<=M && !vis[y] ) vis[y]=true,num[y]=num[x]+1,que[++tail]=y;
if (y==M)
{
sol=true;
break;
}
}
if (sol) break;
}
if (!vis[M]) printf("-1\n");
else printf("%d\n",num[M]);
}
return 0;
}
T2：
小偷与警察
题目描述
为帮助捕获在逃的犯人,警局引进了一套新计算机系统. 系统覆盖了N 个城市，有E条双向的道路。城市标号为1 到N. 犯人经常从一个城市逃到另外一个城市. 所以警察想知道应该在哪里设置障碍去抓犯人.计算机系统需要回答下面两种类型的问题:
1. 考虑城市A 、B； 如果把连接城市G1和G2的那条公路切断，逃犯还能从城市A逃到城市B吗?
2. 考虑三个城市A、B 、C. 如果把城市C*（则不能从其他进入城市C），逃犯还能从城市A逃到城市B吗?
你的任务是帮计算机系统回答这些提问。（一开始，任意两个城市都是可以相互到达的）.
输入格式 1863.in
*第一行:两个整数N 、 E (2 <= N <= 100 000, 1 <= E <= 500 000),表示城市的数量和道路的数量.
*第 2..E+1行: 两个不同整数A和B,表示城市A和城市B之间有一条公路，任意两个城市最多只有一条公路。
* 第 E+2行:一个整数 Q (1 <= Q <= 300 000), 表示有Q个提问。
* 第 E+3..E+Q+2行: 这Q行，每行有4个或5个整数. 第一整数表示提问的类型（1或2）. 如果是提问类型是1, 那么本行后面有4个整数： A、B、G1、G2 ，参数表示的意义题目已经说过，其中A和B不会相同，G1和G2之间肯定有一条公路. 如果提问类型是2，那么本行后面有3个整数: A、B 、C. （ A、B 、C都不相同，意义上面已经说过。）
输出格式 1863.out
*第1..Q行: 每行输出yes 或 no .
输入样例 1863.in
13 15
1 2
2 3
3 5
2 4
4 6
2 6
1 4
1 7
7 8
7 9
7 10
8 11
8 12
9 12
12 13
5
1 5 13 1 2
1 6 2 1 4
1 13 6 7 8
2 13 6 7
2 13 6 8
输出样例 1863.out
yes
yes
yes
no
yes
题目分析：这题是一道好题呀。考场上我是最后做这题的，想了45min，最后只剩30min只好敲暴力完事。赛后我也想了好久，和同学讨论了很多种做法，才找到一种O(n*log(n))的解法，拖到最后才将它改到100。
在做这题之前我们得知道一些性质：一个无向图的dfs生成树是不会有横向边的，只会有后向边，这个很容易通过反证得到。如果有横向边，由于这条边是无向的，所以dfs的时候肯定会优先走这条边。其次，我们还要精通tarjan缩点算法。它主要的精髓在于在每一个点维护一个dfn（代表时间戳），一个low（代表往下走之后所能走到的最小时间戳）。
现在我们考虑删一条边(u，v)是否会使a，b不连通。如果这条边是反向边，那么它对连通性毫无影响，如果这条边在dfs树上不是a->b的路径上的边，那么它也对连通性无影响（判断一条边是否在一条路径上转化为判断它的两个端点是否在路径上，而后者可以通过维护树上倍增LCA判断）。
现在问题变成这样：
假设u是v的儿子，那我们需要知道u是否还有边到达v即其以上的祖先，我们查看low[u]是否小于等于dfn[v]即可。
假设我们要砍掉一个点c呢？很明显，如果这个点不在a->b的路径上，它对连通性不会有影响。如果在，又分为两种情况：
1：c不是LCA(a,b)：
那么a,b必定有且仅有一个点是c的后代（设为a），我们通过倍增将a跳到c的儿子x处，然后看是否有low[x]<dfn[c]，如果有的话x就能上到c的祖先处，然后走到b（红色路径）。
2：c=LCA(a,b)
这样c就同时堵住了a，b向上走的道路。我们像上面一样将a跳到x，b跳到y，然后查看是否有low[x]<dfn[c]&&low[y]<dfn[c]，如果有的话就可以通过途中红色路径连接a，b。
我考试的时候很快就想到了无向图的dfs树没有横向边，还想到了可以用tarjan缩点，缩点完之后就可以处理边了（看看这条边所连接的两个点是否在缩点后的同一个点中，不是的话判断这条边是否在d[a]->d[b]的路径上即可，其中d[x]表示x缩点后所在的点。因为缩点之后就是一棵树了）。但点的情况一直不知道怎么处理，主要是考虑到以下情况：
如图，在缩点的时候a,b,c会被缩到同一个点，但事实上切掉c点，是可以断掉a->b之间的路径的。
然后我就开始往别的地方想了，什么树剖，LCT，treap+启发式合并，拆点都搞出来，然而还是不能解决切点的问题。殊不知其实答案就藏在tarjan缩点的low数组中。主要是对dfs及tarjan缩点的过程理解得不够深入，没有灵活掌握其变形。
CODE：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100100;
const int maxm=500100;
const int maxl=20;
struct edge
{
int obj;
bool vis;
edge *Next,*rev;
} e[maxm<<1];
edge *head[maxn];
int cur=-1;
int dep[maxn];
int fa[maxn][maxl];
int dfn[maxn];
int low[maxn];
int Time=0;
int n,m,q;
void Add(int x,int y)
{
cur++;
e[cur].obj=y;
e[cur].vis=false;
e[cur].rev=&e[cur+1];
e[cur].Next=head[x];
head[x]=e+cur;
cur++;
e[cur].obj=x;
e[cur].vis=false;
e[cur].rev=&e[cur-1];
e[cur].Next=head[y];
head[y]=e+cur;
}
void Dfs(int node)
{
dfn[node]=low[node]=++Time;
for (edge *p=head[node]; p; p=p->Next)
if (!p->vis)
{
p->vis=p->rev->vis=true;
int son=p->obj;
if (!dep[son])
{
dep[son]=dep[node]+1;
fa[son][0]=node;
Dfs(son);
}
low[node]=min(low[node],low[son]);
}
}
int Lca(int u,int v)
{
if (dep[u]<dep[v]) swap(u,v);
for (int j=maxl-1; j>=0; j--)
if (dep[ fa[u][j] ]>=dep[v]) u=fa[u][j];
if (u==v) return u;
for (int j=maxl-1; j>=0; j--)
if (fa[u][j]!=fa[v][j])
u=fa[u][j],v=fa[v][j];
return fa[u][0];
}
bool Judge(int u,int v,int a)
{
int w=Lca(u,v);
int x=Lca(u,a);
int y=Lca(v,a);
if (x!=a) swap(x,y);
return x==a && y==w;
}
int Jump(int x,int y)
{
for (int j=maxl-1; j>=0; j--)
if (dep[ fa[x][j] ]>dep[y]) x=fa[x][j];
return x;
}
int main()
{
freopen("1863.in","r",stdin);
freopen("1863.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) head[i]=NULL;
for (int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
Add(x,y);
}
fa[1][0]=1;
dep[1]=1;
Dfs(1);
for (int j=1; j<maxl; j++)
for (int i=1; i<=n; i++)
fa[i][j]=fa[ fa[i][j-1] ][j-1];
scanf("%d",&q);
while(q--)
{
int id;
scanf("%d",&id);
if (id==1)
{
int a,b,u,v;
scanf("%d%d%d%d",&a,&b,&u,&v);
if ( fa[u][0]!=v && fa[v][0]!=u )
{
printf("yes\n");
continue;
}
if (dep[u]<dep[v]) swap(u,v);
if ( Judge(a,b,u) && Judge(a,b,v) )
if (low[u]>dfn[v]) printf("no\n");
else printf("yes\n");
else printf("yes\n");
}
else
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if ( Judge(a,b,c) )
{
if ( Lca(a,b)==c )
{
int x=Jump(a,c);
int y=Jump(b,c);
if ( low[x]<dfn[c] && low[y]<dfn[c] ) printf("yes\n");
else printf("no\n");
}
else
{
int x=a;
if ( Lca(a,c)!=c ) x=b;
x=Jump(x,c);
if (low[x]<dfn[c]) printf("yes\n");
else printf("no\n");
}
}
else printf("yes\n");
}
}
return 0;
}
T3：
圆桌会议
题目描述
有N个人顺时针围在一圆桌上开会,他们对身高很敏感. 因此决定想使得任意相邻的两人的身高差距最大值最小. 如果答案不唯一,输出字典序最小的排列,指的是身高的排列.
输入格式 1864.in
多组测试数据。第一行：一个整数ng, 1 <= ng <= 5.表示有ng组测试数据。
每组测试数据格式如下：
第一行: 一个整数N, 3 <= N <= 50
第二行, 有个N整数, 第i个整数表示第i个人的身高hi, 1<=hi<=1000. 按顺指针给出N个人的身高. 空格分开。
输出格式 1864.out
字典序最小的身高序列,同时满足相邻的两人的身高差距最大值最小。共ng行，每行对应一组输入数据。
输入样例 1864.in
2
5
1 3 4 5 7
4
1 2 3 4
输出样例 1864.out
1 3 5 7 4
1 2 4 3
题目分析：这题其实并不难，考场上我已AC，用的是二分答案+贪心，主要是考虑应该怎么正确的贪。
考场上我接到这道题的时候，首先发现答案有单调性。然后我将题目分成两个任务：1：二分答案最小化最大身高差，2：在保证答案的前提下输出字典序最小的排列。
考虑任务一。我研究了一会儿发现，合理的身高排列一定是低->高->低，不满足这个条件的一定不会更优。我们可以将其看成一座山峰，先爬坡再下坡，每个人的身高x看成在高度x有一块石头。接下来我们要怎么检验二分出的答案mid呢？我想，如果爬坡的时候用尽可能少的石头（即每一次都选取能到达的最高处的石头），我们就可以留更多的石头给下坡用。我试了几组手造的小数据，发现这样是最优的。
接下来要求字典序最小。我想，山峰的值是最大的，它一定要尽可能靠后出现，而且还要保证接下来能够下坡。那我不如遵循“慢升速降”的原则，先选取尽可能少的石头下坡，其余的用于上坡。接下来还有一个细节，在选择下降的路线时，我要从山顶快速降下去呢，还是尝试从山脚快速升上去，并将这段路作为下坡路呢？（这样选取的两条路线是会有差别的，看图就知道）
如图，左边的下坡路遵循快速下降原则，右边的下坡路遵循快速上升原则。很明显右边的字典序最小。于是我将这个想法写成代码，手造了几组数据都过了……算了不管啦！
然后就A了。
CODE：
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=55;
const int oo=1e8;
bool vis[maxn];
int maxH;
int down[maxn];
int cur;
int h[maxn];
int ng,N;
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
scanf("%d",&ng);
while (ng--)
{
scanf("%d",&N);
for (int i=1; i<=N; i++) scanf("%d",&h[i]);
sort(h+1,h+N+1);
h[N+1]=oo;
int L=-1,R=h[N]-h[1];
while (L+1<R)
{
int mid=(L+R)>>1;
for (int i=1; i<=N; i++) vis[i]=false;
maxH=h[1],vis[1]=true;
int tail=1;
while (tail<N)
{
while (h[tail+1]-maxH<=mid) tail++;
if (vis[tail]) break;
vis[tail]=true;
maxH=h[tail];
}
if (tail<N) L=mid;
else
{
vis[1]=vis[N]=false;
bool sol=true;
for (int i=1; i<N; i++) if (!vis[i])
for (int j=i+1; j<=N; j++) if (!vis[j])
{
if (h[j]-h[i]>mid) sol=false;
break;
}
if (sol) R=mid;
else L=mid;
}
}
for (int i=1; i<=N; i++) vis[i]=false;
cur=1,down[1]=1;
int tail=2;
while (tail<N)
{
while (h[tail+1]-h[ down[cur] ]<=R) tail++;
vis[tail]=true;
down[++cur]=tail;
}
vis[1]=vis[N]=false;
for (int i=1; i<=N; i++) if (!vis[i]) printf("%d ",h[i]);
for (int i=N; i>=1; i--) if (vis[i]) printf("%d ",h[i]);
printf("\n");
}
return 0;
}
总结：这次比赛成绩一般吧。做题顺序1->3->2，比较符合题目难度梯度。1，3题没有写炸，第2题虽然算法简单，但考虑到思维难度，以及我对tarjan算法研究得不够深入，或许考场上敲暴力才是最好的选择吧。事实上，我改第二题的时候WA了好多次，还自己做了个数据生成器和我的暴力程序对拍，排除了很多错误方法，检查出了很多没有考虑到的细节（比如c是LCA(a,b)的情况），交了5,6次才AC。当时考场上我对这题想法是，像这种貌似方法很玄学，又有多次询问（多组数据）的题，如果有了自认为正确的可以AC的算法，一定要对拍，没时间对拍或对拍难写就分段，n<=5000暴力，n较大则跑该算法。但后来连时间复杂度允许的算法都没想到，就写了个裸暴力，现在想来还是有后怕。感觉自己对算法的掌握和思维深度都要提升（说实话我这段时间做了N道LCT，数论（半）裸题，好像思维都退化了QAQ）