JSOI2009 部分简要题解

SYC posted @ 2014年6月24日 14:14 in BZOJ with tags bzoj , 1389 阅读

做了一部分JSOI2009的题,决定来一发题解。。。

difficulty Rating(Just For Those I have Done):

Very Nausea :等差数列(1558)

Meduim:球队收益(1449),火星藏宝图(1560),密码(1559),有趣的游戏(1444)

Easy:Count(1452),瓶子和燃料(2257)

下面是简要题解:


1452:Count

sol:因为c比较小,所以对于每一种颜色开一个二维树状数组即可。。。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
 
int n,m,a[305][305],tree[105][305][305];
int q,opt,x1,y1,x2,y2,x,y,c;
 
 
inline int query(int c,int x,int y)
{
    int ret=0;
    for(int p=x;p;p-=p&(-p))
    for(int z=y;z;z-=z&(-z))
    {
        ret+=tree[c][p][z];
    }
    return ret;
}
 
 
inline void add(int c,int x,int y,int val)
{
    for(int p=x;p<=n;p+=p&(-p))
    for(int z=y;z<=m;z+=z&(-z))
        tree[c][p][z]+=val;
}
 
 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        scanf("%d",&a[i][j]);
        add(a[i][j],i,j,1);
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&opt);
        if(opt==2)
        {
            scanf("%d%d%d%d%d",&x1,&x2,&y1,&y2,&c);
            printf("%d\n",query(c,x2,y2)-query(c,x1-1,y2)-query(c,x2,y1-1)+query(c,x1-1,y1-1));
        }else
        {
            scanf("%d%d%d",&x,&y,&c);
            add(a[x][y],x,y,-1);
            add(c,x,y,1);
            a[x][y]=c;
        }
    }
    return 0;
}

2257:瓶子和燃料;

sol:可以发现,每次选K个体积为v1,v2,v3..vk的瓶子给火星人,最少会返回gcd(v1,v2..vk),于是问题就变为找最大的x,使得x是至少k个数字的约数,Nsqrt(N)枚举+排序即可。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
  
  
int n,m,ans;
int a[1000005],tot;
  
  
  
  
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        for(int j=1;j*j<=x;j++)
        {
            if(x%j==0)
            {
                a[++tot]=j;
                if(j!=x/j)a[++tot]=x/j;
            }
        }
    }
    sort(a+1,a+tot+1);
    for(int i=tot,k=1;i;i--)
    {
        if(a[i]==a[i-1])k++;
        else
        {
            if(k>=m)
            {
                printf("%d\n",a[i]);
                return 0;
            }
            k=1;
        }
    }
    printf("%d\n",ans);
    return 0;
}

1449:球队收益

sol:费用流的想法应该是比较显然。。。,关键在于如何构图?

考虑到又有赢又有输很难搞,又因为一场球队参加的比赛数是一定的。我们先假定每个队伍全都是输的,然后考虑多赢一场可以取得的贡献即可。

一个已经赢了这场后赢了win场,要比tot场,两个系数分别为c,d时的贡献是:

win^2*c+(tot-win)^2*d-(win-1)^2*c+(tot-win+1)^2*d=(c+d)*(2*win-1)-2*d*tot;

