蚂蚁笔试研发编程题20220404

1. 正直者、欺诈者

简单模拟即可.

#include <iostream>
#include <string>
using namespace std;

int main() {
   int n;
   string s;
   cin >> n >> s;
   int q;
   cin >> q;
    
   int x, y;
   while(q--){
       cin >> x >> y;
       x = x-1, y = y-1;
       if(s[x] == 'H'){
           cout << (s[y] == 'H' ? "honester" : "liar");
       } else {
           cout << (s[y] == 'L' ? "honester" : "liar");
       }
       cout << endl;
   }

   return 0;
}

2. 子树问题

后序遍历判断所有子树是否均为红色，并且判断当前节点是否为红色，递归返回。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int ans = 0;  
bool dfs(int u, int fa, const vector<vector<int>> &edges, const string& s){
   bool flag = true;  //当前节点的所有孩子节点是否均为红色。
   for (auto v : edges[u]) {
       if (v == fa) continue;
       flag &= dfs(v, u, edges, s);
   }
   if(flag && s[u-1] == 'R') {
       ans++;
       return true;
   }
   return false;
}

//Q2
int main(){
   int n;
   cin >> n;
   string s;
   cin >> s;
   vector<vector<int>> edges(n+1, vector<int>());
   int u, v;
   for (int i = 0; i < n-1; ++i) {
       cin >> u >> v;
       edges[u].push_back(v);
       edges[v].push_back(u);
   }

   dfs(1, 0, edges, s);
   cout << ans << endl;

   return 0;
}

3. k-好数

笔试过程中没有写出来，只通过了暴力的25%。这里给出后面想的思路，不清楚是否能A掉，可能有些地方讲不明白，见谅。

题目中k-好数可以转换为如下定义：对于任意的十进制数x，其对应的k进制数中是否只有0和1两种数字，即：

$(x)_{10} = (a_{n}a_{n-1}...a_{0})_k, \forall{a_i} \in \{0,1\}$

反向转换为十进制数：

$(a_{n}a_{n-1}...a_{0})_k = a_n * k^n + a_{n-1} * k^{n-1} + ... + a_0 * k^0$

可以看出题目要求与上述定义的等价性。

因此需要一个进制转换的函数：

//将x转换为k进制数，数组下标从小到大依次对应低位到高位的进制数a_i
//typedef long long ll
vector<ll> kPresent(ll x, ll k){
    vector<ll> ans;
    while(x >= k){
        ans.push_back(x % k);
        x/=k;
    }
    if (x != 0)
        ans.push_back(x);

    return ans;
}

但是如何找到[l,r]中满足条件的数，并得到个数？

最简单的方法就是暴力，对于[l,r]中所有的数进行进制转换并判断，但这样超时了。

当时想到的方法是：首先找到区间中第一个满足条件的数x，以及最后一个满足条件的数y，并得到他们对应的k进制表示：

$x = (a_{n}a_{n-1}...a_{0})_k, y = (b_{m}b_{m-1}...b_{0})_k$ ,显然 $m \geq n$

因为 $a_i,b_j$ 均只有0和1，因此可以把这个k进制表示看做2进制表示，那么其他满足条件的数的k进制表示就在这两个 $(a_{n}a_{n-1}...a_{0})_2, (b_{m}b_{m-1}...b_{0})_2$ 二进制表示之间。那么一共就有 $(a_{n}a_{n-1}...a_{0})_2-(b_{m}b_{m-1}...b_{0})_2 + 1$ 个数满足条件

有点说不明白，举个例子，就用测试用例来说,[15,21] 第一个满足条件的数是16，其4进制表示为：(100)4 最后一个满足条件的数是21，其4进制表示为：(111)4 那么其他满足条件的数的4进制表示就还剩下：(101)4，(110)4。加起来一共4个数，即：(111)2 - (100)2 + 1 = 7 - 4 + 1 = 4个

笔试中利用循环去查找第一个数和最后一个数，导致超时了。以下是后面想到的在O(1)时间内找到满足条件的第一个数和最后一个数的方法：

找到第一个满足条件的数：

计算l的k进制表示，要找到第一个大于等于l且k进制表示只有0和1的数
从k进制表示的高位往低位进行判断，找到第一个大于1的位置idx
将比idx位数低的所有数置为0
从下标idx开始往高位进位，并置0，直到遇到第一个0，将其置为1。
此时得到的二进制表示就是大于等于l的且第一个满足条件的k-好数

找到最后一个满足条件的数：

计算r的k进制表示，要找到第一个小于等于r且k进制表示只有0和1的数
从k进制表示的高位往低位进行判断，找到第一个大于1的位置idx
将下标idx以及低位所有数置为1，得到的数就是最后一个满足条件的k-好数

然后通过上面的方法做一次减法即可，代码如下：

#include <iostream>
#include <vector>
#include <string>
typedef long long ll;
using namespace std;

vector<ll> kPresent(ll x, ll k){
    vector<ll> ans;
    while(x >= k){
        ans.push_back(x % k);
        x/=k;
    }
    if (x != 0)
        ans.push_back(x);

    return ans;
}

int main(){
    int q;
    cin >> q;
    while(q--){
        ll l, r, k;
        cin >> l >> r >> k;

        //怎么快速找到第一个数
        //先得到l和r的k进制表示，均是从低位到高位
        auto v1 = kPresent(l, k);
        auto v2 = kPresent(r, k);

        //找到第一个大于等于l的且k进制中只有0、1的数
        //直接对原数组操作
        auto upper = [](vector<ll> &v) -> void {
            int n = v.size();
            //从高位开始找，找到第一个大于1的数字，然后置0，并将下一位+1，以此重复,直到遇到0
            int idx = -1;  //最高位不满足条件的下标
            for (int i = n-1; i >=0 ; --i) {
                if(v[i] > 1) {
                    idx = i;
                    break;
                }
            }

            if(idx == -1) return;  //本身满足条件

            //高位存在一个非1的值，将低位全部置为0
            for (int i = 0; i < idx; ++i) {
                v[i] = 0;
            }

            //将高位进位
            int carry = 0;
            for (int i = idx; i < n; ++i) {
                if (v[i] + carry > 1) {
                    v[i] = 0;
                    carry = 1;
                } else if (v[i] + carry == 1){
                    v[i] = 1;
                    carry = 0;
                }
            }
            if (carry == 1) {
                v.push_back(1);
            }
        };

        //找到第一个小于等与r的且k进制中只有0、1的数
        auto lower = [](vector<ll> &v) -> void {
            int n = v.size();
            int idx = -1;  //最高位不满足条件的下标
            for (int i = n-1; i >=0 ; --i) {
                if(v[i] > 1) {
                    idx = i;
                    break;
                }
            }
            if(idx == -1) return;  //本身满足条件

            //令v[idx] = 1,并将低位全部置1即可
            for (int i = 0; i <= idx; ++i) {
                v[i] = 1;
            }
        };
        upper(v1);
        lower(v2);

        auto func = [](const vector<ll>& v)->ll{
            ll i=1;
            ll ans = 0;
            for(auto c : v){
                ans += c * i;
                i *= 2;
            }
            return ans;
        };
        //转换为十进制做减法
        cout << func(v2) - func(v1) + 1 << endl;
    }

    return 0;
}

#我的实习求职记录#