Hướng dẫn giải của 2023C. Khô ráo và ẩm ướt
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Gợi ý 1
Bài này là một bài tập implement cơ bản
Gợi ý 2
Ta có thể sử dụng phương pháp tham lam để giải bài tập này
Lời giải
Đề bài nói, tháng ẩm ướt là tháng có chuỗi ngày ít nhất K, và trong tất cả các ngày đó ngày nào cũng mưa, và tổng lượng mưa phải ít nhất là S. Vì thế ta có thể sử dụng phương pháp tham để để lấy toàn bộ chuỗi ngày mưa liên tục, từ đó sẽ giúp tăng khả năng chuỗi ngày ít nhất là K, và tổng lượng mưa ít nhất là S. Tiếp đó nếu gặp ngày nắng thì ta reset các thông số lại từ đầu. Khi một ngày nào đó, điều kiện thoả mãn, thì ta sẽ tạo một biến check để lưu đó là tháng ẩm ướt.
Code
/**
* Create: Sunday 2023-12-24-11.15.54 GMT+7
* Title : kho_rao_va_am_uot
* Author:
*****/
#include <bits/stdc++.h>
#line 10 "tranxuantruong"
#ifndef MY_TEMPLATE
#define TranXuanTruong main()
#define Get_better(...) ios::sync_with_stdio(0); cin.tie(0);
using namespace std;
template <typename T> ostream& operator << (ostream& os, const stack <T> &stack_) {os << "["; int n = (int) stack_.size(); vector <T> archive (n); stack <T> stackCopy_ (stack_); for (int i=0; i<n; ++i) {archive[stackCopy_.size()-1]=stackCopy_.top(); stackCopy_.pop();} if (!archive.empty()) {for (auto it=archive.begin(); it!=archive.end()-1; ++it) {os <<*it <<", ";} os <<archive.back();} os <<" "; return os;}
template <typename T> ostream& operator << (ostream& os, const queue <T> &queue_) {os << "->["; int n = (int) queue_.size(); vector <T> archive (n); queue <T> queueCopy_ (queue_); for (int i=0; i<n; ++i) {archive[queueCopy_.size()-1]=queueCopy_ .front(); queueCopy_.pop();} if (!archive.empty()) {for (auto it=archive.begin(); it!=archive.end()-1; ++it) {os <<*it <<", ";} os <<archive.back();} os <<" "; return os;}
template <typename T> ostream& operator << (ostream& os, const priority_queue <T,vector<T>,greater<T>>&Queue_) {os << "["; int n = (int) Queue_.size(); vector <T> archive (n); priority_queue<T,vector<T>,greater<T>> QueueCopy_ (Queue_); for (int i=0; i<n; ++i) {archive[QueueCopy_.size()-1]=QueueCopy_.top(); QueueCopy_.pop();} if (!archive.empty()) {for (auto it=archive.begin(); it!=archive.end()-1; ++it) {os <<*it <<", ";} os <<archive.back();} os <<" "; return os;}
template <typename T> ostream& operator << (ostream& os, const priority_queue <T> &Queue_) {os << "["; int n = (int) Queue_.size(); vector <T> archive (n); priority_queue<T> QueueCopy_ (Queue_); for (int i=0; i<n; ++i) {archive[QueueCopy_.size()-1]=QueueCopy_.top(); QueueCopy_.pop();} if (!archive.empty()) {for (auto it=archive.begin(); it!=archive.end()-1; ++it) {os <<*it <<", ";} os <<archive.back();} os <<" "; return os;}
template <typename T> ostream& operator << (ostream& os, const vector <T> &vector_) {os << "["; if (!vector_ .empty()) {for (auto it = vector_ .begin(), i=0; i< (int) vector_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (vector_ .rbegin());} os << "]"; return os;}
template <typename T> ostream& operator << (ostream& os, const deque <T> &deque_) {os << "["; if (!deque_ .empty()) {for (auto it = deque_ .begin(), i=0; i< (int) deque_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (deque_ .rbegin());} os << "]"; return os;}
template <typename T> ostream& operator << (ostream& os, const set <T> &set_) {os << "["; if (!set_ .empty()) {for (auto it = set_ .begin(), i=0; i< (int) set_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (set_ .rbegin());} os << "]"; return os;}
template <typename T> ostream& operator << (ostream& os, const multiset <T> &multiSet_) {os << "["; if (!multiSet_.empty()) {for (auto it = multiSet_.begin(), i=0; i< (int) multiSet_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (multiSet_ .rbegin());} os << "]"; return os;}
template <typename T, typename _> ostream& operator << (ostream& os, const map <T, _> &map_) {os << "["; if (!map_ .empty()) {for (auto it = map_ .begin(), i=0; i< (int) map_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (map_ .rbegin());} os << "]"; return os;}
template <typename T, typename _> ostream& operator << (ostream& os, const multimap <T, _> &multiMap_) {os << "["; if (!multiMap_.empty()) {for (auto it = multiMap_.begin(), i=0; i< (int) multiMap_ .size()-1; ++i, ++it) {os <<*it <<", ";} os << * (multiMap_ .rbegin());} os << "]"; return os;}
template <typename T, typename _> ostream& operator << (ostream& os, const pair <T, _> &pair_) {os << "{"; {os <<pair_.first; os <<":"; os <<pair_.second;} os << "}"; return os;}
template <typename T> void quick_debug (ostream& os, const char *name, const T &value) {os <<" " << name <<" = " <<value <<endl <<endl;};
template <typename T, typename... Args> void quick_debug (ostream& os, const char *name, const T &value, Args&&... args) {os <<" "; while (*name != ',') {os << *name++;} os << " = " << value << endl; quick_debug (os, name + 1, args...);};
; istream& operator >> (istream& is, __int128 & x) { __int128 sign=1; x=0; char c=is.get(); for( ;!isdigit(c); ){if(c=='-'){sign=-1;}c=is.get();} for( ;isdigit(c); ){x=(x<<3)+(x<<1)+(c^'0');c=is.get();} x*=sign; return is; }
; ostream& operator << (ostream& os, __int128 x) { if(x==0){return os<<"0";} int sign=1; if(x<0){sign=-1; x=-x;} string s=""; for( ;x!=0; ){s+='0'+x%10;x/=10;} if(sign<0){s+='-';} reverse(s.begin(), s.end()); return os<<s;}
#define endl '\n'
#define int __int128
#define hien(...) cerr <<__LINE__ <<" " __FILE__ ":" <<endl; quick_debug (cerr, " "#__VA_ARGS__, __VA_ARGS__)
#endif
TranXuanTruong{
Get_better(học thêm một chút nữa đi, 9000);
int t; cin >> t;
for(int i=0; i<t; ++i){
int n; cin >> n;
int k; cin >> k;
int s; cin >> s;
vector <int> a(n);
for(int i=0; i<n; ++i){
cin >> a[i];
}
int check=false;
int demNgay=0;
int tong=0;
for(int i=0; i<n; ++i){
if(a[i]==0){
demNgay=0;
tong=0;
}
else{
demNgay+=1;
tong+=a[i];
}
if(demNgay>=k && tong>=s){
check=true;
}
}
if(check){
cout <<"AM_UOT" <<endl;
}
else{
cout <<"KHO_RAO" <<endl;
}
}
return 0;
}
Bình luận