然后给每个球队和每场比赛建一个点。源点向比赛连容量为1,费用为0的边,表示每场比赛只有一个获胜。每场比赛向每个球队连容量为1,费用为0的边,表示每场比赛只能算一次贡献。球队向汇点连P条边,P表示它在后面的比赛中参加的比赛数。每条边的费用为赢一场的贡献,容量为1。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define maxn 6005
using namespace std;
  
  
struct e
{
    int u,v,w,c,pre;
}edge[1000005];
int n,UpperLimit,x,dex=-1,source,target;
int c[maxn],d[maxn],num[maxn];
int dis[maxn],visit[maxn],adj[maxn],pre[maxn],qe[maxn];
int ans_cost,ans,m,win[maxn],lose[maxn];
  
  
inline void add(int u,int v,int w,int c)
{
    edge[++dex].u=u;
    edge[dex].v=v;
    edge[dex].w=w;
    edge[dex].c=c;
    edge[dex].pre=adj[u];
    adj[u]=dex;
    edge[++dex].u=v;
    edge[dex].v=u;
    edge[dex].w=0;
    edge[dex].c=-c;
    edge[dex].pre=adj[v];
    adj[v]=dex;
}
  
  
inline int spfa(int source,int target)
{
    memset(dis,0x7f,sizeof(dis));
    memset(visit,0,sizeof(visit));
    memset(pre,-1,sizeof(pre));
    memset(qe,-1,sizeof(qe));
    queue<int>q;
    visit[source]=1;dis[source]=0;
    q.push(source);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=adj[u];i!=-1;i=edge[i].pre)
        if(edge[i].w)
        {
            int v=edge[i].v;
            if(dis[u]+edge[i].c<dis[v])
            {
                dis[v]=dis[u]+edge[i].c;
                pre[v]=u;qe[v]=i;
                if(!visit[v])
                {
                    visit[v]=1;
                    q.push(v);
                }
            }
        }
        visit[u]=0;
    }
    if(dis[target]>10000000)return 0;
    return 1;
}
  
  
inline int ek(int source,int target)
{
    int aug=1<<30;
    for(int i=target;i!=source;i=pre[i])
    {
        aug=min(aug,edge[qe[i]].w);
    }
    ans_cost+=dis[target]*aug;
    for(int i=target;i!=source;i=pre[i])
    {
        edge[qe[i]].w-=aug;
        edge[qe[i]^1].w+=aug;
    }
    return 1;
}
  
  
inline int sqr(int x){return x*x;}
  
  
inline void Build_Graph_To_Do_it(int Source,int Target)
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&win[i],&lose[i],&c[i],&d[i]);
        num[i]=win[i]+lose[i];
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(Source,i+n,1,0);
        add(i+n,u,1,0);
        add(i+n,v,1,0);
        ++num[u];++num[v];
    }
    for(int i=1;i<=n;i++)
    {
        ans+=(c[i]+d[i])*sqr(win[i])+d[i]*sqr(num[i])-2*num[i]*d[i]*win[i];
        for(int j=win[i]+1;j<=num[i]-lose[i];j++)
        {
            add(i,Target,1,(c[i]+d[i])*(2*j-1)-2*num[i]*d[i]);
        } 
    }
    source=Source;
    target=Target;
    //REMEMBER!!!!!!!!!!!!!!!!
}
  
  
inline void work(int source,int target)
{
    while(spfa(source,target))ek(source,target);
}
  
  
int main()
{
    scanf("%d%d",&n,&m);
    memset(adj,-1,sizeof(adj));
    Build_Graph_To_Do_it(0,n+m+1);
    work(source,target);
    printf("%d\n",ans+ans_cost);
    return 0;
}

1560:火星藏宝图

sol:DP比较显然。把所有的点按x,y排序。用F[i]表示到I的最大值,F[i]=max(F[j]-dis(j,i))+a[i];但是这样是N^2的。

如何优化呢,考虑到每列只有行数最大的点才能更新。也就是说每一列只有一个点有用,这样只要枚举列就行了,时间复杂度是NM的。

