【SDOI2010题集整合】BZOJ1922~1927&1941&1951&1952&1972&1974&1975

时间：2024-10-07 20:35:50

BZOJ1922大陆争霸

思路：带限制的单源最短路

限制每个点的条件有二，路程和最早能进入的时间，那么对两个值一起限制跑最短路，显然想要访问一个点最少满足max（dis，time）

那么每次把相连的点以及所保护的点扔进堆中，用以更新答案，不过值得注意的是，入堆的时候进行判断

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

#define p pair<int,int>

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 3010

#define maxm 70010

int n,m;

struct data{int to,next,w;}edge[maxm];

int l[maxn][maxn],lt[maxn],ll[maxn];

int head[maxn],cnt;

int S,T;

void add(int u,int v,int w)

{

    cnt++;

    edge[cnt].next=head[u];  head[u]=cnt;

    edge[cnt].to=v; edge[cnt].w=w;

}

int dis1[maxn],dis2[maxn];

bool visit[maxn];

priority_queue<p,vector<p>,greater<p> >q;

void dijkstra()

{

    memset(dis1,0x3f,sizeof(dis1));

    q.push(make_pair(,S));  dis1[S]=;

    while (!q.empty())

        {

            int now=q.top().second; q.pop();

            if(visit[now]) continue; visit[now]=;

            //printf("%d\n",now);

            int dis=max(dis1[now],dis2[now]);

            for (int i=head[now]; i; i=edge[i].next)

                if (dis+edge[i].w<dis1[edge[i].to])

                    {

                        dis1[edge[i].to]=dis+edge[i].w;

                        int tmp=max(dis1[edge[i].to],dis2[edge[i].to]);

                        if(!ll[edge[i].to]) q.push(make_pair(tmp,edge[i].to));

                    }

            //printf("%d\n",lt[now]);

            for (int i=; i<=lt[now]; i++)

                {

                    int noww=l[now][i]; ll[noww]--;

                    dis2[noww]=max(dis2[noww],dis);

                    if (!ll[noww]) q.push(make_pair(max(dis1[noww],dis2[noww]),noww));

                }

        }

}

int main()

{

    n=read(),m=read();

    for (int i=; i<=m; i++)

        {

            int u=read(),v=read(),w=read();

            if (u!=v) add(u,v,w);

        }

    for (int i=; i<=n; i++)

        {

            ll[i]=read();

            for (int j=; j<=ll[i]; j++)

                {

                    int x=read();

                    l[x][++lt[x]]=i;

                }

        }

    S=;T=n;

    dijkstra();

//  for (int i=1; i<=n; i++)

//      printf("%d %d\n",dis1[i],dis2[i]);

    printf("%d\n",max(dis1[T],dis2[T]));

    return ;

}

大陆争霸

BZOJ1923外星千足虫

思路：高斯消元解xor方程组

对于给出的信息，显然是一个方程组，对于方程组，考虑高斯消元求解，不过这里的方程组带取模，所以考虑位运算xor，套高斯消元即可

Code：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<bitset>

#include<cstring>

#include<cstdlib>

using namespace std;

bitset <> A[];

int B[],n,m,ans;

char s[];

int Gauss()

{

    for (int i=; i<=n; i++)

        {

            int j=i;

            while (j<=m && !A[j][i]) j++;

            if (j==m+) return ;

            ans=max(ans,j);

            swap(A[i],A[j]);

            for (int k=; k<=m; k++)

                if (i!=k && A[k][i])

                    A[k]^=A[i];

        }

    return ;

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=; i<=m; i++)

        {

            scanf("%s%d",s,&B[i]);

            for (int j=; j<=n-; j++) A[i][j+]=s[j]-'';

            A[i][n+]=B[i];

        }

    int OK=Gauss();

    if (!OK) {puts("Cannot Determine"); return ;}

    printf("%d\n",ans);

    for (int i=; i<=n; i++)

        if (A[i][n+]) puts("?y7M#");

            else puts("Earth");

    return ;

}

外形千足虫

BZOJ1924所驼门王的宝藏

思路：Tarjan+拓扑图DP

首先将给出的各种关系相连，这里比较麻烦的是，需要用vector去记录行和列的情况，map判断八连通的情况

选择一个 横/竖 格向同 行/列 所有点连单向边，对 横/竖 格连双向边；八连通直接连；Tarjan并重构，做一个 傻傻的DP即可

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<map>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 100010

int dx[]={,,,,,-,-,-},dy[]={,-,,,-,,,-};

struct EdgeNode{int next,to;}edge[maxn*],road[maxn*];

