Menu
April 23, 2015
只想看代码的直接翻到最下面

BZOJ4002: [JLOI2015]有意义的字符串

PoPoQQQ的题解


BZOJ4003: [JLOI2015]城池攻占

注意到任意时刻在一起的每个骑士的攻击力相对大小不发生改变,于是用可并堆维护最小值,每次把儿子并到父亲上就可以了,使用可以打标记的左偏树实现。


BZOJ4004: [JLOI2015]装备购买

显然第一问答案固定,按照价格排序后贪心取,维护线性基,正确性用拟阵证明,拟阵见花神WC2015课件。
维护线性基:类似高斯消元的做法从前往后枚举每一列,若不为零,则寻找该列是否已经有了,没有该行就是线性基,有的话用已有的基消掉这一列。
由于直接做除法精度可能有问题,所以eps应当设小一点,1e-5即可。


BZOJ4005: [JLOI2015]骗我呢

并没有看懂题= =


BZOJ4006: [JLOI2015]管道连接

斯坦纳树,不会的看这个
按照频率离散化之后去掉只有一个的点,剩下的枚举频率集合的子集,对子集做斯坦纳树,最后将各个子集合并。


BZOJ4007: [JLOI2015]战争调度

设f(i,j)表示子树i,在1到i的父亲的路径节点选择固定时,选择j个人参战的最小贡献。
从根节点开始dfs,每次枚举当前节点的所属集合,然后左右两个子问题是独立的,可以直接枚举。
然后对左右孩子的f数组做背包就得到f[i]了。
时间复杂度:


代码

BZOJ4002: [JLOI2015]有意义的字符串
4002.cpp
#include<cstdio>
#include<iostream>
using namespace std;
typedef unsigned long long ULL;
const ULL M=7528443412579576937ull;
ULL B,D,N;

inline void up(ULL &x,const ULL &y)
{x+=y;if(x>=M)x-=M;}

ULL mult(ULL a,ULL b)
{
    ULL c;
    for(c=0,a%=M;b;b>>=1,up(a,a))
        if(b&1)up(c,a);
    return c;
}

struct Mat
{
    ULL a[2][2];
    inline ULL* operator[](const int &p){return a[p];}
    inline Mat operator*(const Mat &o)const
    {
        Mat r;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
            {
                r.a[i][j]=0;
                for(int k=0;k<2;k++)
                    up(r.a[i][j],mult(a[i][k],o.a[k][j]));
            }
        return r;
    }
}s;

Mat Matpow(Mat a,ULL b)
{
    Mat c;
    c[0][0]=c[1][1]=1;
    c[0][1]=c[1][0]=0;
    for(;b;b>>=1,a=a*a)
        if(b&1)c=c*a;
    return c;
}

int main()
{
    cin>>B>>D>>N;
    s[0][0]=0,s[1][0]=1;s[0][1]=D-B*B>>2,s[1][1]=B;
    Mat a=Matpow(s,N);
    cout<<(mult(a[0][0],2)+mult(a[1][0],B)-(D!=B*B&&!(N&1))+M)%M<<endl;
    return 0;
}


BZOJ4003: [JLOI2015]城池攻占
4003.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
inline void readi(int &x);
inline void readll(LL &x);
const int maxn=300005;
int n,m;
int fa[maxn],dep[maxn],A[maxn];
LL V[maxn],H[maxn];
int head[maxn],adj[maxn],next[maxn],tot;
int death[maxn],start[maxn],fail[maxn];

inline void addedge(int u,int v)
{tot++;adj[tot]=v;next[tot]=head[u];head[u]=tot;}

struct node
{
    LL f,d;
    LL key;
    int id,dis;
    node *lc,*rc;
    inline void tagf(const LL &x)
    {f*=x,d*=x,key*=x;}
    inline void tagd(const LL &x)
    {d+=x,key+=x;}
    inline void downdate()
    {
        if(f!=1)
        {
            lc->tagf(f);
            rc->tagf(f);
            f=1;
        }
        if(d)
        {
            lc->tagd(d);
            rc->tagd(d);
            d=0;
        }
    }
}ndl[maxn],null[1],*root[maxn];