结论证明:如果某一列上最后一个点为last(坐标(x,y),权为a),不是最后一格的某一点是some((x',y),b),当前点是now((vx,vy),c)

那么路径some->now,贡献为 c+b-(vx-x')^2-(vy-y')^2,路径some->last->now 贡献为 a+b+c-(x-x')^2-(vx-x')^2-(vy-y)^2 ;化出来就会发现后面明显小于前面。。。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 2100000000
using namespace std;
  
  
struct Node
{
    int x,y,v;
    inline void read()
    {
        scanf("%d%d%d",&x,&y,&v);
    }
    inline bool operator <(const Node &e)const
    {
        return (x!=e.x)?(x<e.x):(y<e.y);
    }
}a[200005];
int last[1005],val[1005],n,m;
  
  
inline int sqr(int x){return x*x;}
  
  
inline int dis(const Node &A,const Node &B)
{
    return sqr(A.x-B.x)+sqr(A.y-B.y);
}
  
  
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)a[i].read();
    sort(a+1,a+n+1);
    last[1]=1;val[1]=a[1].v;
    for(int i=2;i<=n;i++)
    {
        int x=a[i].x,y=a[i].y,v=a[i].v;
        int ret=-inf;
        for(int j=1;j<=y;j++)
        {
            ret=max(ret,val[j]-dis(a[last[j]],a[i]));
        }
        ret+=v;
        if(i==n)
        {
            printf("%d\n",ret);
            return 0;
        }
        val[y]=ret;
        last[y]=i;
    }
    return 0;
}

1559:密码

sol:AC自动机+状压DP+DFS

首先对于所有串建立AC自动机并在每个节点上维护一个msk[x],01地表示到达这个点会匹配哪些串;然后用F[i][j][mask]表示长度是I时,AC自动机上有J号点,mask表示匹配了那些串的方案数;F[i][j][k]->F[i][tran[j][w]][k|msk[tran[j][w]];

然后是恶心的输出方案暴力存每个点所有可能的前驱(用链表解决)然后dfs即可(我用了string)

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#define CH getchar()
using namespace std;
  
  
int cnt=1,tree[105][30];
int L,n,msk[105],q[105],upl;
int dex,tot,fail[105];
int h[26][105][1027];
int vis[26][105][1027];
long long f[26][105][1027];
long long ans=0;
struct Node
{
    int node,w,msk,next;
}e[10005];
string rec[55];
  
  
void dfs(int len,int node,int msk,string w)
{
    if(!len)
    {
        rec[++tot]=w;
        return;
    }
    for(int i=h[len][node][msk];i;i=e[i].next)
    {
        dfs(len-1,e[i].node,e[i].msk,char(e[i].w+'a')+w);
    }
}
  
  
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("password.in","r",stdin);
    freopen("password.out","w",stdout);
    #endif
    scanf("%d%d",&L,&n);
    for(int i=1;i<=n;i++)
    {
        char ch=CH;
        while(ch<'a'||ch>'z')ch=CH;
        int p=1;
        while(ch>='a'&&ch<='z')
        {
            if(!tree[p][ch-'a'])tree[p][ch-'a']=(++cnt);
            p=tree[p][ch-'a'];
            ch=CH;
        }
        msk[p]=(1<<(i-1));
    }
    upl=(1<<n)-1;
    int l=1,r=0;
    for(int i=0;i<26;i++)
    {
        if(!tree[1][i])tree[1][i]=1;
        else
        {
            fail[tree[1][i]]=1;
            q[++r]=tree[1][i];
        }
    }
    for(;l<=r;l++)
    {
        int u=q[l];
        msk[u]|=msk[fail[u]];
        for(int i=0;i<26;i++)
        if(tree[u][i])
        {
            int x=tree[u][i];
            fail[x]=tree[fail[u]][i];
            q[++r]=x;   
        }else
            tree[u][i]=tree[fail[u]][i];
    }
    f[0][1][0]=1;
    for(int i=0;i<L;i++)
    for(int j=1;j<=cnt;j++)
    for(int k=0;k<=upl;k++)
    if(f[i][j][k])
    {
        for(int l=0;l<26;l++)
        {
            int nxt=tree[j][l];
            f[i+1][nxt][k|msk[nxt]]+=f[i][j][k];
        }
    }
    for(int i=1;i<=cnt;i++)
    if(f[L][i][upl])
    {
        ans+=f[L][i][upl];
        vis[L][i][upl]=1;
    }
    printf("%lld\n",ans);
    if(ans<=42)
    {
        for(int i=L-1;i+1;i--)
        for(int j=1;j<=cnt;j++)
        for(int k=0;k<=upl;k++)
        if(f[i][j][k])
        {
            for(int l=0;l<26;l++)
            {
                int nxt=tree[j][l];
                int st=k|msk[nxt];
                if(vis[i+1][nxt][k|msk[nxt]])
                {
                    vis[i][j][k]=1;
                    ++dex;
                    e[dex].msk=k;
                    e[dex].next=h[i+1][nxt][st];
                    e[dex].w=l;
                    e[dex].node=j;
                    h[i+1][nxt][st]=dex;
                }
            }
        }
        for(int i=1;i<=cnt;i++)
        if(vis[L][i][upl])
            dfs(L,i,upl,"");
        sort(rec+1,rec+tot+1);
        for(int i=1;i<=tot;i++)
        cout<<rec[i]<<endl;
    }
    return 0;
}

