拼多多笔试，4*100，题解攒人品

A

模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
int a[10][10];
int chk()
{
    if(a[1][2])
    {
        if(a[1][4]) return 7;
        return 5;
    }
    int c=0;
    for(int i=0;i<10;++i)
        c+=a[7][i];
    if(c==6) return 2;
    if(c==2) return 4;
    c=0;
    for(int i=0;i<10;++i)
        c+=a[i][2];
    if(!c) return 1;
    if(c==4) return 8;
    if(c==2)
    {
        if(a[3][2]) return 9;
        return 3;
    }
    if(a[4][4]) return 6;
    return 0;
}
int main()
{
    int QAQ;cin>>QAQ;
    while(QAQ--)
    {
        int n;cin>>n;
        int k=n/10;
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                cin>>a[i/k][j/k];
        cout<<chk()<<endl;
    }
}

B

迷宫

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
const int N=25;
char mp[N][N];
int d[N][N];
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int n,m;
bool in(int x,int y){return x<n&&y<m&&x>=0&&y>=0;}
int main()
{
    vector<pii>ans;
    cin>>n>>m;
    typedef array<int,3> ar3;
    ar3 p;
    for(int i=0;i<n;++i)
    {
        cin>>mp[i];
        for(int j=0;j<m;++j)
            if(mp[i][j]=='T')
                p={i,j,0};
    }
    queue<ar3>q;
    int md=1<<30;
    q.push(p);
    memset(d,-1,sizeof(d));
    d[p[0]][p[1]]=0;
    while(!q.empty())
    {
        auto now=q.front();q.pop();
        int x=now[0],y=now[1],dis=now[2];
        if(mp[x][y]=='X')
        {
            if(dis<md)
                md=dis,ans=vector<pii>{{x,y}};
            else if(dis==md)
                ans.push_back({x,y});
        }
        for(int i=0;i<4;++i)
        {
            int nx=x+dx[i],ny=y+dy[i];
            if(in(nx,ny)&&mp[nx][ny]!='1')
            {
                if(d[nx][ny]==-1)
                {
                    d[nx][ny]=dis+1;
                    q.push({nx,ny,dis+1});
                }
            }
        }
    }
    if(ans.empty())
        cout<<0<<endl;
    else
    {
        cout<<md<<endl;
        sort(all(ans));
        for(auto&pp:ans)
            cout<<pp.fi<<' '<<pp.se<<' ';
    }
}

C

n个点的树，点带权，有边相连的两点不能同时被选，要求选k个，求最大权值和，无法取到k个输出-1.

