蓝桥杯自我复习打卡

总复习，打卡1.

一。排序 1。选段排序

太可恶了，直接全排输出，一个测试点都没过。

AC

  首先，这个【l,r】区间一定要包含p,或者q，pq一个都不包含的，[l,r]区间无论怎么变，都对ans没有影响。

  其次，[l,r}区间端点一定要是l,或者r，或者两者都是，不然区间排序后，对应的a[p]不一定是最小的，a[q]也不一定是最大的。

  最后，minn=min(maxx,a[i])，均可以minn=min(minn,a[i])。

我们分别固定一个区间端点，然后去枚举另一个端点，求两个值，还有ans，利用大顶堆，big队列堆顶-minn,以保证ans尽可能大,small队列也是如此。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1e6+5; ll a[N]; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll n,p,q;cin>>n>>p>>q; for(ll i=1;i<=n;i++)cin>>a[i]; priority_queue<ll,vector<ll>,greater<ll>> small; priority_queue<ll,vector<ll>,less<ll>> big; ll minn=a[p],maxx=a[q]; ll len=q-p+1; big.push(a[p]); ll ans=0; for(ll i=p+1;i<=n;i++){ minn=min(maxx,a[i]); big.push(a[i]); if(big.size()>len)big.pop(); ans=max(ans,big.top()-minn); } small.push(a[q]); for(ll i=q-1;i>=1;i--){ maxx=max(maxx,a[i]); small.push(a[i]); if(small.size()>len)small.pop(); ans=max(ans,maxx-small.top()); } cout<<ans; return 0; }

 下面看细节，minn=min(minn,a[i]))，minn=min(maxx,a[i])的区别。

2。字串排序 

 （待补.......）

3。排序

P2824 [HEOI2016/TJOI2016] 排序 

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll n,m;cin>>n>>m; vector<ll> a(n+1,0); for(ll i=1;i<=n;i++)cin>>a[i]; while(m--){ ll op,l,r;cin>>op>>l>>r; if(op==0){ sort(a.begin()+l,a.begin()+r+1); }else if(op==1){ sort(a.rbegin()+l,a.rbegin()+r+1); } } ll q;cin>>q; cout<<a[q]; return 0; }

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, m; cin >> n >> m; vector<ll> a(n + 1, 0); // 注意下标从1开始 // 输入数组 for(ll i = 1; i <= n; i++) { cin >> a[i]; } // 处理m次操作 while(m--) { ll op, l, r; cin >> op >> l >> r; if(op == 0) { // 从a[l]到a[r]进行升序排序 sort(a.begin() + l, a.begin() + r + 1); // 正常的升序排序 } else if(op == 1) { // 从a[l]到a[r]进行降序排序 sort(a.begin() + l, a.begin() + r + 1, greater<ll>()); // 使用greater进行降序排序 } } ll q; cin >> q; cout << a[q] << endl; return 0; }

线段树。。。。。此处略过。。。 

 

4。区间排序

AC 

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll n,m;cin>>n; vector<ll> a(n+1,0); for(ll i=1;i<=n;i++)cin>>a[i]; cin>>m; while(m--){ ll l,r;cin>>l>>r; sort(a.begin()+l,a.begin()+r+1); } for(ll i=1;i<=n;i++)cout<<a[i]<<' '; return 0; } 5。奖牌排序