1444:有趣的游戏

sol:还是AC自动机,设X[i]表示AC自动机上到达i号点的概率。那么就可以对于每个点列出方程

X[i]=sigma(X[j]*P[j][i])。P[j][i]表示从J转移到I的概率,且每个串的结尾不转移(因为此时游戏已经结束了)。

但是这个方程是不对的。因为他的解是X[1]=X[2]=..=X[cnt]=0;于是我们要用一个方程来替代其中一个方程:即所有串的结尾的概率和为1.这样就可以高斯消元解了。。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#define CH getchar()
using namespace std;
  
  
int n,l,m,cnt=1;
double rate[15];
int tree[1005][26];
int fail[1005],gra[1005];
int danger[1005];
double a[1005][1005];
double x[1005];
int q[10005];
  
  
inline void build()
{
    int l=1,r=0;
    for(int i=0;i<m;i++)
    if(!tree[1][i])
    {
        tree[1][i]=1;
    }else
    {
        q[++r]=tree[1][i];
        fail[tree[1][i]]=1;
    }
    for(;l<=r;l++)
    {
        int u=q[l];
        for(int i=0;i<m;i++)
        if(tree[u][i])
        {
            q[++r]=tree[u][i];
            fail[q[r]]=tree[fail[u]][i];
        }else tree[u][i]=tree[fail[u]][i];
    }
}
  
  
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("1444.in","r",stdin);
    freopen("1444.out","w",stdout);
    #endif
    scanf("%d%d%d",&n,&l,&m);
    for(int i=0;i<m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        rate[i]=1.0*u/v;
    }
    for(int i=1;i<=n;i++)
    {
        char ch=CH;
        while(ch<'A'||ch>'Z')ch=CH;
        int p=1;
        while(ch>='A'&&ch<='Z')
        {
            if(!tree[p][ch-'A'])tree[p][ch-'A']=(++cnt);
            p=tree[p][ch-'A'];
            ch=CH;
        }
        gra[i]=p;
        danger[p]=1;
    }
    build();
    for(int i=1;i<=cnt;i++)
    {
        a[i][i]=-1;
        if(danger[i])continue;
        for(int j=0;j<m;j++)
            a[tree[i][j]][i]+=rate[j];
    }
    for(int i=1;i<=cnt;i++)a[1][i]=danger[i];
    a[1][cnt+1]=1;
    for(int i=1,k=1;i<=cnt;i++)
    {
        int p=0;
        for(int j=k;j<=cnt;j++)
        if(a[j][i]!=0)
        {
            p=j;
            break;
        }
        if(!p)continue;
        for(int l=1;l<=cnt+1;l++)swap(a[p][l],a[k][l]);
        for(int j=k+1;j<=cnt;j++)
        if(a[j][i])
        {
            double lamda=a[j][i]/a[k][i];
            for(int l=1;l<=cnt+1;l++)    
                a[j][l]-=lamda*a[k][l];
        }
        ++k;
    }
    x[cnt]=a[cnt][cnt+1]/a[cnt][cnt];
    for(int i=cnt-1;i;i--)
    {
        for(int j=i+1;j<=cnt;j++)
            a[i][cnt+1]-=a[i][j]*x[j];
        x[i]=a[i][cnt+1]/a[i][i];
    }
    for(int i=1;i<=n;i++)
    if(x[gra[i]]>0&&x[gra[i]]<=1)
    {
        printf("%.2lf\n",x[gra[i]]);
    }else puts("0.00");
    return 0;
}

