【2020牛客寒假基础算法训练营】第三场总结

A 签到
- 题意：迷宫遇到D只能向下，遇到R只能向右，遇到B既可以向下也可以向右，问从左上走到右下有多少种方案。
- 思路：dp或者记忆化dfs
B 构造
- 题意：A的逆过程，即知道方案数，构造这样一个迷宫
- 思路：若以方案数为20为例
  
  根据上面的构造过程可以从二进制考虑，先将1,2,4,8,16等构造出来，最后一列填D还是B取决于该位上是0还是1，是1则填B，否则填D。所以1e9+7以内的数肯定能由此方法构造出来，注意特判方法数是0的情况。
- ac代码：

#include <bits/stdc++.h>
using namespace std;
char s[50][50];
int main()
{
    int x, n;
    scanf("%d", &x);
    if(!x) x = 1e9+7;
    for(int i = 0; i <= 40; i++)
        if((1<<i)>x) { n=i; break; }
    printf("%d %d\n", n, n+1);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            s[i][j] = 'B';
    for(int i = 0; i < n; i++) s[i][n] = 'D';
    for(int i = 1; i < n-1; i++)
        for(int j = 0; j < n-(i+1); j++)
            s[i][j] = 'D';
    for(int i = 0; i < n; i++)
        if((x>>i)&1) s[i][n-1] = 'B';
        else s[i][n-1] = 'D';
    for(int i = 0; i < n; i++) printf("%s\n", s[i]);
    return 0;
}

C 签到
D 签到
E 数位dp或者找规律
- 题意：给定t组 $[l_{1}, r_{1}], [l_{2}, r_{2}]$ ，各从中任选一个数a和b，求a^b的期望值
- 思路：等概率，需要求出任意两个数异或值之和。按位考虑对答案的贡献，所以需要求出 $[l_{1}, r_{1}]$ 和 $[l_{2}, r_{2}]$ 区间第p位上为1的数的个数，分别记为p1(q1= $r_{1} - l_{1} + 1 - p 1$ )和p2(同理q2)，那么p这位的贡献就为 $(p 1 q 2 + q 1 p 2) * 2^{p}$ 。可以用数位dp或者找规律来求。
- ac代码：

//找规律
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 70;
const ll mod = 1e9+7;
int t;
ll l1, r1, l2, r2;
ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b&1) ans = (ans%mod*(a%mod))%mod;
        a = (a%mod*(a%mod))%mod;
        b >>= 1;
    }
    return ans%mod;
}
ll solve(ll x, ll y)//1<<p
{
    ll ans = 0;
    if(x&y)
    {
        ans = x%y+1;
        x -= (y+x%y);
    }
    else x -= x%y;
    ans += x/(y*2)*y;
    return ans;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld %lld %lld %lld", &l1, &r1, &l2, &r2);
        ll di = (r2-l2+1)%mod * ((r1-l1+1)%mod)%mod;
        ll sum = 0;
        for(int i = 0; (1ll<<i)<=max(r2, r1); i++)
        {
            ll cnt11 = solve(r1, 1ll<<i)-solve(l1-1, 1ll<<i);
            ll cnt21 = solve(r2, 1ll<<i)-solve(l2-1, 1ll<<i);
            ll cnt10 = r1-l1+1-cnt11, cnt20 = r2-l2+1-cnt21;
            ll cnt = (cnt11%mod*(cnt20%mod)%mod + cnt10%mod*(cnt21%mod)%mod)%mod;
            sum = (sum%mod + cnt%mod*((1ll<<i)%mod)%mod)%mod;
        }
        ll ans = (sum%mod*((qpow(di, mod-2))%mod))%mod;
        printf("%lld\n", ans);
    }
    return 0;
}
/* p43210 00000 0 00001 1 00010 2 00011 3 00100 4 00101 5 00110 6 00111 7 01000 8 01001 9 01010 10 01011 11 01100 12 01101 13 01110 14 01111 15 10000 16 10001 17 10010 18 10011 19 10100 20 10101 21 */
//数位dp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 70;
const ll mod = 1e9+7;
int t;
ll l1, r1, l2, r2;
ll a[maxn], dp[maxn][3];
ll qpow(ll a, ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b&1) ans = (ans%mod*(a%mod))%mod;
        a = (a%mod*(a%mod))%mod;
        b >>= 1;
    }
    return ans%mod;
}
//统计多少个在该位上为1的
ll dfs(ll x, int pos, int p, bool limit)
{
    if(pos==0) return 0;
    if(!limit && dp[pos][limit]!=-1) return dp[pos][limit];
    int up = limit?a[pos]:1;
    ll sum = 0;
    for(int i = 0; i <= up; i++)
    {
        if(pos==p && i==1) sum += limit ? (x%(1ll<<(p-1))+1) : (1ll<<(p-1));
        else if(pos>p)sum += dfs(x, pos-1, p, limit&&i==a[pos]);
    }
    if(!limit) dp[pos][limit] = sum;
    return sum;
}
ll cal(ll x, int p)
{
    if((1ll<<(p-1))>x) return 0;
    int pos = 0;
    ll xx = x;
    while(x) a[++pos]=x%2, x/=2;
    memset(dp, -1, sizeof dp);
    return dfs(xx, pos, p, true);
}
/* * 统计多少个在该位上有多少个不为0的 ll dfs(int pos, int p, bool limit) { if(pos==0) return 1; if(!limit && dp[pos][limit]!=-1) return dp[pos][limit]; int up = limit?a[pos]:1; ll sum = 0; for(int i = 0; i <= up; i++) { if(pos==p && i==0) continue; sum += dfs(pos-1, p, limit&&i==a[pos]); } if(!limit) dp[pos][limit] = sum; return sum; } ll cal(ll x, int p) { if((1ll<<(p-1))>x) return 0; int pos = 0; ll xx = x; while(x) a[++pos]=x%2, x/=2; memset(dp, -1, sizeof dp); return dfs( pos, p, true); } */
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld %lld %lld %lld", &l1, &r1, &l2, &r2);
        ll di = ((r2-l2+1)%mod * ((r1-l1+1)%mod))%mod;
        ll sum = 0;
        for(int i = 1; i <=  64; i++)
        {
            ll cnt11 = cal(r1, i)-cal(l1-1, i), cnt21 = cal(r2, i)-cal(l2-1, i);
            ll cnt10 = r1-l1+1-cnt11, cnt20 = r2-l2+1-cnt21;
            ll cnt = ((cnt11%mod*(cnt20%mod))%mod + (cnt10%mod*(cnt21%mod))%mod)%mod;
            sum = (sum%mod + (cnt%mod*((1ll<<(i-1))%mod))%mod)%mod;
        }
        ll ans = (sum%mod*((qpow(di, mod-2))%mod))%mod;
        printf("%lld\n", ans);
    }
    return 0;
}

