2017.12.02【NOIP提高组】模拟赛A组
T1 3555【GDKOI2014模拟】树的直径
T2 3542【清华集训2014】冒泡排序
T3 3486【NOIP2013模拟联考10】道路改建(rebuild)
T1
树直径的一个性质，两棵树合并，形成新的树的直径的两个端点为原树中的四个端点之二。
可以用反证法证明。用此性质本题就变成了lca裸题了
Code
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#include<bitset>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,x) for(int i=head[x];i;i=next[i])
#define mem(a,x) memset(a,x,sizeof(a))
typedef long long LL;
typedef double DB;
using namespace std;
inline int max(int x,int y) {return (x>y)?x:y;}
inline int min(int x,int y) {return (x>y)?y:x;}
inline int read() {
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') f=(ch=='-')?-1:f,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch-'0'),ch=getchar();return f*x;
}
const int N=200000+50;
int to[N<<1],next[N<<1],tot,head[N],dep[N],go[N][17],s,t,mx,m,x,son;
void add(int x,int y) {to[++tot]=y,next[tot]=head[x],head[x]=tot;}
void dfs(int x) {rep(i,x) dep[to[i]]=dep[x]+1,go[to[i]][0]=x,dfs(to[i]);}
void init_lca() {
dep[1]=1,dfs(1);
fo(i,1,16) fo(x,1,2*m+4) go[x][i]=go[go[x][i-1]][i-1];
}
int lca(int a,int b) {
if(dep[a]<dep[b]) swap(a,b);
int f=dep[a]-dep[b];
fo(i,0,16) if(f&(1<<i)) a=go[a][i];
if(a==b) return b;
fd(i,16,0) if(go[a][i]!=go[b][i]) a=go[a][i],b=go[b][i];
return go[a][0];
}
int main() {
m=read();
add(1,2),add(1,3),add(1,4);
fo(i,1,m) add((x=read()),(son=(i-1)*2+5)),add(x,son+1);
init_lca();
s=2,t=4,mx=2;
fo(i,1,m) {
int son1=(i-1)*2+5,fa1,fa2,dis1,dis2,_s,_t,_dis;
fa1=lca(son1,s);
dis1=dep[son1]+dep[s]-2*dep[fa1];
fa2=lca(son1,t);
dis2=dep[son1]+dep[t]-2*dep[fa2];
if(dis1>dis2) _s=son1,_t=s,_dis=dis1;
else _s=son1,_t=t,_dis=dis2;
if(_dis>mx) s=_s,t=_t,mx=_dis;
printf("%d
",mx);
}
return 0;
}
T2
一看是清华集训题就慌了，但仔细一想还是十分简单的。
若一个数之前有t个比它要大，那么前t轮中每轮它会往前移1个位置，之后便不再会往前移了。
考虑到交换次数=前移次数，可据此求出最大的轮数x使得做了x轮冒泡后交换次数刚好不超过k。
那些t>=x的数的位置前移了x，所有t<x的数之间的顺序已经排好，按顺序填入剩下的位置即可。
求出了做了x轮之后的序列以后再模拟冒泡的过程做剩下的几次就好了。
Code
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,x) for(int i=head[x];i;i=next[i])
#define mem(a,x) memset(a,x,sizeof(a))
typedef long long LL;
typedef double DB;
using namespace std;
inline int max(int x,int y) {return (x>y)?x:y;}
inline int min(int x,int y) {return (x>y)?y:x;}
inline int read() {
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') f=(ch=='-')?-1:f,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+(ch-'0'),ch=getchar();return f*x;
}
const int N=1000001;
int a[N],upper[N],ans[N],sa[N],tr[N],n;
inline int lowbit(int x) {return x&(-x);}
inline void add(int x,int xx) {for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=xx;}
inline int sum(int x) {
int ans=0;
for(int i=x;i>=1;i-=lowbit(i)) ans+=tr[i];
return ans;
}
int main()
{
LL k,sx=0;
n=read(),scanf("%lld",&k);
fo(i,1,n) a[i]=read();
fo(i,1,n) upper[i]=sum(n)-sum(a[i]),add(a[i],1);
int l=1,r=n;
while(l<=r) {
int mid=(l+r)>>1;
sx=0;
fo(i,1,n) sx+=(LL)min(mid,upper[i]);
if(sx<=k) l=mid+1;
else r=mid-1;
}
sx=0;
fo(i,1,n) sx+=(LL)min(r+1,upper[i]);
LL m=k-sx;
if(m>0) {printf("Impossible!
");return 0;}
sx=0;
fo(i,1,n) sx+=(LL)min(r,upper[i]);
m=k-sx;
int p=0;
fo(i,1,n)
if(upper[i]>r) ans[i-r]=a[i];
else p++,sa[p]=a[i];
sort(sa+1,sa+1+p);
p=0;
fo(i,1,n) if(ans[i]==0) p++,ans[i]=sa[p];
for(int i=1;i<n&&m!=0;i++) {
if(ans[i]>ans[i+1]) {
int t=ans[i];
ans[i]=ans[i+1];
ans[i+1]=t;
m--;
}
}
fo(i,1,n-1) printf("%d ",ans[i]);
printf("%d
",ans[n]);
return 0;
}
T3（意外在OJ上莫名打不开题目2017.12.9）
只能凭印象写一下题解了（记性不好，算了 等OJ好了再补齐吧）