字节跳动2019春招研发题

第一题， 简单的模拟耗时有点多，似乎也比别人代码复杂。

第二题， 是个数学的题找到规律就ok。

第三题， 是DFS+贪心算法。

第四题， 没时间做了，开始以为是最小生成树的问题，码了模板发现思路错了。

第五题， 不会旅行商问题，得补。

第六题， 签到题。

第七题， 本来以为是二分+检验，小数据能通过测试，不知道为什么大数据就会溢出，所有的int型改为long按理说可以解决问题，暂时没想通，后来找到的规律，化简式子。

总的来说好久没刷题了，速度变慢了，有几道题没想清楚就开始码代码，think twice ,code once。

没做出来的题，后面补。

题目一. 万万没想到之聪明的编辑

 我叫王大锤，是一家出版社的编辑。我负责校对投稿来的英文稿件，这份工作非常烦人，因为每天都要去修正无数的拼写错误。但是，优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径：

1. 三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello
2. 两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello
3. 上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC

我特喵是个天才！我在蓝翔学过挖掘机和程序设计，按照这个原理写了一个自动校对器，工作效率从此起飞。用不了多久，我就会出任CEO，当上董事长，迎娶白富美，走上人生巅峰，想想都有点小激动呢！
……
万万没想到，我被开除了，临走时老板对我说： “做人做事要兢兢业业、勤勤恳恳、本本分分，人要是行，干一行行一行。一行行行行行；要是不行，干一行不行一行，一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……

请听题：请实现大锤的自动校对程序 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 1e5+5;
char que[maxn];
int judge[maxn];
int main(){
    int n;
    string s;
    cin>>n;
    while(n--){
         
        cin>>s;
        int len = s.length();
        for(int i = 0;i<len;++i){
            judge[i]=0;
        }
        int st = 0,ed = 0,size = 0;
         
        for(int i=0;i<len;++i){
             
            que[ed]=s[i];
            ed++;
            size++;
                         
            if(size==5){
 
                que[4] = s[i];
                que[0] = que[1];
                que[1] = que[2];
                que[2] = que[3];
                que[3] = que[4];
                size=4;
                ed--;
            }  
            if(size==3){
                 
                if(que[0]==que[1] && que[1]==que[2]){
                    judge[i] = 1;
                    ed--;
                    size--;
                }              
                 
            }
            if(size==4){
                if(que[1]==que[2] && que[2]==que[3]){
                    judge[i] = 1;
                    ed--;
                    size--;
                }else if(que[0]==que[1] && que[2]==que[3]){
                    judge[i] = 1;
                    ed--;
                    size--;
                }
            }
     
        }
//      for(int i=0;i<len;++i){
//          cout<<judge[i];
//      }
//      cout<<endl;
         
        for(int i=0;i<len;++i){
            if(judge[i]==0){
                cout<<s[i];
            }
        }
        cout<<endl;
    }
    return 0;
}

题目二. 万万没想到之抓捕孔连顺

 我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工，我提议

1. 我们在字节跳动大街的N个建筑中选定3个埋伏地点。
2. 为了相互照应，我们决定相距最远的两名特工间的距离不超过D。

我特喵是个天才! 经过精密的计算，我们从X种可行的埋伏方案中选择了一种。这个方案万无一失，颤抖吧，孔连顺！
……
万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！

请听题：给定N（可选作为埋伏点的建筑物数）、D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。
注意：
1. 两个特工不能埋伏在同一地点
2. 三个特工是等价的：即同样的位置组合(A, B, C) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用 

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e6+5;
int arr[maxn];
long long int c(long long int cnt){
    return (cnt*(cnt-1)/2)%99997867;
}
int main(){
    int n,d;
    int j=0;
    while(cin>>n>>d){
        for(int i=0;i<n;++i){
            cin>>arr[i];
        }  
        long long int ans =0;
        for(int i=0;i<n;++i){
            int num = arr[i]+d;
            for(;j<n;++j){
                if(num<arr[j]){
                    break;
                }
            }
            long long int cnt = j-i-1;
            ans = (ans+c(cnt))%99997867;
        }
        cout<<ans<<endl;
    }
    return 0;
}

题目三.雀魂启动！

 小包最近迷上了一款叫做雀魂的麻将游戏，但是这个游戏规则太复杂，小包玩了几个月了还是输多赢少。
于是生气的小包根据游戏简化了一下规则发明了一种新的麻将，只留下一种花色，并且去除了一些特殊和牌方式（例如七对子等），具体的规则如下：

    总共有36张牌，每张牌是1~9。每个数字4张牌。
    你手里有其中的14张牌，如果这14张牌满足如下条件，即算作和牌

    14张牌中有2张相同数字的牌，称为雀头。
    除去上述2张牌，剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌（例如234,567等），刻子的意思是相同数字的3个数字牌（例如111,777）


例如：
1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头，可以和牌
1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头，组123,123,567,789的四个顺子，可以和牌
1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头，都无法组成和牌的条件。

