正睿OI补题（排序，高精度）

大家好，欢迎来到IT知识分享网。

排序，高精度

目录：

P1017 [NOIP2000 提高组] 进制转换

P1908 逆序对

P1017 [NOIP2000 提高组] 进制转换

普及一下概念，负整数取模后是正整数取模的相反数，例如-15对-2取模得到-1，因此我们要用它减去模数，即为1。

[NOIP2000 提高组] 进制转换 – 洛谷

思路：一定要懂一个数学知识就是负进制余数的话，需要注意的是他可以转换为正进制的余数，比如说商为2，余数为-1那么就要用商-余数即可

#include<iostream> using namespace std; const int N = ; char a[N]; int n,m; int l = 0; int main() { int i; cin>>n>>m; cout<<n<<"="; while(n != 0) { int j = n % m; n /= m; if(j < 0) j-=m,n++;//如果余数<0，那么：余数-=m；商++； if(j < 10) a[++l] = (char)(j+48); else a[++l] = (char) ((j-10) + 'A'); } for(i = l;i >= 1;i--) { cout<<a[i]; } cout<<"(base"<<m<<")"<<endl; return 0; }

P1908 逆序对 

思路：详细看代码吧

#include<cstdio> #define ll long long using namespace std; const int maxn=5e5+5; //下面就是 归并排序求逆序对 的过程 int a[maxn],r[maxn],n; ll ans=0;//ans作为全局变量，记录逆序对的数量； void msort(int s,int t){ if(s==t) return ; int mid=s+t>>1; msort(s,mid),msort(mid+1,t);//→→→→→→→递归的体现 int i=s,j=mid+1,k=s; while(i<=mid&&j<=t) if(a[i]<=a[j]) r[k++]=a[i++];//先赋值再+1 else r[k++]=a[j++],ans+=(ll)mid-i+1;//可以理解为上面的数学归纳吧 while(i<=mid) r[k]=a[i],k++,i++; while(j<=t) r[k]=a[j],k++,j++; for(int i=s;i<=t;i++) a[i]=r[i];//复制回a数组中 } inline int read(){//快读 char ch=getchar(); int x=0,f=1; while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar(); return x*f; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) a[i]=read(); msort(1,n);//从1到n将a数组排序; printf("%lld\n",ans); return 0; }