2021.3.27 米哈游笔试

不得不说，原本以为没有很难，结果没想到比字节的题还难，不愧是国际大厂 。直接凉凉，心态大蹦。
DP场？前三题全是DP，第四题字符串建树检索，第五题高难图论

一、 给一个纯数字字符串 $S$，让你求必须按"1807"的顺序的最长子序列。（ ∣ S ∣ ≤ 1 0 5 |S| \le 10^5 ∣S∣≤105 ）
比如 “1800077000007”
他可以取子序列 “18000777”（取了中间两个7，则后面的7中间的0就不能取，因为必须要按1807的顺序，但是可以取多个1,8,0,7）
也可以取 “18000000007”
当然，最长的是 “18000000007”，所以答案为11。

思路：
DP4次：
dp1[i]表示前i个字符串最长的"1"的数量
dp2[i]表示前i个字符串最长的"18"的数量
dp3[i]表示前i个字符串最长的"180"的数量
dp4[i]表示前i个字符串最长的"1807"的数量
dp2[i]前必须要出现1，才能dp出最长18的，否则只有8则不行
dp3[i]前必须要出现18，才能dp出最长180的，否则只有0则不行
dp4[i]前必须要出现180，才能dp出最长1807的，否则只有7则不行
所以这个时候，每次DP都需要做一个标记：
vis1[i]=1表示前i个字符串出现过"1"
vis2[i]=1表示前i个字符串出现过"18"
vis3[i]=1表示前i个字符串出现过"180"
循环四次分别按顺序计算出四个dp数组，然后答案为dp4[k.size()-1];
dp公式：

// dp1:
if(k[i]=='1') {dp[0][i]=dp[0][i-1]+1;vis[0][i]=1; //第i位前出现过1
}
else {dp[0][i]=dp[0][i-1];vis[0][i]=vis[0][i-1];
}//dp2:
if(k[i]=='8'&&vis[0][i-1]) { //如果前面一位出现过1dp[1][i]=max(dp[1][i-1]+1,dp[0][i-1]+1); //max(最后一个是8，或者最后多个8)vis[1][i]=1; //第i位前出现过18
}
else {dp[1][i]=dp[1][i-1];vis[1][i]=vis[1][i-1];
}//dp3:
if(k[i]=='0'&&vis[1][i-1]) { //如果前面一位出现过18dp[2][i]=max(dp[2][i-1]+1,dp[1][i-1]+1); //max(最后一个是0，或者最后多个0)vis[2][i]=1; //第i位前出现过180
}
else {dp[2][i]=dp[2][i-1];vis[2][i]=vis[2][i-1];
}//dp4:
if(k[i]=='7'&&vis[2][i-1]) { //如果前面一位出现过180dp[3][i]=max(dp[3][i-1]+1,dp[2][i-1]+1); //max(最后一个是7，或者最后多个7)
}
else {dp[3][i]=dp[3][i-1];vis[3][i]=vis[3][i-1];
}

当时做的时候没有考虑要判断前面是否出现过必须出现1,18,180，就直接dp。。当时感觉思路非常正确，样例都过完了，结束之后问了各位金牌爷他们也没看出来问题。但是就是没有100%，当时心态大蹦

现在突然想到需要加个标记…现在也心态大蹦…

参考代码：

#include 
#define ll long long
#define endl '\n'
#define MP make_pair
using namespace std;const int maxn=1e5+10;int dp[4][maxn];
int vis[3][maxn]; //vis[i][j] 表示前j位出现过{1,8,0}//1800077000007int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);string k;cin>>k;if(k[0]=='1') {dp[0][0]=1;vis[0][0]=1;}for(int i=1;i<k.length();i++) {if(k[i]=='1') {dp[0][i]=dp[0][i-1]+1;vis[0][i]=1; //第i位前出现过1}else {dp[0][i]=dp[0][i-1];vis[0][i]=vis[0][i-1];}}for(int i=1;i<k.length();i++) {if(k[i]=='8'&&vis[0][i-1]) { //如果前面一位出现过1dp[1][i]=max(dp[1][i-1]+1,dp[0][i-1]+1); //max(最后一个是8，或者最后多个8)vis[1][i]=1; //第i位前出现过18}else {dp[1][i]=dp[1][i-1];vis[1][i]=vis[1][i-1];}}for(int i=2;i<k.length();i++) {if(k[i]=='0'&&vis[1][i-1]) { //如果前面一位出现过18dp[2][i]=max(dp[2][i-1]+1,dp[1][i-1]+1); //max(最后一个是0，或者最后多个0)vis[2][i]=1; //第i位前出现过180}else {dp[2][i]=dp[2][i-1];vis[2][i]=vis[2][i-1];}}for(int i=3;i<k.length();i++) {if(k[i]=='7'&&vis[2][i-1]) { //如果前面一位出现过180dp[3][i]=max(dp[3][i-1]+1,dp[2][i-1]+1); //max(最后一个是7，或者最后多个7)}else {dp[3][i]=dp[3][i-1];vis[3][i]=vis[3][i-1];}}if(k.length()<4) cout<<0<<endl;else cout<<dp[3][k.length()-1]<<endl;return 0;
}

