线性素数筛


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
#include <bits/stdc++.h>
using namespace std;
int n,ans,k[20000000],tot;
bool f[20000000];
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++)
    {
        if(!f[i])
        {
            tot++;
            k[tot]= i;
            ans++;
        }
        for(int j=1;j<=tot && k[j]*i<=n;j++)
        {
            f[k[j]*i]=1;
            if(i%k[j]==0)
                break;
        }
    }
    printf("%d",ans);
    return 0;
}

上面线性筛的代码,本文只负责分析代码。

首先bool数组f存一个数是否为素数,不是就为1,是就为0;

然后是k数组,这个数组可以存储所有素数。

代码中筛数的代码是这段


1
2
3
4
5
6
for(int j=1;j<=tot && k[j]*i<=n;j++)
        {
            f[k[j]*i]=1;
            if(i%k[j]==0)
                break;
        }

i同时起到两作用:①指当前循环到哪个数;②指当前素数的i倍数为合数。

所以将f[k[i]*i]这个标记数组赋值为1。

那么为什么i%k[i]==0时循环要停止呢?

这就是这个筛法的强大之处,每个数只筛一遍。

前面提到了,所有合数都可以写成数个素数的积。

举个栗子,当程序i=4时

k[1]=2,然后f[2*4]=1;

当4%2==0时,这个循环筛就停止了,为什么不继续将f[3*4]=1呢?

4%2==0,所以4=2*2;

既然如此3*4=3*2*2=2*6;

那么当我们的i循环到6的时候,f[2*6]便会被赋值为1。

你看 2*6=3*4=12;

在我们用到f[12]之前,一定会先循环过它的因数,那么无论是i=4时将f[3*4]=1,还是i=6时将f[2*6]=1都可以,但这样做会多次赋值同一个数,那还是线性的吗?假如同一个数被赋值上百次,多个数被赋值上百次,那你分就没了。所以在i=4将f[2*4]=1后就应该停止循环了,这样可以避免chong’f我认为这就是这代码比其他筛法优的地方,

NOIP/CSP算法竞赛对拍四步曲(windows + NOILinux2.0环境)详细举例

https://blog.csdn.net/weixin_44561165/article/details/121725375

 

对拍四步曲:

 

运行random.cpp随机生成符合输入格式的.in文件

运行”朴素解法”xxx.bf.cpp生成.ans文件

运行”高效正解”xxx.cpp生成.out文件

运行”对拍程序”compare.cpp自动对比.out 文件和 .ans文件

 

markdown test

Chip Game

题面翻译

有一个 $n$ 行 $m$ 列的方格矩阵,左下角的方格有一个棋子,这个棋子每次移动只能向上或向右移动奇数格。Burenka 和 Tonya 用这个棋子玩一个游戏:两人依次移动一次棋子,最后没法移动棋子的人就输了。Burenka 先手,给你 $n$ 和 $m$,问你谁最后会赢。我们假定他们都精通这个游戏,因此每一步走棋方式都是最优的。

输入第一行一个整数 $t(1\le t\le10^4)$,表示 $t$ 组数据。接下来 $t$ 行每行两个整数 $n,m(1\le n,m\le10^9)$,含义如题面所述。

对于每一组数据,输出一行一个字符串,表示游戏最后的赢家,即“Burenka”或“Tonya”。

题目描述

Burenka and Tonya are playing an old Buryat game with a chip on a board of $ n \times m $ cells.

At the beginning of the game, the chip is located in the lower left corner of the board. In one move, the player can move the chip to the right or up by any odd number of cells (but you cannot move the chip both to the right and up in one move). The one who cannot make a move loses.

Burenka makes the first move, the players take turns. Burenka really wants to win the game, but she is too lazy to come up with a strategy, so you are invited to solve the difficult task of finding it. Name the winner of the game (it is believed that Burenka and Tonya are masters of playing with chips, so they always move in the optimal way).

Chip’s starting cell is green, the only cell from which chip can’t move is red. if the chip is in the yellow cell, then blue cells are all options to move the chip in one move.

输入格式

The first line contains one integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The following is a description of the input data sets.

The only line of each test case contains two integers $ n $ and $ m $ ( $ 1 \leq n, m \leq 10^9 $ ) — the dimensions of the game board.

输出格式

For each test case print a single line — the name of the winner of the game ("Burenka" or "Tonya").

样例 #1

样例输入 #1


1
2
3
4
5
6
7
6
1 1
1 4
5 6
2 2
6 3
999999999 1000000000

样例输出 #1


1
2
3
4
5
6
Tonya
Burenka
Burenka
Tonya
Burenka
Burenka

