【解题报告】CF练一下题 | 难度CF2500左右

代码

#include
using namespace std;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}
typedef long long ll;
const int MAX = 4e3+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

namespace Fast_IO{ ///orz laofu
    const int MAXL((1 << 18) + 1);int iof, iotp;
    char ioif[MAXL], *ioiS, *ioiT, ioof[MAXL],*iooS=ioof,*iooT=ioof+MAXL-1,ioc,iost[55];
    char Getchar(){
        if (ioiS == ioiT){
            ioiS=ioif;ioiT=ioiS+fread(ioif,1,MAXL,stdin);return (ioiS == ioiT ? EOF : *ioiS++);
        }else return (*ioiS++);
    }
    void Write(){fwrite(ioof,1,iooS-ioof,stdout);iooS=ioof;}
    void Putchar(char x){*iooS++ = x;if (iooS == iooT)Write();}
    inline int read(){
        int x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }
    inline long long read_ll(){
        long long x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }
    /**
    #define lll __int128
    inline lll read_lll(){
        lll x=0;for(iof=1,ioc=Getchar();(ioc<'0'||ioc>'9')&&ioc!=EOF;)iof=ioc=='-'?-1:1,ioc=Getchar();
        if(ioc==EOF)exit(0);
        for(x=0;ioc<='9'&&ioc>='0';ioc=Getchar())x=(x<<3)+(x<<1)+(ioc^48);return x*iof;
    }*/
    template <class Int>void Print(Int x, char ch = '\0'){
        if(!x)Putchar('0');if(x<0)Putchar('-'),x=-x;while(x)iost[++iotp]=x%10+'0',x/=10;
        while(iotp)Putchar(iost[iotp--]);if (ch)Putchar(ch);
    }
    void Getstr(char *s, int &l){
        for(ioc=Getchar();ioc==' '||ioc=='\n'||ioc=='\t';)ioc=Getchar();
        if(ioc==EOF)exit(0);
        for(l=0;!(ioc==' '||ioc=='\n'||ioc=='\t'||ioc==EOF);ioc=Getchar())s[l++]=ioc;s[l] = 0;
    }
    void Putstr(const char *s){for(int i=0,n=strlen(s);i<n;++i)Putchar(s[i]);}
} // namespace Fast_IO
using namespace Fast_IO;


int dp[MAX][805];
int pre[MAX][MAX];

int now_K;

int s(int L,int R){
    return pre[R][R] - pre[L-1][R] - pre[R][L-1] + pre[L-1][L-1];
}



void solve(int L,int R,int qL,int qR){
    if(L > R)return;
    int mid = L + R >> 1;
    int ID  = qL;
    int tmp = INF;
    for(int i = qL;i <= qR && i <= mid;++i){
        int val = s(i,mid) + dp[i-1][now_K-1];
        if(val < tmp){
            tmp = val;
            ID = i;
        }
    }
    dp[mid][now_K] = tmp;

    solve(L,mid-1,qL,ID);
    solve(mid+1,R,ID,qR);
}

