CF 1148 题解

Author： RainAir
发布时间：September 17, 2020
890views
No comments
3723 words
Categories：题解

A

贪心想法先把 $a$ 和 $b$ 拼成若干个 $ab$，然后如果有剩余的可以在对应的开头/结尾放，所以答案是 $c+\min(a,b)+[a \neq b]$。

B

枚举我们强制让这个人 $A \to B$ 选择那一班航班起飞（这样就相应 ban 掉了一些航班），然后双指针维护处对应的 $B \to C$ 最近能从哪里开始起飞，就是查一个第 $x$ 大的问题了。因为排好序了可以 $O(1)$ 直接求出。

C

我们只需要实现 $5$ 步内交换两个数的算法就好了：

我们考虑交换 $(x,y)$ 的最一般的情况：$1 < x \leq \frac{n}{2} < y < n$，这样我们需要交换 $(x,n),(y,1),(1,n),(x,n),(y,1)$。需要额外判断一下 $x < y < \frac{n}{2}$，$\frac{n}{2} > x > y$，$x = 1,y = n$ 的各种情况，都能在五步内完成。

然后直接每次将对应的值交换到正确的位置上就好了。

D

要看到能任意交换顺序这一点。不然就只会垃圾做法了。

我们将 $a_i < b_i$ 和 $a_i > b_i$ 分成两组，发现两组内的数不能放在一起，于是可以分开处理。

以解决 $a_i < b_i$ 为例：

一个 sb 的想法是树状数组优化 dp，但是真的是这样么？

我们考虑相邻的两个元素 $a_1 < b_1 > a_2 < b_2$，那么如果 $b$ 越小 $a$ 就越小，所以我们肯定按照 $b$ 从大到小排序，发现 $b_1 > b_2,a_2 < b_2 \Rightarrow b_1 > a_2$，这样就全满足了。

另一组讨论是类似的。

这个问题还是要好好读题，然后在草稿纸上画一画这些组，发现一些性质就好了。

E

又是可以随便排列顺序。。读题一定要仔细了。。

那么我们肯定贪心从大到小排序然后考虑调整：如果一个位置想要减小，一定是找一个后面想要变大的匹配。所以我们记一下当前想要变小的位置和要变小多少，每次如果 $s_i > t_i$ 就把 $i$ 扔到集合内，否则就不断从集合头匹配即可。如果找不到前面的一个数匹配或者是最后没有匹配完就无解。

感觉操作次数 $\leq 2n$ 啊不知道范围是个什么迷惑操作。。

F

考虑先使用归纳法证明一定有解：

首先如果 bit 只有 $1$ 位一定有解：直接翻转即可。

那么假设 bit 有 $k$ 位有解，接下来我们想证明 $k+1$ 位有解。发现当前翻转 $k+1$ 位上的若干位数不会影响最高位 $\leq k$ 的数，所以判断一下是否需要翻转即可。

需要注意虽然我们每次决定是否翻转只是看最高位是 $k+1$ 的数，但是翻转的时候是要全部都翻转的。

G

好神仙啊。。。

首先发现如果得到一个 $k$ 的好的集合，那么一定能得到 $\leq k$ 的好的集合。但是得到了大小为 $k$ 的不好的集合不代表你能得到 $\leq k$ 的好的集合。

首先我们考虑 $O(n^2)$ 的暴力怎么做（小蒟蒻这个都不会）：

如果 $k$ 是偶数：我们任意选出 $k$ 个数，每次先判断一下是不是组成一个团，如果组成直接输出，否则一定存在一对点之间没有边，删除这两个点，并且找这个点的两个相邻的点放入这个集合。如果操作 $\frac{k}{2}$ 次仍然无解，被删除的点的集合一定满足是不好的。

如果 $k$ 是奇数：我们一开始找到三个点 $u,v,w$ 满足 $(u,v),(v,w)$ 边不存在，删去这三个点做子问题，可以得到一个偶数大小的不好集合，最后考虑是否要加入这三个点即可。选择三个点而不是一个点的原因是三个点可以自由决定是否加两个/三个，但是一个点加入之后你不知道是不是会破坏不好的性质。

如果找不到这三个点，考虑这个图的补图，补图一定是森林，好的集合对应一个独立集，黑白染色可知一定存在 $\geq \frac{n}{2}$ 的独立集，只需要在一开始判掉有好集合的情况就好了。

道理我都懂，但是正解怎么做呢？我们可以用一个复杂度 $O(2^8 n \log n)$ 的复杂度解决。

