水题，把a累加，然后向上取整(double)a/5，把b累加，然后向上取整(double)b/10，然后判断a+b是不是大于n即可
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main(){ double a1,a2,a3; double b1,b2,b3; int n; cin >>a1 >> a2 >> a3 >>b1 >> b2 >> b3>> n; int cnt = ceil((a1+a2+a3)/5)+ceil((b1+b2+b3)/10); if(cnt > n) cout <<"NO"<<endl; else cout<<"YES"<<endl; }
题目的意思是：
给两个字符串s和t，对字符串s可以进行下面操作（注意每种操作可以进行无限次）
- 删除s的一个字符，如果只做这种操作，输出automation
- 交换s的任意两个字符，如果只做这种操作，输出array
- 如果既要删除又要交换，则输出both
- 如果上面操作无法完成，则输出need tree
解题思路：
（1）首先判断s和t的长度，如果s的长度比t的长度小，则上面的操作都无法完成如果s的长度大于t的长度，则需要删除字符
（2）将s中不属于t内的字符删除，这剩下的字符为str
（3）统计str和t中各自字符串出现的次数，
如果中的字符不在str中，即strCnt.size() < tCnt.size()，则上面操作无法完成。
如果tCnt中某字符的个数大于strCnt的字符的个数，则上面的操作无法完成。
如果strCnt中存在字符的个数大于tcnt的相应字符的个数，则必须要删除s的字符。
如果s的所有字符的个数和t的所有字符的个数相等，则只需要交换即可
（4）最后通过在str中使用两个指针i,index，i指向str,index指向t，遍历str，如果t[index]==str[i],则index++； 最后判断index是否指向t的末尾，如果是，则只需要删除字符即可，否则既要删除又要交换字符。
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <map> using namespace std; int main(){ string s,t; cin >>s >>t; bool needTree = false,automatonFlag = false; if(s.length() < t.length()) needTree = true; else if(s.length() >t.length()) automatonFlag = true; string str=""; for(int i = 0 ; i < s.length(); ++ i ){ if(t.find(s[i])!=string::npos) str+=s[i]; } map<char,int> strCnt,tCnt; for(int i = 0 ; i < str.length(); ++ i) strCnt[str[i]]++; for(int i = 0 ; i < t.length(); ++ i) tCnt[t[i]]++; if(strCnt.size()!=tCnt.size()) needTree = true; else{ for(map<char,int>::iterator iter = tCnt.begin(); iter!=tCnt.end(); iter++){ if(iter->second > strCnt[iter->first]) {needTree = true;break;} if(iter->second < strCnt[iter->first]) automatonFlag = true; } } if(needTree) cout<<"need tree"<<endl; else{ if(!automatonFlag) cout<<"array"<<endl; else{ int i = 0,index = 0; for(int i = 0 ; i < str.length() && index < t.length(); ++i){ if(t[index] == str[i]) index++; } if(index < t.length()) cout<<"both"<<endl; else cout<<"automaton"<<endl; } } }
题目的简化意思是：
给你一个直方图，每次只能用画笔刷一行（注意是连在一起的）或者1竖，求至少要刷多少次能把这个直方图刷完
解题思路是
每次取min(a1,a2,...an),然后水平刷min(a1,a2,...an)次，刷完后，相当于每个直方条少了ai-min(a1,a2....an)(i=0..n-1)，这时候这些直方条就会被高度为0的直方条隔开，然后对每个部分，进行递归调用，算出次数，注意每次还要和right-left+1（相当于每直方条都刷一次）比较，然后取小值。
#include <iostream> #include <vector> #include <algorithm> using namespace std; int solve(vector<int>& a,int left, int right){ if(right< left) return 0; int minv = *min_element(a.begin()+left,a.begin()+right+1); int res = minv, index = left; for(int i = left; i<=right; ++i) a[i]-=minv; for(int i = left; i<= right; ++ i){ if(a[i] == 0 ){ if(index < i) { res+=solve(a,index,i-1); } index = i+1; } } res+=solve(a,index,right); return min(res,right-left+1); } int main(){ int n; cin >> n ; vector<int> a(n,0); for(int i = 0 ; i < n; ++ i) cin >> a[i]; cout<<solve(a,0,n-1)<<endl; }
求二维数组第k小值，用优先权队列取每个元素的下面和右边的元素插入队列，结果超时。由于用优先权队列其时间复杂度为klognm,而k<=nm则最坏时间复杂度是nmlog(nm)，肯定超时
#include <iostream> #include <vector> #include <cmath> #include <queue> #include <functional> #define LL long long using namespace std; struct Point{ int row; int col; Point(int x=0, int y =0 ):row(x), col(y){} bool operator<(const Point& a) const{ return (LL)row*(LL)col > (LL)a.row*(LL)a.col; } }; int main(){ int n, m; LL k; cin >> n >> m >>k; vector<vector<bool> > visit(n+1,vector<bool>(m+1,false)); priority_queue<Point> que; que.push(Point(1,1)); visit[1][1] = true; LL res = 0; for(int i = 0 ; i <k; ++i){ Point tmp = que.top();que.pop(); res = (LL)tmp.row*(LL)tmp.col; Point a(tmp.row+1,tmp.col),b(tmp.row,tmp.col+1); if(a.row <= n && a.col<=m && !visit[a.row][a.col]){que.push(a);visit[a.row][a.col] = true;} if(b.row<=n && b.col<=m && !visit[b.row][b.col]) {que.push(b);visit[b.row][b.col] = true;} } cout<<res<<endl; }
现在利用二分搜索。
假设对任意给一个数x，如何判断nxm二维数组中小于x的个数？
注意由于对第i行第j列的数是i*j，则j=x/i表示x在第i行的位置，也就是在该行第j列之前的位置都是小于x的
所以遍历每行，然后累加min(m,x/i)即可，则即是小于x的个数。
#include <iostream> #include <vector> #include <algorithm> #define LL long long using namespace std; LL n,m,k; LL calc(LL x){ LL cnt = 0; for(LL i = 1; i <= n; ++ i ) cnt += min(m,x/i); return cnt; } int main(){ cin >> n >>m >>k; LL left = 1, right = n*m; while(left<=right){ LL mid = (left+right)/2; if(calc(mid) >=k) right = mid-1; else left = mid+1; } cout<<right+1<<endl; }
题目的意思：
给定一个整数X，X0=[X]， Xi = [...]由Xi-1各个数的因子组成，求Xk，注意Xk中元素的个数最多为100000
解题思路：
本题先求出X1，即先求出X1的因子，然后对X每个因子进行深搜，直到k=0或者x=1，这样求出每个因子的k，但深搜要注意剪枝，题目要求的Xk的因子数不多余100000，故当搜索的因子数到达100000，就把后面的因子剪掉。这样可以避免超时
#include <iostream> #include <vector> #include <algorithm> #include <vector> #define LL long long using namespace std; LL limit = 1e5; vector<LL> divs,res; bool solve(LL x, LL k){ if(k == 0 || x == 1){ res.push_back(x); return res.size() >= limit; } for(int i = 0 ;i < divs.size(); ++ i){ if(divs[i] > x) break; if(x%divs[i] == 0){ if(solve(divs[i],k-1)) return true; } } return false; } int main(){ LL x,k; cin >> x >> k; for(LL i = 1; i*i <= x; ++ i){ if(x%i == 0){ divs.push_back(i); if(i*i != x) divs.push_back(x/i); } } sort(divs.begin(),divs.end()); solve(x,k); for(int i = 0 ; i < res.size(); ++ i){ if(i) cout<<" "; cout<<res[i]; } cout<<endl; return 0; }