int main()
{
    int n,k;n = read();k = read();

    for(int i = 0;i <= n;++i)
    for(int j = 0;j <= k;++j)
        dp[i][j] = INF;
    dp[0][0] = 0;

    for(int i = 1;i <= n;++i)
    for(int j = 1;j <= n;++j){
        int x = read();
        pre[i][j] = x + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
    }

    for(int i = 1;i <= k;++i){
        now_K = i;
        solve(1,n,1,n);
    }

    int ans = dp[n][k] / 2;
    cout << ans;


    return 0;
}
/**

*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

Least Cost Bracket Sequence | CF3D

题意

• Least Cost Bracket Sequence | CF3D
  给定一个长度为 $n$ 的字符串，只包含 '(',')','?' 三种
  第 $i$ 个问号改成左括号的花费为 $a_i$，改成右括号的花费为 $b_i$
  问你把所有的问号都改成括号后，整个字符串满足一个合法的括号序列，求最小花费值
  若无法完成，输出 -1
• $n\le 5\times 10^4$
  $1\le a_i,b_i\le 10^6$

思路 | 贪心

• 难度 $2600$ 的贪心…
  我们记一个 $pre$ 表示前缀和，遇到左括号加一，遇到右括号减一。
  合法的括号序列即要求每个位置的 $pre$ 都非负，且最后位置的 $pre=0$。
• 我们假设每个问号位置都为右括号。
  如果 $pre<0$ 了，那么我们需要让之前某个问号变为的右括号改成左括号。
  即，我们每次需要额外代价最小的那个右括号改为左括号。
  用一个优先队列维护即可。
  思维难度都在假设。

代码

• 时间复杂度：$O(n\log n)$

#include
using namespace std;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}
typedef long long ll;
const int MAX = 5e4+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;


char ss[MAX];
int aa[MAX],bb[MAX];

struct node{
    int val,pos;
    bool operator < (const node &ND)const{
        return val > ND.val;
    }
};

priority_queue<node>Q;
char ans[MAX];
int main()
{
    scanf("%s%*c",ss+1);
    int n = strlen(ss+1);
    int cnt = 0;
    for(int i = 1;i <= n;++i){
        if(ss[i] == '?')cnt++;
        ans[i] = ss[i];
    }
    for(int i = 1;i <= cnt;++i){
        scanf("%d%d",&aa[i],&bb[i]);
    }
    int pre = 0;
    bool can = true;
    ll fen = 0;
    int ccnt = 0;
    for(int i = 1;i <= n;++i){
        if(ss[i] == '(')pre++;
        else if(ss[i] == ')'){
            pre--;
        }else{
            ccnt++;
            ans[i] = ')';
            fen += bb[ccnt];
            Q.push((node){aa[ccnt] - bb[ccnt],i});
            pre--;
        }
//        show(i,pre);
        if(pre < 0){
            if(Q.empty())can = false;
            else{
                fen += Q.top().val;
                ans[Q.top().pos] = '(';
                Q.pop();
                pre+=2;
            }
        }
    }
    if(pre > 0)can = false;

    if(!can)puts("-1");
    else{
        printf("%lld\n",fen);
        printf("%s",ans+1);
    }

    return 0;
}
/**

*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

Buy Low Sell High | CF865D

题意

• Buy Low Sell High | CF865D
  给定长度为 $n$ 的数组 $p_n$
  位置 $i$ 可以变成左括号，花费 $p_i$
  位置 $i$ 可以变成右括号，收益 $p_i$
  当然这个位置你也可以不管它。
  求最后是一个合法的括号序列，求收益最大是多少。
• $2\le n\le 3\cdot 10^5$
  $1\le p_i\le 10^6$

思路 | 贪心 | 可反悔贪心

• 这题是上一题的升级版诶… （我把题意转换过来了，题意是等价的）
  我们用上一题的思路貌似不能通过，因为有时候留着一些位置可以让总的收益更高
• 我们还是想一下怎么贪心。
  首先假设我们这个位置放右括号，若某个左边的空位置改成左括号让总收益更大，那我们就这么干。若左边有多个位置，我们选择左边花费最小的，这是一个贪心。
• 假设我们使用之前的位置 $i$，匹配当前的位置 $j$，于是收益为 $p[j]-p[i]$，但是有可能未来有一个位置 $k$，满足 $p[k]-p[i]$ 或者 $p[k]-p[j]$ 的收益更高，那么怎么办呢？
• 首先由于我们匹配了 $i,j$，当然应该满足 $p[j]>p[i]$
  若未来的 $k$ 匹配更优，那应该也满足 $p[k]>p[i]$
  即我们有 $i<j<k,p[i]<p[j]<p[k]$
• 目前 $k$ 改成和 $i$ 匹配的话，收益减去 $p[j]-p[i]$ 再加上 $p[k]-p[i]$ 即收益增加 $p[k]-p[j]$，即 可反悔贪心
  目前 $k$ 改成和 $j$ 匹配的话，是不优的，所以我们不会这样决策。
• 当前位置也可以空着，留着之后来匹配。
  注意：由于是可反悔贪心，我们这两种情况都要 push 进优先队列中去，而不是 $k$ 和 $i$ 匹配更优的话我们就一定让 $k$ 匹配掉了，因为有可能更后面的位置和 $i$ 匹配了把 $k$ 留下了。但暂时收益的话仍然是加进去的。

代码

• 时间复杂度：$O(n\log n)$

#include
using namespace std;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}
typedef long long ll;
const int MAX = 5e4+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

struct node{
    int val;
    bool operator <(const node &ND)const{
        return val < ND.val;
    }
};

priority_queue<node>Q;

int main()
{
    int n;scanf("%d",&n);
    ll now = 0;
    for(int i = 1;i <= n;++i){
        int c;
        scanf("%d",&c);
        if(i == 1){
            Q.push((node){-c});
        }else{
            int v = Q.top().val;
//            show(i,c,v);
            if(c + v > 0){
                now += c + v;
                Q.pop();
                Q.push((node){-c});		// 可反悔贪心
            }
            Q.push((node){-c});			// 空着
        }
//        show(i,now);
    }
    cout << now;
    return 0;
}
/**

*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

Nearest Leaf | CF1110F

题意

• Nearest Leaf | CF1110F
  $n$ 个点的一棵树，知道每个点的 $dfn$ 序，树有边权 $w_i$
  树的叶子就是度为 $1$ 的点，且这个树的根度不为 $1$
  两个点的距离为这两个点的简单路径的边权和
  $q$ 个询问，每个询问给定 $v,L,R$
  求 $v$ 号点距离 $x$ 的最近距离，其中 $dfn(x)\in [L,R]$ 且 $x$ 是一个叶子节点
• $3\le n\le 5\times 10^5$
  $1\le q\le 5\times 10^5$
  $1\le w_i\le 10^9$

思路 | 离线 | 线段树 | 换根

• 这题可以离线。想到换根这题就可以直接过了。
  首先我们计算根到每个叶子的距离，放在线段树里。
  注意到，$dfn$ 的性质，即可以使用线段树进行维护或者查询。
• 我们把根换到某个子树，那么某一段的距离减少 $w$，某一段的距离增加 $w$，即线段树加操作。
  我们把根换到 $v$，查询 $[L,R]$ 的叶子距离当前的最近距离，即线段树区间求最值。
  于是代码略。
• 注：给定 $dfn$ 的询问，直接考虑线段树。在线考虑不了，考虑离线，即换根。

Inversion SwapSort | CF1375E

题意

• Inversion SwapSort | CF1375E
  给定长度为 $n$ 的数组 $a_n$
  它有 $m$ 个逆序对 $(i,j)$，其中满足 $1\le i<j\le n,a[i]>a[j]$
  你需要给出这 $m$ 个逆序对的一个排列 $P$，第 $i$ 个逆序对为 $(L_i,R_i)$
  接下来进行 $m$ 次操作，第 $i$ 次操作交换 $a[L_i],a[R_i]$
  操作完成后，满足 $a_n$ 非递减。
• $1\le n\le 10^3$

思路 | 构造 | 排序

• 逆序对我们可以直接 $O(n^2)$ 求出，关键是怎么排列这个顺序
  对于目前的数组 $a[1]\sim a[n]$ ，我们知道里面最大的数字一定要交换到位置 $n$ 去，然后让问题规模变成 $b[1]\sim b[n-1]$。
  若 $a[n]$ 本来就是最大的数了，那么目前也没有 $(?,n)$ 的逆序对了，直接考虑子问题。
  否则，肯定有一些逆序对 $(?,n)$，我们目前只考虑这些逆序对。
• 在交换完这些逆序对的位置后，我们希望让 $b[1]\sim b[n-1]$ 仍然保持原先的一些性质，这样才是一个子问题。什么性质呢？即：
  $$\begin{gathered} 1\le i<j<n \\ 若a[i]\ge a[j]，则b[i]\ge b[j] \\ 若a[i]\le a[j]，则b[i]\le b[j] \end{gathered}$$
  即让这些数字的相对大小不变。因为最后是一个排序，排序只用考虑数字之间的相对大小，不用考虑绝对大小。
• 首先，目前 $(x,n)$ 的逆序对肯定满足 $a[x]>a[n]$ ，即大于 $a[n]$ 的所有位置都有一个逆序对，小于等于 $a[n]$ 的位置都没有逆序对。
  注意到，小于 $a[n]$ 的值目前我们不需要变换，也可以满足他们之前的相对大小不改变。
  大于等于 $a[n]$ 的值，我们需要依次让他们低一位，他们的相对大小才能不改变。
  举例： 6,2,1,5,7,3,4 我们需要变成 x,2,1,x,x,3,7（最大值放最后面，最小值不动），然后再调整成 5,2,1,4,6,3,7 ，即其他每个位置都顺次低一位，这样他们之间的相对顺序不变。
• 若有多个相同值的位置，我们记录他们的下标，若值相同，下标小的值我们记他们更小。
  这样的话，每次我们选择前面比他大的最大的位置 $p$，交换 $aa[p],aa[n]$ 即可。

代码

• 时间复杂度：$O(n^2\log n)$

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 1e5+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

ll qpow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a%MOD;a=a*a%MOD;n>>=1;}return res;}
ll qpow(ll a,ll n,ll p){a%=p;ll res = 1LL;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll npow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a;a=a*a;n>>=1;if(res<0||a<0)return 0;}return res;}
ll inv(ll a){/* */return qpow(a,MOD-2);}
ll inv(ll a,ll p){return qpow(a,p-2,p);}