1558:等差数列

sol:线段树

  发现等差数列很难搞,考虑把数列差分,开一个辅助数组b[i]=a[i]-a[i+1],那么等差数列就是b[i]中连续相等的一段。

但是是不是b[st...ed-1]中的连续相等的段数就是原数列的等差数列数目呢?

  显然不是,比如以下序列:0 1 2 4 7 10 14 19 24差分后是 1 1 2 3 3 4 5 5 应该有5段。但是实际会分成几段呢? (0 1 2) (4 7 10) (14 19 24) 3段就可以了!原来中间的“单独的”(与左右差分值都不相同)的数值可以忽视或合并掉!再探究后会发现:对于中间连续的P个单独的数值要P/2个等差数列。对于边缘的P个单独的数值要(P/2)+1个等差数列。另外还要特判区间全都是单独的值的情况。

  于是我们再线段树上维护以下7个值:Ld,Rd,lval,rval,ans,lazy,all,分别表示左右边连续的单独值,左边的数值,右边的数值,去掉左右的单独值的答案,加标记和是否全都是单独值。对于A对L..R的操作,我们只需在L-1的地方加上st,R的地方减去(R-L)*step+st;中间的(L..R-1)区间加step即可。

  这题最恐怖的地方是up的时候要很多的分类讨论:主要分以下讨论:1.是否全都是单独值;2.左边的rval和右边的lval是否相等。3.是否存在左右两边连续的单独的值。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls(x) ((x)<<1)
