首页 > 代码库 > Codeforces Round #256 (Div. 2)
Codeforces Round #256 (Div. 2)
A - Rewards
水题，把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;}
B - Suffix Structures
题目的意思是：
给两个字符串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; } }}
C - Painting Fence
D - Multiplication Table
求二维数组第k小值，用优先权队列取每个元素的下面和右边的元素插入队列，结果超时。由于用优先权队列其时间复杂度为klognm,而k<=nm则最坏时间复杂度是nmlog(nm)，肯定超时
#include <iostream>#include <vector>#include <cmath>#include <queue>#include <functional>#define LL long longusing 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 longusing 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;}