微软2016校园招聘4月在线笔试 ABC

题目链接：http://hihocoder.com/contest/mstest2016april1/problems

第一题：输入N,P,W,H，代表有N段文字，每段有ai个字，每行有⌊W/S⌋个字，每页有⌊H/S⌋行，每段结束换行，希望总页数不超过P，求最大的S。

题解: 没什么好说的，本来想二分S，结果发现N才1000，直接暴力。0ms过的。【我才不会说交错语言CE这种事

 1 #include <cstdio>
 2 #include <cmath>
 3 using namespace std;
 4 int a[1005];
 5 int main()
 6 {
 7     int t;
 8     int n, w, h, p;
 9     scanf("%d", &t);
10     while (t--) {
11         scanf("%d%d%d%d", &n, &p, &w, &h);
12         for (int i = 0; i < n; ++i) scanf("%d", a + i);
13         for (int s = w; s > 0; --s) {
14             int cnt = 0;
15             for (int i = 0; i < n; ++i) {
16                 cnt += ceil((double)a[i] / floor((double)w / s));
17             }
18             if (ceil((double)cnt / floor((double)h / s)) <= p) {
19                 printf("%d
", s);
20                 break;
21             }
22         }
23 
24     }
25     return 0;
26 }

第二题：先给N个字符串allow或deny，然后是一段ip，点分十进制的形式。后面可能会有掩码位数。然后给M个字符串表示ip（无掩码），如果能找到与上面符合的，allow输出YES，deny输出NO，找不到也输出YES。符合是指化成二进制后前掩码位数的数字相同。如果有多个匹配以第一个为标准。

题解：很容易想到字典树，可惜实在是太弱，写了好久，还好是1A。先预处理出0~255的二进制。然后把每个ip化成字符串，几位掩码字符串就截断到几位，否则就是32位。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 
  5 using namespace std;
  6 
  7 const int KIND = 2;
  8 const int MAXN = 3200010;
  9 int cnt_node;
 10 
 11 struct node{
 12     node* nt[2];
 13     int flag;
 14     int cnt;
 15     void init(){
 16         memset(nt, 0, sizeof(nt));
 17         flag = -1;
 18         cnt = 0;
 19     }
 20 } Heap[MAXN];
 21 
 22 inline node* new_node()
 23 {
 24     Heap[cnt_node].init();
 25     return &Heap[cnt_node++];
 26 }
 27 
 28 void insert(node* root, char *str, int flag, int cnt)
 29 {
 30     for(char *p = str; *p; ++p){
 31         int ch = *p - '0';
 32         if(root->nt[ch] == NULL)
 33             root->nt[ch] = new_node();
 34         root = root->nt[ch];
 35     }
 36     if (root->flag == -1) {
 37         root->flag = flag;
 38         root->cnt = cnt;
 39     }
 40 }
 41 
 42 int count(node* root, char *str)
 43 {
 44     int cnt = 1000000;;
 45     int ans = -1; //printf("flag - %d
", root->flag);
 46     if(root->flag != -1 && root->cnt < cnt) {
 47         cnt = root->cnt;
 48         ans = root->flag;
 49 
 50     }
 51     for(char *p = str; *p; ++p){
 52         int ch = *p - '0';
 53         if(root->nt[ch] == NULL) {
 54             return ans;
 55         }
 56         root = root->nt[ch];
 57         if(root->flag != -1 && root->cnt < cnt) {
 58             cnt = root->cnt;
 59             ans = root->flag;
 60         }
 61     }
 62     return ans;
 63 }
 64 
 65 int num[300][10];
 66 void init()
 67 {
 68     for (int i = 0; i <= 255; i++) {
 69         for (int j = 0; j < 8; j++) {
 70             if (i & (1 << j)) num[i][8 - j - 1] = 1;
 71         }
 72     }
 73 //    for (int i = 0; i < 20; ++i) {
 74 //        for (int j = 0; j < 8; ++j)
 75 //            printf("%d", num[i][j]); printf("
");
 76 //    }
 77 }
 78 //10000000 01111111 0000/1000 01111101 128.127.8.125/20
 79 
 80 void input(char *s)
 81 {
 82     int a[4], mark = 32;
 83     scanf("%d.%d.%d.%d", &a[0], &a[1], &a[2], &a[3]);
 84     //printf("%d %d %d %d", a[0], a[1], a[2], a[3]);
 85     char ch;
 86     scanf("%c", &ch);
 87     if (ch == '/') scanf("%d", &mark);
 88 
 89     for (int i = 0; i < 4; ++i) {
 90         for (int j = 0; j < 8; ++j) {
 91             s[i * 8 + j] = num[ a[i] ][j] + '0';
 92         }
 93     }
 94     s[mark] = 0;
 95     //printf(" s = %s
", s);
 96 }
 97 
 98 int main()
 99 {
100     init();
101     int n, m;
102     while(scanf("%d%d", &n, &m) != EOF)
103     {
104         cnt_node = 0;
105         node *root = new_node();
106         char s[50], op[50];
107         for (int i = 0; i < n; ++i) {
108             scanf("%s", op);
109             input(s);
110             //printf("%s
", s);
111             insert(root, s, *op == 'a' ? 1 : 2, i);
112         }
113         for (int i = 0; i < m; ++i) {
114             input(s);
115             //printf("%s
", s);
116             if (count(root, s) == -1 || count(root, s) == 1) printf("YES
");
117             else printf("NO
");
118         }
119     }
120     return 0;
121 }

第三题：一个机器人只会向右走和向下走，碰到墙才会转弯，问至少改变几块墙（即墙变为空地或空地变为墙），使机器人可以从左上角走到右下角。一开始的方向是向右。

题解：一眼就想到dp，dp[i][j][k]表示从(0,0)走到(i,j)且方向是k的最少花费。k为0表示向右，k为1表示向下。可惜转移那里想了很久，就是有点蒙，重复考虑了一些情况，代码写的比较慢（主要是第二题浪费了太多时间），总之就是没来的提交，赛后A的。

对于每一个点都有向下和向右两种情况，每一种情况都有可能是从左边和上边转移过来的。比如向下的可能是下面两种情况，向右同理。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 char mp[105][105];
 5 int dp[105][105][2];
 6 int n, m;
 7 
 8 int isWall(int i, int j) { if (i == n || j == m || mp[i][j] == 'b') return 1; return 0; }
 9 int notWall(int i, int j) { if (i == n || j == m || mp[i][j] == 'b') return 0; return 1; }
10 
11 int main()
12 {
13     scanf("%d%d", &n, &m);
14     for (int i = 0; i < n; ++i) scanf("%s", mp[i]);
15 
16     for (int i = 0; i < n; ++i) {
17         for (int j = 0; j < m; ++j) {
18             if (i == 0) {
19                 if (j == 0) {
20                     dp[i][j][0] = 0;
21                     dp[i][j][1] = notWall(i, j+1);
22                 } else {
23                     dp[i][j][0] = dp[i][j-1][0];
24                     dp[i][j][1] = dp[i][j-1][0] + notWall(i, j+1);
25                 }
26             } else {
27                 if (j == 0) {
28                     dp[i][j][0] = dp[i-1][j][1] + notWall(i+1, j);
29                     dp[i][j][1] = dp[i-1][j][1];
30                 } else {
31                     dp[i][j][0] = min(dp[i][j-1][0], dp[i-1][j][1] + notWall(i+1, j));
32                     dp[i][j][1] = min(dp[i-1][j][1], dp[i][j-1][0] + notWall(i, j+1));
33                 }
34             }
35 
36             dp[i][j][0] += isWall(i, j);
37             dp[i][j][1] += isWall(i, j);
38         }
39     }
40     printf("%d
", min(dp[n - 1][m - 1][0], dp[n-1][m-1][1]));
41     return 0;
42 }

第四题没做。。。。。跪、、、

总之就是GG了。。。。