首先可以将所有数的唯一分解后的形式的 $>0$ 的指数都改成 $1$，不难发现这样不影响图的形态。

考虑整张图的形态显然是不行的，那么遇到这种问题一定先考虑某些特殊量是否能被算出：首先我们先考虑如何快速算一个点的度数，可以用 $f_i$ 记录包含因子 $i$ 的数的个数然后 $2^8$ 运用容斥原理算出。

类似地我们选出三个点 $u,v,w$，满足 $(u,v),(v,w)$ 边不存在，并删去这三个点。

我们对剩下的点，设和其他所有点都有连边的数量是 $b$，如果 $b \geq k$ 直接输出答案即可，否则剩下的 $n-3-b$ 个元素组成的集合是不好的。因为 $u,v,w$ 之间无边，所以可以全部加入到任意不好的集合内而不破坏性质。考虑有 $b < k \leq \frac{n}{2}$ ，所以 $n-3-b+3 = n-b > n-\frac{n}{2} = \frac{n}{2} \geq k$，所以一定存在一个大小 $\geq k$ 的不好的集合。

现在我们就要考虑如何删除一些数而不破坏性质：我们设 $f(r)$ 表示 $[1\ldots r]$ 数能选出最大的不好的集合，通过二分找到第一个位置 $r$ 满足 $f(r) \geq k,f(r-1) < k$，观察一下可以发现这说明了有 $f(r)-f(r-1)-1$ 个点与前 $r-1$ 个点连边，但是与 $r$ 点不连边，并且 $r$ 点也是不好点。所以我们可以删除这些点而不影响性质（因为其他点都是连到这个点上的，不依赖于它而保持不好的性质），我们发现至多删除 $f(r)-f(r-1)-2$ 个点（因为如果全删了可能 $r$ 点就是好点了），所以经过删除后我们能得到大小为 $k$ 或者 $k+1$ 的集合，这时候我们一开始选出的三个点就派上用场了：我们可以选择保留两个点或三个点而不破坏性质（这些点之间没有连边），按照需求调整即可。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int MAXM = 1e7 + 5;

bool p[MAXM];
int prime[MAXM],cnt;

inline void prework(){
    FOR(i,2,MAXM-1){
        if(!p[i]) prime[++cnt] = i;
        for(int j = 1;j <= cnt && 1ll*i*prime[j] < MAXM;++j){
            p[i*prime[j]] = 1;
            if(!(i%prime[j])) break;
        }
    }
}

int n,k;
int a[MAXN];
std::vector<int> G[MAXN],v[MAXM];

inline void reduce(int i){
    int x = a[i],q = std::sqrt(1.0*x);
    FOR(j,1,cnt){
        int p = prime[j];
        if(p > x || p > q) break;
        if(!(x%p)){
            int c = 0;v[j].pb(i);G[i].pb(p);
            while(!(x%p)) ++c,x /= p;
            --c;while(c--) a[i] /= p;
        }
    }
    if(x != 1){
        G[i].pb(x);
        int p = std::lower_bound(prime+1,prime+cnt+1,x)-prime;
        v[p].pb(i);
    }
}

int f[MAXM];
// 求有多少个和它不互质 枚举gcd容斥即可
int b[MAXN];

inline int deg(int i){
    int sz = G[i].size(),res = 0;
    FOR(S,1,(1<<sz)-1){
        int t = 1;
        FOR(j,0,sz-1){
            if((S>>j)&1) t *= G[i][j];
        }
        int gx = f[t];
        if((__builtin_popcount(S)-1)&1) gx = -gx;
        res += gx;
    }
    return res-1;
}

inline void add(int i,int d){
    int sz = G[i].size();
    FOR(S,1,(1<<sz)-1){
        int t = 1;
        FOR(j,0,sz-1){
            if((S>>j)&1) t *= G[i][j];
        }
        f[t] += d;
    }
}

int m;

inline int chk(int x){
    FOR(i,x+1,m) add(b[i],-1);
    int c = 0;
    FOR(i,1,x) c += (deg(b[i]) == x-1);
    FOR(i,x+1,m) add(b[i],1);
    return x-c+3;
}

bool vis[MAXN];
std::mt19937 g(19260);
int tt[MAXN];

