2018年10月8日 今日头条笔试

三分钟交卷

我觉得他不给输入的行数真是烦，自己调的时候太麻烦了

每次一道题可以纠结好久= = 5个根本来不及思考啊 写输入都花好久

#include<iostream> #include<math.h> #include<algorithm> #include<string.h> #include<string> #include<stdio.h> #include<fstream> using namespace std; const long long MOD=1000000007; int inv(int a) {     return a==1?1:(long long)(MOD-MOD/a)*inv(MOD%a)%MOD; } long long  C(long long n,long long  m) {     if(m<0)return 0;     if(n<m)return 0;     if(m>n-m)m=n-m;     long long up=1,down=1;     for(long long  i=0;i<m;i++)     {         up=up*(n-i)%MOD;         down=down*(i+1)%MOD;     }     return up*inv(down)%MOD; } int main(){     int a,b,k;     cin>>a>>b>>k;     long long ans =0;     for(int i=0;i<=k;i++){         int sum = i * a + (k-i) *b;         int flag = 0;         while(sum){             if(sum%10 == a || sum %10 == b){                 sum/=10;                 continue;             }             flag=1;             break;         }         if(flag==0){             ans = (ans+C(k,i))%MOD;         }     }     cout<<ans<<endl;     return 0; } 第一题 枚举加快速组合数取模

只有第三题100% AC了，代码如下：     public static void main(String[] args) {         Scanner scanner = new Scanner(System.in);         int num = Integer.parseInt(scanner.nextLine());         for(int i=0; i<num; i++) {             String s = scanner.nextLine();             getZeroNumber(s, 0, 0, 0, true);             System.out.println(number);             number = 0;         }     }     private static int number = 0;     private static void getZeroNumber(String s, int start, int now, int sum, boolean minus) {         String subS = s.substring(start, now);         if(subS.length() >= 1) {             long subSum = Long.parseLong(subS);             if (!minus) {                 sum += subSum;             } else {                 sum -= subSum;             }         }                 if (now >= s.length() && start != 0) {             if (sum == 0) {                 number++;                             }             return;         }                 for (int i = now+1; i <= s.length(); i++) {             getZeroNumber(s, now, i, sum, true);             getZeroNumber(s, now, i, sum, false);         }     }

