2022-09-03-挂京东-C++笔试

终于碰到一次没做出来的了

20*2' one chioce

34min

1. which wrong
   a. 四次挥手断开连接，可以确保A发送的最后一个确认报文达到B
   b. TCP 三次握手中可发生SYN攻击
   c. 用三次挥手断开连接可能会出现已经失效的连接请求报文段

a？

2. 32 16 8 20 40 是中序顺序，把这个小根堆转化为大根堆需要 4 次元素交换？

3. 把 10 转化为 1，每次转化要么花3元把数n变成 ，要么花1元把数n减一，最少花 7 元？
   和第二个编程相似

4. n个数的环形拓扑有n条物理链路，m个数的星形拓扑有 m-1 条物理链路？

5. /boot /local /root /proc 中只有最后一个不占磁盘？

6. 0? 1? 编译失败？运行失败？

   enum class t{
   A=0,
   B,
   C
   };
   int main(){
   int a=t::C;
   cout<<a<<endl;
   return 0;
   }

编译失败，把class去掉。

7. 长为10的顺序表中插入一个节点平均移动5次，长13的顺序表中删除一个节点平均移动6次

8. table(user_id, book_name)，统计每个人借了哪些书，书名用 “ | ”分开，前后有空格，最后按id升序输出，sql为？

• A. select id group_concat(books_name order by id separator " | ") As total_books from reading group by id
• B. select id group_concat(books_name separator " | ") As total_books from reading group by id order by id
• C. select id group_concat(books_name separator "|") As total_books from reading group by id order by id
• D. select id group_concat(books_name order by id separator "|") As total_books from reading group by id

9. select * from stu where name in ( select name from stu where name is not null group by name having count(*)>1 )

10. output:

    class test{
    static int x;
    public: 
    test(){x++;}
    static int getx(){return x;}
    };
    int test::x=0;
    int main(){
    cout<<test::getx()<<"\n";
    test t[5];
    cout<<test::getx()<<"\n";
    return 0;
    }

    0 5

coding

// 4min 100%*15
#include<iostream>
using namespace std;

int main(){
    int n,q;
    cin>>n;
    int big=0,tn=0,nn=n;
    while(nn--){
        cin>>q;
        if(big<q){
            big=q;
            tn=1;
        }else if(big==q)
            tn++;
    }
    cout<<n-tn;
    return 0;
}

// 100%*20' 9min
// 小红的元素分裂
// 从数组里选择一个元素x
// x分裂为1和x-1
// x分裂为a和b，a*b=x
// 最少次数使所有数组元素变成1

// 2
// 2 6

// 输出5
// 116
// 1123
// 11113
// 111121
// 111111

// 1<=n,ai<=1e5

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;

int main(){
    int n,q;
    cin>>n;
    vector<int> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    int big=*max_element(a.begin(),a.end());
    vector<int> d(big+1,0);
    d[2]=1;
    for(int i=3;i<=big;i++){
        d[i]=d[i-1];
        for(int x=2;x<=sqrt(i);x++){
            if(i%x==0)
                d[i]=min(d[i],d[i/x]+d[x]);
        }
        d[i]+=1;
    }
    int ans=0;
    for(int i=0;i<n;i++){
        ans+=d[a[i]];
    }
    cout<<ans;
    return 0;
}

// 第三题 -19.5
// https://www.nowcoder.com/discuss/1039184
// 22.2%*25'
// 一个括号串权值为其最长合法括号子序列的长度
// （））（））权值为4，最长合法子序列为（）（）
// 求一个给定括号串的所有子串权值之和
// length<=2e5
// 输入（））（））输出26
// 26=2*9+4*2

// 13min：子串必须连续
#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

// 22.2%
// vector<unordered_map<int,int>> ca;
// int n;
// long ans=0;
// unordered_map<int,int> dfs(const string& s, int i){
// //     if(i==n)return {};
// //     if(ca[i].size()>0){
// //         return ca[i];
// //     }
//     unordered_map<int,int> a;
//     int lc=0,np=0,ii=i;
//     while(i<n){
//         if(s[i]=='('){
//             lc++;
//         }else{
//             lc--;
//             if(lc>=0){
//                 np+=2;
//             }else lc=0;
//         }
//         if(np>0){
//             a[np]++;
// //             cout<<"ii= "<<ii<<", i= "<<i<<", np= "<<np<<", a[np]= "<<a[np]<<"\n";
//         }
//         i++;
// //         unordered_map<int,int> um=dfs(s,i);
// //         if(np==0){
// //             a=um;
// //         }
// //         else{
// //             for(auto& [k,v]:um){
// //                 a[k+np]+=v;
// //                 cout<<"ii= "<<ii<<", i= "<<i<<", np= "<<np<<", k+np= "<<k+np<<", a[k+np]= "<<a[k+np]<<"\n";
// //             }        
// //         }
//     }
//     ca[ii]=a;
//     return a;
// }
// int main(){
//     string s;cin>>s;
//     n=s.length();
//     ca.resize(n);
//     for(int i=0;i<n-1;i++)
//         dfs(s,i);
//     for(auto& um:ca){
//         for(auto&[k,v]:um){
//             ans+=k*v;
//         }
//     }
//     cout<<ans;
//     return 0;
// }


int main(){
    string s;cin>>s;
    int n=s.length();
    long ans=0;
    for(int i=0;i<n-1;i++)
    {
        unordered_map<int,int> a;
        int lc=0,np=0,ii=i;
        while(ii<n){
            if(s[ii]=='('){
                lc++;
            }else{
                lc--;
                if(lc>=0){
                    np+=2;
                }else lc=0;
            }
            ans+=np;
            ii++;
        }
    }
    cout<<ans;
    return 0;
}