[HIHO]hihoCoder太阁最新面经算法竞赛7

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

期末完事了，终于有时间成套刷题了。这套题比较简单，难度上感觉和上一套差不多。除了最后一个题是看了讨论版说数据水才敢写的。

A Word Construction

解法：正解应该是dfs+剪枝，我的思路是贪心，竟然过了。先把字符串按字典序排序，然后枚举每一个串作为起始，记下串内有什么字符，再从头到尾枚举所有字符串，看看每一个是否符合条件。就那么100个字符串，数据弱得很。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <cassert>
 8 #include <cstdio>
 9 #include <cstdlib>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 using namespace std;
20 #define fr first
21 #define sc second
22 #define cl clear
23 #define BUG puts("here!!!")
24 #define W(a) while(a--)
25 #define pb(a) push_back(a)
26 #define Rint(a) scanf("%d", &a)
27 #define Rll(a) scanf("%I64d", &a)
28 #define Rs(a) scanf("%s", a)
29 #define Cin(a) cin >> a
30 #define FRead() freopen("in", "r", stdin)
31 #define FWrite() freopen("out", "w", stdout)
32 #define Rep(i, len) for(int i = 0; i < (len); i++)
33 #define For(i, a, len) for(int i = (a); i < (len); i++)
34 #define Cls(a) memset((a), 0, sizeof(a))
35 #define Clr(a, x) memset((a), (x), sizeof(a))
36 #define Full(a) memset((a), 0x7f7f7f, sizeof(a))
37 #define lrt rt << 1
38 #define rrt rt << 1 | 1
39 #define pi 3.14159265359
40 #define RT return
41 #define lowbit(x) x & (-x)
42 #define onenum(x) __builtin_popcount(x)
43 typedef long long LL;
44 typedef long double LD;
45 typedef unsigned long long ULL;
46 typedef pair<int, int> pii;
47 typedef pair<string, int> psi;
48 typedef pair<LL, LL> pll;
49 typedef map<string, int> msi;
50 typedef vector<int> vi;
51 typedef vector<LL> vl;
52 typedef vector<vl> vvl;
53 typedef vector<bool> vb;
54 
55 const int maxn = 1000;
56 string s[maxn];
57 int n;
58 int ascii[256];
59 
60 int main() {
61     // FRead();
62     while(~Rint(n)) {
63         Rep(i, n) cin >> s[i];
64         sort(s, s+n);
65         int ret = 0;
66         Rep(k, n) {
67             Cls(ascii);
68             Rep(j, s[k].length()) ascii[s[k][j]] = 1;
69             int cur = 1;
70             Rep(i, n) {
71                 bool flag = 0;
72                 Rep(j, s[i].length()) {
73                     if(ascii[s[i][j]] == 1) {
74                         flag = 1;
75                         break;
76                     }
77                 }
78                 if(flag == 0) {
79                     Rep(j, s[i].length()) ascii[s[i][j]] = 1;
80                     cur++;
81                 }
82             }
83             ret = max(ret, cur);
84         }
85         printf("%d
", ret);
86     }
87     RT 0;
88 }
A

B Email Merge

解法：STL+并查集，这题很好想，但是写起来比较麻烦。对于字符串数组，想要做并查集操作的话，需要map<string, int>这样从字符串到整型的映射支持。读入数据按照邮箱为根节点，儿子是用户名，构建一个森林。这个时候同时更新并查集，也就是合并同一个树根下的所有用户名字符串。接着遍历所有用户名，扔到对应的belong中。我开的belong是堆，因为输出要求按照出现的顺序，所以堆序就是输入的顺序，也就是之前赋值的id号。

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <iomanip>
  4 #include <cstring>
  5 #include <climits>
  6 #include <complex>
  7 #include <cassert>
  8 #include <cstdio>
  9 #include <cstdlib>
 10 #include <bitset>
 11 #include <vector>
 12 #include <deque>
 13 #include <queue>
 14 #include <stack>
 15 #include <ctime>
 16 #include <set>
 17 #include <map>
 18 #include <cmath>
 19 using namespace std;
 20 #define fr first
 21 #define sc second
 22 #define cl clear
 23 #define BUG puts("here!!!")
 24 #define W(a) while(a--)
 25 #define pb(a) push_back(a)
 26 #define Rint(a) scanf("%d", &a)
 27 #define Rll(a) scanf("%I64d", &a)
 28 #define Rs(a) scanf("%s", a)
 29 #define Cin(a) cin >> a
 30 #define FRead() freopen("in", "r", stdin)
 31 #define FWrite() freopen("out", "w", stdout)
 32 #define Rep(i, len) for(int i = 0; i < (len); i++)
 33 #define For(i, a, len) for(int i = (a); i < (len); i++)
 34 #define Cls(a) memset((a), 0, sizeof(a))
 35 #define Clr(a, x) memset((a), (x), sizeof(a))
 36 #define Full(a) memset((a), 0x7f7f7f, sizeof(a))
 37 #define lrt rt << 1
 38 #define rrt rt << 1 | 1
 39 #define pi 3.14159265359
 40 #define RT return
 41 #define lowbit(x) x & (-x)
 42 #define onenum(x) __builtin_popcount(x)
 43 typedef long long LL;
 44 typedef long double LD;
 45 typedef unsigned long long ULL;
 46 typedef pair<int, int> pii;
 47 typedef pair<string, int> psi;
 48 typedef pair<LL, LL> pll;
 49 typedef map<string, int> msi;
 50 typedef vector<int> vi;
 51 typedef vector<LL> vl;
 52 typedef vector<vl> vvl;
 53 typedef vector<bool> vb;
 54 
 55 const int maxn = 100010;
 56 typedef struct Node {
 57     string d;
 58     int idx;
 59     Node() { idx = -1; }
 60     Node(string dd, int ii) : d(dd), idx(ii) {}
 61     friend bool operator<(Node a, Node b) { return a.idx > b.idx; }
 62 }Node;
 63 
 64 string mail, user;
 65 bool vis[maxn];
 66 map<string, int> id;
 67 map<string, set<string> > wt;
 68 priority_queue<Node> belong[100010];
 69 
 70 int n, m, cnt;
 71 int pre[maxn];
 72 
 73 int find(int x) {
 74     return x == pre[x] ? x : pre[x] = find(pre[x]);
 75 }
 76 
 77 void unite(int x, int y) {
 78     x = find(x); y = find(y);
 79     if(x < y) pre[y] = x;
 80     else pre[x] = y;
 81 }
 82 
 83 int main() { 
 84     // FRead();
 85     cnt = 1;id.cl(); wt.cl(); Cls(vis);
 86     Rint(n);
 87     Rep(i, n*10) {
 88         pre[i] = i;
 89         while(!belong[i].empty()) belong[i].pop();
 90     }
 91     Rep(i, n) {
 92         cin >> user;
 93         cin >> m;
 94         id[user] = cnt++;
 95         Rep(j, m) {
 96             cin >> mail;
 97             if(id.find(mail) == id.end()) id[mail] = cnt++;
 98             wt[mail].insert(user);
 99             unite(id[user], id[mail]);
100         }
101     }
102     map<string, set<string> >::iterator it;
103     set<string>::iterator each;
104     for(it = wt.begin(); it != wt.end(); it++) {
105         for(each = it->second.begin(); each != it->second.end(); each++) {
106             if(!vis[id[*each]]) {
107                 vis[id[*each]] = 1;
108                 belong[find(id[*each])].push(Node(*each, id[*each]));
109             }
110         }
111     }
112     Rep(i, cnt) {
113         if(!belong[i].empty()) {
114             while(!belong[i].empty()) {
115                 cout << belong[i].top().d << " ";
116                 belong[i].pop();
117             }
118             cout << endl;
119         }
120     }
121     RT 0;
122 }
B

C Matrix Sum

解法：这题毒瘤题…数据里有负数，不同语言对负数取模运算的结果不一样，C++和Java是一个负数对一个正数取模是一个负数，而Python是正数。这题的正解应当是二维线段树or树状数组（树套树），分别维护自己列的值。而我直接维护前缀和了。写了各种语言的解法，改来改去最后改了java。

 1 import java.lang.reflect.Array;
 2 import java.util.Arrays;
 3 import java.util.Comparator;
 4 import java.util.Scanner;
 5 
 6 import javax.swing.text.GapContent;
 7 
 8 public class Main {
 9     public static void main(String[] args) {
10         Scanner in = new Scanner(System.in);
11         int n, m;
12         int[][] dp = new int[1010][1010];
13         String cmd = new String();
14         for(int i = 0; i < 1010; i++) {
15             for(int j = 0; j < 1010; j++) {
16                 dp[i][j] = 0;
17             }
18         }
19         n = in.nextInt(); m = in.nextInt();
20         int x1, x2, y1, y2, num;
21         while(m-- > 0) {
22             cmd = in.next();
23             if(cmd.charAt(0) == 'A') {
24                 x1 = in.nextInt();
25                 y1 = in.nextInt();
26                 num = in.nextInt();
27                 for(int i = y1; i < n; i++) {
28                     dp[x1][i] = (dp[x1][i] + num) % 1000000007;
29                 }
30             }
31             else {
32                 x1 = in.nextInt();
33                 x2 = in.nextInt();
34                 y1 = in.nextInt();
35                 y2 = in.nextInt();
36                 int ret = 0;
37                 for(int i = x1; i <= y1; i++) {
38                     if(x2 == 0) ret = (ret + dp[i][y2]) % 1000000007;
39                     else ret = (ret + dp[i][y2] - dp[i][x2-1]) % 1000000007;
40                 }
41                 System.out.println((ret + 1000000007) % 1000000007);
42             }
43         }
44     }
45 }
C
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/kirai/p/5657687.html