int aa[MAX];
priority_queue<pair<int,int> >Q;
int main()
{
    int n;cin >>n;
    for(int i = 1;i <= n;++i){
        cin >> aa[i];
    }
    int cnt = 0;

    for(int i = 1;i <= n;++i){
        for(int j = i+1;j <= n;++j){
            if(aa[i] > aa[j]){
                cnt++;
            }
        }
    }
    cout << cnt << '\n';

    for(int i = n;i >= 2;--i){
        for(int j = 1;j < i;++j){
            if(aa[j] > aa[i]){
                Q.push(make_pair(-aa[j],-j) );
            }
        }
        while(!Q.empty()){
            int p = -Q.top().second;
            Q.pop();
            cout << p << " " << i << '\n';
        }
    }


    return 0;
}
/**
6 1 9 2 3 4 5

7
6 1 5 2 3 7 4

6
2 5 3 1 7 6

5 2 1 5 3 4
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

Arpa’s overnight party and Mehrdad’s silent entering | CF741C

题意

• Arpa’s overnight party and Mehrdad’s silent entering | CF741C
  有 $2n$ 个位置排成一个环，这些位置分为 $n$ 个对
  你需要让每个位置赋值 $1$ 或者 $2$，满足：
• 其中第 $i$ 个对为 $(a_i,b_i)$，必须满足这两个位置的值不同
• 环上，连续三个位置的值不能都相同
  若无解，输出 -1，否则输出一个构造解

思路 | 构造 | 二分图

• 两种颜色染色，优先考虑二分图！
  容易想到，$a_i,b_i$ 之间连一条边，表示他们的颜色不能相同。
• 考虑连续三个位置的值不能都相同怎么处理
  想到一种构造方案，我们连边所有的 $2k,2k-1$
  为什么这样一定是可行的呢？
• 首先，若无解，则二分图有奇环，否则是一定有解的。
  首先我们先连边 $2k,2k-1$，然后再连边所有的 $a_i,b_i$
  容易想到，每个点最多连出去两条边，即最终每个连通分量要么是一个链，要么是一个环
  链无所谓，我们考虑环。环的奇偶性即为环上点的个数的奇偶性。
  一开始的连边$2k,2k-1$，满足每个连通分量的点都为 $2$。后续的 $a_i,b_i$ 的连边，即合并了某两个连通分量，且这两个连通分量的点为偶数个，那么新的连通分量的点也是偶数个。于是一定有解。
  注意我们讨论的前提是点的度最大为 $2$
  代码略

Kuroni and the Punishment | CF1305F

题意

• Kuroni and the Punishment | CF1305F
  给定长度为 $n$ 的数组 $a_n$
  一次操作，可以让某个数字加一或者减一，注意操作后数字必须非负
  问你最少的操作次数，让数组的 $gcd>1$
• $2\le n\le 2\cdot 10^5$
  $1\le a_i\le 10^{12}$

思路 | 数学 | 随机化

• 假设 $gcd=2$，那么答案最大为 $n$，即这个数组中奇数的个数。那么我们需要求出 $<n$ 的答案。
• 考虑 $gcd=k$，那么我们很容易求出答案：
  a n s = ∑ i = 1 n { m i n ( a i % k , k − a i % k ) a i ≥ k k − a i a i < k ans=\sum_{i=1}^n
  {min(ai%k,k−ai%k)ai≥kk−aiai<k" role="presentation" style="position: relative;">{min(ai%k,k−ai%k)k−aiai≥kai<k$$\{\begin{array}{ll}min(a_i\mathrm{\%}k,k-a_i\mathrm{\%}k)& a_i\ge k\\ k-a_i& a_i<k\end{array}$$
  ans=i=1∑n​{min(ai​%k,k−ai​%k)k−ai​​ai​≥kai​<k​
• 注意到，首先枚举质因子肯定是优于枚举所有的因子的。
  $a_i$ 的最多质因子为 $12$ 个，总共的质因子最多为 $12n$，一次 $check$ 是 $O(n)$ 的，看起来 $O(12n^2)$，但是大多数操作算到一半我们的 $ans$ 就很大了，因此这里其实是算的很快的
  关键是我们算出这所有的质因子，不管是直接根号算还是使用 $Pollard\_Rho$ 都是 TL 飞起的。\
• 质因子有很多，但是我们感觉随便取一些就可以得到最小的答案了，这启发我们使用 随机化
  若答案 $<n$，那么至少有一半的位置最多被操作一次。
  那么我们枚举至多被操作一次的数字 $a_i$，就有二分之一的概率选中最优的那种操作的方案。
  于是我们可以枚举 $m$ 次，算对的概率即为 $1-\frac{1}{2^m}$
  我们可以 random_shuffle，然后选择前 $20$ 个数字，即随机选择了 $20$ 个数字
  然后枚举他们 $a_i+1,a_i,a_i-1$ 的所有质因子作为答案去 $check$ 即可
• 注：我选择 $10$ 个后 wa200 了，运气感人。

代码

• 时间复杂度：$O(60\times (\sqrt{10^{12}}+12n))$

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 2e5+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

ll qpow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a%MOD;a=a*a%MOD;n>>=1;}return res;}
ll qpow(ll a,ll n,ll p){a%=p;ll res = 1LL;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll npow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a;a=a*a;n>>=1;if(res<0||a<0)return 0;}return res;}
ll inv(ll a){/* */return qpow(a,MOD-2);}
ll inv(ll a,ll p){return qpow(a,p-2,p);}