现在，小包从36张牌中抽取了13张牌，他想知道在剩下的23张牌中，再取一张牌，取到哪几种数字牌可以和牌。 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[10];
int brr[10];
void init(){
    for(int i=0;i<10;++i){
        arr[i] = 0;
        brr[i] = 0;
    }
}
int main(){
    init();
    int num;
    for(int i=0;i<13;++i){
        cin>>num;
        arr[num]++;    
    }
    int stc[10];
    int top = 0 ;
    int flag =1;
//  for(int i=1;i<=9;++i){
//      cout<< i << " : " <<arr[i]<<endl;
//  }
    for(int i=1;i<=9;++i){               //假设添加进去的牌是i
     
        arr[i-1]--;
        arr[i]++;
        if(arr[i]>4){
            continue;
        }
        for(int j=1;j<=9;++j){           //假设取出来的是雀头是j
          
            for(int n=1;n<=9;++n){
                brr[n] = arr[n];   
            }
             
//          if(i==4 && j==1){
//              cout<<"this way "<<endl;
//              for(int i=1;i<=9;++i){
//                  cout<< i << " : " <<brr[i]<<endl;
//              }
//          }
            if(brr[j]<2){                //根本取不出来这个雀头
                continue;              
            } else{
                brr[j] -= 2;            //取出来了这个雀头
            }
            int cnt = 0 ;               //取出来的数量
            for(int k=1;k<=9;++k){           //先把顺子全部取出来
                if(brr[k]>=3){
                    brr[k]-=3;
                    cnt++;
                }
            }
            for(int m=1;m<=7;++m) {          //再把刻子全部取来         
                while(brr[m]>=1 && brr[m+1]>=1 && brr[m+2]>=1){
                    brr[m] --;
                    brr[m+1] --;
                    brr[m+2] --;
                    cnt++;
                }
            }
            if(cnt==4) {        //取出来了
                stc[top++] = i;
                flag=0;
                break;
            }
             
            //*******************
            for(int n=1;n<=9;++n){
                brr[n] = arr[n];   
            }
             
            if(brr[j]<2){                //根本取不出来这个雀头
                continue;              
            } else{
                brr[j] -= 2;            //取出来了这个雀头
            }
            cnt = 0 ;               //取出来的数量
            for(int m=1;m<=7;++m) {          //先把刻子全部取来         
                while(brr[m]>=1 && brr[m+1]>=1 && brr[m+2]>=1){
                    brr[m] --;
                    brr[m+1] --;
                    brr[m+2] --;
                    cnt++;
                }
            }
            for(int k=1;k<=9;++k){           //再把顺子全部取出来
                if(brr[k]>=3){
                    brr[k]-=3;
                    cnt++;
                }
            }
 
            if(cnt==4) {        //取出来了
                stc[top++] = i;
                flag=0;
                break;
            }
        }
    }
    if(flag){
        //cout<<"来任何牌都无法和牌"<<endl;
        cout<<0<<endl;
    } else {
        for(int i=0;i<top;++i){
            if(i==0){
                cout<<stc[i];
            }else {
                cout<<" "<<stc[i];
            }
        }
        cout<<endl;
    }
    return 0;
}

题目四.特征提取

题目五.毕业旅行问题

题目六.找零

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为的商品，请问最少他会收到多少硬币？

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    int n;
    while(cin>>n){
        n = 1024 -n;   
        int ans = 1<<30;
        for(int i=0;i<=16;++i){
            for(int j=0;j<=64;++j){
                for(int k=0;k<=256;++k){
                    int m = n - 64*i -16*j - 4*k;
                        if(64*i+16*j+4*k+1*m ==n && m>=0){
                            ans = min(ans,(i+j+k+m));
                        }              
//                  for(int m=0;m<=1024;++m){
//                      if(64*i+16*j+4*k+1*m ==n){
//                          ans = min(ans,(i+j+k+m));
//                      }
//                  }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

题目七.机器人跳跃问题

 机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位。 

起初， 机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E, 下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将得到 E - H(k+1) 的能量值。

游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？ 

#include <iostream>
#include <algorithm>
using namespace std;
long long int arr[10050];
bool check(long long int num,int len){
    for(int i = 1;i<=len;++i){
        if(num>arr[i]){
            num += num-arr[i];
        }else {
            num -= arr[i]-num;
        }
        if(num<0){
            return false;
        }
    }
    return true;
}
int cal(long long int l,long long int r,int len){
    while(l < r){
        long long int mid  = (l + r) /2;
        //cout<<"this "<<endl;
        //int mid = l>>1 + r>>1;
        //cout<<"way"<<endl;
        if(check(mid,len)){
            r = mid ;
        } else {
            l = mid + 1;
        }
    }
    return l;
}
int main(){
    int n;
    while(cin>>n){
        arr[0]=0;
         
        for(int i=1;i<=n;++i){
            cin>>arr[i];
        }
 
//      long long int maxn = 1<<30;
////        if(check(2,n)){
////            cout<<"可以"<<endl;
////        }
//      long long int ans = cal(0L,maxn,n);
        int ans = 0;
        for(int i=n;i>=1;--i){
            ans=(int)(1.0*(ans+arr[i])/2+0.5);
        }  
        cout<<ans<<endl;
    }
    return 0;
}