題目連結: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\n", 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