A.算法提高 找素数

用到的算法：素数筛选
注意数据范围，L和R的选取范围在之间。说明普通的素数筛选暴力求解肯定是不行的。但是题目中给了，我们就可以根据这个关键来打表。
一个左右的合数，它的某个因子必定,所以我们可以先素数筛选出前的质数。然后给定的L和R，如果R在之前，就直接在之前打好的素数表直接计数复杂度O(),然后如果,我们就用前的质数去把后面的合数给筛掉，打个表。注意表需要进行坐标映射，也就是本来是[L,R]区间，然后映射到[0,R-L]，这样打表就不会超内存了。打表完了之后，计个数就可以了，复杂度

总时间复杂度

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 5e4+10;
typedef long long ll;
int L,R;
bool vis[maxn];//前sqrt的表
bool vis2[1000010];//[0,R-L]的表
int P[maxn],tail;//保存前sqrt的质数

void init(){
    vis[0] = vis[1] = true;
    for(ll i = 2;i<maxn;i++){
        if(!vis[i]){
            P[tail++] = i;
            for(ll j = i*i;j<maxn;j+=i){
                vis[j] = true;
            }
        }
    }
}
void judge(){ //用于对拍
    int cnt = 0;
    for(int i = L;i<=R;i++){
        int ok = 1;
        for(int j = 2;j*j<=i;j++){
            if(i%j == 0){
                ok = 0;
                break;
            }
        }
        if(ok) cnt++;
    }
    cout<<cnt<<endl;
}
void fun(){
    int cnt = 0;
    if(R<maxn){
        for(int i = L;i<=R;i++){
            if(!vis[i]) cnt++;
        }
    }else{
        for(ll i = 0;i<tail && P[i]*P[i]<=R;i++){
            for(ll j = (L+P[i]-1)/P[i];j<=R/P[i];j++){ //(L+P[i]-1)/P[i]为向上取整
                if(j == 0 || j == 1) continue;
                vis2[P[i]*j-L] = true; //-L是为了映射
            }
        }
        for(int i = 0;i<=R-L;i++)
            if(!vis2[i]) cnt++;
    }
    cout<<cnt<<endl;
}
int main(){
    init();
    cin>>L>>R;
    if(L == 1) L = 2;//1不是质数，直接跳过
    fun();
    return 0;
}

B.算法训练 区间k大数查询

用到的算法：排序

这题重在数据范围不大，询问次数也不大。我们完全可以在每次询问的时候，把[L,R]区间内的数拷贝出来，排个序，然后求第K大的数。总时间复杂度，是可以1s计算完的
总时间复杂度
AC 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1010;

int N,M;
int arr[maxn];

int fun(int l,int r,int k){
    int len = r-l+1,tail = 0;
    vector<int> ve(len);
    for(int i = l;i<=r;i++) ve[tail++] = arr[i];
    sort(ve.begin(),ve.end());
    return ve[len-k];
}
int main(){
    cin>>N;
    for(int i = 1;i<=N;i++) scanf("%d",&arr[i]);
    cin>>M;
    int l,r,k;
    while(M--){
        scanf("%d %d %d",&l,&r,&k);
        printf("%d\n",fun(l,r,k));
    }
    return 0;
}

C.算法训练 操作格子

用到的算法：线段树单点修改

这题是一个线段树的模板题，只不过是把区间求和和区间求最值绑定在了一起。具体怎么做就不讲了，因为线段树只是个工具，这题只是进行修改和查询而已，只是在用这个工具。
如果没有学习过线段树的同学，请看这个入门视频(代码风格不一样，但是思想是一样的):传送门

#include <iostream>
#include <algorithm>
#include <vector>
#define fs first
#define sc second
using namespace std;
const int maxn = 100010;
typedef pair<int,int> pii;
int N,M;
int arr[maxn];

struct node{
    int l,r;
    pii p;
}tr[4*maxn];

