D.Playlist(Технокубок2021Финал)题解xiaodangao

题目链接：D. Playlist
题意：略
思路：模拟，先思考我们需要完成什么操作，因为数组是$1e5$级别的，所以用遍历的方式一次次的删除，太慢，所以我们需要一种数据结构，支持插入，删除，查找，遍历，且最坏时间复杂度是$\Theta(logn)$，平衡树恰巧能够干这个活，所以我们选择用set来处理，具体思路如下，第一次遍历整个数组，将$gcd(a_{i-1},a_i) = 1$的$a_{i-1}$位置的下标放入平衡树，这些都是我们需要删除的位置，因为第一次遍历之后，所有需要删除的位置都已经找到，而且该位置只会减少不会增加，接下来就是模拟，设该位置为p，他下一个位置为s，如果$gcd(a_p,a_s) = 1$那么将s位置永久在平衡树里删除，如果不为1，那么下一次遍历需要删除位置前，将p删除，因为p已经不能够满足删除下一个数这个操作，他和普通的数组一样了。
$Code1:$

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define x first
#define y second
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
using namespace std;

const int N = 1e5+10;
int _,n;

set<int>S,G;
bool st[N];
int gos[N];int a[N];
vector<int>ans;
int q[N],tot  = 0;
void solve(){
    read(_);
    while(_--){
        G.clear();ans.clear();
        S.clear();
         read(n);
        rep(i,1,n){
            read(a[i]);
            S.insert(i);//一颗平衡树存所有可用下标
            st[i] = false;
        }
        rep(i,2,n){
            if(__gcd(a[i],a[i-1]) == 1){
                G.insert(i-1);//另一颗平衡树存所有删除下标
            }
        }
        if(__gcd(a[n],a[1]) == 1)G.insert(n);//循环
        //删除1个
        //int cnt = 0;
        while(true){
            tot = 0;
            bool flag = false;
            for(auto p:G){
                if(q[tot] == p)continue;
                if(S.size() == 0){flag = false;break;}//及时退出
                auto s = S.upper_bound(p);//在所有可用下标中找下一个
                if(s == S.end()){
                    s = S.begin();//循环
                }
                if(__gcd(a[*s],a[p]) != 1){//如果不满足gcd为1，先将其下标存入一个数组，最后进行删除，如果现在进行删除，那么会Runtime Error
                    q[++tot] = p;
                    //G.erase(p);
                    //if(G.size()==0){flag = false;break;}
                    continue;
                }
                if(G.find(*s)!=G.end()){//如果在另一颗平衡树中找到了他
                    //G.erase(*s);
                    q[++tot] = *s;
                    flag = true;
                    ans.pb(*s);
                    S.erase(*s);//if(G.size() == 0){flag = false;break;}
                }
                else {
                    flag = true;
                    ans.pb(*s);
                    S.erase(*s);
                }
            }
            rep(i,1,tot){
                G.erase(q[i]);
            }
            if(S.empty()||flag == false||G.empty())break;

        }
        write((int)ans.size());pc(' ');
        for(auto p:ans)write(p),pc(' ');
        pc('\n');
    }
}
signed main(){solve();return 0;}

利用vector进行存储
$Code2:$

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define x first
#define y second
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}
using namespace std;

const int N = 1e5+10;
int _,n;

set<int>S;
bool st[N];
int gos[N];int a[N];
vector<int>G,ans;
void solve(){
    read(_);
    while(_--){
        G.clear();ans.clear();
        S.clear();
         read(n);
        rep(i,1,n){
            read(a[i]);
            S.insert(i);
            st[i] = false;
        }
        rep(i,2,n){
            if(__gcd(a[i],a[i-1]) == 1){
                G.pb(i-1);
            }
        }
        if(__gcd(a[n],a[1]) == 1)G.pb(n);
        //删除1个
        while(true){
            if(S.empty())break;
            bool flag = false;
            for(int i=0;i<(int)G.size();++i){
                //if(G.size()<)
                int p = G[i];
                if(S.find(p) == S.end()){
                    G.erase(G.begin()+i);
                    i--;
                    continue;
                }
                int idx = -1;
                if(p==*--S.end()){
                    idx = *S.begin();
                }
                else {
                    idx = *S.upper_bound(p);
                }
                int k = a[idx];
                if(__gcd(k,a[p]) == 1){
                    ans.pb(idx);
                    //printf("%d %d\n",k,a[p]);
                    S.erase(idx);
                    flag = true;
                }
                else {
                    G.erase(G.begin()+i);
                    i--;
                }
            }
            if(flag == false)break;
        }
        write((int)ans.size());pc(' ');
        for(auto p:ans)write(p),pc(' ');
        pc('\n');
    }
}
signed main(){solve();return 0;}

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章