【CF1483B】Playlist

· · 题解

传送门

ARC掉分后脑子抽，2C卡了1h，最后2：05的时候pp了这个题最后成功上分

话说我是样例RE一个，就加个特判，然后最后一遍pp还A了？

不难想到维护一个链表代表当前的歌曲链表，然后问题就在与我们需要每次快速找到最近的需要删除的数，不妨先处理所有 gcd(a_i,a_{i+1})=1 的 i 写一个链表，从链表第一项开始计算，计算完以后看 a_i 和 next_{a_i}（即第一个链表，实际中的下一项）是否为 1. 如果为 1，我们不删除链表二中的节点 i，遍历下一个。否则，i 不会再删除它后面的，我们删除掉链表二中的节点 i，遍历下一个。

注意点：

  1. 如果预处理时没有符合条件的 i（链表二为空），直接输出 0.

  2. 注意删除链表和跳转的先后顺序等。

  3. 不删除链表二的节点 i 的时候，若链表二只剩下 i 一项，下一次还是跳转到 i 而不是跳转到 0 导致错误的中断循环。

  4. 若删除链表二的节点 i，出现 3 的情况，那么直接中断循环。

这个 DS 题好像我用的 DS 是最平凡的，这个 D 比 C 友好多了吧，Div2好像都被 C 恶心到了都没人做 D 这个大水题（）

#include<bits/stdc++.h>
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(ll i=(a);i>=(b);i--)
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
#define next Cry_For_theMoon
#define il inline
#define pb(x) push_back(x)
#define mapit map<int,int>::iterator
#define vit vector<int>::iterator
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double db;
using namespace std;
const int MAXN=1e5+10;
ll T,n,a[MAXN];
ll pre1[MAXN],next1[MAXN],pre2[MAXN],next2[MAXN],ret;
vector<int>ans;
ll gcd(ll a,ll b){
    if(!b)return a;
    return gcd(b,a%b);
}
void Delete(int i){
    int p=pre1[i],n=next1[i];
    pre1[i]=next1[i]=0;
    next1[p]=n;
    pre1[n]=p; 
}
void Delete2(int i){
    int p=pre2[i],n=next2[i];
    pre2[i]=next2[i]=0;
    next2[p]=n;
    pre2[n]=p;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;ret=0;ans.clear();
        rep(i,1,n){
            cin>>a[i];
            next1[i]=i+1;
            pre1[i]=i-1;
            pre2[i]=next2[i]=0;
        }
        pre1[1]=n;next1[n]=1;
        int last=0,head=0;
        rep(i,1,n){
            if(gcd(a[i],a[next1[i]])==1){
                if(!last){
                    head=i;
                }else{
                    pre2[i]=last;
                    next2[last]=i;
                }
                last=i;
            }
        }
        pre2[head]=last;
        next2[last]=head;
        if(!head){
            printf("0\n");continue; 
        }
        int tmp=head;
        while(tmp){
            ret++,ans.pb(next1[tmp]);
            if(next1[tmp]==tmp)break;
            if(next2[tmp]==next1[tmp]){Delete2(next2[tmp]);}
            Delete(next1[tmp]);
            if(next2[tmp]){
                if(gcd(a[tmp],a[next1[tmp]])!=1){
                    ll t=next2[tmp];
                    Delete2(tmp);
                    if(tmp==t)break;
                    tmp=t;
                }else{
                    tmp=(next2[tmp])?next2[tmp]:tmp;
                }
            }else break;
        }
        cout<<ret<<' ';
        for(vit it=ans.begin();it!=ans.end();it++){
            cout<<*it<<' ';
        }
        cout<<'\n';
    }
    return 0;
}