node* merge(node *a,node *b)
{
    if(a==null)return b;
    if(b==null)return a;
    if(b->key<a->key)swap(a,b);
    a->downdate();
    a->rc=merge(a->rc,b);
    if(a->lc->dis<a->rc->dis)swap(a->lc,a->rc);
    a->dis=a->rc->dis+1;
    return a;
}

void init()
{
    readi(n),readi(m);
    null->dis=-1;
    for(int i=1;i<=n;i++)
        readll(H[i]),root[i]=null;
    dep[1]=1;
    for(int i=2;i<=n;i++)
        readi(fa[i]),readi(A[i]),readll(V[i]),dep[i]=dep[fa[i]]+1,addedge(fa[i],i);
    LL s;
    int v;
    for(int i=1;i<=m;i++)
    {
        readll(s),readi(v);
        ndl[i].f=1;
        ndl[i].key=s;
        ndl[i].id=i;
        ndl[i].lc=ndl[i].rc=null;
        start[i]=dep[v];
        root[v]=merge(root[v],ndl+i);
    }
}

void work()
{
    for(int x=n,i;x>0;x--)
    {
        for(i=head[x];i;i=next[i])
            root[x]=merge(root[x],root[adj[i]]);
        while(root[x]!=null&&root[x]->key<H[x])
        {
            death[x]++;
            root[x]->downdate();
            fail[root[x]->id]=dep[x];
            root[x]=merge(root[x]->lc,root[x]->rc);
        }
        if(A[x])root[x]->tagf(V[x]);
        else root[x]->tagd(V[x]);
    }
    for(int i=1;i<=n;i++)
        printf("%d\n",death[i]);
    for(int i=1;i<=m;i++)
        printf("%d\n",start[i]-fail[i]);
}

int main()
{
    init();
    work();
    return 0;
}
inline void readi(int &x)
{
  char c;bool fl;
  while(c=getchar(),c!='-'&&(c>'9'||c<'0'));
  if(c=='-')fl=1,x=0;
  else fl=0,x=c^'0';
  while(c=getchar(),c>='0'&&c<='9')x=x*10+(c^'0');
  if(fl)x=-x;
}
inline void readll(LL &x)
{
  char c;bool fl;
  while(c=getchar(),c!='-'&&(c>'9'||c<'0'));
  if(c=='-')fl=1,x=0;
  else fl=0,x=c^'0';
  while(c=getchar(),c>='0'&&c<='9')x=x*10+(c^'0');
  if(fl)x=-x;
}


BZOJ4004: [JLOI2015]装备购买
4004.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=505;
const double eps=1e-5;
int n,m;
struct line
{
    double x[maxn];
    int cost;
    double& operator[](const unsigned &p){return x[p];}
    bool operator<(const line &o)const{return cost<o.cost;}
}a[maxn];
int ans,sum,p[maxn];
void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%lf",a[i].x+j);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i].cost);
    sort(a+1,a+n+1);
}

void work()
{
    double t;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(fabs(a[i][j])>eps)
            {
                if(p[j])
                {
                    t=a[i][j]/a[p[j]][j];
                    for(int k=j;k<=m;k++)
                        a[i][k]-=a[p[j]][k]*t;
                }
                else
                {
                    p[j]=i;
                    ans++,sum+=a[i].cost;
                    break;
                }
            }
    printf("%d %d\n",ans,sum);
}

int main()
{
    init();
    work();
    return 0;
}


BZOJ4005: [JLOI2015]骗我呢

看不懂题QAQ


BZOJ4006: [JLOI2015]管道连接
4006.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=1111,L=65535,inf=0x3f3f3f3f;
template<class T> inline bool ten(T &x,const T &y){return y<x?(x=y,1):0;}
template<class T> inline bool rel(T &x,const T &y){return x<y?(x=y,1):0;}

struct point
{
    int p,c;
    bool operator<(const point &o)const{return c<o.c;}
}po[15],tpo[15];

int n,m,P,C,cnt;
int f[maxn][maxn],g[50];
int head[maxn],adj[maxn*9],c[maxn*9],next[maxn*9],tot=1;
int q[L+1],qh,qt,inq[maxn];

inline void addedge(int u,int v,int w)
{tot++;adj[tot]=v;c[tot]=w;next[tot]=head[u];head[u]=tot;
tot++;adj[tot]=u;c[tot]=w;next[tot]=head[v];head[v]=tot;}