int cnt,tot,head[maxn],last[maxn];

void addedge(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}

void insertedge(int u,int v) {if (u==v) return; addedge(u,v);}

void addroad(int u,int v) {tot++; road[tot].next=last[u]; last[u]=tot; road[tot].to=v;}

void insertroad(int u,int v) {addroad(u,v);}

int x[maxn],y[maxn],t[maxn],dfn[maxn],low[maxn],stack[maxn],num[maxn],belong[maxn],dp[maxn];

bool visit[maxn];

int n,r,c,ans,top,qcnt;

vector<int>h[maxn*],l[maxn*];

map<int,int>mp[maxn*];

void BuildGraph()

{

    for (int i=; i<=r; i++)

        {

            int hn=h[i].size(),now=;

            for (int j=; j<=hn-; j++) if (t[h[i][j]]==) {now=h[i][j]; break;}

            for (int j=; j<=hn-; j++) {insertedge(now,h[i][j]); if (t[h[i][j]]==) insertedge(h[i][j],now);}

        }

    for (int i=; i<=c; i++)

        {

            int ln=l[i].size(),now=;

            for (int j=; j<=ln-; j++) if (t[l[i][j]]==) {now=l[i][j]; break;}

            for (int j=; j<=ln-; j++) {insertedge(now,l[i][j]); if (t[l[i][j]]==) insertedge(l[i][j],now);}

        }

    for (int i=; i<=n; i++)

        if (t[i]==)

            for (int xx,yy,j=; j<=; j++)

                {

                    xx=x[i]+dx[j],yy=y[i]+dy[j];

                    if (mp[xx][yy]) insertedge(i,mp[xx][yy]);

                }

}

void Tarjan(int x)

{

    dfn[x]=low[x]=++tot; visit[x]=; stack[++top]=x;

    for (int i=head[x]; i; i=edge[i].next)

        {

            if (!dfn[edge[i].to])

                {

                    Tarjan(edge[i].to);

                    if (low[edge[i].to]<low[x]) low[x]=low[edge[i].to];

                }

            else

                if(visit[edge[i].to] && dfn[edge[i].to]<low[x])

                    low[x]=dfn[edge[i].to];

        }

    if (dfn[x]==low[x])

        {

            int uu=; qcnt++;

            while (x!=uu)

                uu=stack[top--],num[qcnt]++,visit[uu]=,belong[uu]=qcnt;

        }

}

void reBuildGraph()

{

    for (int i=; i<=n; i++)

        for (int j=head[i]; j; j=edge[j].next)

            if (belong[i]!=belong[edge[j].to])

                insertroad(belong[i],belong[edge[j].to]);

}

void DP(int now)

{

    visit[now]=;

    for (int i=last[now]; i; i=road[i].next)

        {

            if (!visit[road[i].to]) DP(road[i].to);

            dp[now]=max(dp[now],dp[road[i].to]);

        }

    dp[now]+=num[now];

    ans=max(ans,dp[now]);

}

int main()

{

    n=read(); r=read(); c=read();

    for (int i=; i<=n; i++)

        {

            x[i]=read(),y[i]=read(),t[i]=read();

            mp[x[i]][y[i]]=i; h[x[i]].push_back(i); l[y[i]].push_back(i);

        }

    BuildGraph();

    for (int i=; i<=n; i++) if (!dfn[i]) Tarjan(i);

    reBuildGraph();

    for (int i=; i<=qcnt; i++) if (!visit[i]) DP(i);

    printf("%d\n",ans);

    return ;

}

所驼门王的宝藏

BZOJ1925地精部落

思路：DP 抖动子序列

f[i][j]表示以j为开头的长度为i的抖动子序列个数，这种序列有些性质：

1.在一个1-n的排列构成的抖动序列里,交换任意的元素i和i+1,它仍然是符合条件的抖动序列 
2.一个开头上升的抖动序列翻转过来就变成了符合条件的开头下降的

那么就可以转移了$f[i][j]=f[i-1][j]+f[i-1][i-j]$,最后的结果当然就是$f[n][n]*2$ 还有就是这题需要滚动数组

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 5010

int n,p;

int f[][maxn];

int main()

{

    n=read(),p=read();

    f[][]=;

    for (int i=; i<=n; i++)

        for (int j=; j<=i; j++)

            f[i&][j]=(f[i&][j-]%p+f[(i&)^][i-j]%p)%p;

    printf("%d\n",(f[n&][n]*)%p);

    return ;

}

地精部落

BZOJ1926粟粟的书架

思路：前缀和  主席树  二合一  （二维莫队）

