CF686div3 vp A~D

以你之姓@ 2024-03-26 15:12 77阅读 0赞

**哈哈，快一个月没v了，我是什么纯的**

**依旧是好死，不会\*1300**

**这省赛还玩nm**

**E后面单独补，因为我要睡觉了**

![7904d35e6caac8ca103f36660140c5ca.png][]

[Problem - A - Codeforces][]

题意：

让你构造一个排列，使其不存在p\[i\]=i

思路：

典

如果是偶数，直接倒序输出

如果是奇数，在倒序输出的基础上交换中间那两个数

Code：

#include <bits/stdc++.h>
    using namespace std;
    
    int n;
    void solve(){
        cin>>n;
        if(n%2==0){
            for(int i=n;i>=1;i--) cout<<i<<" \n"[i==1];
        }else{
            for(int i=n;i>=n/2+2;i--) cout<<i<<" ";
            cout<<n/2<<" "<<n/2+1<<" ";
            for(int i=n/2-1;i>=1;i--) cout<<i<<" \n"[i==1];
        }
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - B - Codeforces][]

题意：

让你找到最小的数，使得其出现次数只有一次，若没找到就输出-1

思路：

模拟

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e5+10;
    
    
    map<int,int> mp,mp2;
    int n;
    int a[mxn];
    void solve(){
        mp.clear();mp2.clear();
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++,mp2[a[i]]=i;
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++){
            if(mp[a[i]]==1){
                cout<<mp2[a[i]]<<'\n';
                return;
            }
        }
        cout<<-1<<'\n';
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - C - Codeforces][]

题意：

给定一个序列，可以选定一个数，这个数把序列隔成好几段，问你段数最少是多少

思路：

一开始写的是枚举选的是哪个数，然后去双指针，然后t了

应该是贪心，段数最少，就是让连通块最少，那就是把相同的数看作一个数，然后去看哪个数出现次数最少就好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e5+10;
    map<int,int> mp;
    int n;
    int a[mxn];
    void solve(){
        mp.clear();
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            if(a[i]==a[i-1]) continue;
            mp[a[i]]++;
        }
        mp[a[1]]--;
        mp[a[n]]--;
        int ans=1e9;
        for(auto it:mp){
            ans=min(ans,it.second+1);
        }
        cout<<ans<<'\n';
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - D - Codeforces][]

哈哈，不会的1300

题意：

给定一个n，让你构造一串因子链，使得其前一个能整除后一个，然后链的长度最大

思路：

一开始想的是给n质因数分解，然后从p1已知这样添上去，相邻元素之间乘一个质因子

但是这样难以保证乘积为n

正解是取幂最大的p，其中幂为k，然后平摊k-1个p，最后一个数就是n/p^(k-1)

**其实就是把前后整除这个条件特殊化成前后相等了**，然后最后一项是n/p^(k-1)，因为p一定能整除n/p^(k-1)

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=2e5+10;
    int n,len=0,mx=-1e9,mx_p,tmp;
    int vis[mxn],prime[mxn];
    void p_init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    void solve(){
        mx=-1e9;
        cin>>n;
        tmp=n;
        for(int i=1;i<=len;i++){
            int p=prime[i];
            int s=0;
            while(n%p==0){
                n/=p;
                s++;
            }
            if(s>mx){
                mx=s;
                mx_p=p;
            }
        }
        if(mx>=2){
            cout<<mx<<'\n';
            for(int i=1;i<mx;i++) cout<<mx_p<<" ",tmp/=mx_p;
            cout<<tmp<<'\n';
        }else{
            cout<<1<<'\n';
            cout<<tmp<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;cin>>__;
        p_init(2e5);
        while(__--)solve();return 0;
    }

[7904d35e6caac8ca103f36660140c5ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/81618e7a4c2f4194ba6d4b0f1b078999.png
[Problem - A - Codeforces]: https://codeforces.com/contest/1454/problem/A
[Problem - B - Codeforces]: https://codeforces.com/contest/1454/problem/B
[Problem - C - Codeforces]: https://codeforces.com/contest/1454/problem/C
[Problem - D - Codeforces]: https://codeforces.com/contest/1454/problem/D