第一个填空题前缀和
第二个填空题质数筛
这道题的难点
1. 质数筛要知道
2. 数据范围容易爆，各种爆int爆longlong要小心处理，否则前功尽弃
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e7+9;//10^7再平方的范围肯定是大于23333333333333
ll ans = 0;
ll prime[N];
bool vis[N];
int main(){
int n = sqrt(N);
for(int i=2;i<=n;i++){// 埃氏筛 ,也可以线性筛，都一样
if(!vis[i]){
for(int j=i*i;j<=N;j+=i){
vis[j] = true;
}
}
}
int cnt = 0;
for(int i=2;i<=N;i++){
if(!vis[i]){
prime[cnt++] = i;
}
}
for(ll i=0;i<cnt;i++){
ll pp = prime[i]*prime[i];
if(pp * pp >23333333333333) break;//一点小优化
for(ll j=i+1;j<cnt;j++){
ll qq = prime[j]*prime[j];
if(pp*qq>23333333333333) break;
if(pp*qq<2333) continue;
ans++;
}
}
cout<<ans<<endl;
return 0;
}
班级活动
纯暴力
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int cnt[N];
int main() {
int n;
cin >> n;
for(int i = 1;i <= n;i++){
int a;
cin >> a;
cnt[a]++;
}
int p = 0,q = 0;
for(int i = 1;i <= n;i++){
if(cnt[i] > 2){
q += cnt[i] - 2;
}else if (cnt[i] == 2 || cnt[i] == 0){
continue;
}else if (cnt[i] == 1){
p++;
}
}
int ans = 0;
ans += q;
if(p - q > 0){
ans += (p-q)/2;
}
cout << ans << endl;
}
合并数组
暴力解法就是用双指针，每次哪个小哪个进位，可以拿75%的分。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int s1[N],s2[N];
int main(){
int n,m;
cin >> n >> m;
// 计算第一个数组的前缀和
s1[0] = 0;
for(int i = 1; i <= n; i++){
int a;
cin >> a;
s1[i] = s1[i-1] + a;
}
// 计算第二个数组的前缀和
s2[0] = 0;
for(int i = 1; i <= m; i++){
int a;
cin >> a;
s2[i] = s2[i-1] + a;
}
int ans = 0;
int i = 1, j = 1;
// 同时遍历两个前缀和数组
while(i <= n && j <= m) {
if(s1[i] == s2[j]) {
// 当前前缀和相等，继续比较下一个
i++;
j++;
} else if(s1[i] < s2[j]) {
// s1的前缀和较小，需要前进i
i++;
ans++; // 每前进一次i，相当于删除了一个元素
} else {
// s2的前缀和较小，需要前进j
j++;
ans++; // 每前进一次j，相当于删除了一个元素
}
}
cout << ans << endl;
return 0;
}
正解为双端队列。与直接双指针相比，队列更加灵活，可以处理到更多的情况，适合“合并”这一用法。
#include<bits/stdc++.h>
using namespace std;
long long n,m,a,sum;//sum 用于记录答案
deque<int>a1,a2;
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a,a1.push_back(a);//输入 n 次 a，并在 a1 队列中加入 a 元素
for(int i=0;i<m;i++)
cin>>a,a2.push_back(a);//输入 m 次 a，并在 a2 队列中加入 a 元素
while(!a1.empty())//如果 a1 队列还有剩余元素，那么就继续运行程序
{
if(a1.front()==a2.front())//如果相等就直接出队
{
a1.pop_front();//弹出 a1 队列中的第一个元素
a2.pop_front();//弹出 a2 队列中的第一个元素
}
else if(a1.front()>a2.front())//如果a2小就合并a2的前两个数
{
a2[1]+=a2[0];//将 a2 队列中的第 1 项和第 2 项合并
a2.pop_front();//弹出 a2 队列中的第一个元素
sum++;//将合并次数增加 1
}
else//如果 a1 小就合并 a1 前两个数
{
a1[1]+=a1[0];//将 a1 队列中的第 1 项和第 2 项合并
a1.pop_front();//弹出 a2 队列中的第一个元素
sum++;//将合并次数增加 1
}
}
cout<<sum<<endl; //输出需要合并的次数
}
数三角
有点难，没想出来很好的暴力，直接看正解吧。
大概意思就是，记录完所有点的x，y坐标，枚举每一个点到其他点的距离，存入map中，在后续调用map中的值，只要距离一样的就累加答案。还要注意不能共线。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
double dis(ll x1, ll y1, ll x2, ll y2){
return pow((x1 - x2), 2) + pow((y1-y2),2);
}
bool check(pll p1, pll p2, pll p3){//判断是否三点共线
if(p1.second == p2.second || p1.second == p3.second) return p1.second == p2.second && p1.second == p3.second;
double a = (p1.first - p2.first) * 1.0 / (p1.second-p2.second);
double b = (p1.first - p3.first) * 1.0 / (p1.second-p3.second);
return abs(a - b) < 1e-6;
}
int main() {
ll n; cin >> n;
vector<pll> arr;
for (int i = 0; i < n; ++i) {
ll x, y;
cin >> x >> y;
arr.emplace_back(x, y);
}
ll ans = 0;
//equ[i]存储的是第i个点所对应的map表
//map表的含义是 有哪些点到第i个点的距离为key，这些点的下标用一个vector收集
vector<map<double,vector<int>>> equ(n);
for(int i = 0; i < n; ++i){
auto m= equ[i];
for(int j = 0; j < n; ++j){//遍历其他的所有点，在map中记录相等距离
if(i != j){
pll p1 = arr[i]; pll p2 = arr[j];
double d = dis(p1.first,p1.second,p2.first,p2.second);
m[d].push_back(j);
}
}
//收集完成之后，遍历这张map表
for(const auto& [k,v] : m){
for(int a = 0; a < v.size(); ++a){ //从到当前点的距离相等的点之中选取两个点a，b
for(int b = a + 1; b < v.size(); ++b){
if(!check(arr[i],arr[v[a]],arr[v[b]])){//只要不是三点共线
ans++;
}
}
}
}
}
cout << ans;
}
AB路线
讲真有点复杂，看得我头晕，好久没写算法题了。。。
一种特殊的bfs代码是直接扒的，注释我自己写的。
通过三维数组来额外记录每个点的不同状态是否走过。
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f//定义最大值
using namespace std;
const int N = 1e3 + 10;
int g[N][N];
bool st[N][N][20];//前两个记录坐标，最后一位记录状态
int dis[N][N][20];//前两个记录坐标，最后一位记录状态
int n, m, k;
int dx[4] = {-1, 0, 1, 0};//定义bfs的四个方向
int dy[4] = {0, 1, 0, -1};
bool check(int x, int y) {//判断是否出界
return x >= 0 && x < n && y >= 0 && y < m;
}
int bfs() {
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
for(int p = 0; p < k; p ++) {
dis[i][j][p] = INF;//所有点的所有状态先初始化为正无穷
}
}
}
queue<array<int,3>>q;//array定义一个定长的数组
q.push({0, 0, 1});//先加入左上角的点
dis[0][0][1] = 1;//更新状态
st[0][0][1] = true;//更新判断
while(q.size()){//bfs经典，当队列不为空时一直执行
auto t = q.front();//取出队首元素
q.pop();
int x = t[0], y = t[1], cnt = t[2];//取出坐标和状态
int d = dis[x][y][cnt];
for(int i = 0; i < 4; i ++) {
int nx = x + dx[i];
int ny = y + dy[i];
int nc = (d / k) % 2;//判断该走哪个
if(check(nx, ny) && g[nx][ny] == nc && !st[nx][ny][(d + 1) % k]) {//判断是否出界，判断下一个是否合法，以及下一个点是否在当前状态走过
st[nx][ny][(d + 1) % k] = true;//更新判断
q.push({nx, ny, (d + 1) % k});//加入下一个点
dis[nx][ny][(d + 1) % k] = d + 1;//更新最短路
}
}
}
int minv = INF;
for(int i = 0; i < k; i ++) {//将所有可能状态的终点分别取最小值，得到最小的可能路线并返回
minv = min(minv, dis[n - 1][m - 1][i]);
}
return minv;
}
void solve(){
cin >> n >> m >> k;
for(int i = 0; i < n; i ++) {
string s; cin >> s;
for(int j = 0; j < m; j ++) {
g[i][j] = (s[j] != 'A');//0/1决定状态
}
}
int res = bfs();
if(res == INF){
cout << -1 << endl;
}else{
cout << res - 1 << endl;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while(t--){
solve();
}
return 0;
}
抓娃娃
思维题
只需要知道条件中给出的最大的线段长小于等于最小的区间长就能得出只要区间过了线段的终点即可包含该线段。
在这道题中，还有一点很关键，那就是直接求中点会有小数，不方便比较，可以都乘以二，这样规避了小数的问题
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10; //数据范围：1e6 * 2 （由下可知为什么乘以2）
int a[N] , s[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n , m;
cin >> n >> m;
while(n--){
int l , r;
cin >> l >> r;
a[l + r]++; //取中点（至少一半），为避免像1/2这样的小数，所以直接乘以2（ (l + r) / 2 * 2 ）
}
for(int i = 1 ; i <= N ; i++) s[i] = s[i - 1] + a[i];
while(m--){
int l , r;
cin >> l >> r;
cout << s[r * 2] - s[l * 2 - 1] << endl; //与上面相应的，这里也要乘以2
}
return 0;
}
OK累了，23年的蓝桥杯就此完结
