NOIP2017提高组模拟赛 9 （总结）

NOIP2017提高组模拟赛 9 （总结）

第一题 星星

    天空中有N(1≤N≤400)颗星，每颗星有一个唯一的坐标(x,y),(1≤x,y ≤N)。请计算可以覆盖至少K(1≤K≤N)颗星的矩形的最小面积。矩形的边必须平行于X轴或Y轴，长度必须为正整数。星如果在矩形的边上，也认为它是属于矩形内的。

　　思路：枚举矩形左上角的x，以及在x轴上的长度（矩形的长），然后单调的往下扫。

#include<cstdio>
#include<algorithm>
#include<cmath>

#define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b))

typedef long long ll;

using namespace std;

int n,ne,ans;
int sum[410][410];
bool d[410][410];

int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    scanf("%d%d",&n,&ne);
    ans=n*n;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b); d[a][b]=1;
    }
    for(int i=1;i<=n;i++)
    {
        sum[i][0]=0;
        for(int j=1;j<=n;j++) sum[i][j]=sum[i][j-1]+(d[i][j]?1:0);
    }
    for(int ll=1;ll<=n;ll++)
    {
        for(int i=1;i<=n-ll+1;i++)
        {
            int fr=1,la=1,ss=sum[fr][i+ll-1]-sum[fr][i-1];
            while(la<=n)
            {
                while(ss<ne)
                {
                    la++; ss+=sum[la][i+ll-1]-sum[la][i-1];
                    if(la>n) break;
                }
                if(la>n) break;
                ans=imin(ans,(la-fr+1)*ll);
                ss-=sum[fr][i+ll-1]-sum[fr][i-1]; fr++;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

第二题 战争

    X国和Y国是死对头，X国有N个炮台, Y国有M个基地和K个发电站，炮台、基地、发电站所在的位置的坐标都是整数。Y国的每个发电站能对距离其L以内（包括L）的基地供电。X国的每个炮台都可以发射无限次，每次发射可以击毁一个基地或者一个发电站，消耗的能量为两者距离的平方，这里的距离是欧几里德距离。X国决定要摧毁Y国的所有基地，我们说Y国的某个基地被摧毁的条件是：基地本身被直接摧毁或者对其供电的所有发电站被击。
    问X国摧毁Y国所有基地需要消耗的总能量最小是多少。
    提示：点（X1,Y1）和点（X2,Y2）的欧几里德距离是：
    dis = sqrt((X2-X1)*(X2-X1)+(Y2-Y1)*(Y2-Y1)).

　　经典的网络流01模型，直接构图，跑一次dinic就行了。
　　S向各个基地基地bi连边，代价为距离基地bi最近的炮台之间的距离。
　　各个电厂向T连边，代价为距离电厂ci最近的炮台之间的距离。
　　若电厂ci可以供电给基地dj，那么基地dj连向电厂ci，代价为∞。
　　图的S到T的最小割即为answer。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

#define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b))

typedef long long ll;

using namespace std;

const int N=50;
const int M=15000;
const int oo=1e9;
struct data { int x,y; } ad[N+10],bd[N+10],cd[N+10];
int to[M],h[M],ne[M],val[M],tt,S,T;
int vis[M],lev[M],q[M];
int an,bn,cn,L,bfstime;

void read(int n,data* A)
{
    for(int i=1;i<=n;i++) scanf("%d",&A[i].x);
    for(int i=1;i<=n;i++) scanf("%d",&A[i].y);
}

void add(int a,int b,int c)
{
    to[++tt]=b; ne[tt]=h[a]; val[tt]=c; h[a]=tt;
    to[++tt]=a; ne[tt]=h[b]; val[tt]=0; h[b]=tt;
}

int dis(data A,data B) { return ((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); }

void init()
{
    scanf("%d%d%d%d",&an,&bn,&cn,&L);
    read(an,ad); read(bn,bd); read(cn,cd);
    tt=1; S=110; T=111;
    for(int i=1;i<=bn;i++)
    {
        int dd=oo;
        for(int j=1;j<=an;j++) dd=imin(dd,dis(ad[j],bd[i]));
        add(S,i,dd);
    }
    for(int i=1;i<=cn;i++)
    {
        int dd=oo;
        for(int j=1;j<=an;j++) dd=imin(dd,dis(ad[j],cd[i]));
        add(50+i,T,dd);
    }
    int ml=L*L;
    for(int i=1;i<=bn;i++)
    {
        for(int j=1;j<=cn;j++)
        if(dis(bd[i],cd[j])<=ml) add(i,50+j,oo);
    }
}

bool bfs()
{
    lev[S]=1; vis[S]=++bfstime;
    int he=1,ta=1; q[1]=S;
    while(he<=ta)
    {
        int u=q[he++];
        for(int p=h[u];p;p=ne[p])
        {
            int v=to[p];
            if(vis[v]==bfstime || !val[p]) continue;
            q[++ta]=v; vis[v]=bfstime; lev[v]=lev[u]+1;
        }
    }
    return (vis[T]==bfstime);
}

int dfs(int now,int maxf)
{
    int ret=0,t=0;
    if(!maxf || now==T) return maxf;
    for(int p=h[now];p;p=ne[p])
    {
        int v=to[p];
        if(lev[v]!=lev[now]+1 || !val[p]) continue;
        t=dfs(v,imin(maxf,val[p]));
        ret+=t; maxf-=t;
        val[p]-=t; val[p^1]+=t;
    }
    if(!maxf) lev[now]=-1;
    return ret;
}

int dinic()
{
    int ret=0;
    while(bfs()) ret+=dfs(S,oo);
    return ret;
}

int main()
{
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    init();
    printf("%d\n",dinic());
    return 0;
}

第三题 染色树

    一棵共含有X个结点的树，结点编号1至X，根结点编号是1。有Y种不同的颜色，颜色编号从1至Y。
    现在给每个结点都染上一种颜色，整颗树染色后满足：
    1、对于编号是i的颜色，整颗树当中，至少有一个结点被染成了颜色i。
    2、根结点必须被染成1号颜色，而且整颗树当中，恰好要有Z个结点被染成1号颜色。

    染色过程结束后，现在要计算染色的总代价，总代价等于每一条边的代价之和，那么怎么计算一条边的代价呢？
    不妨设结点a与结点b之间有一条边，该边的权重是W。
    1、如果结点a和结点b最终被染成不同的颜色，那么a与b之间的那条边的代价等于0。
    2、如果结点a和结点b最终被染成相同的颜色，那么a与b之间的那条边的代价等于W。

    现在的问题是：在满足上述要求的前提下，染色树最小的总代价是多少？如果无法完成染色的任务，输出-1。

　　显然的，这是一道树形DP题（DP做的有点多-_-||），X,Y,Z好像都很大。直接做无疑是超时的。
　　那么想考虑一下，answer=-1的情况。每个节点都可以是任意颜色（只是会有代价而已），唯一不满足的情况就是Z>X-Y+1（极限情况）。
　　这是一棵树（这很重要），那么只需要两种颜色就可以使整棵树的任意x和x的父亲的颜色不同。
　　又多了一个颜色1恰好为Z的限制条件，那么也只需要3种颜色就行了（多余的颜色是没任何作用的）。
　　时间复杂度：O（9N³）

#include<cstdio>
#include<algorithm>
#include<cmath>

#define imax(a,b) ((a>b)?(a):(b))
#define imin(a,b) ((a<b)?(a):(b))

typedef long long ll;

using namespace std;

const int oo=1e9;
const int M=700;
int X,Y,Z,ans;
int to[M],ne[M],h[M],val[M],tt;
int f[302][4][302];

void add(int a,int b,int c)
{
    to[++tt]=b; ne[tt]=h[a]; h[a]=tt; val[tt]=c;
    to[++tt]=a; ne[tt]=h[b]; h[b]=tt; val[tt]=c;
}

void dfs(int x,int fa)
{
    for(int i=1;i<=Y;i++)
    {
        for(int j=0;j<=Z;j++) f[x][i][j]=oo;
        if(i==1) f[x][i][1]=0; else f[x][i][0]=0;
    }
    for(int p=h[x];p;p=ne[p])
    {
        int v=to[p];
        if(v==fa) continue;
        dfs(v,x);
        for(int i=1;i<=Y;i++)
        for(int j=Z;j>=0;j--)
        {
            int bes=oo;
            for(int g=1;g<=Y;g++) bes=imin(bes,f[v][g][0]+(i==g?val[p]:0));
            f[x][i][j]=imin(oo,f[x][i][j]+bes);
            for(int k=1;k<=j;k++)
            {
                int yu=oo;
                for(int g=1;g<=Y;g++) yu=imin(yu,f[v][g][k]+(i==g?val[p]:0));
                f[x][i][j]=imin(f[x][i][j],f[x][i][j-k]+yu);
            }
        }
    }
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);
    scanf("%d%d%d",&X,&Y,&Z); tt=1;
    if(Z>X-Y+1) printf("-1\n"); else
{
    Y=imin(Y,3);
    for(int i=1;i<X;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); }
    dfs(1,1);
    printf("%d\n",f[1][1][Z]);
}
    return 0;
}

　　终于拿了一次AK了（虽然这次的题目有点水……）。