int main(){
    prework();
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d",a+i),tt[i] = a[i],reduce(i);
    FOR(i,1,cnt){
        if(v[i].size() >= k){
            FOR(j,0,k-1) printf("%d ",v[i][j]);
            puts("");
            return 0;
        }
    }
    FOR(i,1,n) add(i,1);
    int u=-1,v=-1,w=-1;
    FOR(i,1,n){
        if(n-1-deg(i) >= 2){
            v = i;
            FOR(j,1,n){
                if(j == i) continue;
                if(std::__gcd(a[i],a[j]) > 1) continue;
                if(u == -1) u = j;
                else w = j;
            }
            break;
        }
    }
    add(u,-1);add(v,-1);add(w,-1);
    if(k == 3){
        printf("%d %d %d\n",u,v,w);
        return 0;
    }
    FOR(i,1,n){
        if(i == u || i == v || i == w) continue;
        b[++m] = i;
    }
    int c = 0;
    FOR(i,1,m) if(deg(b[i]) == m-1) ++c;
    if(c >= k){
        c = 0;
        FOR(i,1,m){
            if(deg(b[i]) == m-1) ++c,printf("%d ",b[i]);
            if(c == k) break;
        }
        puts("");
        return 0;
    }
    int l = 1,r = m,ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(chk(mid) >= k) ans = mid,r = mid-1;
        else l = mid+1;
    }
    int _ = chk(ans),t = _-chk(ans-1)-2,d = _-k;
    FOR(i,ans+1,m) add(b[i],-1);
    FOR(i,1,ans) vis[i] = (deg(b[i]) != ans-1);
    FOR(i,1,ans-1){
        if(!d) break;
        if(t <= 0) break;
        if(!vis[i]) continue;
        if(std::__gcd(a[b[i]],a[b[ans]]) != 1) continue;
        if(deg(b[i]) != ans-2) continue;
        --d;--t;vis[i] = 0;
    }
    FOR(i,1,ans) if(vis[i]) printf("%d ",b[i]);
    if(!d) printf("%d ",u);
    printf("%d %d\n",v,w);
    return 0;
}

H

还在咕咕咕

Last modification：September 17th, 2020 at 08:12 am

如果觉得我的文章对你有用，请随意赞赏

CF 1148 题解

RainAir • 2020 年 09 月 17 日

A

贪心想法先把 $a$ 和 $b$ 拼成若干个 $ab$，然后如果有剩余的可以在对应的开头/结尾放，所以答案是 $c+\min(a,b)+[a \neq b]$。

B

C

我们只需要实现 $5$ 步内交换两个数的算法就好了：

然后直接每次将对应的值交换到正确的位置上就好了。

D

要看到能任意交换顺序这一点。不然就只会垃圾做法了。

我们将 $a_i < b_i$ 和 $a_i > b_i$ 分成两组，发现两组内的数不能放在一起，于是可以分开处理。

以解决 $a_i < b_i$ 为例：

一个 sb 的想法是树状数组优化 dp，但是真的是这样么？

另一组讨论是类似的。

这个问题还是要好好读题，然后在草稿纸上画一画这些组，发现一些性质就好了。

E

又是可以随便排列顺序。。读题一定要仔细了。。

感觉操作次数 $\leq 2n$ 啊不知道范围是个什么迷惑操作。。

F

考虑先使用归纳法证明一定有解：

首先如果 bit 只有 $1$ 位一定有解：直接翻转即可。

需要注意虽然我们每次决定是否翻转只是看最高位是 $k+1$ 的数，但是翻转的时候是要全部都翻转的。

G

好神仙啊。。。

首先发现如果得到一个 $k$ 的好的集合，那么一定能得到 $\leq k$ 的好的集合。但是得到了大小为 $k$ 的不好的集合不代表你能得到 $\leq k$ 的好的集合。

首先我们考虑 $O(n^2)$ 的暴力怎么做（小蒟蒻这个都不会）：

道理我都懂，但是正解怎么做呢？我们可以用一个复杂度 $O(2^8 n \log n)$ 的复杂度解决。

首先可以将所有数的唯一分解后的形式的 $>0$ 的指数都改成 $1$，不难发现这样不影响图的形态。

类似地我们选出三个点 $u,v,w$，满足 $(u,v),(v,w)$ 边不存在，并删去这三个点。

#include <bits/stdc++.h>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e5 + 5;
const int MAXM = 1e7 + 5;

bool p[MAXM];
int prime[MAXM],cnt;

inline void prework(){
    FOR(i,2,MAXM-1){
        if(!p[i]) prime[++cnt] = i;
        for(int j = 1;j <= cnt && 1ll*i*prime[j] < MAXM;++j){
            p[i*prime[j]] = 1;
            if(!(i%prime[j])) break;
        }
    }
}

