21-22-1蓝桥训练4

• • T1：字串统计(暴力题)
  • T2：c++_ch06_02(cpp语法题)
  • T3：*找素数（有收获的题）
  • T4：种树(能暴力dfs过)
  • T5：质数的后代(简单质数筛)
  • T6：学做菜（签到题）

OJ平台

直接暴力计数枚举就行。

#include
using namespace std;
int main(){
    int l;string s;
    cin>>l>>s;
    int n = s.size();
    int num = INT_MIN;
    string res;
    mapcnt;
    map >cc;
    for(int len = l;len<=n;len++){
        for(int i=0;i<=n-len;i++){
                string cur = s.substr(i,len);
                cnt[cur]++;
        }
        for(map::iterator it = cnt.begin();it!=cnt.end();++it){
            cc[it->second].push_back(it->first) ;
        }
        map >::iterator  it = max_element(cc.begin(),cc.end());
        if(it->first>=num){
            num = it->first;
            int cmpidx = INT_MAX;
            for(int i=0;isecond.size();i++){
                int idx = s.find(it->second[i]);
                if(idxsecond[i];
                }
            }
        }
        cc.clear();
        cnt.clear();
    }
    cout< 
T2：c++_ch06_02(cpp语法题) 

 OJ平台
 
 
 
这道题主要就是不清楚到底该如何操作区域的push，这个时候直接用C++的vector容器解决一切问题！
 
 
#include 
using namespace std;
vectora,b;
int m,n,m1,n1;
void add(){
    if(n1==0){//如果需要push的个数为0则保存原样
        a.resize(m);
        return;
    }
    a.resize(m1);
    int i = 0;
    while(i>m>>n;
    a.resize(m+n);
    b.resize(n);
    for(int i=0;i>a[i];
    }
    for(int i=0;i>b[i];
    }
    cin>>m1>>n1;
    add();
    print();
}
 
T3：*找素数（有收获的题） 

 OJ平台
 
 
 
首先这种找质数的题目，很快想到质数筛。
 
 
普通质数筛的做法：
 
假设要更新一个从0~r 的质数筛，只需要外层循环为 0~sqrt(r) ,里层循环则每次都不断的增加 i(质数) 的倍数来更新不是质数的数，需要循环的范围是 i*i~r。
 
这马上出现一个问题，数据量非常大了该怎么办？
 
但如果r的范围太大质数筛也是顶不住的！毕竟质数筛更新也是需要O(n) 时间的，如果需要更新几十亿长度的质数筛，首先时间上就肯定已经是超时了！如果你用 bitset 的位来记录，空间上并不会超时，但时间上还是超时了！
 
所以对于数据量非常大的筛质数，我们肯定是只筛需要的范围内的质数！
 那么我们如何更新给定区间的质数筛呢？
 
这就引出了这道题的做法：通过辅助筛来维护另外一个区间筛！
 
什么是辅助筛？它是辅助我们完成是否为质数的判断筛，由于外层循环中的数据范围为 2~sqrt(r) 所以即便 r 为几十亿也是hold的住的，这个时候我们只需要建立一个 0~sqrt(r) 的质数筛对外层循环的判断进行一个辅助即可，让外层循环能马上判断出是否为质数，关于外层循环为什么是 sqrt® 而不是 r ，这里有很明显的对称性，所以只需要考虑 sqrt® 所有的 0~r 则均可被更新（毕竟乘以倍数进行更新的）。
什么是区间筛？也就是下标 0~n 映射的是一个区间 ，比如这题我们需要更新 [l,r] 区间的质数筛，那么我们在更新辅助筛的同时，首先找到 大于等于 l 的 i 的倍数(非质数) 的最小值，只要找到这个最小值，就可以直接往上一直不断的更新区间筛了！
如何找到大于等于 l 的 i 的倍数(非质数) 的最小值？我们只需要考虑到底这个 最小的i的倍数 为多少就行了，这一共有三种情况： 
  
如果 l 等于 i(质数步长) ，则最小的非质数倍数肯定就是 2 了，这也就是特殊情况了。
如果 l = i*k,(k!=1) 则这个倍数就是 k 。
如果 l%i!=0(无法被整除) ，则这个倍数肯定就是 l/i 再向上取整的结果了。
 
如何把这三种情况用一个式子解决？
 只需要这一个式子即可：max(2,(l+i-1)/i)
 
最后再提醒大家一下，由于这个数据量就是INT_MAX，所以随时存在爆INT的风险，所以千万千万用 LL！
 
#include
using namespace std;
#define INF 1000010
typedef long long ll;
ll l,r;
bitset isPrime1;//我们先通过isPrime1做好0~sqrt(r)的质数筛(只是起辅助作用，防止后续筛子判断过多)
bitset isPrime2;//然后顺手把l,r之间的质数筛也顺手做了，这个时候就需要我们注意先得到距离l最近的非质数！
void update(){
    isPrime1.set();
    isPrime2.set();
    isPrime1[0] = isPrime1[1] = 0;
    int cmp = sqrt(r);
    for(ll i=2;i*i>l>>r;
    update();
    int cnt = 0;
    for(ll i=l;i<=r;i++){
        if(isPrime2[i-l]){
            cnt++;
        }
    }
    cout< 
T4：种树(能暴力dfs过) 

 OJ平台
 
 
 
这一看就是可以通过排列组合过的问题，那么就直接通过回溯进行一个n个数中取m个数的枚举，对于两个树是否相邻可以根据check数组记录当前选择的情况，前一个和后一个的情况可以通过取模直接获得(可以无视最左和最右的特殊情况)。
 
 
#include 
using namespace std;
int n,m;
int res = INT_MIN;
vectorcheck(100);
vectorthings;
void dfs(int pos,int k,int sum){
    if(k==m){
        res = max(res,sum);
        return;
    }
    for(int i=pos;i>n>>m;
    things.resize(n);
    for(int i=0;i>things[i];
    }
    int t = n/2;
    if(m>t){//这是肯定无法进行间隔的情况
        cout<<"Error!";
        return 0;
    }
    dfs(0,0,0);
    cout< 
T5：质数的后代(简单质数筛) 

 OJ平台
 
#include 
using namespace std;
#define INF 1000000
bitsetisPrime;
int T;
void update(){//埃式筛
    isPrime.set();
    isPrime[0] = isPrime[1] = false;
    for(int i=2;i*i>T;
    for(int i=0;i>t;
        if(isCon(t)){
            cout<<"Yes"< 
T6：学做菜（签到题） 

 OJ平台
 
#include 
using namespace std;
int nums[4];
int res[5];
int things[5][4]={
        {2,1,0,2},
        {1,1,1,1},
        {0,0,2,1},
        {0,3,0,0},
        {1,0,0,1}
};
bool check(int i){
    for(int k=0;k<4;k++){
        if(things[i][k]>nums[k]){
            return false;
        }
    }
    for(int k=0;k<4;k++){
        nums[k] -= things[i][k];
    }
    res[i]++;
    return true;
}
void print(){
    for(int i=0;i<5;i++){
        cout<>nums[i];
    }
    for(int i=0;i<5;i++){
        while (1){
            if(!check(i))
                break;
        }
    }
    print();
}