• 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 ] [l_1, r_1] , [l_2, r_2] [l1,r1],[l2,r2],各从中任选一个数a和b,求a^b的期望值
    • 思路:等概率,需要求出任意两个数异或值之和。按位考虑对答案的贡献,所以需要求出 [ l 1 , r 1 ] [l_1,r_1] [l1,r1] [ l 2 , r 2 ] [l_2,r_2] [l2,r2]区间第p位上为1的数的个数,分别记为p1(q1= r 1 l 1 + 1 p 1 r_1-l_1+1-p1 r1l1+1p1)和p2(同理q2),那么p这位的贡献就为 ( p 1 q 2 + q 1 p 2 ) 2 p (p1q2+q1p2)*2^p (p1q2+q1p2)2p。可以用数位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;
}