Hexo

Posted on

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Posted on Edited on

Preface

Content

Problem

判断一个数是否是质数；

给大树作质因数分解；

Solution

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void divide(int n) {
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            int s = 0;
            while (n % i == 0) {
                s ++;
                n /= i;
            }
            cout << i << ' ' << s << endl;
        }
    }
    if (n > 1) cout << n << ' ' << 1 << endl;
    cout << endl;
}

Miller_Rabin算法

U82118 【模板】Miller Rabin算法

Pollard rho 算法

P4718 【模板】Pollard rho 算法

Remark

Posted on Edited on

Preface

学校的$$Tarjan$$模板题都还没过，不知道卡了哪个点；

Content

Problem

对于一个有向无环图$$(DAG)$$,找到其拓扑排序，或者判断有向图是否是$$DAG$$；

在 $$DAG$$ 上，使用$$ DP$$ 求最长（短）路；

对于有向图，利用$$Tarjan$$算法进行缩点，重构$$DAG$$;

孤立的一个点也是一个强连通分量；

对于无向图，利用$$Tarjan$$算法进行缩点，指出割点，割边，点双连通分量，边双连通分量；

单独的一条边带两个端点我们也认为是点双连通分量；

Solution

拓扑排序

对于一个有向图$$G$$，$$G$$是有向无环图的充分必要条件为能进行拓扑排序，拓扑排序的思路是：

  1. 建图，计算所有点的入度；
  2. 所有入度为0的点入队；
  3. 队首出队同时记录队首的拓扑序，队首的所有儿子入读自减，如果有儿子为0则儿子入队，直至队列为空；

记录一个小性质：对于一个$$DAG$$，至少添加几条边才能使它变为强连通图？

我们计算入度为零的点数为$$a$$，出度为零的点数为$$b$$，那么我们至少需要添加的边数为$$max(a,b)$$，如果只有一个点的话，我们不需要添加任何边；

B3644 【模板】拓扑排序 / 家谱树

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int maxn=1e5;
class Edge{
    public:
    int to;
    int head;
    int nxt;
    int cnt;
}e[maxn];
vector<int> head;
int indeg[maxn];
void add(int u,int v,int&cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u;
    e[cnt].to=v;
    cnt++;
    indeg[v]++;
}

queue<int> q;
int dot[maxn];
void topusort(int(&indeg)[maxn],int (&dot)[maxn],int n){
    for(int i=1;i<=n;i++){
        if(indeg[i]==0) q.push(i);
    }
    int id=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        dot[++id]=x;
        for(int j=head[x];j!=-1;j=e[j].nxt){
            int y=e[j].to;
            indeg[y]--;
            if(indeg[y]==0) q.push(y);
        }
    }
    return ;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n;
    cin>>n;
    head.resize(n+1,-1);
    int cnt=0;
    memset(indeg,0,sizeof(indeg));
    memset(dot,0,sizeof(dot));
    for(int i=1;i<=n;i++){
        int x=0;
        while(cin>>x&&x!=0) add(i,x,cnt);
    }
    topusort(indeg,dot,n);
    for(int i=1;i<=n;i++) cout<<dot[i]<<" ";
    return 0;
}

$$Tarjan$$缩点

关于$$Tarjan$$算法的流程这篇博客图解挺清楚的，稍微总结一下流程：

  1. 深度优先搜索这个图，选取一个根节点（注意整个图可能会有多个连通分支，根节点要遍历所有未访问过的结点）；
  2. 遍历当前根节点的所有儿子，按照时间戳给当前根节点的$$dfn,low$$初始化（$$dfn$$表示在$$dfs$$过程中访问该该节点的序号，也即时间戳，这个值不会更新，$$low$$表示这个点能回访的节点中最小的时间戳，在更新结束后同属于一个强连通分量的点$$low$$值相同），同时根节点入栈，将儿子作为新的根节点继续搜索；
  3. 在搜索图过程中如果搜索到了已经访问过的节点，如果该点还在栈中，那么意味着回访，我们更新当前根节点的$$low$$，搜索开始回溯，同属于一个强连通分量的结点的$$low$$都开始更新为刚刚回访结点的$$low$$值；（注意在栈中这个条件是必须的，如果一个点不在的$$low$$值被不在栈中的点更新了，那么这个点将一直不满足出栈的条件而被留在栈中，典型的反例就是一个点$$P$$指向一个强连通分量的所有点，但强连通分量的点此时均已出栈,$$P$$点的$$low$$会被错误地更新，最终表现为强连通分量的缺少）；
  4. 在所有儿子遍历完成后，检查这个点的$$dfn,low$$是否相等，如果相等那么它作为回访的结点，让它带着同一个强联通分量的点出栈，算法保证了这些点是栈顶部的若干点；