提示

In the first case, Burenka has no move, so Tonya wins.

In the second case, Burenka can move $ 3 $ cells to the right, after which Tony will not be able to make a move, which means that Burenka wins.

In the third case, Burenka can move $ 5 $ squares to the right. Then we can say that we have a game on a board of $ 1 \times 5 $ cells, and Tonya is the first player. In such game the second player wins, so in the original one Burenka will win.

常州day12

1

字符串处理,水

2

栈和贪心,自找规律,栈的先入后出符合区间不相交要求,引用:发现当前栈内元素与 a[i]不同时,首先退栈直到栈内元素值小于a[i]等于 ,随后加入一个修改操作补齐差值即可。

4

类安装雷达,考虑在排除两边山后的其他山遮挡

 

常州集训day13

T1.sifra

简单字符串,找到所有数字判断存在个数

T2.po

栈+贪心

手动模拟要做的事找到规律

我们可以用栈来维护一个修改操作的数值以及左端点进行扫描。由于区间之间互不相交或者互相包含,所以区间之间的出入关系满足栈的限制。发现当前栈内元素与 a[i]不同时,首先退栈直到栈内元素值小于a[i]等于 ,随后加入一个修改操作补齐差值即可。

T4.Planine

注意到,对于每一个山谷,存在一个 坐标的区间,在这个区间上放置精灵可以照亮这个山谷。

将每个山谷要被照到的精灵所在位求出来,会得出多个区间(注意会被山脉阻挡),然后就是区间覆盖问题。

。。。。。。见鬼的捆绑测试

CZOI-SCZ-DAY10

记录一下可能是这个月最后一篇BLOG。

DAY10的题只能补出来200pts了,T3、T4不是分治+双指针,就是线段树,T5的原理和代码长度令人不解。

[Patkic]

题意:给你一个地图,最开始时你可以向上下左右走一步,随后只能顺着洋流飘,问能否到达终点。

只需要最开始的时候暴力去判断,至于字典序的问题,我们可以按照东(E),北(N),南(S),西(W)来搜索就可以了。

具体的细节还是挺多的。


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
#include<bits/stdc++.h>
using namespace std;
int n,m,st[105][105];
char Map[105][105];
int dfs(int x,int y,int ans)
{
    if(x<0||x>=n||y<0||y>=m)return -1;
    if(Map[x][y]=='x')return ans;
    if(Map[x][y]=='o'||Map[x][y]=='.'||st[x][y])return -1;
    st[x][y]=1;
    if(Map[x][y]=='<')return dfs(x,y-1,ans+1);
    else if(Map[x][y]=='>')return dfs(x,y+1,ans+1);
    else if(Map[x][y]=='^')return dfs(x-1,y,ans+1);
    else if(Map[x][y]=='v')return dfs(x+1,y,ans+1);
}
int main()
{
    freopen("patkice.in","r",stdin);
    freopen("patkice.out","w",stdout);
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=0;i<n;i++)
    {
        scanf("%s",Map[i]);
        for(int j=0;j<m;j++)
        {
            if(Map[i][j]=='o')
            {
                x=i;
                y=j;
                break;
            }
        }
    }
    vector<pair<int,char> >V;
    memset(st,0,sizeof st);
    int tmp=dfs(x,y+1,0);
    if(tmp!=-1)V.push_back({tmp,'E'});
    memset(st,0,sizeof st);
    tmp=dfs(x-1,y,0);
    if(tmp!=-1)V.push_back({tmp,'N'});
    memset(st,0,sizeof st);
    tmp=dfs(x+1,y,0);
    if(tmp!=-1)V.push_back({tmp,'S'});
    memset(st,0,sizeof st);
    tmp=dfs(x,y-1,0);
    if(tmp!=-1)V.push_back({tmp,'W'});
    if(!V.size())printf(":(");
    else
    {
        sort(V.begin(),V.end());
        printf(":)\n%c",V.front().second);
    }
    return 0;
}

[Bajka]

一个DP。

设f[i][j]表示我们位于不喜欢的串的第i个位置,下一个字符为喜欢的串的第j位的代价。

