递增三元组
思路:对A C数组排序后，分别二分A，C数组,这样我们就会得到A中小于B[ j ]的数和C中大于B[ j ]的数，由于 A C 是有序的，那么A数组二分数之前的数和C数组二分数之后的数也满足，两数组满足数相乘即可，这样我们边找到了包含B[ j ]的所有递增三元组的数量，遍历数组B即可。这种方法的时间复杂度为O ( n ( l o g n ) ) .
#include<iostream> #include<algorithm> using namespace std; //4 //1 3 4 5 //1 2 2 2 //2 3 3 4 int a[100010]; int b[100010]; int c[100010]; int n; long long ans = 0; int main(){ //输入数据 cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ cin>>b[i]; } for(int i=1;i<=n;i++){ cin>>c[i]; } //排序 sort(a+1,a+n+1); sort(b+1,b+n+1); sort(c+1,c+n+1); //定义两个指针（下标） int j = 1; int k = 1; //以b为中间值 在a数组 c数组中查找 for(int i=1;i<=n;i++){ while(j<=n && a[j] < b[i]) j++; //在a数组中查找第一个大于等于b[i]的数 while(k<=n && c[k] <= b[i]) k++; //在c数组中查找第一个大于b[i]的数 ans += (long long)(j-1) * (n-k+1); //计算公式 可以自己举例推导出来 } cout<<ans<<endl; }
螺旋折线
思路:我们可以将其看成有边长为2、4、6、8......的正方形组成的，所以可以根据给出的X、Y值求max(X,Y)来判断这个点是属于哪个正方形里面的，再从X,Y的位置判断是位于正方形的上下左右那一条边的来求dis(X,Y)
代码
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; typedef long long LL; const int Max_n=100005; int f(int x,int y,int n){ if(x==-n){ if(y==-n) return 8*n;//n*2*4; return y+n;//1+(y+n-1); } if(y==n){ return 3*n+x;//1+2*n-1+x+n; } if(x==n){ return 5*n-y;//1+2*n-1+2*n+n-y; } if(y==-n){ return 7*n-x;//1+2*n-1+2*n+2*n+n-x; } } int main(){ int x,y; scanf("%d%d",&x,&y); int n=max(abs(x),abs(y)); LL ans=1LL*n*(n-1)*4+f(x,y,n); printf("%lld\n",ans); return 0; }
日志统计
思路:这个在代码里标记得很清楚
代码
#include <iostream> #include <vector> #include <algorithm> #include <set> #include <map> using namespace std; int N,D,K,ans; //存储日志 struct log{ int id,time; }; //对id进行升序排序 bool cmp(log a,log b) { return a.time < b.time; } int main() { //快读配置 std::ios::sync_with_stdio(0); //读取规模 cin>>N>>D>>K; //存储多个日志并排序 vector<log> logs(N); for(int i = 0;i<N;++i) { cin>>logs[i].time>>logs[i].id; } sort(logs.begin(),logs.end(),cmp); //记录答案 set<int> ans; //记录id出现的次数 map<int,int>cnt; int j = 0;//哨兵 for(int i = 0;i<N;++i) { while(j<N&&logs[j].time-logs[i].time<D) { cnt[logs[j].id]++; if(cnt[logs[j].id]>=K)ans.insert(logs[j].id); j++; } cnt[logs[i].id]--; } for(set<int>::iterator i = ans.begin();i !=ans.end();i++)cout<<*i<<endl; return 0; }
全球变暖
思路:可以这样求解，通过广度优先遍历BFS查找地图,查找过程中记录某连通陆地中临近水的陆地数量和连通块里的陆地数量，如果二者相同那么该连通陆地会被淹没
#include <iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<queue> using namespace std; int N,ans; char F_area[1000][1000]; int M_area [1000][1000]; //坐标的四周 int Lx[] = {0,0,1,-1}; int Ly[] = {1,-1,0,0}; //存储坐标 struct Point{ int x,y; }; void BFS(int i,int j) { M_area[i][j] = 1;//标记该点已读 queue<Point> q; q.push({i,j});//将当前坐标存入队列 int cn1 = 0,cn2 = 0;//记录当前连通陆地的数量以及和水相邻的数量 while(!q.empty()) { Point first = q.front(); q.pop(); cn1 ++;//数量 bool swed = false;//标记该坐标四周是否有水 for(int k = 0;k<4;++k)//查找四周 { int x = first.x + Lx[k]; int y = first.y + Ly[k]; if(0<=x&&x<N&&0<=y&&y<N&&F_area[x][y]=='.')swed = true; if(0<=x&&x<N&&0<=y&&y<N&&F_area[x][y]=='#'&&M_area[x][y] ==0) { q.push({x,y});//与某陆地坐标相邻的陆地进入队列 M_area[x][y] = 1; } } if (swed)cn2++; //如果该坐标四周有水，则记录到临近水的陆地数量中 } if(cn1 == cn2)ans++;//某坐标点开始找，找完所有陆地 } int main() { //快读配置 std::ios::sync_with_stdio(0); //读取规模 cin>>N; //读取地图 for(int i = 0;i<N;++i) { for(int j = 0;j<N;++j) { cin>>F_area[i][j]; } } //进行广搜查找 for(int i = 0;i<N;++i) { for(int j = 0;j<N;++j) { if(M_area[i][j]==0&& F_area[i][j]=='#')//如果这个坐标是陆地且没有被访问过 { BFS(i,j); } } } cout<<ans<<endl;; return 0; }
乘积最大
思路:家人们肝不动了,拿大佬的代码，在这里给大家参考吧，共同学习
博客:蓝桥杯-历届试题-乘积最大_柯基吹泡泡的博客-CSDN博客_乘积最大蓝桥杯
代码
#include<iostream> #include<algorithm> using namespace std; const int N=1e5+10; long long int st[N]; int main() { int n,k; cin>>n>>k; int ft=0; for(int i=0;i<n;i++) { cin>>st[i]; if(st[i]<0)ft++; } sort(st,st+n); long long int ans=1; if(k%2!=0&&ft==n) { for(int i=0;i<k;i++) { ans=ans*st[n-1-i]%1000000009; ans=ans%1000000009; } cout<<ans%1000000009; return 0; } if(k%2!=0) { ans=st[n-1]; k--; n--; } int tt=0; int u=0,v=n-1; while(tt<k) { if(st[u]*st[u+1]>=st[v]*st[v-1]) { long long pp=st[u]*st[u+1]%1000000009; ans=ans*pp%1000000009; ans=ans%1000000009; u+=2; tt+=2; } else { long long oo=st[v]*st[v-1]%1000000009; ans=ans*oo%1000000009; ans=ans%1000000009; v=v-2; tt=tt+2; } } cout<<ans%1000000009; }
好啦，今天就到这里，学累了吧xdm，上图缓解视觉疲劳