class Node { public:     int price;     int level;     Node(int m,int n):     price(m),level(n)     {}; }; class Solution { public:     int C(int num,int all)     {         int up = 1;         int down = 1;         if(all - num < num)             num = all - num;         for(int i = 0;i < num;i ++)         {             up = up * (all - i);             down = down * (i + 1);         }         return up / down;     }     int count(int num,int all,int a,int b)     {         int sum = 0;         for(int i = 0;i < num;i ++)             sum += a;         for(int i = 0;i < all - num;i ++)             sum += b;         while(sum)         {             int temp = sum % 10;             if(temp == a || temp == b)                 sum = sum / 10;             else                 return 0;         }         return 1;              }     int luckNumber(int a,int b,int k)     {         int sum = 0;         for(int i = 0;i <= k;i ++)             sum += C(i,k) * count(i,k,a,b);         return sum;     }     void pos(int m, vector<vector<int>> dis)     {         for(int i = 0;i < 4;i ++)             for(int j = 0;j < 4;j ++)             {                 if(dis[i][j] == 1)                 {                     dis[i][j] = 0;                 }                 else if(dis[i][j] == 0)                 {                     dis[i][j] = INT_MAX;                 }             }         for(int i = 0;i < 4;i ++)             for(int j = 0;j < 4;j ++)                 if(dis[i][j] == 0) // side                 {                     dfs(dis,i + 1,j,1);                     dfs(dis,i - 1,j,1);                     dfs(dis,i,j + 1,1);                     dfs(dis,i,j - 1,1);                 }         for(int i = 0;i < 4;i ++)         {             for(int j = 0;j < 4;j ++)             {                 if(dis[i][j] <= m)                     if(j < 3)                         cout<< 0 << ",";                     else                         cout<< 0;                 else                     if(j < 3)                         cout<< 1 << ",";                     else                         cout<< 1;             }             cout<<endl;         }     }     void dfs(vector<vector<int>>& dis,int i,int j,int step)     {         if(i < 0 || i >= dis.size() || j < 0 || j >= dis[0].size())            return;         if(dis[i][j] == -1)             return;         if(dis[i][j] < step)  // has already reached current position             return;         dis[i][j] = step;         dfs(dis, i + 1,j, step + 1);         dfs(dis, i - 1,j , step + 1);         dfs(dis, i, j - 1, step + 1);         dfs(dis, i, j + 1, step + 1);     }     static bool compare(Node node1,Node node2)     {         return node1.price < node2.price;     }     int SumLevel(vector<Node> nodes,int n,int m)     {         vector<vector<vector<int>>> dp(nodes.size() + 1,vector<vector<int>>(m + 1,vector<int>(n + 1,0)));         sort(nodes.begin(),nodes.end(),compare);         for(int i = 0;i < nodes.size();i ++)         {             for(int j = m;j >= nodes[i].price;j --)      // cost             {                 for(int k = n;k >= 1;k --)                 {                     if(j >= nodes[i].price)                         dp[i + 1][j][k] = max(dp[i][j][k],dp[i][j - nodes[i].price][k - 1] + nodes[i].level);                     else                         dp[i + 1][j][k] = dp[i][j][k];                 }             }         }         return dp[nodes.size()][m][n];     }     int getZeroNumber(string s,int sum,int start,int now,bool minus)     {         string subS = s.substr(start, now - start);         int num = atoi(subS.c_str());         int count = 0;         if(now - start >= 1)             if(minus)                 sum -= num;             else                 sum += num;         if(now == s.length())             if(sum == 0)                 return 1;             else                 return 0;         for(int i = now + 1;i <= s.length();i ++)         {             count += getZeroNumber(s, sum, now, i, true);             count += getZeroNumber(s, sum, now, i, false);         }         return count;     }     int countStairs(int m,int a,int b,int n)     {         vector<int> dp(m + 1,0);         int j = 0;         if(m < a || n > b)             return 0;         for(int i = a ;i < b + 1;i ++)             dp[i] = 1;         for(int i = a ;i < m + 1;i ++)             if(i <= n)                 dp[i] = 0;             else                 for(int j = max(0,i - b);j < i - a + 1;j ++)                     dp[i] += dp[j];         return dp[m];     } };

我a了1.7道收到面试通知了？？？估计是去送菜的吧

20 80 100 100 40啥时候能有面试通知呀😂

第一题 组合问题 第二题 有限制的01背包问题，两维DP 第三题 leetcode494的变形，符号是 +，-和自定义的符号来实现1 # 1-->11,然后backtrack 第四题 找到矩阵的出口，然后从各个出口开始brute force，如果发现距离>k则停止，结合结果最后写出最终矩阵 第五题 有缺陷的楼梯，判断条件如果楼梯总数<a or 连续缺陷的楼梯个数>b,返回0，遇到缺陷的楼梯，dp状态置为0 PS：5道0%的通过率渣渣的YY

请问谁有这五个题的题目呀？麻烦贴一下啊

大佬这么厉害。

100% 80% 100% 0 40%😥

一道题没做出来

请问还有后面还有复考的机会吗？

同怀疑人生

10，20，0 ，0 ，0，顿时开始怀疑人生

第一题都没过hh，有大佬指导一下20位数以后咋办吗

第四题是leetcode Walls and Gates的小变种，但是我不知道如何处理输入的行数和列数

凉凉

自己的代码，第五题40%，求a了的大佬指导下。。 m = int(input()) a = int(input()) b = int(input()) n = int(input()) bb = [] for i in range(n):     bb.append(int(input())) num = [] for i in range(m+1):     num.append(0) for i in range(a):     # num.append(0)     num[i] = 0 for i in range(a, b+1):     num[i] = 1 for i in range(a+1, m+1):     if i in bb:         num[i] = 0     else:         for j in range(i-b, i-a+1):                 num[i] += (num[j] % (pow(10, 9)+7)) print(num[m])