用二合一的方法水过这道题，对于行数=1的情况，很显然裸主席树；对于矩阵的情况，范围允许$n^{2}$的，考虑预处理两个二维的前缀和

sum[i][j][k]表示>=k的数的和，num[i][j][k]表示>=k的数的个数 那么询问的时候二分一下就好

Code：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-')f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

int R,C,M;

#define maxn 500010

int Sum[maxn*],Num[maxn*],ll[maxn*],rr[maxn*],root[maxn<<],sz;

int sum[][][],num[][][],p[][];

void Insert(int l,int r,int &now,int fat,int val)

{

    now=++sz; Sum[now]=Sum[fat]+val; Num[now]=Num[fat]+;

    if (l==r) return;

    ll[now]=ll[fat],rr[now]=rr[fat];

    int mid=(l+r)>>;

    if (val<=mid) Insert(l,mid,ll[now],ll[fat],val);

    else Insert(mid+,r,rr[now],rr[fat],val);

}

int Query(int l,int r,int L,int R,int kth)

{

    if (Sum[root[R]]-Sum[root[L-]]<kth) return -;

    L=root[L-]; R=root[R];

    int re=;

    while (l<r)

        {

            int mid=(l+r)>>,tmp=Sum[rr[R]]-Sum[rr[L]];

            if (tmp<kth) {re+=Num[rr[R]]-Num[rr[L]]; kth-=tmp; r=mid; L=ll[L]; R=ll[R];}

                else {l=mid+; L=rr[L]; R=rr[R];}

        }

    re+=(kth+l-)/l;

    return re;

}

void Part1()

{

    for (int i=; i<=C; i++) Insert(,,root[i],root[i-],read());

    while (M--)

        {

            int x1=read(),y1=read(),x2=read(),y2=read(),h=read();

            int ans=Query(,,y1,y2,h);

            if (ans==-) {puts("Poor QLW"); continue;}

            printf("%d\n",ans);

        }

}

int GetSum(int x1,int y1,int x2,int y2,int k) {return sum[x1-][y1-][k]+sum[x2][y2][k]-sum[x1-][y2][k]-sum[x2][y1-][k];}

int GetNum(int x1,int y1,int x2,int y2,int k) {return num[x1-][y1-][k]+num[x2][y2][k]-num[x1-][y2][k]-num[x2][y1-][k];}

void Part2()

{

    int maxx=;

    for (int i=; i<=R; i++)

        for (int j=; j<=C; j++)

            p[i][j]=read(),maxx=max(maxx,p[i][j]);

    for (int i=; i<=R; i++)

        for (int j=; j<=C; j++)

            for (int k=; k<=maxx; k++)

                num[i][j][k]=num[i-][j][k]+num[i][j-][k]-num[i-][j-][k]+(p[i][j]>=k?:),

                sum[i][j][k]=sum[i-][j][k]+sum[i][j-][k]-sum[i-][j-][k]+(p[i][j]>=k?p[i][j]:);

    while (M--)

        {

            int x1=read(),y1=read(),x2=read(),y2=read(),h=read();

            int l=,r=maxx+,k=-;

            while (l+<r)

                {

                    int mid=(l+r)>>;

                    if (GetSum(x1,y1,x2,y2,mid)>=h) l=mid,k=mid; else r=mid;

                }

            if (k==-) {puts("Poor QLW"); continue;}

            printf("%d\n",GetNum(x1,y1,x2,y2,k)-(GetSum(x1,y1,x2,y2,k)-h)/k);

        }

}

int main()

{

    R=read(),C=read(),M=read();

    if (R==) Part1(); else Part2();

    return ;

}

粟粟的书架

BZOJ1927星际竞速

思路：最小费用流

每个星球拆成两个点，入点$u_{i}$出点$v_{i}$

$S-->u_{i}$  容量为1，费用为0；

$S-->v_{i}$  容量为1，费用为0；

$v_{i}-->T$  容量为1，费用为0；

读入U,V,C如果$V>U$则交换，$U_{u_{i}}-->V_{v_{i}}$  容量为1，费用为C；

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define inf 0x7fffffff

struct data{

    int next,to,v,c;

}edge[];

int cnt=,head[];

int q[],h,t;

bool mark[];

bool visit[];

int n,m;

int ans,num;

int dis[];

int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void add(int u,int v,int cap,int cost)

{

    cnt++;edge[cnt].to=v;

    edge[cnt].next=head[u];head[u]=cnt;

    edge[cnt].v=cap;edge[cnt].c=cost;

}

void insert(int u,int v,int cap,int cost)