二、 有 $n$ 个项目，一开始的时间为 0，完成每个项目所需时间为 1，每个项目 $i$ 有一个截止时间 t i t_i ti​，如果在这个时间之前完成这个项目，则可以获得积分 w i w_i wi​ ，否则扣除积分 w i w_i wi​ 。 （ n ≤ 1 0 5 n \le 10^5 n≤105 ）

思路：
DP

三、 给一个区间 $[L,R]$ ，问在这个区间内的所有数字里，奇数位的和与偶数位的和相等的数有多少个。（ 1 ≤ L ≤ R ≤ 1 0 9 1 \le L \le R \le 10^9 1≤L≤R≤109）
比如 242 ：奇数位的和为 2+2=4 ，偶数位的和为 4，所以满足条件。

思路：
数位DP

四、
给一个字符串 S 表示一颗二叉树，他的格式如下：
$"10(5(4,3),6(,2))"$
$10(5,6)$ 表示节点10的左子树为5，右子树为6。
$6(,2)$ 表示节点6的左子树为空，右子树为2。
如果节点右边没有括号，则表示这个节点为叶子节点。
让你输出这个字符串表示的树的中序遍历。（ ∣ S ∣ ≤ 1 0 5 |S| \le 10^5 ∣S∣≤105 ）

思路：
重点在于解析这个字符串。
对这个字符串进行dfs，

node* dfs(string k,int l,int r) {}

表示返回从字符串从 $l->r$ 的子节点
找到这个节点之后的第一个括号，然后再对这个括号深度的逗号左边进行dfs，对这个括号深度的逗号右边进行dfs，分别绑定到这个节点的左子树和右子树上。
当 $l>r$ 的时候则返回一个空节点。
当 $l==r$ 的时候则返回当前的叶子节点。
对于绑定完左右子树的节点，则返回当前节点。
中序遍历就不用多说，按"左根右"的顺序dfs即可。
具体可以看参考代码。

AC参考代码：

#include 
#define ll long long
#define endl '\n'
#define MP make_pair
using namespace std;const int maxn=1e7+10;int ans[maxn];struct node {string val;node *lef;node *rig;
};//解析字符串
node *dfs(string k,int l,int r) {if(l>r) return nullptr;if(l==r) {node *tmp=new node;tmp->val=k.substr(l,1);tmp->lef=nullptr;tmp->rig=nullptr;return tmp;}int nexl=0,nexr=0,mid=0;int deep=0;for(int i=l;i<r;i++) {if(k[i]=='(') {deep++;if(deep==1) {nexl=i;}} else if(k[i]==')'){deep--;if(deep==0) {nexr=i;}}if(k[i]==','&&deep==1) {mid=i;break;}}node *now=new node;now->val=k.substr(l,nexl-l);now->lef=dfs(k,nexl+1,mid-1);now->rig=dfs(k,mid+1,r-1);return now;
}void middfs(node *root) {if(root==nullptr) return;middfs(root->lef);cout<<root->val<<" ";middfs(root->rig);
}//10(5(4,3),6(,2))int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);string st;cin>>st;node *root=new node;root=dfs(st,0,st.size()-1);middfs(root);cout<<endl;return 0;
}

五、 有一个图，有 $n$ 个节点，图中有两种边，输入 $u,v$表示每种边的数量，以下 $u$ 行每行 $a,b$ 表示 $a与b$ 连接第一种边，以下 $v$ 行每行 $c,d$ 表示 $c与d$ 连接第二种边。 （ 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105 ）
输出每个节点能通过两种边都能到达的点的数量（包括自己）。

例如：

6 4 3
1 4
1 3
1 2
5 6
1 3
3 6
2 6

则建图如下：

1通过两种边都能到达的点有1,2,3
2通过两种边都能到达的点有1,2,3
3通过两种边都能到达的点有1,2,3
4通过两种边都能到达的点有4
5通过两种边都能到达的点有5
6通过两种边都能到达的点有6
所以输出

3 3 3 1 1 1

思路：
不会做，感觉是 CF difficulty 2400 以上的题

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！