2022-09-15-蚂蚁工程研发笔试-61

稍微难一点就败北了，伪大佬

1、5
6、7‘、10

6*2'

1. InnoDB 存储引擎，事务提交commit依赖什么日志机制实现？

      A. redolog undo log
      B. undolog binlog
      C. redo undo bin 三个都要
      D. redo binlog

D？

2. which wrong
   A. 文件、进程可以作为shell命令的参数
   B. 附带选项和参数，二者shell命令一次只能带一个
   C. shell命令可省略参数
   D. 命令选项后面可能带附带参数

B?

3. 打印a.txt的最后10个字符
   A. tail +10 a
   B. tail -c 10 a
   C. tail -n +10 a
   D. tail -n -10 a

3B

4. 长n的数与长m的数相加，用高精度加法，时间复杂度为
   A. O(max(n,m))
   B. O(lg max(n,m))
   C. O(1)
   D. O(nm)

4A

5. which wrong
   A. 并行索引分局部和全局索引，通过全局索引可快速找到任意...
   B. 检索有区分属性k的特性码值k1的元组的查询，可以找到某分区保存码值k1，使用该分区中的局部索引来查找所需元组
   C. 全局索引可以跨多个节点进行分区
   D. 全局索引是建在存储于特定节点中的元组上的索引，建立在给定关系的索引分区上，内容和数据存在同一节点上

5C？

6*4' 少选1/3

6. HTTP 请求报文包括：
   请求行、首部字段、内容实体、状态行

响应报文(状态行、消息报头、响应正文)
ABC

7. 虚拟存储的特征：
   一次性、多次性、离散性、对换性

bcd

8. 无需事先确定好线性表长度就可以编程实现线性表 （错）
   允许线性表的长度有很强的可变性（错）

9. 引入缓冲区
   A. 可以解决CPU与IO设备之间速度不匹配的矛盾
   B. 一定程度上提高CPU、IO之间的并行性
   C. 一定长度上减少CPU中断频率
   D. 可解决基本数据单元大小不匹配的问题

BCD

10. 选对的
    A. Dijkstra 允许负边和负环
    B. Dijkstra 允许负边不允许负环
    C. Floyed 依次算所有点对（i，j）经过的中间节点属于{1},{1,2}...{1,2...,v}的最短路径
    D. Bellman-ford 计算特定点对的时间复杂度是O(VE)

CD？

3编程 64'

// 14‘ 100% 13min
// 离谱！！！不能cout打印string，最后用char数组打印的
#include<iostream>
#include<vector>
#include<string>
#include<string.h>
using namespace std;

int main(){
    int x;cin>>x;
    string s="";
    char c[26];int ci=0;
    memset(c,0,26);
    vector<int> a(26,0);
    a[0]=1;
    for(int i=1;i<26;i++){
        a[i]=2*a[i-1];
    }
    int i=9;
    while(x>0){
//         printf("%d %d x=%d\n",i,a[i],x);
        if(a[i]<=x){
//             s.append(string('a'+i,1));
//             s=s+string('a'+i,1);
                c[ci++]='a'+i;
//             cout<<"add "<<string('a'+i,1)<<"\n";
//             printf("%d %d x=%d, s=%s\n",i,a[i],x,s.c_str());
            x-=a[i];
        }
        i--;
    }
//     cout<<s;
    c[ci]='\0';
    cout<<c;
    return 0;
}



// 20' 13min 70% -6'
// 20' 90% unsigned long long -2'
#include<iostream>
#include<vector>
#include<string>
#include<functional>
using namespace std;
typedef unsigned long long ull;
int main(){
    ull n,a,b;cin>>n;
    ull sumo=0;
    vector<vector<ull>> e(n);
    for(int i=1;i<n;i++){
        cin>>a>>b;
        a--,b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    function<void(ull,ull)> f = [&](ull i, ull fa){
        sumo+=i-fa;
//         cout<<"i= "<<i<<", fa= "<<fa<<", po= "<<po<<endl;
        for(auto j:e[i])
            if(j!=fa)
                f(j,i);
    };
//     cout<<"size o"<<e[0].size()<<"\n";
    for(auto i:e[0])
        f(i,0);
    cout<<sumo;
    return 0;
}



// 30' 20% 16min -24'
#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;

// unsigned long long f(const string& s, int l,int r){
//     if(l==r) return 1;
//     unsigned long long a=0;
//     int mid = (l+r)/2;
//     f(s,l,mid);
//     f(s,mid+1,r);

//     return a;
// }

int main(){
    string s;
    cin>>s;
    int ans=s.length();
    unordered_map<int,unordered_map<int,int>> k;

    int c=0;

    for(int i=0;i<3;i++)
        c=c^(1<<(s[i]-'a'));
    k[0][3]=c;
    if(__builtin_popcount(c)==1)
        ans++;

    for(int i=0;i<s.length()-3;){
        c=c^(1<<(s[i]-'a'))^(1<<(s[i+3]-'a'));
//         k[++i][3]=c;
        i++;
        if(__builtin_popcount(c)==1)
            ans++;
    }

    for(int l=5;l<=s.length();l+=2){
        c=k[0][l-2];
        c=c^(1<<(s[l-2]-'a'))^(1<<(s[l-1]-'a'));
        k[0][l]=c;
        if(__builtin_popcount(c)==1)
            ans++;

        for(int i=0;i<s.length()-l;){
            c=c^(1<<(s[i]-'a'))^(1<<(s[i+l]-'a'));
//             k[++i][l]=c;
            i++;
            if(__builtin_popcount(c)==1)
                ans++;
        }
    }
    cout<<ans;
    return 0;
}