{

    add(u,v,cap,cost);add(v,u,,-cost);

}

bool spfa()

{

    memset(visit,,sizeof(visit));

    for (int i=; i<=num; i++) dis[i]=inf;

    h=,t=;

    q[]=num;visit[num]=;dis[num]=;

    while (h<t)

        {

            int now=q[h];h++;visit[now]=;

            for (int i=head[now]; i; i=edge[i].next)

                if (edge[i^].v && dis[now]-edge[i].c<dis[edge[i].to])

                    {

                        dis[edge[i].to]=dis[now]-edge[i].c;

                        if (!visit[edge[i].to])

                            {

                                visit[edge[i].to]=;

                                q[t++]=edge[i].to;

                            }

                    }

        }

    return dis[]!=inf;

}

int dfs(int loc,int low)

{

    mark[loc]=;

    if (loc==num)   return low;

    int w,used=;

    for (int i=head[loc]; i; i=edge[i].next)

        if (dis[edge[i].to]==dis[loc]-edge[i].c && edge[i].v && !mark[edge[i].to])

            {

                w=dfs(edge[i].to,min(low-used,edge[i].v));

                ans+=w*edge[i].c;

                edge[i].v-=w;edge[i^].v+=w;

                used+=w;if (used==low)  return low;

            }

    return used;

}

void zkw()

{

    int tmp=;

    while (spfa())

        {

            mark[num]=;

            while (mark[num])

                {

                    memset(mark,,sizeof(mark));

                    tmp+=dfs(,inf);

                }

        }

}

int main()

{

    n=read();m=read();num=*n+;

    for (int i=; i<=n; i++)

        {

            int cost=read();

            insert(,i,,);

            insert(i+n,num,,);

            insert(,i+n,,cost);

        }

    for (int i=; i<=m; i++)

        {

            int x=read(),y=read(),z=read();

            if (x>y) {int temp=x;x=y;y=temp;}

            insert(x,y+n,,z);

        }

    zkw();

    printf("%d\n",ans);

    return ;

}

星际竞速

BZOJ1941Hide and Seek

思路： KD-Tree

把所有点加入KD-Tree，然后枚举每个点去找他的最远、最近点，并更新答案

需要注意的是,计算最远和最近的两个分开写,而且计算最近点的时候不能计算到自己

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-')f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define inf 0x7fffffff

#define maxn 500010

int n,D,ans;

struct PointNode

{

    int l,r; int d[],maxx[],minn[];

    PointNode (int x=,int y=) {l=r=; d[]=x,d[]=y;}

    bool operator < (const PointNode & A) const {return d[D]<A.d[D];}

}p[maxn];

int dis(PointNode A,PointNode B) {return abs(A.d[]-B.d[])+abs(A.d[]-B.d[]);}

struct KDTreeNode

{

    PointNode tree[maxn<<],Point;

    int rt,ansMax,ansMin;

    void Update(int now)

        {

            for (int i=; i<=; i++)

                {

                    tree[now].minn[i]=tree[now].maxx[i]=tree[now].d[i];

                    if (tree[now].l)

                        tree[now].minn[i]=min(tree[tree[now].l].minn[i],tree[now].minn[i]),

　　　　　　　　　　　　　　tree[now].maxx[i]=max(tree[tree[now].l].maxx[i],tree[now].maxx[i]);

                    if (tree[now].r)

                        tree[now].minn[i]=min(tree[tree[now].r].minn[i],tree[now].minn[i]),

　　　　　　　　　　　　　　tree[now].maxx[i]=max(tree[tree[now].r].maxx[i],tree[now].maxx[i]);

                }

        }

    int BuildTree(int l,int r,int dd)

        {

            int mid=(l+r)>>;

            D=dd; nth_element(p+l,p+mid,p+r+);

            tree[mid]=p[mid];

            for (int i=; i<=; i++) tree[mid].minn[i]=tree[mid].maxx[i]=tree[mid].d[i];

            if (l<mid) tree[mid].l=BuildTree(l,mid-,dd^);

            if (r>mid) tree[mid].r=BuildTree(mid+,r,dd^);

            Update(mid);

            return mid;

        }

    int disMax(int now)

        {

            if (!now) return -inf;

            int re=;

            for (int i=; i<=; i++)

                re+=max(abs(tree[now].maxx[i]-Point.d[i]),abs(tree[now].minn[i]-Point.d[i]));

            return re;

        }

    int disMin(int now)

