CF1245 E. Hyakugoku and Ladders

题目大意

有一个10 \(\times\) 10的网格，你要按这样的路径行走：

网格中有一些单向传送门，每个传送门连接的两个格子在同一列。传送门的方向一定是从下往上的，而且每个格子的出度至多为1，最上面一行的格子没有出去的传送门。
你的行走步骤是这样：
1.抛一枚六面骰子，如果往前走点数步不会走超过终点就往前走点数步，反之站着不动并且跳过第二步；
2.如果这一点有传送门，可以选择进传送门或不进。
在恰好走到终点上之前，你会不断重复以上两步。
求在用最优策略进传送门时，期望重复以上步骤多少次。

题解

设\(f(i,j)\)表示从坐标为\((i,j)\)的格子走到终点期望几次。
按题意模拟。

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#define LL long long
#define D double
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x*f;
}
void write(int x)
{
    char ch[20];int f=0;
    if(!x){putchar('0'),putchar('\n');return;}
    if(x<0)putchar('-'),x=-x;
    while(x)ch[++f]=x%10+'0',x/=10;
    while(f)putchar(ch[f--]);
    putchar('\n');
}
D f[107];
int h[17][17],to[107],px[107],py[107],bac[17][17],cntp;
int main()
{
    dwn(i,10,1)
    {
        if(!(i&1)){rep(j,1,10)cntp++,bac[i][j]=cntp;}
        else {dwn(j,10,1)cntp++,bac[i][j]=cntp;}
    }
    rep(i,1,10)
        rep(j,1,10) 
        {
            h[i][j]=read();int x=i-h[i][j],y=j;
            to[bac[i][j]]=bac[x][y];
        } 
    f[100]=0;
    dwn(i,99,1)
    {
        D tmp=1.0;int li=min(6,100-i);
        if((100-i)<6)tmp=6.0/(100.0-(D)i),f[i]+=(6.0-(D)li)/6.0;
        rep(j,1,li)
        {
            D x=min(f[i+j],f[to[i+j]]);
            f[i]+=(x+1.0)/6.0;
        }
        f[i]*=tmp;
    }
    printf("%.10lf",f[1]);
    return (0-0);
}

CF1245F. Daniel and Spring Cleaning

题目大意

给区间\([l,r]\)，问有多少\(a\in[l,r],b\in[l,r]\)满足\(a\space xor \space b=a+b\)。
\(0\leq l\leq r\leq 10^9\)。

题解

设\(f(x,y)\)表示有多少\(a\in[0,x],b\in[0,y]\)满足\(a\space xor \space b=a+b\)。
答案=\(f(r,r)-2\times f(l-1,r)+f(l-1,l-1)\)。
计算\(f\)可以按二进制位数位dp。

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define LL long long
#define maxn 37
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x*f;
}
void write(LL x)
{
    if(x==0){putchar('0'),putchar('\n');return;}
    int f=0;char ch[20];
    if(x<0)putchar('-'),x=-x;
    while(x)ch[++f]=x%10+'0',x/=10;
    while(f)putchar(ch[f--]);
    putchar('\n');
    return;
}
int t,l,r,a[maxn],b[maxn],len;
LL f[maxn];
LL getf(int i,int yes1,int yes2)
{
    if(i==-1){return 1;}
    if(f[i]!=-1&&yes1&&yes2)return f[i];
    int li1=yes1?1:a[i],li2=yes2?1:b[i];
    LL res=0;
    res=getf(i-1,yes1|a[i],yes2|b[i]);
    if(li1==1)res+=getf(i-1,yes1,yes2|b[i]);
    if(li2==1)res+=getf(i-1,yes1|a[i],yes2);
    if(yes1&&yes2)f[i]=res;
    return res;
}
LL work(int x,int y)
{
    if(x<0||y<0)return 0;
    memset(f,-1,sizeof(f));
    len=0;
    while(((1ll<<(len+1))-1ll)<(LL)x)len++;
    while(((1ll<<(len+1))-1ll)<(LL)y)len++;
    rep(i,0,len)a[i]=(x&(1<<i))?1:0;
    rep(i,0,len)b[i]=(y&(1<<i))?1:0;
    return getf(len,0,0);
}
int main()
{
    t=read();
    while(t--)
    {
        l=read(),r=read();
        write(work(r,r)-2ll*work(r,l-1)+work(l-1,l-1));
    }
    return 0;
}