NOIP 2015

神奇的幻方

题目
模拟。

#include<iostream>
using namespace std;
int a[40][40];
int main()
{
    register int n,s=1,x,y;
    cin>>n;
    while(s<=n*n)
        if(s==1) a[x=1][y=n+1>>1]=s++;
        else if(x==1&&y!=n) a[x=n][++y]=s++;
    else if(x!=1&&y==n) a[--x][y=1]=s++;
    else if(x==1&&y==n) a[++x][y]=s++;
    else if(x!=1&&y!=n)
        if(!a[x-1][y+1]) a[--x][++y]=s++;
        else a[++x][y]=s++;
    for(int i=1;i<=n;++i,cout<<endl) for(int j=1;j<=n;++j) cout<<a[i][j]<<' ';
    return 0;
}

信息传递

题目
并查集求最小环。
记录父亲的同时记录到根的长度，若一条边两端属于同一集合则更新最小环长度。

#include<bits/stdc++.h>
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
const int N=200007;
int ans=1e9,d[N],fa[N];
int Find(int x)
{
    if(x^fa[x])
    {
    int f=fa[x];
    fa[x]=Find(fa[x]),d[x]+=d[f];
    }
    return fa[x];
}
void check(int u,int v)
{
    int x=Find(u),y=Find(v);
    if(x^y) fa[x]=y,d[u]=d[v]+1; else ans=min(ans,d[u]+d[v]+1);
}
int main()
{
    int n=read(),i;
    for(i=1;i<=n;++i) fa[i]=i;
    for(i=1;i<=n;++i) check(i,read());
    printf("%d",ans);
}

跳石头

题目
二分答案。

#include<bits/stdc++.h>
using namespace std;
int a[100002],d,n,m,l,r,mid,ans;
int read(){int x;scanf("%d",&x);return x;}
int check(int x)
{
    int num=0,now=0;
    for(int i=1;i<n+2;++i) if(a[i]-a[now]<x) ++num; else now=i;
    return num<=m;
}
int main()
{
    d=read(),n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    a[n+1]=d,l=1,r=d;
    while(l<=r) mid=(l+r)>>1,check(mid)? ans=mid,l=mid+1:r=mid-1;
    cout<<ans;
    return 0;
}