蓝桥杯自我复习打卡

总复习，打卡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 和 bfor (ll i = 1; i <= n; i++) {cin >> a[i];b[i] = a[i];F[a[i]] = i;  // 记录每个元素的位置}// 排序数组 bsort(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++;}// 对于每个环，需要交换的次数是环的长度 - 1if (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];// 输入查询数组 cfor (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;
}​