头条实习笔试题目
分类:
IT文章
•
2024-05-03 21:15:07
官方题解：http://discuss.acmcoder.com/topic/58dd094d6f37d3610507b06e
1. 直接从左往右扫，上升而且长度至少为1，然后再扫，下降的长度至少为1，更下答案，从这个位置重新开始。
![]()
1 /*
2 ID: y1197771
3 PROG: test
4 LANG: C++
5 */
6 #include<bits/stdc++.h>
7 #define pb push_back
8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)
9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
10 typedef long long ll;
11 using namespace std;
12 typedef pair<int, int> pii;
13 const int maxn = 1e7 + 10;
14 int n;
15 int a[maxn];
16 void solve() {
17 while(cin >> n){
18 for (int i = 0; i < n; i++) {
19 cin >> a[i];
20 }
21 int res = 0;
22 int tleft, tright; tleft = tright = -1;
23 int i = 0;
24 while(i < n) {
25 int tl = i;
26 while(i + 1 < n && a[i + 1] > a[i]) {
27 i++;
28 }
29 if(i == tl) {
30 i++;
31 continue;
32 }
33 int tm = i;
34 while(i + 1 < n && a[i + 1] < a[i]) {
35 i++;
36 }
37 if(i == tm) {
38 i++;
39 continue;
40 }
41 int tlen = i - tl + 1;
42 if(tlen > res) {
43 res = tlen;
44 tleft = tl;
45 tright = i;
46 }
47 }
48 cout << tleft << " " << tright << endl;
49 }
50 }
51 int main() {
52 freopen("test.in", "r", stdin);
53 //freopen("test.out", "w", stdout);
54 ios::sync_with_stdio(0);
55 cin.tie(0); cout.tie(0);
56 solve();
57 return 0;
58 }
View Code
2. 直接按照要求，每一个句子搞一个set，然后对测试的每一个句子拆分单词，找最多的匹配，码的代码比较多，题意挺直接的。
![]()
1 /*
2 ID: y1197771
3 PROG: test
4 LANG: C++
5 */
6 #include<bits/stdc++.h>
7 #define pb push_back
8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)
9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
10 typedef long long ll;
11 using namespace std;
12 typedef pair<int, int> pii;
13 const int maxn = 1e3 + 10;
14 int n, m;
15 set<string> se[603];
16 string a[603];
17 void solve() {
18 cin >> n >> m;
19 string s;
20 getchar();
21 for (int i = 0; i < n; i++) {
22 getline(cin, s);
23 //cout << s << endl;
24 a[i] = s;
25 s += " ";
26 int tn = s.size();
27 int p = 0;
28 while(p < tn) {
29 int t = p;
30 while(p < tn && s[p] != ' ') p++;
31 string st = s.substr(t, p - t);
32 se[i].insert(st);
33 p++;
34 }
35 }
36 set<string> v;
37 for (int i = 0; i < m; i++) {
38 getline(cin, s);
39 v.clear();
40 s += " ";
41 int tn = s.size();
42 int p = 0;
43 while(p < tn) {
44 int t = p;
45 while(p < tn && s[p] != ' ') p++;
46 string st = s.substr(t, p - t);
47 v.insert(st);
48 p++;
49 }
50 int res = 0, id = -1;
51 for (int j = 0; j < n; j++) {
52 int sc = 0;
53 for (string t : v) {
54 if(se[j].count(t)) {
55 sc++;
56 }
57 }
58 if(sc > res) {
59 res = sc;
60 id = j;
61 }
62 }
63 cout << a[id] << endl;
64 }
65 }
66 int main() {
67 freopen("test.in", "r", stdin);
68 //freopen("test.out", "w", stdout);
69 //ios::sync_with_stdio(0);
70 //cin.tie(0); cout.tie(0);
71 solve();
72 return 0;
73 }
View Code
stringstream该可以按照空格拆分字符串，利用这个可以简单的拆分单词。
3. 题意挺明显的，先找最深层次，这关系到最后的输出长度，然后逐个扫描输出。
我不清楚到底要不要输出空格。一直是30%。
![]()
1 /*
2 ID: y1197771
3 PROG: test
4 LANG: C++
5 */
6 #include<bits/stdc++.h>
7 #define pb push_back
8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)
9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
10 typedef long long ll;
11 using namespace std;
12 typedef pair<int, int> pii;
13 const int maxn = 1e3 + 10;
14 string s;
15
16 void solve() {
17 while(cin >> s) {
18 int n = s.size();
19 int len = 0;
20 int x, y;
21 x = 0;
22 for (char t : s) {
23 if(t == '[') x++;
24 else x--;
25 len = max(len, x);
26 }
27 int m = 0;
28 int cur = 0;
29 for (int i = 0; i < n; i++) {
30 if(s[i] == '[') {
31 cur++;
32 if(cur == 1) {
33 m = 2 * len - 1;
34
35 cout << "+";
36 for(int j = 0; j < m; j++)
37 cout << '-';
38 cout << "+" << endl;
39
40 if(i + 1 < n && s[i + 1] == ']') {
41 cout << "|";
42 for(int j = 0; j < m; j++)
43 cout << ' ';
44 cout << "|" << endl;
45
46 for (int j = 0; j < 2 * len + 1; j++)
47 cout << " ";
48 cout << endl;
49
50 cout << "|";
51 for(int j = 0; j < m; j++)
52 cout << ' ';
53 cout << "|" << endl;
54 }
55 } else {
56 m = 2 * (len - cur + 1) - 1;
57
58 for (int j = 0; j < cur - 2; j++)
59 cout << " ";
60 cout << "|";
61 cout << "+";
62 for(int j = 0; j < m; j++)
63 cout << '-';
64 cout << "+";
65 cout << "|";
66 for (int j = 0; j < cur - 2; j++)
67 cout << " ";
68 cout << endl;
69
70
71 if(i + 1 < n && s[i + 1] == ']') {
72
73 for (int j = 0; j < cur - 1; j++)
74 cout << " ";
75 cout << "|";
76 for(int j = 0; j < m; j++)
77 cout << ' ';
78 cout << "|" ;
79 for (int j = 0; j < cur - 1; j++)
80 cout << " ";
81 cout << endl;
82
83
84 for (int j = 0; j < 2 * len + 1; j++)
85 cout << " ";
86 cout << endl;
87
88
89 for (int j = 0; j < cur - 1; j++)
90 cout << " ";
91 cout << "|";
92 for(int j = 0; j < m; j++)
93 cout << ' ';
94 cout << "|";
95 for (int j = 0; j < cur - 1; j++)
96 cout << " ";
97 cout << endl;
98 }
99 }
100
101 } else {
102
103 if(cur == 1) {
104 m = 2 * len - 1;
105 cout << "+";
106 for(int j = 0; j < m; j++)
107 cout << '-';
108 cout << "+" << endl;
109
110 } else {
111 m = 2 * (len - cur + 1) - 1;
112 for (int j = 0; j < cur - 2; j++)
113 cout << " ";
114 cout << "|";
115 cout << "+";
116 for(int j = 0; j < m; j++)
117 cout << '-';
118 cout << "+";
119 cout << "|";
120 for (int j = 0; j < cur - 2; j++)
121 cout << " ";
122 cout << endl;
123
124 }
125 cur--;
126 }
127 }
128 }
129 }
130 int main() {
131 freopen("test.in", "r", stdin);
132 //freopen("test.out", "w", stdout);
133 ios::sync_with_stdio(0);
134 cin.tie(0); cout.tie(0);
135 solve();
136 return 0;
137 }
View Code
4. 显然暴力是不行的，先写个暴力的，拿到30%的分数。接下来分析有没有什么好办法，考虑到题目数目范围[1， 1e5],很容的就可以开1e5大小的数组，然后就是桶排序。观察到i的顺序无关紧要。不能在线一个一个做的话，就离线，按照x的值进行排序，固定第一个值，然后动态的更新第二个数，而且第二个数还要求点更新和区间查询，显然树状数组是满足要求的，（当然线段树也是可以的，什么更高深的算法更是不在话下吧，学学莫队算法，treap，splay等）。然后就很直接了。
注意，即使使用优化的cin，cout也会超时tle，我猜是题目的数据太多了的缘故，（而且输出不是很大），必须换成scanf，printf或者开挂（采用read读取，write写出）。
![]()
1 /*
2 ID: y1197771
3 PROG: test
4 LANG: C++
5 */
6 #include<bits/stdc++.h>
7 #define pb push_back
8 #define FOR(i, n) for (int i = 0; i < (int)n; ++i)
9 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl
10 typedef long long ll;
11 using namespace std;
12 typedef pair<int, int> pii;
13 const int maxn = 1e5 + 10;
14 int n, q;
15 vector<pii> e[maxn];
16 pii a[maxn];
17 int res[maxn];
18 int f[maxn];
19 int lb(int x) {
20 return x & -x;
21 }
22 int ask(int t) {
23 int r = 0;
24 while(t > 0) {
25 r += f[t];
26 t -= lb(t);
27 }
28 return r;
29 }
30 void upd(int x) {
31 while(x <= 100000) {
32 f[x]++;
33 x += lb(x);
34 }
35 }
36
37 void solve() {
38 cin >> n >> q;
39 for (int i = 0; i < n; i++) {
40 //cin >> a[i].first;
41 scanf("%d", &a[i].first);
42 }
43 for (int i = 0; i < n; i++) {
44 //cin >> a[i].second;
45 scanf("%d", &a[i].second);
46 }
47 int x, y;
48 for (int i = 0; i < q; i++) {
49 //cin >> x >> y;
50 scanf("%d%d", &x, &y);
51 e[x].pb({y, i});
52 }
53 sort(a, a + n);
54 int p = n - 1;
55 for (int i = 100000; i >=1; i--) {
56 while(p >= 0 && a[p].first >= i) {
57 int t = a[p].second;
58 upd(t);
59 p--;
60 //cout << i << " " << p << endl;
61 }
62
63 for (int j = 0; j < e[i].size(); j++) {
64 int t = e[i][j].first;
65 int t2 = e[i][j].second;
66 res[t2] = (n - 1 - p) - ask(t - 1);
67 }
68
69 }
70 for (int i = 0; i < q; i++)
71 printf("%d
", res[i]);
72
73 }
74 int main() {
75 freopen("test.in", "r", stdin);
76 //freopen("test.out", "w", stdout);
77 //ios::sync_with_stdio(0);
78 //cin.tie(0); cout.tie(0);
79 solve();
80 return 0;
81 }
