首页分享每日一练 19.2.18

每日一练 19.2.18

来源：花匠小妙招时间：2024-12-04 07:31

noip2013提高组

花匠

题目描述
花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。具体而言，栋栋的花的高度可以看成一列整数ℎ1, ℎ2, … , ℎn。设当一部分花被移走后，剩下的花的高度依次为g1, g2, … , gm，则栋栋希望下面两个条件中至少有一个满足：条件 A：对于所有的1 ≤ i ≤ m/2，g2i > g2i−1，且g2i > g2i+1；条件 B：对于所有的1 ≤ i ≤ m/2，g2i < g2i−1，且g2i < g2i+1。注意上面两个条件在m = 1时同时满足，当m > 1时最多有一个能满足。请问，栋栋最多能将多少株花留在原地。

输入
输入的第一行包含一个整数，表示开始时花的株数。
第二行包含个整数，依次为ℎ1, ℎ2,… , ℎn，表示每株花的高度。

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤ ℎn≤ 1,000,000，所有的ℎn随机生成，所有随机数服从某区间内的均匀分布。

输出
输出一行，包含一个整数m，表示最多能留在原地的花的株数。

样例输入
5
5 3 2 1 2

样例输出
3

思路
这题可以看做是一个最大抖动序列，设dp[i][0]为符合条件B的序列，dp[i][1]为符合条件A的序列，即可推出答案

代码实现

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849 火柴排队（逆序数）

题目描述
涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为：，其中 ai 表示第一列火柴中第 i 个火柴的高度，bi 表示第二列火柴中第 i 个火柴的高度。
每列火柴中相邻两根火柴的位置都可以交换，请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离，最少需要交换多少次？如果这个数字太大，请输出这个最小交换次数对 99,999,997 取模的结果。

输入
输入共三行，第一行包含一个整数 n，表示每盒中火柴的数目。
第二行有 n 个整数，每两个整数之间用一个空格隔开，表示第一列火柴的高度。
第三行有 n 个整数，每两个整数之间用一个空格隔开，表示第二列火柴的高度。

对于 100%的数据，1 ≤ n ≤ 100,000，0 ≤火柴高度≤ maxlongint

输出
输出共一行，包含一个整数，表示最少交换次数对 99,999,997 取模的结果。

样例输入
4
2 3 1 4
3 2 1 4

样例输出
1

提示
最小距离是 0，最少需要交换 1 次，比如：交换第 1 列的前 2 根火柴或者交换第 2 列的前 2 根火柴。

思路
由题目要求可推出当两个序列为同一顺序时，题目条件即成立，那么我们就可以构造出一个数组c，c[i]代表a序列不动，b序列中的第i个数字要移动到位置c[i]上，此时c中的逆序对个数就是我们的最小交换次数

代码实现
归并排序

#include <iostream> #include <cstdio> #include <string> #include <queue> #include <cstring> #include <cmath> #include <cctype> #include <vector> #include <algorithm> #include <map> #include <stack> using namespace std; typedef long long ll; typedef pair<int,int> pa; const int N=100005; const int mod=99999997; struct stri { int x,p,bp; }a[N],b[N]; int cnt=0; int c[N],tempa[N]; void merge_sort(int l, int r, int *A) { if(l>=r) return; int mid=(l+r)>>1; merge_sort(l,mid,A); merge_sort(mid+1,r,A); int ll=l,rr=mid+1,t=0; while(ll<=mid && rr<=r) { if(A[ll]<A[rr]) tempa[t++]=A[ll++]; else { tempa[t++]=A[rr++]; cnt+=(mid-ll+1)%mod; cnt%=mod; } } while(ll<=mid) tempa[t++]=A[ll++]; while(rr<=r) tempa[t++]=A[rr++]; for(int i=0;i<t;i++) A[i+l]=tempa[i]; } bool cmp1(stri a,stri b) { return a.p<b.p; } bool cmp2(stri a,stri b) { return a.x<b.x; } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i].x); a[i].p=i; } for(int i=0;i<n;i++) { scanf("%d",&b[i].x); b[i].p=i; } sort(a,a+n,cmp2); sort(b,b+n,cmp2); for(int i=0;i<n;i++) a[i].bp=b[i].p; sort(a,a+n,cmp1); for(int i=0;i<n;i++) c[i]=a[i].bp; merge_sort(0,n-1,c); printf("%dn",cnt%mod); return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475

树状数组

#include <iostream> #include <cstdio> #include <string> #include <queue> #include <cstring> #include <cmath> #include <cctype> #include <vector> #include <algorithm> #include <map> #include <stack> using namespace std; typedef long long ll; typedef pair<int,int> pa; const int N=100005; const int mod=99999997; struct node { int p,x; }a[N],b[N]; int c[N],n,s[N]; ll ans; bool cmp(node a,node b) { return a.x<b.x; } int lowbit(int x) { return x&(-x); } void update(int x) { for(int i=x;i<=n;i+=lowbit(i)) c[i]++; } void Search(int x) { for(int i=x;i>0;i-=lowbit(i)) { ans+=c[i]; ans%=mod; } } int main() { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i].x); a[i].p=i+1; } for(int i=0;i<n;i++) { scanf("%d",&b[i].x); b[i].p=i+1; } sort(a,a+n,cmp); sort(b,b+n,cmp); for(int i=0;i<n;i++) s[a[i].p]=b[i].p; for(int i=n;i>0;i--) { Search(s[i]); update(s[i]); } cout<<ans%mod<<endl; return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768