void spfa(int *d)
{
    for(int u,v,i;qh!=qt;)
    {
        qh=qh+1&L;
        u=q[qh];
        inq[u]=0;
        for(i=head[u];i;i=next[i])
            if(ten(d[v=adj[i]],d[u]+c[i])&&!inq[v])
                    q[qt=qt+1&L]=v,inq[v]=1;
    }
}

int SteinerTree()
{
    for(int i=1,j,k;i<1<<cnt;i++)
    {
        for(j=1;j<=n;j++)
        {
            for(k=i&i-1;k;k=k-1&i)
                ten(f[i][j],f[k][j]+f[i^k][j]);
            if(f[i][j]<inf)
                q[++qt]=j;
        }
        spfa(f[i]);
    }
    int ret=inf;
    for(int i=1;i<=n;i++)
        ten(ret,f[(1<<cnt)-1][i]);
    return ret;
}

void init()
{
    scanf("%d%d%d",&n,&m,&P);
    for(int i=1,u,v,w;i<=m;i++)
        scanf("%d%d%d",&u,&v,&w),addedge(u,v,w);
    for(int i=1;i<=P;i++)
        scanf("%d%d",&po[i].c,&po[i].p);
    sort(po+1,po+P+1);
    for(int i=1;i<=P;i++)
        if(po[i].c!=po[i-1].c&&po[i].c!=po[i+1].c)
        {
            for(int j=i;j<=P;j++)po[j]=po[j+1];
            i--;P--;
        }
    for(int i=1,j,k;i<=P;i=j)
    {
        C++;
        for(j=i;po[j].c==po[i].c;j++);
        for(k=i;k<j;k++)po[k].c=C;
    }
  memset(g,63,sizeof(g));
}

void work()
{
    for(int i=1;i<1<<C;i++)
    {
        cnt=0;
        for(int j=1;j<=P;j++)
            if(i&(1<<po[j].c-1))cnt++;
        memset(f,63,maxn<<cnt+2);
        cnt=0;
        for(int j=1;j<=P;j++)
            if(i&(1<<po[j].c-1))
                f[1<<cnt++][po[j].p]=0;
        g[i]=SteinerTree();
    }
    for(int i=1,j;i<1<<C;i++)
        for(j=i&i-1;j;j=j-1&i)
            ten(g[i],g[j]+g[i^j]);
    printf("%d\n",g[(1<<C)-1]);
}

int main()
{
    init();
    work();
    return 0;
}


BZOJ4007: [JLOI2015]战争调度
4007.cpp
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=1111;
int n,m,ans;
int W[2][maxn][15];
int c[maxn];
int f[maxn][maxn];

template<class T> inline bool rel(T &x,const T &y){return x<y?(x=y,1):0;}

void init()
{
    scanf("%d%d",&n,&m);
    for(int i=1<<n-1;i<1<<n;i++)
        for(int j=1;j<n;j++)
            scanf("%d",W[1][i]+j);
    for(int i=1<<n-1;i<1<<n;i++)
        for(int j=1;j<n;j++)
            scanf("%d",W[0][i]+j);
}

void work(int x,int d)
{
    if(x>=1<<n-1)
    {
        f[x][0]=f[x][1]=0;
        for(int j=1;j<n;j++)
            f[x][c[x>>j]]+=W[c[x>>j]][x][j];
        return;
    }
    int *g=f[x],lc=x<<1,rc=x<<1|1,ss=1<<n-d-1;
    memset(g,0,(4<<n-d)+4);
    c[x]=1;
    work(lc,d+1);
    work(rc,d+1);
    for(int i=0;i<=ss;i++)
        for(int j=0;j<=ss;j++)
            rel(g[i+j],f[lc][i]+f[rc][j]);
    c[x]=0;
    work(lc,d+1);
    work(rc,d+1);
    for(int i=0;i<=ss;i++)
        for(int j=0;j<=ss;j++)
            rel(g[i+j],f[lc][i]+f[rc][j]);
}

int main()
{
    init();
    work(1,1);
    for(int i=0;i<=m;i++)
        rel(ans,f[1][i]);
    printf("%d\n",ans);
    return 0;
}

Tags: JLOI, bzoj,
 
comments powered by Disqus