出题人题解｜欢乐赛#34

桌子乱的反义词

2024-11-21 16:14:16

发布于：马来西亚

13阅读

0回复

0点赞

ACGO欢乐赛34

T1

方法一：使用数组统计

观察到 $1 \leq A_i \leq 10^5$ ，所以可以开一个长度为 $10^5$ 的数组进行统计。

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

int n;
bool cnt[100010];

int main(){
   cin >> n;
    while(n -- ){
        int x;
        cin >> x;
        cnt[x] ++;
    }
    cout << accumulate(cnt + 1, cnt + 1 + 100000, 0);
    return 0;
}

方法二：使用set统计

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

int main(){
    int n;
    set<int>s;
    cin >> n;
    while(n -- ){
        int x;
        cin >> x;
        s.insert(x);
    }
    cout << s.size();
    return 0;
}

方法三：使用map统计

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

int main(){
    int n;
    map<int,int>mp;
    cin >> n;
    while(n -- ){
        int x;
        cin >> x;
        mp[x] ++;
    }
    cout << mp.size();
    return 0;
}

直接按照题目要求模拟即可

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

int n;
string s;

int main(){
    cin >> n >> s;
    int x = 0, y = 0;
    for(auto it : s){
        if(it == 'D') y --;
        if(it == 'R') x ++;
        if(it == 'L') x --;
        if(it == 'U') y ++;
    }
    printf("(%d,%d)",x,y);
    return 0;
}

根据分析，最小值的最大值，可以联想到二分算法。需要考虑的有序性，在题目中寻找。

我们发现， $d_1+d_2+d_3$ 的结果是一定的，为 $n-3$ 。

考虑枚举三者之中最小的间隔，但是不确定元素不止有间隔本身大小，还有间隔之间的差值，这个思路舍弃。

现在考虑二分枚举三个间隔之间的最小的那个差值。

证明：

设 $d_1,d_2,d_3$ 三个间隔从小到大。

枚举三者之间最小差值为 $x$ ，那么第二个差值也是不小于 $x$ ，否则当前假设 $x$ 不成立。

设 $d_1 = l$ ,则如果要满足假设必须满足 $d_2$ 最小也是 $l+x$ ,同理 $d_3$ 最小也是 $l+2*x$ 。此外，对于 $d3$ 还可以通过 $n-3-l-(l+x)$ ，即为 $n-3-2*l-x$ 。

如果根据总长度算出来的理论高度，不小于满足最小间隔差值是 $x$ 要求的最小高度，即为 $n-3-2*l-x \ge l+2*x$ 化简得到 $n-3\ge 3*l+3*x$

看似存在两个不确定元素，间隔本身大小，还有间隔之间的差值，但是要求取最小值的最大值，也就是说 $x$ 要最大，满足题目的前提下是 $l = 0$ 。即 $n-3\ge 3*x$ 。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,MOD = 1e9+7;
map<char,int>mp1,mp2;
int n,a[200];
string s,t;
bool check(int x){
    return 3*x <= n-3;
}
int main(){
    cin >>n;
    n -= 3;
    int l = 0,r = n / 3;
    while(l<r){
        int mid = (l+r+1) / 2;
        if(check(mid)) l = mid;//mid 满足要求，把l指向mid位置
        else r = mid-1;
    }
    cout << l;
    
    return 0;
}

当然这题你也可以用结论写，结论自己摸索哈。

埃氏筛法，时间复杂度 $O(nloglogn)$

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

const int N = 1000010;
int n;
bool st[N];

int main(){
    cin >> n;
    int cnt = 0;
    for(int i = 2; i <= n; i ++ ){
        if(!st[i]){
            cnt ++;
            for(int j = i + i; j <= n; j += i){
                st[j] = 1;
            }
        }
    }
    cout << cnt;
    return 0;
}

利用两个map维护即可。

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

void solve(){
    int n;
    string s1, s2;
    cin >> n >> s1 >> s2;
    map<char,int>mp1,mp2;
    for(auto it : s1){
        mp1[it] ++;
    }
    for(auto it : s2){
        mp2[it] ++;
    }
    if(mp1 == mp2) cout << "YES\n";
    else cout << "NO\n";
}

int main(){
    int tt;
    cin >> tt;
    while(tt -- ){
        solve();
    }
    return 0;
}

你也可以不用map，开两个数组，映射到对应的ASCII即可。

#include <bits/stdc++.h>
using namespace std;
int a[200], b[200];
void solve(){
    int n;
    string s1, s2;
    cin >> n >> s1 >> s2;
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    for(auto it : s1){
        a[it] ++;
    }
    for(auto it : s2){
        b[it] ++;
    }
    bool f = 1;
    for(int i = 33; i <= 126; i ++ ){
        if(b[i] != a[i]){
            f = 0;
            break;
        }
    }
    if(f) cout << "YES\n";
    else cout << "NO\n";
}

int main(){
    int tt;
    cin >> tt;
    while(tt -- ){
        solve();
    }
    return 0;
}

直接输出即可

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

int main(){
    cout << "Good Luck!";
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

ACGO欢乐赛34

T1

热门讨论