/*
dp[n][k][2]:
    dp[i][j][t]表示以i节点为根的子树下，选择j个点，其中包括i节点(t=1)/不包括i节点(t=0)能取到的最大权值和，以节点1为根做树形背包，max(dp[1][k][0],dp[1][k][1])即为答案。转移参考背包。
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
const int N=1<<14;
const int K=1<<7;
vector<int>G[N];
int a[N],dp[N][K][2],sz[N];
int n,k;
void dfs(int u,int p)
{
    sz[u]=1;
    vector<int>son;
    son.push_back(0);
    for(int&v:G[u])
    {
        if(v==p) continue;
        son.pb(v);
    }
    int z=son.size()-1;
    vector<vector<int>>f(z+1,vector<int>(k+1,-1));    //f[i][j]表示前i个儿子取j个最大权值和，其中只对不选儿子的情况进行背包，因为要用来转移到dp[u][i][1]。
    vector<vector<int>>g(z+1,vector<int>(k+1,-1));    //g[i][j]表示前i个儿子取j个最大权值和，不限制是否选择儿子。
    f[0][0]=g[0][0]=0;
    for(int i=1;i<=z;++i)
    {
        int v=son[i];
        dfs(v,u);
        for(int j=0;j<=sz[v];++j)
            if(~dp[v][j][0])
                for(int o=k;o>=j;--o)
                    if(~f[i-1][o-j])
                        f[i][o]=max(f[i][o],f[i-1][o-j]+dp[v][j][0]);
        for(int j=0;j<=sz[v];++j)
            for(int o=0;o<2;++o)
                if(~dp[v][j][o])
                    for(int l=k;l>=j;--l)
                        if(~g[i-1][l-j])
                            g[i][l]=max(g[i][l],g[i-1][l-j]+dp[v][j][o]);
        sz[u]+=sz[v];
    }
    for(int i=0;i<=k;++i)
        dp[u][i][0]=g[z][i];
    for(int i=1;i<=k;++i)
        if(~f[z][i-1])
        {
            dp[u][i-1][0]=max(f[z][i-1],dp[u][i-1][0]);
            dp[u][i][1]=f[z][i-1]+a[u];
        }
}
int main()
{
    int QAQ;cin>>QAQ;while(QAQ--)
    {
        memset(dp,-1,sizeof(dp));
        cin>>n>>k;
        for(int i=1;i<=n;++i) G[i].clear();
        for(int i=1;i<=n;++i) cin>>a[i];
        for(int i=1,u,v;i<n;++i)
        {
            cin>>u>>v;
            G[u].pb(v);
            G[v].pb(u);
        }
        dfs(1,0);
        cout<<max(dp[1][k][0],dp[1][k][1])<<endl;
    }
}

D

n行m列的道路， $1\leq n\leq10^9,1\leq m\leq 5$ ，有两种规格的瓷砖分别是 $1\times1$ 和 $2\times2$ ，问多少种方案铺满道路，答案对 $10^9+7$ 取模。

本质上是求有多少种放 $2\times2$ 的方案，因为只要放完 $2\times2$ ，剩下的全放 $1\times1$ 就行。注意到 $m$ 很小，可以对 $m$ 状态压缩，用一个数字 $x$ 表示当前状态，如果 $x$ 的二进制表示 $x_{(2)}$ 第 $i$ 位为1，那么该状态的第 $i$ 个位置有瓷砖。

例如 $15_{(2)}=1111$ ，那么当前行全部铺满了，要注意有些状态不合法，比如 $13_{(2)}=1101,9_{(2)}=1001$ ，原因是现在只铺 $2\times2$ 的瓷砖，那么 $1$ 的个数必须为偶数，且要能划分为若干个连续的 $11$ ，下面用 $legal_i\in\{0,1\}$ 表示状态 $i$ 是否合法，可以简单预处理出来。

然后用 $dp$ 来解决这个问题。显然，如果 $n=1\ or\ m=1$ ，那只有一种方案，因为放不下 $2\times2$ ，否则我们用 $dp[i][j]$ 来表示在第 $i$ 行，且第 $i$ 行状态为 $j$ 的方案数。从第二行开始。转移方程如下( $S$ 为所有合法状态集合)。 $dp[i][j]=\begin{cases}legal_j&i=2\\\sum_{k\in S\ and\ (j\&k)=0} dp[i-1][k] &i>2\end{cases}\\ans=\sum_{i\in S}dp[n][i]$
每行状态个数最多为 $2^m$ ，有 $n$ 行，转移复杂度为 $2^m$ ，总复杂度为 $O(n*2^{2m})$ 显然爆炸。考虑优化。

观察转移方程，可以发现是个递推，我们可以预处理出一个 $2^m\times 2^m$ 的 $01$ 矩阵 $A$ ，其中 $A[i][j]=legal_i \&\& legal_j\&\&(i\&j=0)$
那么，把 $dp_i$ 看作一个 $2^m\times1$ 的矩阵，显然有 $A\times dp_i=dp_{i+1}\\ ((A^{n-1})[0])^T=dp_n$
最后 $dp_n$ 所有元素求和即为答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
const int M=5;
const int K=1<<M;
const int mod=1000000007;
bool o[K];            //legal[K]
bool ok(int x)        //检查状态x是否合法
{
    int c=__builtin_popcount(x);
    if(c&1) return 0;
    for(int i=0;i<M;++i)
    {
        if(!((x>>i)&1)) continue;
        if(i==M-1) return 0;
        if(!((x>>(i+1))&1)) return 0;
        ++i;
    }
    return 1;
}
bool ok(int x,int y)    //判断y是否能从x转移过来。
{
    if(!o[x]||!o[y]) return 0;
    return (x&y)==0;
}
string s(int x){string ret;if(!x) return "0";while(x)ret+='0'|(x&1),x>>=1;return ret;}                    //调试输出用。
void add(int &x,int y){x+=y;if(x>=mod) x-=mod;}
int mul(const int&x,const int&y){return 1LL*x*y%mod;}
struct Mat
{
    int n;
    int a[K][K];
    Mat(){for(int i=0;i<K;++i)a[i][i]=1;}
    Mat(int z)
    {
        memset(a,0,sizeof(a));
        if(z==0) return;
        n=z;
        for(int i=0;i<n;++i)    //初始化为单位矩阵
            a[i][i]=1;
    }
    Mat operator*(Mat w)    //矩阵乘法
    {
        Mat ret(0);
        ret.n=n;
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                for(int k=0;k<n;++k)
                    add(ret.a[i][j],mul(a[i][k],w.a[k][j]));
        return ret;
    }
    void output()
    {
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                cout<<a[i][j]<<" \n"[j==n-1];
        cout<<endl;
    }
};
Mat qp(Mat A,int b,int n)    //矩阵快速幂。
{
    Mat ret(n);
    for(;b;b>>=1,A=A*A)
        if(b&1) ret=ret*A;
    return ret;
}
int main()
{
    int n,m;cin>>n>>m;
    if(min(n,m)==1) return cout<<1<<endl,0;
    for(int i=0;i<K;++i)
        o[i]=ok(i);
    int k=1<<m;
    Mat A(k);
    for(int i=0;i<k;++i)
        for(int j=0;j<k;++j)
            A.a[i][j]=ok(i,j);        //矩阵A初始化
    A=qp(A,n-1,k);                    //A=A^(n-1)
    int ans=0;
    for(int i=0;i<k;++i)
        add(ans,A.a[i][0]);            //A第一行/第一列的和即为答案
    cout<<ans<<endl;
}

#拼多多##笔试题目##题解#