#include<bits/stdc++.h> using namespace std; typedef long long ll; struct node { ll x, y, z; // 重载操作符== bool operator==(const node& other) const { return x == other.x && y == other.y && z == other.z; } }; bool cmp1(const node &a, const node &b) { if (a.x != b.x) return a.x > b.x; else return 1; } bool cmp2(const node &a, const node &b) { if (a.y != b.y) return a.y > b.y; else return 1; } bool cmp3(const node &a, const node &b) { if (a.z != b.z) return a.z > b.z; else return 1; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n; cin >> n; vector<node> nodes(n); for (ll i = 0; i < n; i++) { cin >> nodes[i].x >> nodes[i].y >> nodes[i].z; } vector<node> n1(n), n2(n), n3(n); n1 = nodes; n2 = nodes; n3 = nodes; sort(n1.begin(), n1.end(), cmp1); sort(n2.begin(), n2.end(), cmp2); sort(n3.begin(), n3.end(), cmp3); for (ll i = 0; i < n; i++) { ll idx1 = find(n1.begin(), n1.end(), nodes[i]) - n1.begin(); ll idx2 = find(n2.begin(), n2.end(), nodes[i]) - n2.begin(); ll idx3 = find(n3.begin(), n3.end(), nodes[i]) - n3.begin(); cout << min({idx1, idx2, idx3})+1 << '\n'; } return 0; }

AC 

