首页 > 代码库 > hihoCoder太阁最新面经算法竞赛19

hihoCoder太阁最新面经算法竞赛19

比赛链接:http://hihocoder.com/contest/hihointerview28/problems

 

A. 固定一个方向,两两相邻的点顺时针或逆时针构造三个向量,判断这个点在这个向量的左侧还是右侧,看看是否在同一侧。trick就是点在向量上,对应的情况就是值为0.

 1 def do(p1x, p1y, p2x, p2y, p3x, p3y):
 2     return (p3x - p1x) * (p2y - p1y) - (p2x - p1x) * (p3y - p1y);
 3 
 4 T = map(int, raw_input().split( ))[0]
 5 while T > 0:
 6     T -= 1
 7     px, py, ax, ay, bx, by, cx, cy = map(int, raw_input().split( ))
 8     x, y, z = do(ax, ay, px, py, bx, by), do(bx, by, px, py, cx, cy), do(cx, cy, px, py, ax, ay)
 9     if (x >= 0 and y >= 0 and z >= 0) or (x <= 0 and y <= 0 and z <= 0):
10         print YES
11     else:
12         print NO

 

B.打表规律,发现<=16的时候可以暴搜,>16的时候f(n)=4*f(n-5)(?如果没记错的话),矩阵加速一下就行了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 typedef long long LL;
 5 const LL mod = 1000000007LL;
 6 const int maxn = 10;
 7 LL n;
 8 LL ret;
 9 
10 typedef struct Matrix {
11     LL m[maxn][maxn];
12     int r;
13     int c;
14     Matrix() {
15         r = c = 0;
16         memset(m, 0, sizeof(m));
17     } 
18 } Matrix;
19 
20 Matrix mul(Matrix m1, Matrix m2, LL mod) {
21     Matrix ans = Matrix();
22     ans.r = m1.r;
23     ans.c = m2.c;
24     for(int i = 1; i <= m1.r; i++) {
25         for(int j = 1; j <= m2.r; j++) {
26                for(int k = 1; k <= m2.c; k++) {
27                 if(m2.m[j][k] == 0) continue;
28                 ans.m[i][k] = ((ans.m[i][k] + m1.m[i][j] * m2.m[j][k] % mod) % mod) % mod;
29             }
30         }
31     }
32     return ans;
33 }
34 
35 Matrix quickmul(Matrix m, LL n, LL mod) {
36     Matrix ans = Matrix();
37     for(int i = 1; i <= m.r; i++) {
38         ans.m[i][i]  = 1;
39     }
40     ans.r = m.r;
41     ans.c = m.c;
42     while(n) {
43         if(n & 1) {
44             ans = mul(m, ans, mod);
45         }
46         m = mul(m, m, mod);
47         n >>= 1;
48     }
49     return ans;
50 }
51 
52 void dfs(LL n, LL cur, LL sz) {
53     if(n == 0) {
54         ret = max(ret, cur);
55         return;
56     }
57     if(n >= 3) dfs(n-3,cur*2%mod, cur);
58     if(n >= 1 && sz) dfs(n-1, (cur+sz)%mod, sz);
59         dfs(n-1,(cur+1)%mod, sz);
60 }
61 
62 int main() {
63     // freopen("in", "r", stdin);
64     while(cin >> n) {
65         if(n < 16) {
66             ret = 0;
67             dfs(n, 0, 0);
68             cout << ret << endl;
69             continue;
70         }
71         Matrix x; x.r = 5, x.c = 1;
72         x.m[1][1] = 81, x.m[2][1] = 64, x.m[3][1] = 48, x.m[4][1] = 36, x.m[5][1] = 27;
73         Matrix p; p.r = p.c = 5;
74         memset(p.m, 0, sizeof(p.m));
75         p.m[1][5] = 4;
76         for(int i = 2; i <= 5; i++) p.m[i][i-1] = 1;
77         p = quickmul(p, n-15, mod);
78         p = mul(p, x, mod);
79         cout << p.m[1][1] << endl;
80     }
81     return 0;
82 }

 

C.对于trie上的每个节点u,求最小的整数x满足 节点u对应的字符串(trie上root->u的路径) 是 S[1..x]的子序列。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 10100;
 5 const int maxm = 100100;
 6 const int maxc = 30;
 7 
 8 typedef pair<int, int> pii;
 9 typedef struct Trie {
10     int rt, sz;
11     int id[maxm][maxc], val[maxm];
12     int dp[maxm];
13     string s;
14     void build() {
15         rt = sz = 0;
16         memset(dp, 0, sizeof(dp));
17         memset(id, -1, sizeof(id));
18         memset(val, 0, sizeof(val));
19     }
20     void insert(const char* str) {
21         int u = rt;
22         int n = strlen(str);
23         for(int i = 0; i < n; i++) {
24             int v = str[i] - a;
25             if(id[u][v] == -1) id[u][v] = ++sz;
26             u = id[u][v];
27         }
28         val[u] = max(val[u], n);
29     }
30     void dfs(int x, int u) {
31         if(x == s.length()) return;
32         for(int i = 0; i < 26; i++) {
33             int &v = id[u][i];
34             if(v == -1) continue;
35             int y = x;
36             while(s[y] != i + a && y < s.length()) y++;
37             if(y == s.length()) break;
38             if(i + a == s[y]) {
39                 dp[v] = dp[u] + 1;
40                 dfs(y+1, v);
41             }
42         }
43     }
44 }Trie;
45 
46 int n;
47 char tmp[maxm];
48 Trie trie;
49 
50 int main() {
51     // freopen("in", "r", stdin);
52     while(~scanf("%d", &n)) {
53         trie.build();
54         for(int i = 0; i < n; i++) {
55             scanf("%s", tmp);
56             trie.insert(tmp);
57         }
58         scanf("%s", tmp);
59         trie.s = tmp;
60         trie.dfs(0, 0);
61         int ret = 0;
62         for(int i = 0; i <= trie.sz; i++) {
63             // printf("%d %d\n", trie.dp[i], trie.val[i]);
64             if(trie.dp[i] != 0) {
65                 ret = max(ret, trie.val[i]);
66             }
67         }
68         printf("%d\n", ret);
69     }
70     return 0;
71 }

 

hihoCoder太阁最新面经算法竞赛19