A.u

只涉及到区间修改可以考虑差分，然而如果每一行都差分复杂度还是过高。我们发现差分标记也是连续的(一行横着的一行斜着的)，所以可以维护两个差分的差分，扫两遍统计即可。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

typedef long long ll;

const int N=2005;

int read()

{

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

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

int n,q;

ll dif1[N][N],dif2[N][N];

int main()

{

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

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

    n=read();q=read();

    while(q--)

    {

        int r=read(),c=read(),l=read(),val=read();

        dif1[r][c]+=val;dif1[r+l][c]-=val;

        dif2[r][c+1]-=val;dif2[r+l][c+l+1]+=val;

    }

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

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

            dif2[i][j]+=dif2[i-1][j-1],dif1[i][j]+=dif1[i-1][j];

    ll ans=0;

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

    {

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

            dif1[i][j]+=dif1[i][j-1]+dif2[i][j],ans^=dif1[i][j];

    }

    cout<<ans<<endl;

    return 0;

}

B.v

二进制状压一下当前场上剩余球的状态，记搜即可。记忆化状态需要手写Hash表，直接map会T飞。

另外，在本题中形如00110和0110的状态是不同的，为了区分我们可以给Hash表多加一个长度的参数，每次查询或插入时先调到相应的长度再操作。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int H=2e7+5;

struct hash_map

{

    int head[19260820],nxt[H],to[H],tot;

    short L[H],len;

    double val[H];

    double &operator [] (int key)

    {

        int x=1LL*key*len%19260817;

        for(int i=head[x];i;i=nxt[i])

            if(to[i]==key&&L[i]==len)return val[i];

        nxt[++tot]=head[x];

        head[x]=tot;

        to[tot]=key;

        L[tot]=len;

        return val[tot]=-1;

    }

}h;

const int N=35;

int n,K;

char s[N];

int erase(int st,int pos)

{

    return st>>pos<<pos-1|st&(1<<pos-1)-1;

}

double dfs(int pos,int st)

{

    if(n-K==pos)return 0;

    h.len=pos;int sst=st;

    if(h[st]>=0)return h[st];

    h[st]=0;

    int rez[N];

    for(int i=1;i<=pos;i++,sst>>=1)

        rez[i]=sst&1;

    for(int i=1;i<=(pos>>1);i++)

    {

        int j=pos-i+1;

        int s1=erase(st,j),s2=erase(st,i);

        double res1=dfs(pos-1,s1)+rez[j],res2=dfs(pos-1,s2)+rez[i];

        h.len=pos;h[st]+=2.0/pos*max(res1,res2);

    }

    if(pos&1)

    {

        int i=(pos>>1)+1,s1=erase(st,pos-i+1);

        double res=dfs(pos-1,s1)+rez[i];

        h.len=pos;h[st]+=1.0/pos*res;

    }

    return h[st];

}

int main()

{

    scanf("%d%d%s",&n,&K,s+1);

    int now=0;

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

    {

        now<<=1;

        if(s[i]=='W')now|=1;

    }

    printf("%.7lf\n",dfs(n,now));

    return 0;

}

C.w

神仙dp。如果把反转一条路径看作增加这样的一条路径，那么最终增加的路径数就等于奇点个数/2。

(由于这道题太神了所以我还是咕掉好了)

#include<cstdio>

#include<iostream>

#include<cstring>

#define pa pair<int,int>

using namespace std;

int read()

{

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

    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

    return x*f;

}

const int N=1e5+5,inf=0x3f3f3f3f;

int n;

int to[N<<1],head[N],nxt[N<<1],w[N<<1],tot;

pa dp[N][2];

pa pls(pa x,pa y)

{

    return make_pair(x.first+y.first,x.second+y.second);

}

void add(int x,int y,int z)

{

    to[++tot]=y;

    nxt[tot]=head[x];

    head[x]=tot;

    w[tot]=z;

}

void dfs(int x,int f,int e)

{

    pa a=make_pair(0,0),b=make_pair(inf,inf),c,d;

    for(int i=head[x];i;i=nxt[i])

    {

        int y=to[i];

        if(y==f)continue;

        dfs(y,x,w[i]);

        c=min(pls(a,dp[y][0]),pls(b,dp[y][1]));

        d=min(pls(a,dp[y][1]),pls(b,dp[y][0]));

        a=c;b=d;

    }

    if(e==1)dp[x][0]=make_pair(inf,inf);

    else dp[x][0]=min(a,make_pair(b.first+1,b.second));

    if(e==0)dp[x][1]=make_pair(inf,inf);

    else dp[x][1]=min(make_pair(a.first+1,a.second+1),make_pair(b.first,b.second+1));

}

int main()

{

    n=read();

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

    {

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

        if(aim==2)z=aim;

        else z=col^aim;

        add(x,y,z);add(y,x,z);

    }

    dfs(1,1,0);

    cout<<(dp[1][0].first>>1)<<' '<<dp[1][0].second<<endl;

    return 0;

}

巴特西

[CSP-S模拟测试53]题解

A.u

B.v

C.w

最新文章

热门文章