P3387 【模板】缩点

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=1e5+10;
int w[maxn];
vector<int> head;
vector<int> DAGhead;
class Edge{
    public:
    int head;
    int to;
    int nxt;
}e[maxn],DAGe[maxn];
void add(int u,int v,int&cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u;
    e[cnt].to=v;
    return ;
}
void DAGadd(int u,int v,int&cnt){
    DAGe[cnt].nxt=DAGhead[u];
    DAGhead[u]=cnt;
    DAGe[cnt].head=u;
    DAGe[cnt].to=v;
    return ;
}

int dfn[maxn];
int low[maxn];
bool instk[maxn];
stack<int> stk;
vector<int> scc[maxn];int sccnum=0;int sccid[maxn];int color[maxn];
int ww[maxn];
int dep=0;

void tarjan(int x){
    dfn[x]=++dep;
    low[x]=dep;
    stk.push(x);
    instk[x]=true;
    for(int i=head[x];i!=-1;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y]) low[x]=min(low[x],dfn[y]);
        
    }
    if(dfn[x]==low[x]){
        sccid[++sccnum]=x;
        while(!stk.empty()&&stk.top()!=x){
            int y=stk.top();
            stk.pop();
            instk[y]=false;
            color[y]=sccnum;
            scc[sccnum].push_back(y);
        }
        stk.pop();
        instk[x]=false;
        color[x]=sccnum;
        scc[sccnum].push_back(x);
    }
}

