[21.04.18]周赛（ak）
第四题很离谱，做完一看，wow想拿奖要20分钟写完四道题5555
判断句子是否为全字母句
无脑hash
雪糕的最大数量
无脑贪心
单线程 CPU
需要绑定当前下标，起始时间和执行长度。按起始时间排序。
优先队列。按事件长度排序。
每次把所有符合时间段的事件扔进优先队列。
队列每次取出事件长度最小的事件，更新当前时间，扔新的事件进去。
这道题几乎百分百考察的是代码稳定性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| class Solution {
public:
static bool cmp_time(pair<int, vector<int>>&taska, pair<int, vector<int>>&taskb){
if(taska.second[0] < taskb.second[0])return true;
return false;
}
struct cmp_len{
bool operator()(pair<int, vector<int>>&taska, pair<int, vector<int> >&taskb) {
if(taska.second[1] > taskb.second[1])return true;
else if(taska.second[1] == taskb.second[1] && taska.first > taskb.first)return true;
return false;
}
};
vector<int> getOrder(vector<vector<int>>& tasks) {
vector<int>ret;
pair<int,vector<int>> order[tasks.size()+5];
memset(order, 0, sizeof(order));
ret.clear();
for(int i = 0; i < tasks.size(); i++){
order[i].first = i;
order[i].second.push_back(tasks[i][0]);
order[i].second.push_back(tasks[i][1]);
}
sort(order, order+tasks.size(), cmp_time);
priority_queue<pair<int, vector<int>>, vector<pair<int, vector<int>> >, cmp_len>q;
while(!q.empty())q.pop();
int time = 0;
for(int i = 0; i < tasks.size();){
if(q.empty()){
q.push(order[i]);
time = max(time, order[i].second[0]);
i++;
}
while(i < tasks.size() && time >= order[i].second[0]){
q.push(order[i]);
i++;
}
if(i < tasks.size() && time < order[i].second[0]){
time += q.top().second[1];
ret.push_back(q.top().first);
q.pop();;
}
}
while(!q.empty()){
ret.push_back(q.top().first);
q.pop();
}
return ret;
}
};
|
所有数对按位与结果的异或和
考虑与或非运算：
与相当于按位乘法，异或相当于按位加法（不进位） 。
众所周知，a_1b+a_2b+…+a_n*b = (a_1+a_2+…+a_n)*b
按位运算同样符合其性质。
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int getXORSum(vector<int>& arr1, vector<int>& arr2) {
int arra = 0;
int ans = 0;
for(int i = 0; i < arr1.size(); i++)arra ^= arr1[i];
for(int j = 0; j < arr2.size(); j++)ans ^= arra & arr2[j];
return ans;
}
};
|