void pushup(node &fa,node &L,node &R){
    fa.p.fs = L.p.fs+R.p.fs;
    fa.p.sc = max(L.p.sc,R.p.sc);
}
void build(int u,int l,int r){
    if(l == r){
        tr[u] = {l,r,{arr[l],arr[l]}};
    } else{
        tr[u] = {l,r};
        int mid = (l+r)>>1;
        build(u*2,l,mid);
        build(u*2+1,mid+1,r);
        pushup(tr[u],tr[u*2],tr[u*2+1]);
    }
}
void modify(int u,int idx,int v){
    if(tr[u].l == idx && tr[u].r == idx){
        tr[u].p = {v,v};
    }else{
        int mid = (tr[u].l+tr[u].r)>>1;
        if(idx<=mid) modify(u*2,idx,v);
        else modify(u*2+1,idx,v);
        pushup(tr[u],tr[u*2],tr[u*2+1]);
    }
}
node query(int u,int l,int r){
    if(tr[u].l>=l && tr[u].r<=r){
        return tr[u];
    }else{
        int mid = (tr[u].l+tr[u].r)>>1;
        node p1,p2,p3;
        if(l<=mid) p2 = query(u*2,l,r);
        if(r>mid) p3 = query(u*2+1,l,r);
        pushup(p1,p2,p3);
        return p1;
    }
}
int main(){
    cin>>N>>M;
    for(int i = 1;i<=N;i++) scanf("%d",&arr[i]);
    build(1,1,N);
    int op,a,b;
    while(M--){
        scanf("%d%d%d",&op,&a,&b);
        if(op == 1){
            modify(1,a,b);
        }else if(op == 2){
            node res = query(1,a,b);
            printf("%d\n",res.p.fs);
        }else{
            node res = query(1,a,b);
            printf("%d\n",res.p.sc);
        }
    }
    return 0;
}

D.算法提高 士兵排队问题

用到的算法：拓扑排序
这是一个拓扑排序的模板题，主要是让大家回顾一下拓扑排序，这里是否可以排队其实就是问是否可以构成一个拓扑图，无果无法构成一个拓扑图就必定图中存在环。所以先要记录一下拓扑图中有多少人，然后在遍历拓扑图的时候，记录出去了多少人。如果存在环，那么必定存在有人还在图里面，因为环的存在出不来。

这题也是有一个坑点：他说的是能不能求出一种高低排序，我做的是否同时存在有两个入度为0的点，结果他的意思是是否存在环。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 300;
typedef pair<int,int> pii;

int in[maxn];//记录士兵的入度
bool st[maxn];//是否出现过
vector<char> h[maxn];//存储图
vector<char> ans; //结果
int main(){
    char str[4];
    while(~scanf("%s",str+1)){
        h[str[1]].push_back(str[3]);
        in[str[3]]++;
        st[str[1]] = st[str[3]] = true;
    }
    queue<char> q;
    for(int c = 'A';c<='Z';c++){
        if(in[c] == 0 && st[c]){
            q.push(c);
        }
    }
    int total = 0;
    for(int c = 'A';c<='Z';c++) if(st[c]) total++;
    while (q.size()){
        char u = q.front();q.pop();
        total--;
        ans.push_back(u);
        for(int i = 0;i<h[u].size();i++)
        {
            char v = h[u][i];
            --in[v];
            if(in[v] == 0) q.push(v);
        }
    }
    if(total == 0){
        for(int i = 0;i<ans.size();i++) cout<<ans[i];
    }else{ //total不为0，就说明有环
        puts("No Answer!");
    }
    return 0;
}

E.基础练习 十六进制转八进制

用到的算法：高精度
这题可以现将十六进制的每一位转换成4个二进制数，然后在对每3个二进制数进行转换成8进制就可以了。只是一些细节问题需要注意，比如二进制转八进制的时候，可能不是3的倍数，这时候就需要在前面补0，在输出的时候，如果有前导0就不需要输出。还有一些需要反着来处理的，也需要注意。

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 300;
typedef pair<int,int> pii;

int T;
map<char,int> mp;
void init(){ //初始化一下，把十六进制位数映射一下。
    for(char c = '0';c<='9';c++) mp[c] = c-'0';
    for(char c = 'A',v = 10;c<='F';c++,v++) mp[c] = v;
}
void fun(string &s){
    vector<int> bin(s.length() * 4);int idx = 3;//需要四倍长度
    for(int i = 0;i<s.length();i++,idx+=4){ // 十六进制转2进制
        int t = mp[s[i]];
        int ind = idx;
        while(t){
            bin[ind--] = t % 2;
            t/=2;
        }
    }
    while(bin.size()%3) bin.insert(bin.begin(),0); //补前导0，长度成3的倍数
    vector<int> eight;int cur = 0;
    for(int i = 0;i<bin.size();i++){ //二进制转8进制
        cur = cur*2+bin[i];
        if((i+1)%3 == 0)
            eight.push_back(cur),cur = 0;
    }
    for(int i = 0;i<eight.size();i++){
        if(i == 0 && eight[i] == 0) continue;
        cout<<eight[i];
    }
    cout<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    init();
    cin>>T;
    while(T--){
        string s;cin>>s;
        fun(s);
    }

    return 0;
}

F.算法训练 最大最小公倍数