ll aa[MAX];
map<ll,bool>M;

void check(ll x){
    for(ll i = 2;i * i <= x;++i){
        if(x % i == 0){
            M[i] = 1;
            while(x % i == 0){
                x /= i;
            }
        }
    }
    if(x > 1)M[x] = 1;
}

int main()
{
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;++i){
        scanf("%lld",&aa[i]);
    }
    random_shuffle(aa+1,aa+1+n);
    random_shuffle(aa+1,aa+1+n);
    random_shuffle(aa+1,aa+1+n);

    for(int i = 1;i <= min(20,n);++i){
        ll now = aa[i];
        if(now > 1){
            check(now);
        }
        now = aa[i]+1;
        if(now > 1){
            check(now);
        }
        now = aa[i]-1;
        if(now > 1){
            check(now);
        }
    }

    ll ans = n;
    for(auto [a,b] : M){
        ll tmp = 0;
        for(int i = 1;i <= n;++i){
            if(aa[i] <= a)
                tmp += (a - aa[i]);
            else
                tmp += min(aa[i] % a,a - aa[i] % a);
            if(tmp > ans)break;
        }
        ans = min(ans,tmp);
    }
    printf("%lld",ans);
    return 0;
}
/**

*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

Make It One | CF1043F

题意

• Make It One | CF1043F
  给定 $a_n$，求最小的子集大小，满足这个子集的元素的 $gcd=1$
  若无解，输出 $-1$
• $1\le n\le 3\times 10^5$
  $1\le a_i\le 10^5$

思路 | 数学 | 容斥

• 首先我们 -1 判断很简单，若 $a_n$ 的 $gcd>1$ 肯定是无解的
  考虑到，$a_i$ 最多有 $7$ 个不同的质因子，即答案 $\le 7$
• 假设目前的答案为 $k$，即我们能否找到 $k$ 个元素，让他们的 $gcd=1$
  非常套路的，我们令 $f(i)$ 表示 $gcd=i$ 的方案数，令 $F(i)$ 表示 $gcd$ 为 $i$ 的倍数的方案数
  $$f(i)=\sum _{i|j}\mu (\frac{j}{i})F(j)$$
• 即我们怎么快速算 $F(i)$，答案就是 $f(1)$
  我们记 $barr[i]$ 表示有多少个数为 $i$ 及其倍数，这里可以 $O(R\log R)$ 预处理得到
  即答案为 $C_{barr[i]}^k$，因为我们要选 $k$ 个数。
  若 $f(1)>0$ 表示可行。

代码

• 时间复杂度：$O(n\log n+R\log R)$

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 3e5+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

ll qpow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a%MOD;a=a*a%MOD;n>>=1;}return res;}
ll qpow(ll a,ll n,ll p){a%=p;ll res = 1LL;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll npow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a;a=a*a;n>>=1;if(res<0||a<0)return 0;}return res;}
ll inv(ll a){/* */return qpow(a,MOD-2);}
ll inv(ll a,ll p){return qpow(a,p-2,p);}