#define rs(x) (((x)<<1)|1)
using namespace std;
  
  
struct Node
{
    int l,r,lval,rval,lazy;
    int ld,rd,ans;
    int all;
}tree[400005],Ans;
int a[100005],b[100005];
int n;
  
  
void up(Node &x,Node &lef,Node &rig)
{
    x.lval=lef.lval;x.rval=rig.rval;
    x.ld=lef.ld;x.rd=rig.rd;
    if(lef.all)
    {
        if(lef.rval==rig.lval)x.ld--;
        else x.ld+=rig.ld;
    }
    if(rig.all)
    {
        if(lef.rval==rig.lval)x.rd--;
        else x.rd+=lef.rd;
    }
    x.ans=lef.ans+rig.ans;
    if(lef.all&&rig.all&&(lef.rval!=rig.lval))x.all=1;else x.all=0;
    if(lef.all)
    {
        if(lef.rval==rig.lval)
        {
            if(rig.all)x.ans++;
            else if(rig.ld)x.ans+=(rig.ld-1)/2+1;
        }
    }else
    if(lef.rd)
    {
        if(lef.rval==rig.lval)
        {
            if(rig.all)x.ans+=(lef.rd-1)/2+1;else
            if(rig.ld)x.ans+=(rig.ld-1)/2+(lef.rd-1)/2+1;
            else x.ans+=(lef.rd-1)/2;
        }else
        {
            if(!rig.all)x.ans+=(lef.rd+rig.ld)/2;
        }
    }else
    {
        if(lef.rval==rig.lval)
        {
            if(!rig.all)if(rig.ld)x.ans+=(rig.ld-1)/2;else x.ans--;
        }else
        {
            if(!rig.all&&rig.ld)x.ans+=rig.ld/2;
        }
    }
}
  
  
void build(int x,int L,int R)
{
    tree[x].l=L;tree[x].r=R;
    if(L==R)
    {
        tree[x].lval=b[L];
        tree[x].rval=b[R];
        tree[x].ld=tree[x].rd=tree[x].all=1;
        return;
    }
    int mid=(L+R)>>1;
    build(ls(x),L,mid);
    build(rs(x),mid+1,R);
    up(tree[x],tree[ls(x)],tree[rs(x)]);
}
  
  
void Add(int x,int val)
{
    tree[x].lval+=val;
    tree[x].rval+=val;
    tree[x].lazy+=val;
}
  
  
void down(int x)
{
    if(!tree[x].lazy)return;
    Add(ls(x),tree[x].lazy);
    Add(rs(x),tree[x].lazy);
    tree[x].lazy=0;
}
  
  
void change(int x,int G,int val)
{
    if(tree[x].l==tree[x].r)
    {
        Add(x,val);
        return;
    }
    down(x);
    int mid=(tree[x].l+tree[x].r)>>1;
    if(G<=mid)change(x<<1,G,val);
    else change((x<<1)|1,G,val);
    up(tree[x],tree[x<<1],tree[(x<<1)|1]);
}
  
  
void change(int x,int L,int R,int val)
{
    if(L<=tree[x].l&&tree[x].r<=R)
    {
        Add(x,val);
        return ;
    }
    down(x);
    int mid=(tree[x].l+tree[x].r)>>1;
    if(L<=mid)change(ls(x),L,R,val);
    if(mid<R)change(rs(x),L,R,val);
    up(tree[x],tree[ls(x)],tree[rs(x)]);
}
  
  
Node query(int x,int L,int R)
{
    if(L<=tree[x].l&&tree[x].r<=R)return tree[x];
    int mid=(tree[x].l+tree[x].r)>>1;
    down(x);
    Node lef,rig,now;
    if(L<=mid)
    {
        lef=query(ls(x),L,R);
        if(R<=mid)return lef;
    }
    if(mid<R)
    {
        rig=query(rs(x),L,R);
        if(mid<L)return rig;
    }
    up(now,lef,rig);
    return now;
}
  
  
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("arithseq.in","r",stdin);
    freopen("arithseq.out","w",stdout);
    #endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<n;i++)b[i]=a[i+1]-a[i];
    build(1,1,n-1);
    int Q;
    scanf("%d",&Q);
    while(Q--)
    {
        char x=getchar();
        while(!(x>='A'&&x<='B'))x=getchar();
        if(x=='A')
        {
            int L,R,st,val;
            scanf("%d%d%d%d",&L,&R,&st,&val);
            if(L>1)change(1,L-1,st);
            if(R<n)change(1,R,-st-val*(R-L));
            if(L<R)change(1,L,R-1,val);
        }else
        {
            int L,R;
            scanf("%d%d",&L,&R);
            if(L==R)
            {
                puts("1");
                continue;
            }
            Ans=query(1,L,R-1);
            if(Ans.all)
            {
                printf("%d\n",(R-L+2)/2);
            }else
            {
                printf("%d\n",Ans.ans+(Ans.ld+1)/2+(Ans.rd+1)/2);
            }
        }
    }
    return 0;
}

下面是坑:

1443:游戏GAME

1561:去括号

2221:面试的考验

但愿能填好坑。。。。

Avatar_small
Junior Dakil Result 说:
2022年8月28日 15:23

Jessore Divisional education board of Bangladesh has successfully conducted the Grade 8th terminal examination tests for both Junior School Certificate & Junior Dakhil Certificate course students at all districts under the division to the academic year of 2022, there are a huge number of students are appeared from all Secondary schools under the board like as previous years, Junior Dakil Result jessore Board and this is most important examination tests for class 8th standard students of the country.Government of Bangladesh, Secondary and Higher Secondary Education Board has successfully completed the JSC & JDC examinations in the month of November 2022 to all eligible students of the division at all selected examination centers at all rural and urban area schools, both of Junior School Certificate & Junior Dakhil Certificate terminal exams are conducted as per date sheet announced by all education board Bangladesh.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta
Butterfly Theme | Design: HRS Hersteller of mobile Hundeschule.