F 签到前后缀和
G F的进阶版线段树
H 签到
I 递推
- 题意：求汉诺塔将n个盘子从A移到C的过程中A->B,B->C…A->C的次数
- 思路：根据汉诺塔的递推式：f[n]=2f[n-1]+1，相当于把前n-1个盘子从A->B，再将第n个盘子从A->C，再将n-1个盘子从B->C，所以当每种移动的次数也可以根据此递推出来。
J dp
- 题意：
- 思路：将宝可梦的按照出现时间排序，floyd求出任意两点之间的最短路。遍历宝可梦的所有出现，dp[i]表示最终结束时停在第i个宝可梦出现的位置时，能够收获的最大战斗力之和，看之前可以到达哪些已经出现过的宝可梦，注意数组的初始化，因为不能从一个不可达的状态/点去更新答案。因为给定的点数最大为200个，所以超过200步可以从1个点到达图中的任意一点，根据此可知最多向前查找200次即可。
- ac代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const ll mod = 1e9+7;
int n, m, k, u, v;
int d[210][210];
ll dp[maxn];
struct node{
    ll t, p, val;
    friend bool operator < (node a, node b)
    {
        return a.t < b.t;
    }
}a[maxn];
void floyd()
{
    for(int i = 1; i <= n; i++) d[i][i] = 0;
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    memset(d, 0x3f, sizeof d);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d %d", &u, &v);
        d[u][v] = d[v][u] = 1;
    }
    scanf("%d", &k);
    for(int i = 1; i <= k; i++) scanf("%lld %lld %lld", &a[i].t, &a[i].p, &a[i].val);
    sort(a+1, a+1+k);
    a[0].t=0, a[0].p=1, a[0].val=0;
    floyd();
    ll ans = 0;
    for(int i = 1; i <= k; i++)
    {
        dp[i] = LLONG_MIN;
        for(int j = 1; j <= min(200, i); j++)
        {
            //printf("(%lld %d)", a[i].t-a[i-j].t, d[a[i].p][a[i-j].p]);
            if((a[i].t-a[i-j].t) >= (d[a[i].p][a[i-j].p]))
                dp[i] = max(dp[i], dp[i-j]+a[i].val);
            ans = max(ans, dp[i]);
        }
    }
    printf("%lld\n", ans);
    return 0;
}