        {

            if (!now) return inf;

            int re=;

            for (int i=; i<=; i++) re+=max(,tree[now].minn[i]-Point.d[i]);

            for (int i=; i<=; i++) re+=max(,Point.d[i]-tree[now].maxx[i]);

            return re;

        }

    void GetMax(int now)

        {

            if (!now) return;

            int dl,dr,d0;

            d0=dis(tree[now],Point);

            ansMax=max(d0,ansMax);

            if (tree[now].l) dl=disMax(tree[now].l);

            if (tree[now].r) dr=disMax(tree[now].r);

            if (dl>dr)

                {

                    if (dl>ansMax) GetMax(tree[now].l);

                    if (dr>ansMax) GetMax(tree[now].r);

                }

            else

                {

                    if (dr>ansMax) GetMax(tree[now].r);

                    if (dl>ansMax) GetMax(tree[now].l);

                }

        }

    void GetMin(int now)

        {

            if (!now) return;

            int dl,dr,d0;

            d0=dis(tree[now],Point);

            if (d0) ansMin=min(ansMin,d0);

            if (tree[now].l) dl=disMin(tree[now].l);

            if (tree[now].r) dr=disMin(tree[now].r);

            if (dl<dr)

                {

                    if (dl<ansMin) GetMin(tree[now].l);

                    if (dr<ansMin) GetMin(tree[now].r);

                }

            else

                {

                    if (dr<ansMin) GetMin(tree[now].r);

                    if (dl<ansMin) GetMin(tree[now].l);

                }

        }

    int QueryMax(PointNode P) {Point=P; ansMax=-inf; GetMax(rt); return ansMax;}

    int QueryMin(PointNode P) {Point=P; ansMin=inf; GetMin(rt); return ansMin;}

}KDTree;

int main()

{

    n=read();

    for (int x,y,i=; i<=n; i++) x=read(),y=read(),p[i].d[]=x,p[i].d[]=y;

    for (int i=; i<=; i++) p[].maxx[i]=-inf,p[].minn[i]=inf;

    KDTree.rt=KDTree.BuildTree(,n,);

    ans=inf;

    for (int i=; i<=n; i++)

        {

            int minn=KDTree.QueryMin(p[i]),maxx=KDTree.QueryMax(p[i]);

            ans=min(ans,maxx-minn);

        }

    printf("%d\n",ans);

    return ;

}

Hide and Seek

BZOJ1951古代猪文

思路：组合数取模Lucas定理、中国剩余定理

首先弄清楚求解的东西：$G^{\sum_{d|n}C_{n}^{d}} mod 999911659$

这个东西，设指数为M，模数为P，经过费马小定理可以转化一下：$G^{M}modP=G^{Mmod(P-1)}(G!=P)$

这里$P-1$不是质数，所以把它拆成多个质数的形式，最后用中国剩余定理合并即可

Code：

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

using namespace std;

int pp[]={,,,};int G,N,P=;

int jc[][];

int M[];

void exgcd(int a,int b,int &x,int &y)

{

    if (b==) {x=;y=;return;}

    exgcd(b,a%b,x,y);

    int tmp=x;x=y;y=tmp-a/b*y;

}

int quick_pow(long long a,int b,int p)

{

    int ans=;

    for(int i=b;i;i>>=,a=(a*a)%p)

        if(i&)ans=(ans*a)%p;

    return ans;

}

void cs()

{

    jc[][]=jc[][]=jc[][]=jc[][]=;

    for (int i=; i<; i++)

        for (int j=; j<=pp[i]; j++)

            jc[i][j]=(jc[i][j-]*j)%pp[i];

}

int C(int n,int m,int p)

{

    if (n<m) return ;

    return jc[p][n]*quick_pow(jc[p][m]*jc[p][n-m],pp[p]-,pp[p])%pp[p];

}

int lucas(int n,int m,int p)

{

    if (m==) return ;

    return C(n%pp[p],m%pp[p],p)*lucas(n/pp[p],m/pp[p],p)%pp[p];

}

int china()

{

    int a1,b1,a2,b2,a,b,c,x,y;

    a1=pp[],b1=M[];

    for(int i=;i<;i++)

    {

        a2=pp[i],b2=M[i];

        a=a1;b=a2;c=b2-b1;

        exgcd(a,b,x,y);

        x=((c*x)%b+b)%b;

        b1=b1+a1*x;

        a1=a1*b;

    }

    return b1;

}

int work()

{

    G%=P;

    for (int i=; i*i<=N; i++)

        {

            if (N%i==)

                {

                    int tmp=N/i;

                    for (int j=; j<; j++)

                        {

                            if (tmp!=i)

                                M[j]=(M[j]+lucas(N,i,j))%pp[j];

                            M[j]=(M[j]+lucas(N,tmp,j))%pp[j];

                        }

                }

        }

    printf("%d\n",quick_pow(G,china(),P));

}