有f[i][j]=min(f[k][j-1]+c)(满足s[i]=s[k-1] or s[i]=s[k+1])


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
#include<bits/stdc++.h>
using namespace std;
const int N=3005;
int n,m,idx[N],f[N][N];
char a[N],b[N];
vector<int>pos[30];
int main()
{
    freopen("bajka.in","r",stdin);
    freopen("bajka.out","w",stdout);
    scanf("%d%d%s%s",&n,&m,a+1,b+1);
    for(int i=1;i<=n;i++)
    {
        pos[a[i]-'a'].push_back(i);
        idx[i]=pos[a[i]-'a'].size()-1;
    }
    if(!pos[a[1]-'a'].size())
    {
        puts("-1");
        return 0;
    }
    for(int i=2;i<=m;i++)
    {
        vector<int>&u=pos[b[i]-'a'];
        for(int j=0;j<u.size();j++)
        {
            f[i][j]=1e9;
            if(a[u[j]-1]==b[i-1])f[i][j]=min(f[i][j],f[i-1][idx[u[j]-1]]+1);
            if(a[u[j]+1]==b[i-1])f[i][j]=min(f[i][j],f[i-1][idx[u[j]+1]]+1);
        }
        for(int j=1;j<u.size();j++)f[i][j]=min(f[i][j],f[i][j-1]+u[j]-u[j-1]);
        for(int j=u.size()-2;~j;j--)f[i][j]=min(f[i][j],f[i][j+1]+u[j+1]-u[j]);
    }
    int res=1e9;
    for(int i=0;i<pos[b[m]-'a'].size();i++)res=min(res,f[m][i]);
    printf("%d",res==1e9?-1:res);
    return 0;
}

常州DAY10

附:T4随机化代码


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
#include<bits/stdc++.h>
#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
#define drp(i,j,k) for(int i=(j);i>=(k);--i)
using namespace std;
inline int read(){
    int x=0,f=0;char ch;
    while(!isdigit(ch=getchar())) f|=ch=='-';
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;

}
inline int max3(int x,int y,int z){return max(max(x,y),z);}
inline int min3(int x,int y,int z){return min(min(x,y),z);}
inline int jc3(int x,int y,int z){return max3(x,y,z)-min3(x,y,z);}
//------------------------------------------------------//
const int N=2e5+5;
int n,ans=N;
int fir[N],nex[N<<1],to[N<<1],pos;
void add(int x,int y){
    to[++pos]=y;nex[pos]=fir[x];fir[x]=pos;
    std::swap(x,y);
    to[++pos]=y;nex[pos]=fir[x];fir[x]=pos;
}

int siz[N],dep[N],fa[N][21];
int leaf[N],cnt;
void dfs1(int u,int f){
    dep[u]=dep[fa[u][0]=f]+1;siz[u]=1;
    for(int i=fir[u];i;i=nex[i]){
        int v=to[i];
        if(v==f) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
    }
    if(siz[u]==1) leaf[++cnt]=u;
}
int lca(int x,int y){
    if(dep[x]<dep[y]) std::swap(x,y);
    drp(i,17,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
    drp(i,17,0) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return x==y?x:fa[x][0];
}
int w(int x,int y){
    int z=lca(x,y);
    if(x==z||y==z){
        if(dep[x]<dep[y]) std::swap(x,y);
        return jc3(siz[x],siz[z]-siz[x],n-siz[z]);
    }
    else return jc3(siz[x],siz[y],n-siz[x]-siz[y]);
}


void find(int root,int k){
    if(ans!=N&&n<=2000) return ;
    dfs1(root,0);
    rep(i,1,17) rep(u,1,n)
      fa[u][i]=fa[fa[u][i-1]][i-1];
    if(n<=2000){
        if(ans!=N) return;
        rep(i,1,n) rep(j,1,n)
          ans=std::min(ans,w(i,j));
        return ;
    }

    int tim=40;
    while(tim--){
        int x,y;
        if(tim&1) {
            x=leaf[rand()%cnt+1];
            y=leaf[rand()%cnt+1];
        }
        else {
            x=rand()%n+1;
            y=rand()%n+1;
        }  
        bool con=true;
        int now=w(x,y);
        while(con) {
            con=false;
            drp(i,k,0) if(fa[x][i]) {
                int ne=w(fa[x][i],y);
                if(ne>now) continue;
                x=fa[x][i]; now=ne;
                con=true;
            }
            if(!con) {
                std::swap(x,y);
                drp(i,0,0) if(fa[x][i]) {
                    int ne=w(fa[x][i],y);
                    if(ne>now) continue;
                    x=fa[x][i]; now=ne;
                    con=true;
                }
            }
            if(rand()&1)std::swap(x,y);
        }
        ans=std::min(ans,now);
    }
}

signed main(){
    srand(time(0));
    freopen("papricice.in","r",stdin);
    freopen("papricice.out","w",stdout);
    n=read();
    rep(i,1,n-1) add(read(),read());
    rep(i,1,5) find(rand()%n+1,i),cnt=0;
    printf("%lld\n",ans);
}