第一题，暴力
#include <iostream>
#include <vector>
using namespace std;
bool helper(const vector<int> &a,
const vector<int> &b,
const vector<int> &c)
{
int W[10] = {0};
W[1] = W[4] = W[7] = 1;
int B[10] = {0};
B[2] = B[5] = B[8] = 1;
int T[10] = {0};
T[3] = T[6] = T[9] = 1;
int cnt = 0;
for (auto i : a){
if (W[i] == 1){
--W[i];
++cnt;
}
}
for (auto i : b){
if (B[i] == 1){
--B[i];
++cnt;
}
}
for (auto i : c){
if (T[i] == 1){
--T[i];
++cnt;
}
}
return cnt >= 7;
}
int main()
{
int len;
cin >> len;
while (len--){
vector<int> W, B, T;
for (int i = 0; i < 7; ++i){
string s;
cin >> s;
if (s.size() != 2)
continue;
if (s.back() == 'W'){
W.push_back(s[0] - '0');
}
else if (s.back() == 'B'){
B.push_back(s[0] - '0');
}
else if (s.back() == 'T'){
T.push_back(s[0] - '0');
}
}
if (helper(W, B, T) || helper(W, T, B)
|| helper(T, W, B) || helper(T, B, W)
|| helper(B, W, T) || helper(B, T, W)){
cout << "YES" << endl;
}
else{
cout << "NO" << endl;
}
}
} 第二题，暴力
#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> helper(vector<vector<int>>& nums){
if(nums.empty()) return nums;
int len = nums.size();
vector<int> row(len);
vector<int> col(len);
for(int i=0; i<len; ++i){
for(int j=0; j<len; ++j){
row[i] += nums[i][j];
}
}
for(int i=0; i<len; ++i){
for(int j=0; j<len; ++j){
col[i] += nums[j][i];
}
}
int mx = 0, r = 0, c = 0;
for(int i=0; i<len; ++i){
for(int j=0; j<len; ++j){
if(row[i] + col[j] - nums[i][j] > mx){
mx = row[i] + col[j] - nums[i][j];
r = i;
c = j;
}
}
}
cout<< r+1 << " " << c+1 <<endl;
vector<vector<int>> newNums;
for(int i=0; i<len; ++i){
if(i == r) continue;
vector<int> line;
for(int j=0; j<len; ++j){
if(j == c) continue;
line.push_back(nums[i][j]);
}
newNums.emplace_back(line);
}
// helper(newNums); //递归只能过30%，消耗过多的栈空间
return newNums;
}
int main(){
int len;
cin >> len;
vector<vector<int>> nums(len);
for(int i=0; i<len; ++i){
vector<int> line(len);
for(int j=0; j<len; ++j){
int n; cin >> n;
line[j] = n;;
}
nums[i] = std::move(line);
}
while(!(nums = helper(nums)).empty()) ; // 迭代不消耗额外栈空间， 100%
}
第三题， 真不是暴力...
#include <iostream>
#include <unordered_map>
#include <stack>
#include <climits>
using namespace std;
int main()
{
int total; cin >> total;
while(total--){
unordered_map<int, int> mp; // event_id, begin_time
stack<pair<int, int>> stk; // begin_time, cost_time
int id = INT_MAX;
int mx = 0;
int item; cin >>item;
while(item--){
int t, e, s;
cin >> t >> e >> s;
if(s == 0){
mp.insert({e, t});
}else if(s == 1){
int curTotalTime = t - mp[e];
int curSelfTime = curTotalTime;
while(!stk.empty() && stk.top().first > mp[e]){
curSelfTime -= stk.top().second;
stk.pop();
}
stk.push({mp[e], curTotalTime});
if(curSelfTime > mx){
mx = curSelfTime;
id = e;
}else if(curSelfTime == mx && e <id){
id = e;
}
}
}
cout<< id <<endl;
}
}
全部评论
(0) 回帖