int main()

{

    cs();

    scanf("%d%d",&N,&G);

    if (G==P) {puts("");return ;}

    work();

    return ;

}

古代猪文

BZOJ1952城市规划

思路： 仙人掌DP  最大点权独立集

求解最大点权独立集，然后仔细读样例发现，这里的“独立集”不同于平常的独立集，即不能选中间隔着一个的两个点

那么对于正常的求解方法是dp[i][0/1]表示当前到i位，选或不选的答案，这里就带限制的dp[i][0/1/2]去进行dp即可，转移是类似的

对仙人掌的处理方法一样是找环，拆环单独DP

Code：

自己的正确版

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxn 1000100

struct EdgeNode{int to,next;}edge[maxn<<];

int head[maxn],cnt;

void add(int u,int v) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v;}

void insert(int u,int v) {add(u,v); add(v,u);}

int deep[maxn],fa[maxn],dfn[maxn],low[maxn],dp1[maxn][],dp2[maxn][],ring[maxn],HX[maxn],t;

int n,m,ans;

void CactusDP(int st,int tt)

{

    ring[]=tt; int zz=;

    while (ring[zz]!=st) {ring[zz+]=fa[ring[zz]]; zz++;}

    //printf("Num=%d  :",zz);

    //for (int i=1; i<=zz; i++) printf("%d ->",ring[i]); printf("\n");

    int f0=,f1=,f2=;

    for (int opt=; opt<=; opt++)

        {

            dp2[][]=dp2[][]=dp2[][]=;

            dp2[][opt]=dp1[tt][opt];

            if (opt==) dp2[][]=dp2[][];

            for (int i=; i<=zz; i++)

                dp2[i][]=dp2[i-][]+dp1[ring[i]][],

                dp2[i][]=max(max(dp2[i-][],dp2[i-][])+dp1[ring[i]][],dp2[i-][]+dp1[ring[i]][]),

                dp2[i][]=max(dp2[i-][],dp2[i-][])+dp1[ring[i]][];

            if (opt==) f1=max(f1,dp2[zz][]);

            if (opt==) f1=max(f1,dp2[zz][]),f2=max(f2,dp2[zz][]);

            if (opt==) f1=max(f1,dp2[zz][]),f0=max(f0,dp2[zz][]),f2=max(f2,dp2[zz][]);

        }

    dp1[st][]=f0; dp1[st][]=f1; dp1[st][]=f2;

}

void TreeDP(int now)

{

    dfn[now]=low[now]=++t;

    dp1[now][]=; dp1[now][]=HX[now]; int maxx=;

    for (int i=head[now]; i; i=edge[i].next)

        if (edge[i].to!=fa[now])

            {

                if (deep[edge[i].to]) {low[now]=min(dfn[edge[i].to],low[now]); continue;}

                fa[edge[i].to]=now; deep[edge[i].to]=deep[now]+;

                TreeDP(edge[i].to);

                if (low[edge[i].to]>low[now])

                    dp1[now][]+=max(dp1[edge[i].to][],dp1[edge[i].to][]),

                    dp1[now][]+=dp1[edge[i].to][],

                    maxx=max(maxx,dp1[edge[i].to][]-max(dp1[edge[i].to][],dp1[edge[i].to][]));

                low[now]=min(low[now],low[edge[i].to]);

            }

    dp1[now][]=maxx+dp1[now][];

    for (int i=head[now]; i; i=edge[i].next)

        if (low[edge[i].to]==dfn[now] && edge[i].to!=fa[now] && deep[edge[i].to]!=deep[now]+)

            CactusDP(now,edge[i].to);

}

void Freopen() {freopen("area.in","r",stdin); freopen("area.out","w",stdout);}

void Fclose() {fclose(stdin); fclose(stdout);}

int main()

{

    //Freopen();

    n=read(),m=read();

    for (int i=; i<=n; i++) HX[i]=read();

    for (int u,v,i=; i<=m; i++) u=read(),v=read(),insert(u,v);

    for (int i=; i<=n; i++) if (!dfn[i]) {fa[i]=i,deep[i]=; TreeDP(i); ans+=max(dp1[i][],max(dp1[i][],dp1[i][]));}

    printf("%d\n",ans);

    //Fclose();

    return ;

}

Area

错误的标算

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std; 

const int N = , inf = ~0U >> ; 

#define forEdges(iter,u) for(edge* iter = e[u]; iter; iter = iter->n)