ll fac[MAX],ivfac[MAX];

void init(int n){
    fac[0] = 1;
    for(int i = 1;i <= n;++i)fac[i] = fac[i-1] * i % MOD;
    ivfac[n] = inv(fac[n]);
    for(int i = n - 1;~i;--i)ivfac[i] = ivfac[i+1] * (i+1) % MOD;
}

ll C(int n,int m){
    if(n < 0 || m > n)return 0;
    return fac[n] * ivfac[m] % MOD * ivfac[n - m] % MOD;
}


bool vis[MAX];
int prime[MAX];
int mu[MAX];
int cnt;
void shai(int n){
    mu[1] = 1;
    for(int i = 2;i <= n;++i){
        if(!vis[i]){
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1;j <= cnt && i * prime[j] <= n;++j){
            vis[i*prime[j]] = 1;
            if(i % prime[j])mu[i*prime[j]] = -mu[i];
            else {
            	mu[i*prime[j]] = 0;
                break;
            }
        }
    }
}

int barr[MAX];

ll F(int x,int shu){
    return C(barr[x],shu);
}

int main()
{
    shai(300000);
    init(300000);

    int n;scanf("%d",&n);

    int gcd = 0;

    for(int i = 1;i <= n;++i){
        int x;scanf("%d",&x);
        barr[x] = 1;
        gcd = __gcd(gcd,x);
    }

    if(gcd > 1){
        puts("-1");
        return 0;
    }

    for(int i = 1;i <= 300000;++i)
    for(int j = 2;i * j <= 300000;++j){
        barr[i] += barr[i*j];
    }

    for(int i = 1;i <= 7;++i){
        ll now = 0;
        for(int j = 1;j <= 300000;++j){
            now = (now + mu[j] * F(j,i) % MOD + MOD) % MOD;
        }
//        show(i,now);
        if(now > 0){
            printf("%d",i);
            break;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

Emotional Fishermen | CF1437F

题意

• Emotional Fishermen | CF1437F
  给定 $a_n$，你需要问你有多少种它的排列后的数组 $b_n$ ，满足：
  p r e [ i ] = max ⁡ j = 1 i { b [ i ] } , p r e [ 0 ] = 0 b [ i ] ≥ 2 ⋅ p r e [ i − 1 ] 或 者 2 ⋅ b [ i ] ≤ p r e [ i − 1 ] 成 立 pre[i] = \max_{j=1}^{i}\{ b[i]\},pre[0]=0\\ b[i] \ge 2\cdot pre[i-1] 或者 2\cdot b[i] \le pre[i-1] 成立 pre[i]=j=1maxi​{b[i]},pre[0]=0b[i]≥2⋅pre[i−1]或者2⋅b[i]≤pre[i−1]成立
• 方案数取模 $998244353$
  $2\le n\le 5\times 10^3$
  $1\le a_i\le 10^9$

思路 | dp | 组合数学

• 首先可对 $a_n$ 进行升序排序
  考虑计算 $dp[i]$ 表示处理完前 $i$ 个数，且放进去了 $a[i]$的方案数。 显然目前的 $pre[i]=a[i]$
  我们考虑每次从前面已处理到一半的数组中，新放进去一些数字。我们只要考虑新放进去数字的个数，他们的相对位置。
  想一下，目前有一些数字可能是放不进去的，放不进去的数字的值范围为 $(a[i]/2,a[i])$，容易发现他们的下边是连续的。且目前 $a[i]$ 一定是放在最后面的。
  我们记录 $lim[i]$ 表示最大的满足 $j$，满足 $2\cdot a[j]\le a[i]$
  那么，目前我们对于 $dp[i]$，我们放进去的数字的个数为 $\lim [i]+1$，其他的数字目前还放不进去。
• 我们考虑从 $dp[j]$ 转移到 $dp[i]$，当然 $j<i$ 且 $2\cdot a[j]\le a[i]$
  对于 $dp[j]$，能放进去的数的下标为 $[1,lim[j]]$；对于 $dp[i]$，能放进去的数的下标为 $[1,lim[i]]$
  即我们需要新/多放进去 $lim[i]-lim[j]-1$ 个数字。注意 $a[j]$ 放在哪里我们不知道，也需要额外考虑进去。但是 $a[i]$ 是放在最后的，不需要考虑。
  对于 $dp[j]$，我们已经放入了 $\lim [j]+1$ 个数字，一共有 $n$ 个数字，还剩下 $n-\lim [j]-1$ 个位置，其中最后的位置是放置 $a[i]$ 的，即我们还有 $n-\lim [j]-2$ 个位置。
  仍然注意，这里的位置是相对位置不是绝对位置。
  那么这些数字放进这些位置中，任意都可以摆放，方案数自然为 $A_{n-\lim [j]-2}^{lim[i]-lim[j]-1}$
  综上，我们的转移为：
  $$dp[i]=\sum _{j=0}^{\lim [i]}dp[j]\times A_{n-\lim [j]-2}^{lim[i]-lim[j]-1}$$
• 最后注意下无解，即 $2a[n-1]>a[n]$ 是非法的。
  注意，我们的时间复杂度为 $O(n^2)$，但这题可以优化成 $O(n\log n)$，首先 $lim[x]$ 使用二分进行求解，然后 $dp[x]$ 可以稍微化简一下：
  $$dp[i]=\sum _{j=0}^{\lim [i]}dp[j]\times \frac{(n-lim[j]-2)!}{(n-lim[i]-1)!}=\frac{1}{(n-lim[i]-1)!}\times Pre[lim[i]]$$
  即可以快速求出。

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
typedef long long ll;
void show(){std::cerr << endl;}template<typename T,typename... Args>void show(T x,Args... args){std::cerr << "[ " << x <<  " ] , ";show(args...);}

const int MAX = 5e3+50;
const int MOD = 998244353;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-5;

ll qpow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a%MOD;a=a*a%MOD;n>>=1;}return res;}
ll qpow(ll a,ll n,ll p){a%=p;ll res = 1LL;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
ll npow(ll a,ll n){/* */ll res = 1LL;while(n){if(n&1)res=res*a;a=a*a;n>>=1;if(res<0||a<0)return 0;}return res;}
ll inv(ll a){/* */return qpow(a,MOD-2);}
ll inv(ll a,ll p){return qpow(a,p-2,p);}

int aa[MAX];
int lim[MAX];
ll f[MAX];

ll fac[MAX],ivfac[MAX];

void init(int n){
    fac[0] = 1;
    for(int i = 1;i <= n;++i)fac[i] = fac[i-1] * i % MOD;
    ivfac[n] = inv(fac[n]);
    for(int i = n - 1;~i;--i)ivfac[i] = ivfac[i+1] * (i+1) % MOD;
}

ll A(int n,int m){
    if(n < 0 || m > n)return 0;
    return fac[n] * ivfac[n-m] % MOD;
}

int main()
{
    init(5000);
    int n;cin >>n;
    for(int i = 1;i <= n;++i)cin >>aa[i];
    sort(aa+1,aa+1+n);

    if(2*aa[n-1] > aa[n]){
        puts("0");
        return 0;
    }

    for(int i = 1;i <= n;++i){
        for(int j = 1;j < i;++j){
            if(2*aa[j] <= aa[i]){
                lim[i] = j;
            }else{
                break;
            }
        }
    }
    f[0] = 1;
    lim[0] = -1;

    for(int i = 1;i <= n;++i){
        for(int j = 0;j <= lim[i];++j){
            f[i] = (f[i] + f[j] * A(n - lim[j] - 2,lim[i] - lim[j] - 1) % MOD) % MOD;
        }
    }

    cout << f[n];
    return 0;
}
/**

*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73