T1：字串统计(暴力题)

OJ平台

直接暴力计数枚举就行。

#include<bits/stdc++.h>
using namespace std;
int main(){int l;string s;cin>>l>>s;int n = s.size();int num = INT_MIN;string res;map<string,int>cnt;map<int,vector<string> >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<string,int>::iterator it = cnt.begin();it!=cnt.end();++it){cc[it->second].push_back(it->first) ;}map<int,vector<string> >::iterator  it = max_element(cc.begin(),cc.end());if(it->first>=num){num = it->first;int cmpidx = INT_MAX;for(int i=0;i<it->second.size();i++){int idx = s.find(it->second[i]);if(idx<cmpidx){cmpidx = idx;res = it->second[i];}}}cc.clear();cnt.clear();}cout<<res;
}

T2：c++_ch06_02(cpp语法题)

OJ平台

这道题主要就是不清楚到底该如何操作区域的push，这个时候直接用C++的vector容器解决一切问题！

#include <bits/stdc++.h>
using namespace std;
vector<int>a,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<n1){a.push_back(b[i]);i++;}
}
void print(){int sz = a.size();for(int i=0;i<sz-1;i++){cout << a[i] << ", ";}cout<<a[sz-1]<<endl;
}
int main(){cin>>m>>n;a.resize(m+n);b.resize(n);for(int i=0;i<m;i++){cin>>a[i];}for(int i=0;i<n;i++){cin>>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的倍数 为多少就行了，这一共有三种情况：
  1. 如果 l 等于 i(质数步长) ，则最小的非质数倍数肯定就是 2 了，这也就是特殊情况了。
  2. 如果 l = i*k,(k!=1) 则这个倍数就是 k 。
  3. 如果 l%i!=0(无法被整除) ，则这个倍数肯定就是 l/i 再向上取整的结果了。
• 如何把这三种情况用一个式子解决？
  只需要这一个式子即可：max(2,(l+i-1)/i)

最后再提醒大家一下，由于这个数据量就是INT_MAX，所以随时存在爆INT的风险，所以千万千万用 LL！

#include<bits/stdc++.h>
using namespace std;
#define INF 1000010
typedef long long ll;
ll l,r;
bitset<INF> isPrime1;//我们先通过isPrime1做好0~sqrt(r)的质数筛(只是起辅助作用，防止后续筛子判断过多)
bitset<INF> 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<r;i++){if(isPrime1[i]){for(ll j = i*i;j<=cmp;j+=i){//更新辅助筛isPrime1[j] = 0;}//核心算法：求出大于等于l的最小非质数for(ll j = max(2LL,(l+i-1)/i)*i;j<=r;j+=i){//更新真正需要的质数筛isPrime2[j-l] = 0;}}}
}
int main(){cin>>l>>r;update();int cnt = 0;for(ll i=l;i<=r;i++){if(isPrime2[i-l]){cnt++;}}cout<<cnt;
}

T4：种树(能暴力dfs过)

OJ平台

这一看就是可以通过排列组合过的问题，那么就直接通过回溯进行一个n个数中取m个数的枚举，对于两个树是否相邻可以根据check数组记录当前选择的情况，前一个和后一个的情况可以通过取模直接获得(可以无视最左和最右的特殊情况)。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int res = INT_MIN;
vector<bool>check(100);
vector<int>things;
void dfs(int pos,int k,int sum){if(k==m){res = max(res,sum);return;}for(int i=pos;i<n;i++){if(!check[(i-1+n)%n]&&!check[(i+1+n)%n]){check[i] = true;dfs(i+1,k+1,sum+things[i]);check[i] = false;}}
}
int main(){cin>>n>>m;things.resize(n);for(int i=0;i<n;i++){cin>>things[i];}int t = n/2;if(m>t){//这是肯定无法进行间隔的情况cout<<"Error!";return 0;}dfs(0,0,0);cout<<res;
}

T5：质数的后代(简单质数筛)

OJ平台

#include <bits/stdc++.h>
using namespace std;
#define INF 1000000
bitset<INF>isPrime;
int T;
void update(){//埃式筛isPrime.set();isPrime[0] = isPrime[1] = false;for(int i=2;i*i<INF;i++){if(isPrime[i]){int j = i;while (i*j<INF){isPrime[i*j] = 0;j++;}}}
}
bool isCon(int n){if(isPrime[n])return false;for(int i=2;i*i<=n;i++){if(n%i==0&&isPrime[i]&&isPrime[n/i]){return true;}}return false;
}
int main(){update();cin>>T;for(int i=0;i<T;i++){int t;cin>>t;if(isCon(t)){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}}return 0;
}

T6：学做菜（签到题）

OJ平台

#include <bits/stdc++.h>
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<<res[i]<<endl;}
}
int main(){for(int i=0;i<4;i++){cin>>nums[i];}for(int i=0;i<5;i++){while (1){if(!check(i))break;}}print();
}