struct edge { int t; edge *n; }

    ebf[N << ], *e[N], *ec = ebf; 

int weight[N], n;

int dfn[N], low[N], S[N], sTop, dTime;

int f[N][], rf[N][], id[N], opt[N]; 

inline void updateN (int &x, int y) { if (x > y) x = y; }

inline void updateX (int &x, int y) { if (x < y) x = y; } 

inline void dfs (int u, int au)

{

    int v;

    dfn[u] = low[u] = ++dTime, S[++sTop] = u;

    forEdges(it, u) if ((v = it->t) != au)

        if (!dfn[v]) dfs(v, u), updateN(low[u], low[v]);

        else updateN(low[u], dfn[v]);

    int maxDelt();

    f[u][] = , f[u][] = weight[u];

    forEdges(it, u) if ((v = it->t) != au && low[v] > dfn[u]) // Sons

    {

        f[u][] += max(f[v][], f[v][]);

        f[u][] += f[v][];

        updateX(maxDelt, f[v][] - max(f[v][], f[v][]));

    }

    f[u][] = f[u][] + maxDelt; 

    forEdges(it, u) if (low[it->t] == dfn[u]) // A ring

    {

        int rs = ;

        while (S[sTop] != u) id[++rs] = S[sTop--];

        id[++rs] = u;

        /* RingDP : Line 53 .. 55 */

        int f0 = , f1 = , f2 = ;

        for (int st = ; st <= ; ++st)

        {

            rf[][] = rf[][] = rf[][] = ;

            rf[][st] = f[id[]][st];

            if (st == ) rf[][] = rf[][];

            for (int i = ; i <= rs; ++i)

            { //RingDP

                rf[i][] = f[id[i]][] + rf[i - ][];

                rf[i][] = max(f[id[i]][] + max(rf[i - ][], rf[i - ][]), f[id[i]][] + rf[i - ][]);

                rf[i][] = f[id[i]][] + max(rf[i - ][], rf[i - ][]);

            }

            switch (st)

            {

                case  : updateX(f1, rf[rs][]); break; //!!

                case  : updateX(f1, rf[rs][]), updateX(f2, rf[rs][]); break;

                case  : updateX(f0, rf[rs][]), updateX(f1, rf[rs][]), updateX(f2, rf[rs][]); break;

            }

        }

        f[u][] = f0, f[u][] = f1, f[u][] = f2;

    } 

    if (dfn[u] == low[u]) while (S[sTop + ] != u) --sTop;

    opt[u] = max(f[u][], max(f[u][], f[u][]));

} 

int main ()

{

    int m, a, b;

   // freopen("area.in", "r", stdin);

   // freopen("area.out", "w", stdout);

    scanf("%d%d", &n, &m);

    for (int i = ; i <= n; ++i) scanf("%d", weight + i);

    while (m--)

    {

        scanf("%d%d", &a, &b);

        *ec = (edge){b, e[a]}; e[a] = ec++;

        *ec = (edge){a, e[b]}; e[b] = ec++;

    }

    int res = ;

    for (int i = ; i <= n; ++i)

        if (!dfn[i]) dfs(i, ), res += opt[i]; //A Connected Component

    printf("%d\n", res);

    return ;

}

Area-std

BZOJ1972猪国杀

思路：大模拟

Code：

迟迟不敢动手

猪国杀

BZOJ1974auction代码拍卖会

思路：DP、组合数学

发现从左到右每一位不减，那么有个不错的性质，可以组成的数，拆成${1，11，111，1111....}$中取$<=8$个数组合出来

而这些数%p，最多有p种可能，那么找循环，DP，用组合数计算一下答案即可

那么方程就是$dp[i][j][k]$表示前i种可能选了j个，组合出来的数%p结果为k的方案数

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define mod 999911659

long long n;int p,a,ans;

long long dp[][][],inv[],c[][],data[],cnt[];

long long C(long long x,int y)

{

    if (y>x) return ;

    long long re=;

    for (long long i=x-y+; i<=x; i++)

        (re*=(i%mod))%=mod;

    return re*inv[y]%mod;

}

void GetInv()

{

    inv[]=,inv[]=;

    for (int i=; i<=; i++)

        inv[i]=(mod-mod/i)*inv[mod%i]%mod;

    for (int i=; i<=; i++)

        inv[i]=inv[i]*inv[i-]%mod;

}

int main()