int f[maxn];
void dp(int x){
    if(f[x]) return ;
    f[x]=ww[x];
    int res=0;
    for(int i=DAGhead[x];i!=-1;i=DAGe[i].nxt){
        int y=DAGe[i].to;
        if(!f[y]) dp(y);
        if(res<f[y]) res=f[y];
    }
    f[x]+=res;
    return ;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    head.resize(n+1,-1);
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,i);
    }
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(sccid,0,sizeof(sccid));
    memset(instk,0,sizeof(instk));
    memset(ww,0,sizeof(ww));
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=sccnum;i++) {
        for(int j=0;j<scc[i].size();j++){
            ww[i]+=w[scc[i][j]];
        }
    }
    DAGhead.resize(sccnum+1,-1);
    int cnt=0;
    for(int i=0;i<m;i++){
        int u=e[i].head;
        int v=e[i].to;
        if(color[u]!=color[v]) {
            DAGadd(color[u],color[v],cnt);
            cnt++;
        }
    }
    int ans=0;
    for(int i=1;i<=sccnum;i++){
        if(!f[i]){
            dp(i);
            if(ans<f[i]) ans=f[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

割点

由于割点是相较于无向图的概念所以$$Tarjan$$算法不能直接应用于求出割点，但是我们利用$$Tarjan$$算法的思想魔改一下，根据$$dfn$$序将图中顶点分成若干性质相同的块（$$low$$相同的属于同一个集合）便可以找到割点；

注意这里的$$low$$数组的含义与传统的$$Tarjan$$有略微的不同，更新条件也不一样；

对于无向图$$DFS$$树的相关性质：

  • 对于每个结点的子树之间没有边相连（否则搜索这棵子树的时候一定会顺着这条边把另一棵子树一并搜索，所以另一棵子树将没有机会成为子树，矛盾）

  • 对于非树边的两个端点，其中一个一定是另一个的祖先（非树边不能连接不同子树上的结点，所以非树边的两个端点一定在同一个子树上，自然具有了祖先关系）；

  • 祖先的时间戳一定小于其子孙的时间戳；

  • 对于树边总可以指定一个方向使得父亲指向儿子，相对的，对于无向图中儿子指向父亲的边就是非树边；

对于一个无向连通图，取出其中一棵可能的$$DFS$$树，对于非根结点$$x$$，我们记$$T(x)$$为$%$$$x$$伸展出来的子树（包括$$x$$），那么倘若$$x$$是割点，那么将其删去变得不再连通，对于$$x$$的儿子$$y$$来说，$$y$$通过非树边回访的点$$u$$一定不是$$x$$的祖先，（注意在$$DFS$$无法搜索到未访问的点时，一定是通过非树边回访那些已经访问的点，有些点回访它的父亲，也有的点回访其他祖先，因为不可能在其他子树上），换言之，$$u$$在$$T(x)$$中，因此在所有$$y$$所能回访的节点中，我们维护这些结点最小的$$dfn$$，更新$$low(y)$$；在一个儿子递归结束后，我们用儿子们中的最小$$low$$值更新父亲结点的$$low$$，如果儿子能回访的结点甚至都不能是$$x$$的祖先($$low[y]\ge dfn[x]$$)，那么$$x$$就是割点；

对于根节点则要简单许多，只需要一个特判：如果根节点发出两个及以上真-子树（不包括$$x$$）的话，说明把$$x$$删去就会导致不连通（因为子树之间没有边相连）；

对于一般的图，我们只需要考虑每个连通分量即可；

根据以上描述手搓的一个草图，防止以后看不懂；

P3388 【模板】割点（割顶）

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
#define local
#include<bits/stdc++.h>
#include<iostream>
using namespace std;

const int maxn=200005;
class edge{
    public:
    int head;
    int to;
    int nxt;
}e[maxn];
vector<int>head;
void add(int u,int v,int&cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u;
    e[cnt].to=v;
    cnt++;
}
int dep=0;
int dfn[maxn];
int low[maxn];
bool cut[maxn];
stack<int> stk;
void Cut(int now,int fa,int rt){
    dfn[now]=low[now]=++dep;
    int sontree=0;
    for(int i=head[now];i;i=e[i].nxt){
        int sn=e[i].to;
        if(!dfn[sn]){
            sontree++;
            Cut(sn,now,rt);
            low[now]=min(low[now],low[sn]);
            if(low[sn]>=dfn[now]&&now!=rt) cut[now]=1;
        }
        else low[now]=min(low[now],dfn[sn]);
    }
    if(now==rt&&sontree>=2) cut[now]=1;  
    return;
}

int main()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    head.resize(n+1);
    int cnt=1;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,cnt);
        add(v,u,cnt);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) Cut(i,-1,i);
    vector<int> ans;
    for(int i=1;i<=n;i++){
        if(cut[i])ans.push_back(i);
    }
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

割边

一个基本的事实是所有的割点都依附于割边，我们用相同的办法更新相应的$$dfn,low$$数组，但是判定条件略有区别：我们忽略对回边（树边的逆向边）的更新，如果对于边$$xy$$，$$y$$只能能回访到时间戳严格大于$$x$$的点，说明$$xy$$是割边，否则不是；

T103481 【模板】割边

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=6e5+10;
class edge{
    public:
    int head;
    int to;
    int nxt;
}e[maxn];
vector<int> head;
void add(int u,int v,int cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].to=v;
    e[cnt].head=u;
}
int rev(int x){
    return x%2?x+1:x-1;
}
int dfn[maxn];
int low[maxn];
bool bdg[maxn];
int dep=0;
void bridge(int x,int eg){
    dfn[x]=low[x]=++dep;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y]){
            bridge(y,i);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x]) bdg[i]=bdg[rev(i)]=true;
        }
        else if(eg!=rev(i))
            low[x]=min(low[x],dfn[y]);
    }
    return ;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    head.resize(n+1);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,2*i-1);
        add(v,u,2*i);
    }
    for(int i=1;i<=n;i++)if(!dfn[i]) bridge(i,0);
    int bdgnum=0;
    for(int i=1;i<=2*m;i+=2) {
        if(bdg[i]) bdgnum++;
    }
    cout<<bdgnum<<endl;
    return 0;
}

点双连通分量

称极大的不包含割点的连通块被称为点的双连通分量

点双连通分量是点双连通极大子图；

  • $$BCC$$中无割点
  • 若$$BCC$$间有公共点，那么公共点是原图的割点；
  • 无向连通图中割点至少属于两个$$BCC$$，非割点属于一个$$BCC$$
  • 点双连通不具有传递性；

由上述性质我们知道，割点是每个点双的公共点，在遍历$$DFS$$树时候发现点双意味着割点（或者$$DFS$$的树根）必然最先发现，因此在与有向图求解强连通分量时不同，如果回访到了割点（或者树根），应该立即让子树出栈，包括割点（或者树根），加入新的点双中；