用到的算法：思维
这题的关键在与只选取3个数，我们知道如果只选择两个数的话，那么肯定选两个相邻的两数，因为他两互质所以最小公倍数是最大的。所以面对要选择三个数，我们也可以设法选出3个互质的数。对于相邻的a,b,c三个数有奇偶奇，偶奇偶，可以发现奇偶奇三个数一定是互质的，a与b互质，b与c互质，a与b之间不可有共因子2，|c-a|<3,所以也不可能存在共因子3，之后的更别说了。
然后是偶奇偶，其最大最小公倍数必定至少除2，所以可以尝试把其中一个偶换成奇数，且不构成3的倍数，或者整体-1，变成奇偶奇。

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 300;
typedef pair<int,int> pii;
typedef long long ll;

ll N;
int main(){
    cin>>N;
    ll mx = 0;
    if(N<3) mx = 2;
    else if(N&1){ //奇偶奇
        mx = N*(N-1)*(N-2);
    }else{
        if(N%3 !=0){ //N和N-3不是3的倍数
            mx = N*(N-1)*(N-3);
        }else{ //整体-1
            mx = (N-1)*(N-2)*(N-3);
        }
    }
    cout<<mx<<endl;
    return 0;
}

G.算法提高 欧拉函数

用到的算法：欧拉筛
线性复杂度，把前maxn个数的欧拉值筛选出来

#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 2e6+10;
typedef pair<int,int> pii;
typedef long long ll;

ll N;
int E[maxn];
void init()
{
    E[1] = 1;
    for(int i=2;i<maxn;i++){
        if(!E[i])
            for(int j=i;j<maxn;j+=i){
                if(!E[j]) E[j]=j;
                E[j] = E[j]/i*(i-1);
            }
    }
}
int main(){
    init();
    cin>>N;
    cout<<E[N]<<endl;
    return 0;
}

H. 算法训练 乘法次数

用到的算法：快速幂
可以假定底数是2，然后就把 转换成二进制的形式，假如转换后的二进制，共有cnt个1，最高位1是poww，那么cnt个1就是cnt个底数相乘需要cnt-1次乘法，最高次方是poww需要经过poww-1次乘法，所以总共需要cnt+poww-2次乘法

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int T;
ll ksm(ll a,ll b){
    int poww = 0,cnt = 0;
    while(b){
        if(b&1) {
            cnt += 1;
        }
        a = a*a% mod;// 也可以不写
        poww++;
        b>>=1;
    }
    return poww+cnt-2;
}
int main(){
    cin>>T;
    while(T--){
        ll b;scanf("%lld",&b);
        printf("%lld\n",ksm(2,b));
    }

    return 0;
}

I.算法训练 方格取数

用到的算法：动态规划
此题不可以采用贪心策略的dp(分别走两次dp),因为有后效性。
考虑两个人同时走，就有四种可能，下下，右右，下右，右下，一共要走2*n-1步，所以dp需要三次循环，枚举步数，枚举第一个人的位置，枚举第二个人的位置。位置可以用一维来表示，也就是(x,y) 只用保存x就可以了，y = 步数-x来表示，然后要保证y不越界就好。然后每一步都是上一步下下，右右，下右，右下中取最大值+目前两人的位置上的数，如果两个人位置一样则只加一次。

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int N;
ll mp[11][11];
ll dp[22][11][11];

ll fun(){
    for(int k = 2;k<=N+N;k++){
        for(int i1 = 1;i1<=N;i1++){
            for(int i2 = 1;i2<=N;i2++){
                int j1 = k-i1,j2 = k-i2; //求出y坐标
                if(j1<1 || j2<1 || j1>N || j2>N) continue; //保证不越界
                ll mx = 0;
                mx = max(mx,dp[k-1][i1-1][i2]);//i1-1表示上一步是y+1,i2不减表示上一步是x+1
                mx = max(mx,dp[k-1][i1][i2-1]);
                mx = max(mx,dp[k-1][i1][i2]);
                mx = max(mx,dp[k-1][i1-1][i2-1]);
                if(i1 == i2) dp[k][i1][i2] = mp[i1][j1] + mx;
                else dp[k][i1][i2] = mp[i1][j1] + mp[i2][j2] + mx;
            }
        }
    }
    return dp[2*N][N][N];
}
int main(){
    cin>>N;
    int x,y,v;
    while(cin>>x>>y>>v){
        if(x == 0 && y == 0 && v == 0 ) break;
        mp[x][y] = v;
    }
    printf("%lld\n",fun());

    return 0;
}

J.基础练习 01字串

用到的算法：二进制枚举
这题也可以用DFS枚举，更可以直接写答案。
可以发现题目要求输出的字符串，其实就是0～31的二进制代码，所以二进制枚举一下就可以了。

#include <iostream>
#include <string>
using namespace std;

int main(){
    for(int i = 0;i<(1<<5);i++){
        for(int j = 4;j>=0;j--){
            if(i>>j &1) putchar('1');
            else putchar('0');
        }
        puts("");
    }

    return 0;
}