AcWing 第62场周赛
本文最后更新于 722 天前,其中的信息可能已经有所发展或是发生改变。

4500. 三个元素


原题链接

Origional Linl


思想

  • pair<int,int> a存储值和对应下标
  • 对值进行排序,遍历找到三个不同值
  • 若存在则输出下标

代码

#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> st存储当前可以构成一套的数,当st.size() == n说明可以构成一套
  • vis[i]标记i是否在st中,num存储目前为止的未成套的数及其数量
  • 若读入的数未在st中,则将其加入并标记
  • 每次加入st对其进行判断:
    • st.size() == n说明已成套
    • string s标记是否成套,在st.size() == n时进行标记
    • stvis清空,遍历num将未成套的数加入st并标记
  • 输出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值
  • 由题可知序列单调递增
  • 则$mean(s)$一定是从前面获取一段连续的数+该最大值
  • 加进来的数和平均值比较
    • 如果新加进来的数比平均值小,那么这个当前状态子集元素的平均值一定会减小
    • 如果相等,平均值不变
    • 如果新加进来的数比平均值大,平均值会增加

代码

#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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