P8435 【模板】点双连通分量

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=4e6+10;
class edge{
    public:
    int head;
    int to;
    int nxt;
}e[maxn];
vector<int> head;
void add(int u,int v,int cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u;
    e[cnt].to=v;
}

int dfn[maxn];
int low[maxn];
int dep=0;
stack<int> stk;
vector<int> bcc[maxn];
bool instk[maxn];
int bccnum=0;
void BCC(int x,int fa){
    dfn[x]=low[x]=++dep;
    stk.push(x);
    int son=0;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y]){
            son++;
            BCC(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                bccnum++;
                while(stk.top()!=y) {
                    bcc[bccnum].push_back(stk.top());
                    stk.pop();
                }
                bcc[bccnum].push_back(y);
                stk.pop();
                bcc[bccnum].push_back(x);
            }
        }
        else if(y!=fa) low[x]=min(low[x],dfn[y]);
    }
    if(fa==0&&son==0) bcc[++bccnum].push_back(x);
    return;
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    head.resize(n+1);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,2*i-1);
        add(v,u,2*i);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) BCC(i,0);
    cout<<bccnum<<endl;
    for(int i=1;i<=bccnum;i++){
        cout<<bcc[i].size()<<" ";
        for(int j=0;j<bcc[i].size();j++){
            cout<<bcc[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

边双连通分量

极大的不含有桥的连通区域被称为边的双连通分量;

观察我们知道把所有的割边删除留下来的连通分支本身构成边连通分量，所以整体与有向图求强连通分量类似；

注意对重边的处理即可；

P8436 【模板】边双连通分量

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=4e6+5;
class edge{
    public:
    int head;
    int to;
    int nxt;
}e[maxn];
vector<int> head;
void add(int u,int v,int&cnt){
    e[cnt].nxt=head[u];
    head[u]=cnt;
    e[cnt].head=u;
    e[cnt].to=v;
    cnt++;
}

int dfn[maxn];
int low[maxn];
int dep=0;
int instk[maxn];
stack<int> stk;
vector<int> edcc[maxn];
int edccnum=0;
int rev(int x){
    return x%2?x+1:x-1;
}
void EDCC(int x,int fa,int eg){
    dfn[x]=low[x]=++dep;
    stk.push(x);
    instk[x]=1;
    int revis=0;
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(!dfn[y]){
            EDCC(y,x,i);
            low[x]=min(low[x],low[y]);
        }
        else if(i!=rev(eg)&&instk[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        edccnum++;
        while(stk.top()!=x){
            edcc[edccnum].push_back(stk.top());
            instk[stk.top()]=0;
            stk.pop();
        }
        edcc[edccnum].push_back(x);
        instk[x]=0;
        stk.pop();
    }
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    int cnt=1;
    head.resize(n+1);
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v,cnt);
        add(v,u,cnt);
    }

    for(int i=1;i<=n;i++) if(!dfn[i]) EDCC(i,0,0);
    cout<<edccnum<<endl;
    for(int i=1;i<=edccnum;i++){
        cout<<edcc[i].size()<<" ";
        for(int j=0;j<edcc[i].size();j++){
            cout<<edcc[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

Example

Gym - 104197K

Remark

重新整理了一遍笔记还是没过学校的逆天模板题，留大坑于此；

Posted on Edited on

Preface

这是2023.7.12的比赛，由于$$codeforces$$崩了所以本场$$unrated$$;

从这场开始好像有点适应了，但只签到了$$A$$，一时间没有想到打表；

题目也都是后面补的，感觉跟榜做难度还是挺合理的；

#A. Lucky Numbers (easy)

题源：CF96B

题意：

给定询问$$x$$，找到不小于$$x$$的，只有相等数量的$$7,4$$构成的数；

思路：

注意到上来按位数直接构造很可能会陷入死胡同，因为$$1≤x≤10^9$$,所以本身这样的数并不多，我们直接打表即可；

AC code：

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
#define local
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
int main ()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local
    set<ll> a;
    a.insert(47);a.insert(74);
    for(int i=0;i<=3;i++){
        for(int j=i+1;j<=3;j++){
            ll x=3*pow(10,i)+3*pow(10,j);
            a.insert(7777-x);
        }
    }
    for(int i=0;i<=5;i++){
        for(int j=i+1;j<=5;j++){
            for(int k=j+1;k<=5;k++){
                ll x=3*pow(10,i)+3*pow(10,j)+3*pow(10,k);
                a.insert(777777-x);
            }
        }
    }
    for(int i=0;i<=7;i++){
        for(int j=i+1;j<=7;j++){
            for(int k=j+1;k<=7;k++){
                for(int p=k+1;p<=7;p++){
                    ll x=3*pow(10,i)+3*pow(10,j)+3*pow(10,k)+3*pow(10,p);
                    a.insert(77777777-x);
                }
                
            }
        }
    }
    for(int i=0;i<=9;i++){
        for(int j=i+1;j<=9;j++){
            for(int k=j+1;k<=9;k++){
                for(int p=k+1;p<=9;p++){
                    for(int q=p+1;q<=9;q++){
                        ll x=3*pow(10,i)+3*pow(10,j)+3*pow(10,k)+3*pow(10,p)+3*pow(10,q);
                        a.insert(7777777777-x);
                    }
                    
                }
                
            }
        }
    }
    int n;
    cin>>n;
    for(auto iter=a.begin();iter!=a.end();iter++){
        ll y=*iter;
        if(y>=n) {
            cout<<y<<endl;
            break;
        }
    }
    return 0;
}

#B. Sad powers

题源：CF955C

题意：

给定 $$q$$ 个询问，每次询问$$[l,r]$$ 这个区间内满足 $$x=a^p,a>0,p>1$$ 的 $$x$$ 的数量;

思路：

一眼转化为区间$$[1,r],[1,l-1]$$相减，但之后好像是个结论题，之前做过这样的上界估计，当时就是把容斥原理减去的项丢掉了；

现在要精确的把数量算出来，我们还原容斥原理：记$$\mu[k]$$表示$$k$$的莫比乌斯函数，那么
$$
res(x)=1+\sum_{k=2}^{\infty}(-\mu[k])(\left \lfloor \sqrt[k]{x} \right \rfloor-1 )
$$
简单证明一下：对于$$a^k\in [2,x] \Leftrightarrow a\in [2,\left \lfloor \sqrt[k]{x} \right \rfloor] $$,那么满足条件的$$x$$数量就为$$\left \lfloor \sqrt[k]{x} \right \rfloor-1$$，再分$$k$$的素因子归纳讨论前面的符号（如果$$k$$有平方因子说明计算$$k=\prod_{prime\ p|k}p$$的那一步时已经计算过了一次了，不需要重复计算，对于只有偶数个素因子相乘的$$k$$被重复计算一次，需要减去，对于只有奇数个素因子相乘的$$k$$被重复减去一次，需要加上）;

经过以上抽象证明以后，接下来就是卡常技巧和卡精度技巧了；

由于$$x\le 10^{18}$$,所以开long long ,pow(x,1.0/k)对一些刚好开根的数可能会算错而导致WA(难蚌)，所以算完要进行验证一下；

看完一圈题解下来我这个确实不是正解，但懒得把正解复制下来了,思路是把非平方数暴力存下来，大概在$$10^6$$个数左右；

AC code：

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=64;
int vis[maxn]={0};
int mu[maxn]={0};//mobius相反数
int prime[maxn]={0};
int find(long long x,long long k){
    long long y=pow(x,1.0/k);
    long long z=pow(y,k);
    if(k>=10) return y;
    if(z<=x){
        long long t=pow(y+1,k);
        if(t>x) return y;
        else {
            long long s=pow(y+2,k);
            if(s>x) return y+1;
            else return y+2;
        } 
    }
    else {
        long long r=pow(y-1,k);
        if(r<=x)  return y-1;
        else {
            long long j=pow(y-2,k);
            if(j<=x) return y-2;
            else return y-3;
        }
    }
    return y;
}
int cnt=0;
void mobius(){
    vis[1]=1;
    mu[1]=1;
    for(int i=2;i<maxn;i++){
        if(!vis[i]) {
            prime[++cnt]=i;
            mu[i]=1;
        }
        for(int j=1;j<=cnt;j++){
            if(i*prime[j]>maxn) break;
            vis[i*prime[j]]=1;
            if(i%prime[j]!=0) {
                mu[i*prime[j]]=-mu[i];
            }
            else {
                mu[i*prime[j]]=0;
            }
        }
    }
}
int res(long long x){
    if(x==0) return 0;
    if(x==1||x==2||x==3) return 1;
    int tmp=1;
    int c=0;
    for(int k=2;k<maxn;k++){
        if(c==1) break;
        if(mu[k]==0) continue;
        c=find(x,1LL*k);
        tmp+=mu[k]*(c-1);
    }
    return tmp;
}
int main ()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int q;
    mobius();
    // for(long long x=0;x<100002;x++){
    //     cout<<x<<" "<<res(x)<<endl;
    // }
    cin>>q;
    while(q--){
        long long l,r;
        cin>>l>>r;
        int res2=res(l-1);
        int res1=res(r);
        int ans=res1-res2;
        //cout<<res1<<" "<<res2<<" "<<ans<<endl;
        cout<<ans<<endl;
    }
    return 0;
}

#C. Destruction of a Tree

题源：CF963B

题意：

思路：

AC code：

1

#D. Time to Raid Cowavans

题源：CF103D

题意：

给定长度为$$n$$的数列$$w$$，给定$$p$$组询问$$(a,b)$$，回答$$\sum_{a\le i \le n,b|i-a}a_i$$的值；

思路：

根号分治加离线；

首先观察数据范围不考虑在线做法，离线处理所有$$b$$值相同的询问；

划分界限$$T$$，对于$$b>T$$，由于和式个数不会很多，直接暴力即可；对于$$b<T$$，由于模$$b$$的余数不会很多，预处理所有可能按模数跳跃的前缀和复杂度不会太高，对于询问找到两个合适的前缀和作差即可；

复杂度为$$O(plogp+\sum_{every\ question \ b>T}{\frac{b}{T}}+\sum_{b<T}{n})=O(O(p)*\frac{n}{T}+Tn)$$,取$$T=\sqrt n$$能过；

AC code：

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
int w[maxn];
ll ans[maxn];
struct question{
    int a,b,id;
}q[maxn];
ll s[maxn];
void init(int b,int n){
    for(int i=1;i<=b;i++)s[i]=w[i];
    for(int i=b+1;i<=n;i++)s[i]=s[i-b]+1LL*w[i];
}
int main ()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,p;
    cin>>n;
    int sn=sqrt(n);
    for(int i=1;i<=n;i++) cin>>w[i];
    cin>>p;
    for(int i=1;i<=p;i++) cin>>q[i].a>>q[i].b,q[i].id=i;
    sort(q+1,q+p+1,[](question&l,question&r){
        return l.b<r.b;
    });
    for(int i=1;i<=p;i++){
        if(q[i].b>=sn) {
            int k=q[i].id;
            for(int j=q[i].a;j<=n;j+=q[i].b){
                ans[k]+=1LL*w[j];
            }
        }
        else {
            int k=q[i].id;
            int x=(n-q[i].a)*1.0/q[i].b;
            if(q[i].b!=q[i-1].b)init(q[i].b,n);
            ans[k]=(q[i].a>q[i].b)?s[q[i].a+x*q[i].b]-s[q[i].a-q[i].b]:s[q[i].a+x*q[i].b];
        }
    }
    for(int i=1;i<=p;i++) cout<<ans[i]<<endl;
    return 0;
}

#E. Report

题源：CF631C

题意：

给定长度为$$n$$的数列，一次操作是指将一个前缀升序或者降序重新排列，求出$$m$$次操作后的序列；

思路：

观察数据范围，应该排除在线和暴力做法；

对于所有的操作$$(t,r)$$,若$$i<j,r_i\le r_j$$，那么不论$$t$$的取值，后面的操作会严格覆盖掉前面的操作，可以称前面的操作时无效的，我们维护一个单调栈，找到确实有效的操作；

对于这些操作会将数列分割成一个个的小区间，有的区间上升有的区间下降，我们利用双指针扫描一遍原来数组（有效操作最长的哪个区间）的升序即可；

AC code:

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
#define local
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=2e5+5;
int a[maxn];
int ans[maxn];
int t[maxn];
int r[maxn];
stack<int> stk;
int opt[maxn];
bool cmp1(int l,int r){
    return l<r;
}
bool cmp2(int l,int r){
    return l>r;
}
int main ()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>t[i]>>r[i];
    int top=1;
    while(top<=m){
        if(stk.empty()) stk.push(top);
        else {
            while(!stk.empty()&&r[stk.top()]<=r[top]) stk.pop();
            stk.push(top);
        }
        top++;
    }
    int sz=stk.size();
    for(int i=sz;i>0;i--){
        opt[i]=stk.top();
        stk.pop();
    }
    int L=1,R=r[opt[1]],now=1;
    for(int i=R+1;i<=n;i++) ans[i]=a[i];
    sort(a+1,a+R+1);
    for(int i=R;i>0;i--){
        if(now+1<=sz&&i<=r[opt[now+1]]) 
            now++;
        if(t[opt[now]]==1) 
            ans[i]=a[R--];
        else 
            ans[i]=a[L++];
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
    return 0;
}

#F. Renting Bikes

题源：CF363D

题意：

给定$$n$$个男孩的私房钱，总公共预算$$a$$,$$m$$辆单车的租金，最大化租用的单车数量，并计算此时支出了的私房钱；

思路：

先粗略估计租用单车的上界$$R$$：让钱最多的$$R$$个男孩租用最便宜的$$R$$辆单车，并且预算（差点就）花光的边界情况；此时意味着在多租借一辆就会爆炸，给男孩私房钱降序排序和单车租金升序排序，找到临界情况；

然后再精细的调整$$r$$的值，从$$R$$开始下降，采用田忌赛马的办法，假设租用了$$r$$辆单车，让钱最多的$$r$$个男孩租用最便宜的$$r$$辆单车，而且钱越多的男孩承担越贵的租金，并小心的计算此时的真实挪用的最小预算（让这些男孩充分用私房钱）；

得出$$r$$后，男孩们多出的私房钱当然是所有租用的单车的租金减去总公共预算了；

Ac code:

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=1e5+5;
int p[maxn];
int b[maxn];
typedef long long ll;
int n,m,a;
ll sum[maxn];
ll cap[maxn];
ll dp(int r){
    ll res=0;
    for(int i=1;i<=r;i++){
        res+=(p[i]>b[r+1-i])?(p[i]-b[r+1-i])*1LL:0;
    }
    return res;
}
ll cost(int r){
    if(r==0) return 0;
    ll res=0;
    for(int i=1;i<=r;i++) {
        res+=p[i]*1LL;
    }
    return max(0LL,res-a*1LL);
}
int main ()
{
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // loca

    cin>>n>>m>>a;
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=m;i++) cin>>p[i];
    sort(b+1,b+n+1,[](int l,int r){return l>r;});
    sort(p+1,p+m+1);
    for(int i=1;i<=m;i++) sum[i]=sum[i-1]+p[i]*1LL;
    for(int i=1;i<=n;i++) cap[i]=cap[i-1]+b[i]*1LL;
    int r=0;
    while(r<=n&&r<=m&&cap[r]+a>=sum[r]) 
        r++;
    r--;
    while(r<=n&&r<=m&&dp(r)>a) 
        r--;
    cout<<r<<" "<<cost(r)<<endl;
    return 0; 
}

#G. Full Binary Tree Queries

题源：CF960D

题意：

思路：

大细节模拟题，跳了跳了；

AC code：

1

#H. Vladik and Complicated Book

题源：CF811B

题意：

给定长度为$$n$$的置换，询问$$m$$个区间，对区间内的数进行升序排序， 考察某个下标是否发生变化，询问结束后还原置换；

思路：

直接根据题意模拟即可；

注意复杂度和值域范围，排序不选择sort,应该采用线性复杂度的桶排序；

AC code：

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
#define local
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int maxn=1e4+10;
int p[maxn];
int cpy[maxn];
int buc[maxn];
int main ()
{
    #ifdef local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // local

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    for(int i=1;i<=n;i++) cpy[i]=p[i];
    
    while(m--){
        int l,r,x;
        scanf("%d%d%d",&l,&r,&x);
        if(x<l||x>r) {
            puts("Yes");
            continue;
        }
        memset(buc,0,sizeof(buc));
        for(int i=l;i<=r;i++)buc[p[i]]++;
        int id=0;int cnt=0;
        for(int i=1;i<=n;i++) {
            cnt+=buc[i];
            if(cnt==x-l+1) {id=i;break;}
        }
        if(id==p[x]) puts("Yes");
        else puts("No");
    }
    return 0;
}

Remark

![](https://kytolly-1318202921.cos.ap-chengdu.myqcloud.com/202307310221042.png

0%