拼多多笔试，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，那么该状态的第
个位置有瓷砖。
例如，那么当前行全部铺满了，要注意有些状态不合法，比如
，原因是现在只铺
的瓷砖，那么
的个数必须为偶数，且要能划分为若干个连续的
，下面用
表示状态
是否合法，可以简单预处理出来。
然后用来解决这个问题。显然，如果
，那只有一种方案，因为放不下
，否则我们用
来表示在第
行，且第
行状态为
的方案数。从第二行开始。转移方程如下(
为所有合法状态集合)。
每行状态个数最多为，有
行，转移复杂度为
，总复杂度为
显然爆炸。考虑优化。
观察转移方程，可以发现是个递推，我们可以预处理出一个的
矩阵
，其中
那么，把看作一个
的矩阵，显然有
最后所有元素求和即为答案。
#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;
} #拼多多##笔试题目##题解#
