做了一部分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:面试的考验

但愿能填好坑。。。。