【9.20腾讯笔试后台/综合】也太简单了吧（附个人ac做法）

先说坑点，第一题一开始交过90%，然后后面同样代码再交就100%。第三题居然卡常，真辣鸡，当然可能是做法不对。

题目都挺简单的，没有难度（如果第三题真的是我想的那样做的话）。

个人做法已补，欢迎讨论，求大佬轻喷。

题目和个人做法

第一题：

题意：已知合法的电话号码是11位的且第一位一定是8，现给定一个只含数字的字符串，问是否能删除若干个字符使得这个字符串成为一个合法的电话号码

个人做法：只用判断0到倒数第11位是否有8出现就好，有的话就把这个8前面的都删掉，8后面的删剩11位就好。

第二题：

题意：现在领导有m（m为偶数）个人，每两个人一起共同完成一个任务，完成任务的时间为两个人的时间权值之和，现在给出n行数据，每行数据有两个值x和y，代表有x个人的时间权值为y，求所有任务最快在什么时候都完成。

个人做法：按照时间权值从小到大排序，然后双指针从两边往中间扫即可。最优的方案一定是时间权值最小的人和时间权值最大的人匹配，次小的和次大的匹配，以此类推。

第三题：

题意：有n个人比赛，每个人都有一个权值，现在要将n个人分成两组，两组间的人数差<=1，问怎么分组可以使得两个组的人的权值和的差最小。

个人做法：题目有个很关键的条件就是所有人的权值和<=1e5，所以可以用类似背包的方法做。

第i个人的权值记为a[i]，令dp[i][j][k]表示只考虑前i个人，用j个人是否能将权值凑成k，如果可以则dp[i][j][k]=1,否则为0，那么转移就是如果dp[i-1][j][k]为1，那么dp[i][j+1][k+a[i]]也为1，否则为0，初始条件dp[0][0][0]=1。

考虑到dp数组空间可能会超，可以使用滚动数组节省空间。楼主这里可能代码写的比较屎，一开始只过了60%，然后到90%，最后才全过。

第四题：

题意：有n个正整数，然后将下述操作进行k次，下述操作包括3步：1.选出n个数中最小的正数x（非0）；2.输出x；3. 将所有>0的数减去x；

个人做法：将n个数排序，然后去重，假设去重之后的数组长度为m，则对于第i次操作（i<=m)，输出a[i]-a[i-1]（这里假设数组下标为1到m，且a[0]=0)，如果i>m则输出0。

第五题：

题意：给出两个长度为n的数组a和b，然后求下面这个东西（语文不好用代码代替2333）（n<=200000)

int sum=0;
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
        sum=sum^(a[i]+b[j]);
    }
}
cout<<sum<<endl;

个人做法：这种求异或的题99%都是按位算贡献，就是判断答案在二进制下的每位是1还是0然后组合起来。然后对于第i位(即2^i)，枚举数组a（设枚举的下标为j），如果a[j]的第i位为0（即(a[j]&(1<<i))==0）那么如果a[j]和某个数x相加能使得这一位变成1，会存在如下两种情况：

1.x这位为0，且a[j]和x两个数低于这位的数(即%(1<<i)之后)相加大于等于(1<<i)，那么就说明这位一定可以从更低位进位变成1；

2. x这位为1，且a[j]和x两个数低于这位的数(即%(1<<i)之后)相加小于(1<<i)，那么这位就不存在进位，然后a[j]+x的第i位就很自然的是1（因为x的第i位是1）。

a[j]的第i位为0是同样的道理。所以这题的做法就是先记录下b数组中第i位为0/1的时候%(1<<i)的值，然后枚举位数i，然后在枚举数组a(枚举下标为j)，然后可以计算出res=(1<<i)-a[j]%(1<<i)，即让a[j]在和x相加在第i位发生进位时，x%(1<<i)的最小值，然后就可以利用lower_bound算出数量，进而统计出对于每个数a[j]，和b数组每个数字相加后能使得第i位是1的数量，然后求个总和，如果是奇数说明答案第i位为1，偶数说明答案第i位为0。

对b数组记录代码如下

vector<int> magic[2][35]; //第一维表示当前位为0还是1，第二维表示存的第几位
for(int i=0;i<=30;i++){
    for(int j=0;j<n;j++){    
        if((b[j]&(1<<i))==0){  //如果b[j]的第i位为0
           magic[0][i].push_back(b[j]%(1<<i));        //存的时候要存%(1<<i)的值
        }
        else{
            magic[1][i].push_back(b[j]%(1<<i));
        }
    }
    //排序是为了二分查找
    sort(magic[0][i].begin(),magic[0][i].end());
    sort(magic[1][i].begin(),magic[1][i].end());
}