#include<bits/stdc++.h> using namespace std; typedef int ll; const ll N=200005; ll a[N],b[N],c[N]; ll a1[N],b1[N],c1[N]; ll n; bool cmp(ll x,ll y){ return x>y; } int erfen1(int x)//在a数组中二分查找 { int l = 0,r = n+1; while(l+1 < r) { int mid = (l+r)/2; if(a[mid] <= x) r = mid;//右边的都不是答案 else l = mid;//左边的都不是答案 } return r; } int erfen2(int x)//在b数组中二分查找 { int l = 0,r = n+1; while(l+1 < r) { int mid = (l+r)/2; if(b[mid] <= x) r = mid; else l = mid; } return r; } int erfen3(int x)//在c数组中二分查找 { int l = 0,r = n+1; while(l+1 < r) { int mid = (l+r)/2; if(c[mid] <= x) r = mid; else l = mid; } return r; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>n; for(ll i=1;i<=n;i++){ cin>>a1[i]>>b1[i]>>c1[i]; a[i] = a1[i]; b[i] = b1[i]; c[i] = c1[i]; } sort(a+1,a+n+1,cmp); sort(b+1,b+n+1,cmp); sort(c+1,c+n+1,cmp); //for(ll i=1;i<=n;i++)cout<<a[i]<<" "<<b[i]<<" "<<c[i]<<'\n'; for(ll i=1;i<=n;i++){ ll idx1=erfen1(a1[i]); ll idx2=erfen2(b1[i]); ll idx3=erfen3(c1[i]); cout<<min({idx1,idx2,idx3})<<'\n'; } return 0; } 6。排列排序

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int a[1000005]; int main() { int T; cin >> T; while (T--) { int n, ans = 0; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); int i = 1; while (i <= n) { if (a[i] == i) // 当前元素已经在正确的位置 { i++; } else // 不在正确位置 { int maxv = a[i]; int j = i + 1; maxv = max(maxv, a[j]); while (j <= n && maxv > j) // 继续扩展区间直到可以排序 { j++; maxv = max(maxv, a[j]); } ans += (j - i + 1); i = j + 1; // 跳过已处理的区间 } } cout << ans << endl; } return 0; } 7。数列排序 

 

这题老演员了，逆序遍历，每个数前面如果有比它大的数，就和比他大的最大的那个数交换位置，纸上模拟是对的，但事实却差强人意 。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 1e5 + 5; ll a[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n; cin >> n; for (ll i = 1; i <= n; i++) cin >> a[i]; ll count = 0; for (ll i = n; i >= 2; i--) { auto it = max_element(a + 1, a + i); if (it != a + i - 1) { // 如果当前最大元素不在当前位置 swap(*it, a[i - 1]); // 交换 count++; } } cout << count << '\n'; return 0; }

逆天，居然可以直接暴力。。。。。。。。应该Just do it。。。。。。这个题写法超级多，我看甚至还有人用dfs，树状数组。。

 AC

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 1e5 + 5; ll a[N]; ll b[N]; map<ll, ll> F; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n; cin >> n; // 输入数组 a 和 b for (ll i = 1; i <= n; i++) { cin >> a[i]; b[i] = a[i]; F[a[i]] = i; // 记录每个元素的位置 } // 排序数组 b sort(b + 1, b + n + 1); ll count = 0; for (ll i = 1; i <= n; i++) { if (a[i] != b[i]) { count++; ll x = F[b[i]]; // 获取 b[i] 在 a 数组中的原位置 F[a[i]] = x; // 更新位置映射 swap(a[x], a[i]); // 交换 } } cout << count << '\n'; return 0; } #include<bits/stdc++.h> using namespace std; struct node { int z,p;//其值、位置 }a[100005]; int n,b[100005],ans=0; bool cmp(node n1,node n2){return n1.z<n2.z;} int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&b[i]); a[i].z=b[i]; a[i].p=i; }//输入 sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++)//可以改成i<n { if(a[i].z==b[i])continue; int j=a[i].p;ans++; swap(b[i],b[j]);//注意了 b[i]和b[j]已交换 不要搞混对象 int l=i+1,r=n,mid; while(l<=r)//二分查找 { mid=(l+r)/2; if(a[mid].z>b[j])r=mid-1; else if(a[mid].z<b[j])l=mid+1; else break;//找到了 } a[mid].p=j;//修改地址 } printf("%d\n",ans); return 0; } #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> a(n), sorted_a(n); // 读取输入 for (int i = 0; i < n; i++) { cin >> a[i]; sorted_a[i] = a[i]; } // 排序后得到的数列 sort(sorted_a.begin(), sorted_a.end()); // 映射原数组到排序数组的索引 vector<int> index_map(n); for (int i = 0; i < n; i++) { auto it = find(sorted_a.begin(), sorted_a.end(), a[i]); index_map[i] = distance(sorted_a.begin(), it); } vector<bool> visited(n, false); int min_swaps = 0; // 遍历每个元素 for (int i = 0; i < n; i++) { // 如果这个元素已经被访问过或者已经在正确的位置上，跳过 if (visited[i] || index_map[i] == i) continue; // 计算环的长度 int cycle_length = 0; int j = i; while (!visited[j]) { visited[j] = true; j = index_map[j]; // 跳到下一个索引 cycle_length++; } // 对于每个环，需要交换的次数是环的长度 - 1 if (cycle_length > 1) { min_swaps += (cycle_length - 1); } } cout << min_swaps << endl; return 0; }

 非AC

本来不想用struct,想简化一下，结果弄巧成拙，我好像知道我哪里错了。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1e5+5; ll a[N]; ll b[N]; ll erfen(ll x,ll l,ll r){ ll mid=0; while(l<=r){ mid=(l+r)/2; if(b[mid]>x)r=mid-1; else if(b[mid]<x)l=mid+1; else break; } return mid; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll n;cin>>n; for(ll i=1;i<=n;i++)cin>>a[i],b[i]=a[i]; sort(b+1,b+n+1); ll count=0; for(ll i=1;i<=n;i++){ if(b[i]!=a[i]){ ll idx=erfen(a[i],i+1,n); swap(a[idx],a[i]); count++; } } cout<<count<<'\n'; return 0; }

修改一下：

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll n;cin>>n; ll a[n+1]; ll b[n+1]; map<ll,ll> mp; for(ll i=1;i<=n;i++){ cin>>a[i]; mp[a[i]]=i; b[i]=a[i]; } sort(b+1,b+n+1);///不要写成b+n了。。。。是b+n+1..... ll count=0; for(ll i=1;i<=n;i++){ if(a[i]!=b[i]){ count++; ll idx=mp[b[i]]; swap(a[idx],a[i]); mp[a[i]]=i; mp[a[idx]]=idx; //a[idx]=a[i]; } } cout<<count<<'\n'; return 0; } 8。分数排序

暴力才27分

#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> PII; const ll N = 1e5 + 5; ll a[N]; ll b[N]; ll c[N]; // 自定义比较函数，按最简分数的大小排序 bool cmp(const PII &a, const PII &b) { long double x = a.first * 1.0 / a.second; long double y = b.first * 1.0 / b.second; return x < y; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, q; cin >> n >> q; // 输入 a 和 b 数组 for (ll i = 1; i <= n; i++) cin >> a[i]; for (ll i = 1; i <= n; i++) cin >> b[i]; // 输入查询数组 c for (ll i = 1; i <= q; i++) cin >> c[i]; // 用 vector 存储所有分数 vector<PII> ppp; // 生成所有分数并存储 for (ll i = 1; i <= n; i++) { for (ll j = 1; j <= n; j++) { ll yueshu = __gcd(a[i], b[j]); ll x = a[i] / yueshu; ll y = b[j] / yueshu; ppp.push_back({x, y}); } } // 对分数按值进行排序 sort(ppp.begin(), ppp.end(), cmp); // 输出查询的分数 for (ll i = 1; i <= q; i++) { cout << ppp[c[i] - 1].first << " " << ppp[c[i] - 1].second << '\n'; } return 0; }

AC

#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const ll N =1e6+10; ll a[N],b[N]; bool p[N]; ll check(ld x,ll n){ ll i=1,j=0; ll sum=0; while(i<=n){ while((ld)a[j+1]<(ld)x*b[i]&&j<n)j++; sum+=j; i++; } return sum; } int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll n,q;cin>>n>>q; for(ll i=1;i<=n;i++)cin>>a[i],p[a[i]]=1; for(ll i=1;i<=n;i++)cin>>b[i]; sort(a+1,a+1+n); sort(b+1,b+n+1); //for(ll i=1;i<=n;i++)cout<<a[i]<<" "<<b[i]<<'\n'; while(q--){ ll c;cin>>c; ld r=(ld)a[n]/b[1]; ld l=(ld)a[1]/b[n]; ld mid=0; while((r-l)>=1e-13){ mid=(l+r)/2; if(check(mid,n)>=c)r=mid;//精度比较高，所以步长不可以为一了，也即不可以r=mid-1;l=mid+1; else l=mid; //else break; } ll fz=0; for(ll i=1;i<=n;i++){ fz=round(l*b[i]); if(fz<=1e6&&p[fz]==1&&fabs(fz-l*b[i])<1e-7){ ll yueshu=__gcd(fz,b[i]); //fz/=yueshu,b[i]/=yueshu;//不要这样会影响后面的数的计算 cout<<fz/yueshu<<" "<<b[i]/yueshu<<'\n'; break; } } } return 0; } 9。排列排序问题 

1~n的排列正序或者逆序，通过切割成若干子序列，重排子序列或者反转，使最终的整个排列有序，我们知道如果相邻元素不相差1，比如1 5 7 6 2 4 3，其中无论15怎么翻转都不会使最终序列有序，所以1，5一定要切割开，通过重排使其有序，题目也就转化成了，求abs（a[i+1]-a[i])>1的个数了。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1e6+5; ll a[N]; int main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); ll n;cin>>n; for(ll i=1;i<=n;i++)cin>>a[i]; ll cnt=0; for(ll i=1;i<n;i++){ if(abs(a[i+1]-a[i])>1) cnt++; } cout<<cnt<<'\n'; return 0; } 10。排序集合

​ #include<bits/stdc++.h> using namespace std; int n, k; int main() { // 读取输入 scanf("%d%d", &n, &k); // 特殊情况，如果k == 1，意味着空集 if (k == 1) { printf("0\n"); return 0; } k--; // 从0开始计数，因此减去1 // 遍历所有的元素 for (int i = 1; i <= n; i++) { // 如果k已经为0，说明我们已经找到了目标子集 if (k == 0) { break; } // 如果k小于等于 2^(n-i)，说明当前元素i必定在第k小的子集中 if (k <= pow(2, n - i)) { printf("%d ", i); // 输出当前元素 k--; // 减去已经选择的这个元素对应的子集数量 } else { // 如果k大于 2^(n-i)，说明当前元素i不在第k小的子集中 k -= pow(2, n - i); // 跳过包含当前元素i的子集，更新k } } return 0; } ​