{

    scanf("%lld%d",&n,&p);

    GetInv();

    int x=%p,sz=;

    while (!cnt[x]) {cnt[x]=++sz; data[sz]=x; if (sz>=n) break; x=(x*+)%p;}

    if (sz!=n)

        {

            long long N=n-cnt[x]+; int SZ=sz-cnt[x]+;

            if (SZ>) a=(p-data[cnt[x]+(N%SZ?N%SZ:SZ)-])%p;

                else a=(p-data[cnt[x]])%p;

            for (int i=,t=cnt[x]; i<p; i++)

                if (cnt[i])

                    if (cnt[i]<t) cnt[i]=;

                        else

                            if (SZ> && (N%SZ)>cnt[i]-t)

                                cnt[i]=N/SZ+; else cnt[i]=N/SZ;

        }

    else

        {

            a=(p-x)%p;

            for (int i=; i<p; i++) if (cnt[i]) cnt[i]=;

        }

    for (int i=; i<p; i++)

        for (int j=; j<; j++)

            if (cnt[i]) c[i][j]=C(cnt[i]+j-,j);

    dp[][][]=;

    int now=;

    for (int i=; i<p; i++)

        if (cnt[i])

            {

                now^=;

                for (int j=; j<; j++)

                    for (int k=; k<p; k++)

                        dp[now][j][k]=dp[now^][j][k];

                for (int j=; j<; j++)

                    for (int k=; k<p; k++)

                        if (dp[now^][j][k])

                            for (int l=; l<-j; l++)

                                (dp[now][j+l][(k+l*i)%p]+=dp[now^][j][k]*c[i][l]%mod)%=mod;

            }

    for (int i=; i<; i++)

        ans=(ans+dp[now][i][a])%mod;

    printf("%d\n",ans);

    return ;

}

auction代码拍卖会

BZOJ1975魔法猪学院

思路：A*求K短路

大体的思路就是： 首先需要求出每个点到T的最短路径，要求它需要： 
1.先建出当前图的反图，即每个边的反向边。 
2.用反向边做一遍SPFA，dis数组存储的即是当前点到T的最短距离； 然后建立估价函数，利用估价函数去维护一个堆，此处使用STL里的Priority_Queue； 
不断的入队出队，当T出队次数达到K次，即返回值。即为所求K短路；

会求k短路之后，就每次求k短并相减即可；

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxm 200010

#define maxn 5010

struct data{int to,next;double power;}edge[maxm],reedge[maxm];

int head[maxn],cnt;int rehead[maxn],recnt;

int n,m,S,T,ans;

double po;

void add(int u,int v,double p)

{

    cnt++;

    edge[cnt].next=head[u]; head[u]=cnt;

    edge[cnt].to=v; edge[cnt].power=p;

    recnt++;

    reedge[recnt].next=rehead[v]; rehead[v]=recnt;

    reedge[recnt].to=u; reedge[recnt].power=p;

}

double dis[maxn];

#define inf 1000000001.0

inline void spfa()

{

    queue<int>q;

    bool visit[maxn]; memset(visit,,sizeof(visit));

    for (int i=S; i<=T; i++) dis[i]=inf;

    q.push(T); dis[T]=0.0; visit[T]=;

    while (!q.empty())

        {

            int now=q.front(); q.pop();

            for (int i=rehead[now]; i; i=reedge[i].next)

                if (dis[now]+reedge[i].power<dis[reedge[i].to])

                    {

                        dis[reedge[i].to]=dis[now]+reedge[i].power;

                        if (!visit[reedge[i].to])

                            {

                                q.push(reedge[i].to);

                                visit[reedge[i].to]=;

                            }

                    }

            visit[now]=;

        }

}

struct node{

    double g; int v;

    node() {}

    node(double x,int y):g(x),v(y){}

    bool operator < (const node & A) const

        {

            return g+dis[v]>A.g+dis[A.v];

        }

};

inline void Astar()

{

    priority_queue<node>Q;

    Q.push(node(0.0,S));

    while(po> && !Q.empty())

        {

            node cur=Q.top(); Q.pop();

            for(int i=head[cur.v]; i; i=edge[i].next)

                {

                    node A; A.g=edge[i].power+cur.g; A.v=edge[i].to;

                    Q.push(A);

                }

            if (cur.v==T)

                {

                    po-=cur.g; if (po<) return; ans++;

                }

        }

}

int main()

{

    n=read(); m=read(); scanf("%lf",&po);

    for (int i=; i<=m; i++)

        {

            int u=read(),v=read(); double p;

            scanf("%lf",&p); add(u,v,p);

        }

    S=; T=n;

    spfa();

    Astar();

    printf("%d\n",ans);

    return ;

}

魔法猪学院

相关文章