int n,k;
int a[MAXN];
std::vector<int> G[MAXN],v[MAXM];

inline void reduce(int i){
    int x = a[i],q = std::sqrt(1.0*x);
    FOR(j,1,cnt){
        int p = prime[j];
        if(p > x || p > q) break;
        if(!(x%p)){
            int c = 0;v[j].pb(i);G[i].pb(p);
            while(!(x%p)) ++c,x /= p;
            --c;while(c--) a[i] /= p;
        }
    }
    if(x != 1){
        G[i].pb(x);
        int p = std::lower_bound(prime+1,prime+cnt+1,x)-prime;
        v[p].pb(i);
    }
}

int f[MAXM];
// 求有多少个和它不互质 枚举gcd容斥即可
int b[MAXN];

inline int deg(int i){
    int sz = G[i].size(),res = 0;
    FOR(S,1,(1<<sz)-1){
        int t = 1;
        FOR(j,0,sz-1){
            if((S>>j)&1) t *= G[i][j];
        }
        int gx = f[t];
        if((__builtin_popcount(S)-1)&1) gx = -gx;
        res += gx;
    }
    return res-1;
}

inline void add(int i,int d){
    int sz = G[i].size();
    FOR(S,1,(1<<sz)-1){
        int t = 1;
        FOR(j,0,sz-1){
            if((S>>j)&1) t *= G[i][j];
        }
        f[t] += d;
    }
}

int m;

inline int chk(int x){
    FOR(i,x+1,m) add(b[i],-1);
    int c = 0;
    FOR(i,1,x) c += (deg(b[i]) == x-1);
    FOR(i,x+1,m) add(b[i],1);
    return x-c+3;
}

bool vis[MAXN];
std::mt19937 g(19260);
int tt[MAXN];

int main(){
    prework();
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d",a+i),tt[i] = a[i],reduce(i);
    FOR(i,1,cnt){
        if(v[i].size() >= k){
            FOR(j,0,k-1) printf("%d ",v[i][j]);
            puts("");
            return 0;
        }
    }
    FOR(i,1,n) add(i,1);
    int u=-1,v=-1,w=-1;
    FOR(i,1,n){
        if(n-1-deg(i) >= 2){
            v = i;
            FOR(j,1,n){
                if(j == i) continue;
                if(std::__gcd(a[i],a[j]) > 1) continue;
                if(u == -1) u = j;
                else w = j;
            }
            break;
        }
    }
    add(u,-1);add(v,-1);add(w,-1);
    if(k == 3){
        printf("%d %d %d\n",u,v,w);
        return 0;
    }
    FOR(i,1,n){
        if(i == u || i == v || i == w) continue;
        b[++m] = i;
    }
    int c = 0;
    FOR(i,1,m) if(deg(b[i]) == m-1) ++c;
    if(c >= k){
        c = 0;
        FOR(i,1,m){
            if(deg(b[i]) == m-1) ++c,printf("%d ",b[i]);
            if(c == k) break;
        }
        puts("");
        return 0;
    }
    int l = 1,r = m,ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(chk(mid) >= k) ans = mid,r = mid-1;
        else l = mid+1;
    }
    int _ = chk(ans),t = _-chk(ans-1)-2,d = _-k;
    FOR(i,ans+1,m) add(b[i],-1);
    FOR(i,1,ans) vis[i] = (deg(b[i]) != ans-1);
    FOR(i,1,ans-1){
        if(!d) break;
        if(t <= 0) break;
        if(!vis[i]) continue;
        if(std::__gcd(a[b[i]],a[b[ans]]) != 1) continue;
        if(deg(b[i]) != ans-2) continue;
        --d;--t;vis[i] = 0;
    }
    FOR(i,1,ans) if(vis[i]) printf("%d ",b[i]);
    if(!d) printf("%d ",u);
    printf("%d %d\n",v,w);
    return 0;
}

H

还在咕咕咕

CF 1148 题解

A

B

C

D

E

F

G

H

Leave a Comment Cancel reply

I'm back

NOI2021 退役记

SDOI2020 退役记

点双连通分量 & 圆方树学习笔记

CSP2019 游记

「CF1097G」Vladislav and a Great Legend

点分治初探

多次询问的最长瓶颈路

「ZR 18 省选 3」题解

降智比赛题解

CF 1148 题解

A

B

C

D

E

F

G

H