Codeforces Round #590 (Div. 3) Editorial
Codeforces Round #590 (Div. 3) Editorial
不要因为走得太远，就忘记为什么出发！
Problem A
题目大意:商店有n件商品，每件商品有不同的价格，找出一个最小的可能值price，使得price * n >= sum，sum指的是原来商品价格的总和。
知识点：模拟
思路：求出sum/n向上取整即可，有两种方法。一是使用ceil()函数，但注意ceil()返回的是向上取整后的浮点数，所以要进行强制类型转换；二是直接向下取整，然后用if语句判断，防止精度损失。
#include <bits/stdc++.h>
using namespace std;
int q,n,sum;
int main(){
scanf("%d",&q);
while(q--){
scanf("%d",&n);
sum = 0;
for(int i = 0;i < n;i++){
int x;
scanf("%d",&x);
sum += x;
}
printf("%d\n",(int)ceil(1.0 * sum / n));
/*int ans = sum / n;
if(ans * n >= sum){
printf("%d\n",ans);
}
else printf("%d\n",ans + 1);
*/
}
return 0;
}
Problem B1 B2
题目大意：有一台能显示至多k条短信的手机，每条短信对应的朋友编号不同，在某天你会收到n条短信。如果某条短信的发件人已存在于屏幕中，则无事发生。否则，如果短信条数已满k条，那么会删去最后一条短信，然后让这条短信显示在屏幕的第一位，其他短信依次后移。求收到n条短信后屏幕的短信情况，并按顺序输出每条短信的发件人。
知识点：模拟，STL
个人思路：n，k在hard版本中数量级达到2e5的级别，如果用map标记可能会达到最坏时间复杂度 O(n^2) ，当时第一反应是离散化标记，O(1)查询，上deque模拟短信情况（实际上就是一个队列），最后反向输出。
题解思路：运用STL中的set进行标记，用队列模拟，用vector存储并输出答案，代码比较简洁
mycode:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n,k,x;
int num[maxn],tp[maxn],id[maxn],re[maxn];
bool ok[maxn];
map<int,int> mp;
deque<int> q;
int main() {
scanf("%d %d",&n,&k);
for(int i = 0;i < n;++i){
scanf("%d",&num[i]);
tp[i] = num[i];
}
sort(tp,tp + n);
int m = unique(tp,tp + n) - tp;
for(int i = 0;i < m;i++){
mp[tp[i]] = i + 1;
re[i + 1] = tp[i];
}
for(int i = 0;i < n;++i) id[i] = mp[num[i]];
for(int i = 0;i < n;i++){
x = id[i];
if(q.size() < k){
if(ok[x] == 0){
q.push_back(x);
ok[x] = 1;
}
else continue;
}
else{
if(ok[x] == 1) continue;
else{
int y = q.front();
q.pop_front();
ok[y] = 0;
q.push_back(x);
ok[x] = 1;
}
}
}
printf("%d\n",q.size());
while(!q.empty()){
int x = q.back();
q.pop_back();
x = re[x];
printf("%d%c",x,q.size() == 0?'\n':' ');
}
return 0;
}
solution:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
queue<int> q;
set<int> vals;
for (int i = 0; i < n; ++i) {
int id;
cin >> id;
if (!vals.count(id)) {
if (int(q.size()) >= k) {
int cur = q.front();
q.pop();
vals.erase(cur);
}
vals.insert(id);
q.push(id);
}
}
vector<int> res;
while (!q.empty()) {
res.push_back(q.front());
q.pop();
}
reverse(res.begin(), res.end());
cout << res.size() << endl;
for (auto it : res) cout << it << " ";
cout << endl;
return 0;
}
Problem C
题目大意：给出一个2*n的块中每一格的管子类型，判断水流能否从(1,0)流向(2,n + 1)。
知识点：思维
思路：观察发现，1，2之间，3，4，5，6之间可以通过旋转获得彼此，所以本质上只有两种类型的管子。遇到第一种类型的管子我们只能让它朝右，让水流往右流（显然其他方向是不可能的）；遇到第二种类型的管子，水流只能进行上下移动，也就是说，如果(1,k)处是第二种类型的管子，那么(2,k)处也必须是第二种类型的管子，水流所在层数发生变化。如果最后水流位于第二层，并且流到n+1列，则为可行解。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int q,n;
char s[2][maxn];
bool check(){
int pos = 0,i = 0;
for(pos = 1;pos <= n;pos++){
if(s[i][pos] - '0' < 3) continue;
if(s[i ^ 1][pos] - '0' < 3) return false;
i ^= 1;
}
if(pos == n + 1 && i == 1) return true;
return false;
}
int main(){
scanf("%d",&q);
while(q--){
scanf("%d",&n);
for(int i = 0;i < 2;i++) scanf("%s",s[i] + 1);
if(check()) printf("%s\n","YES");
else printf("%s\n","NO");
}
return 0;
}
Problem D
题目大意：给出一个只含小写字母的字符串s，有q次询问，两种操作。操作一是改变某个位置的字符，操作二是统计某段子串的字符种类，对于操作二，输出答案。
知识点：STL，树状数组
思路：开26个vector套set，存储每一种小写字母的出现位置，利用set增加、删除、查询均为O(logn)的性质优化复杂度。对于操作一，删除原来的字符的位置，加入新的字符的位置即可；对于操作二，利用lower_bound()二分查找大于等于l的第一个数，如果这个数<=r，则该段区间存在该字符。
据说还可以用BIT和线段树做，速度更快。DFS貌似也可以解
时间复杂度：O(nlogn*AL)，AL是字母的数量=26
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
char s[maxn];
int q,len,x,pos,l,r;
vector<set<int> > v(26);
int main(){
scanf("%s",s);
len = strlen(s);
for(int i = 0;i < len;i++){
v[s[i] - 'a'].insert(i);
}
scanf("%d",&q);
while(q--){
scanf("%d",&x);
if(x == 1){
char c;
scanf("%d",&pos);
cin >> c;
--pos;
v[s[pos] - 'a'].erase(pos);
s[pos] = c;
v[c - 'a'].insert(pos);
}
else{
scanf("%d %d",&l,&r);
--l,--r;
int cnt = 0;
for(int i = 0;i < 26;i++){
set<int>::iterator it;
it = v[i].lower_bound(l);
if(it != v[i].end() && *it <= r) cnt++;
}
printf("%d\n",cnt);
}
}
return 0;
}
最新文章
- ComboTree 的json格式和引用
- 转：ASP.NET MVC利用TryUpdateModel来做资料更新 (一)
- [C++][代码库]Vector3空间向量类
- Selenium2Library系列 keywords 之 _SelectElementKeywords 之 page_should_not_contain_list(self, locator, message='', loglevel='INFO')
- Hadoop 2.4.0全然分布式平台搭建、配置、安装
- 关于MapReduce
- jquery ajax post, get, javascript ajax post, get 处理
- 【Java】使用Runtime执行其他程序
- netstat简介
- mycat环境搭建
- 1、let const
- 《Effective Java 第三版》新条目介绍
- 【Hive学习之八】Hive 调优【重要】
- muduo网络库学习笔记(五) 链接器Connector与监听器Acceptor
- linux下mysql重置密码并且远程可以访问
- nyoj1076-方案数量 【排列组合 dp】
- Spark你需要知道这些
- 对于Redis的了解
- storm架构及原理
- GIT团队实战