【AcWing 62nd Weekly Game】

$更好的阅读体验$

---

4500. 三个元素

---

原题链接

Origional Linl

---

思想

• pair<int,int> aStores the value and the corresponding subscript
• 对值进行排序,Traverse to find three distinct values
• If it exists, output the subscript

---

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

pair<int,int> a[N];

void solve(){
    
    
    int n;
    
    cin >> n;
    
    for(int i = 0; i < n; i ++){
    
        int x;
        cin >> x;
        a[i] = {
    x, i + 1};
    }
    
    sort(a,a + n);
    
    int cnt = 0;
    int flag = a[0].first;
    
    int ans[10];
    
    ans[cnt] = a[0].second;
    
    for(int i = 1; i < n; i ++){
    
        if(a[i].first != flag){
    
            flag = a[i].first;
            ans[++cnt] = a[i].second;
            if(cnt == 2) break;
        }
    }
    
    if(cnt == 2){
    
        for(int i = 0; i <= cnt ; i ++) cout << ans[i] <<" ";
    }
    else cout << -1 << " " << -1 <<" " << -1;
    
}

int main(){
    
    
    solve();
    
    return 0;
    
}

---

4501. 收集卡牌

---

原题链接

Origional Link

---

思想

• vector<int> stStores the number of numbers that can currently be formed into a set,当st.size() == nInstructions can form a set
• vis[i]标记i是否在st中,numStores the number of uncompleted sets so far and their quantities
• If the read number does not existst中,then add it and mark it
• 每次加入st对其进行判断：
  • 若st.size() == nDescription is complete
  • 用string sWhether the mark is complete,在st.size() == n时进行标记
  • 将st和vis清空,遍历numAdd uncompleted numbersst并标记
• 输出s即为答案

---

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int n, m;

map<int,int> num;

bool vis[N];

void solve(){
    
    
    cin >> n >> m;
    
    string s(m,'0');
    
    vector<int> st;
    
    for(int i = 0; i < m; i ++){
    
        int x;
        cin >> x;
        num[x]++;
        if(!vis[x]){
    
            vis[x] = 1;
            num[x] --;
            st.push_back(x);
            if(st.size() == n){
    
                st.clear();
                s[i] = '1';
                for(int i = 1; i <= n; i ++) vis[i] = 0;
                for(auto &j : num){
    
                    if(j.second > 0){
    
                        j.second --;
                        st.push_back(j.first);
                        vis[j.first] = 1;
                    }
                }
            }
        }
    }
    
    
    cout << s << endl;
    
}

int main(){
    
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    
    return 0;
    
}

---

AcWing 4502. 集合操作

---

原题链接

Origional Link

---

思想

• $max(s)-mean(s)$的最大可能值,取决于$mean(s)$最小z值
• It can be seen from the question that the sequence is monotonically increasing
• 则$mean(s)$It must be a continuous number from the front+该最大值
• The added number is compared to the average
  • If the newly added number is smaller than the average,Then the average value of the current state subset elements must decrease
  • 如果相等,平均值不变
  • If the newly added number is larger than the average,The average will increase

---

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int idx, cnt = 1;

double a[N],s[N];

double check(int u){
    
    return a[idx] - (s[u-1]+a[idx])/u;
}

void solve(){
    
    
    int _;
    
    cin >> _;
    
    while (_ --){
    
        
        int op;
        
        cin >> op;
        
        if(op == 1){
    
            cin>>a[++ idx];
            s[idx]=s[idx - 1]+a[idx];
        }
        else{
    
            while(cnt + 1 <= idx && check(cnt + 1) > check(cnt)) ++cnt ;
            printf("%.6lf\n", check(cnt));
        }
    }
    
}

int main(){
    
   
    solve();
   
    return 0;
}