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;
}