Codevs 1497
Codevs 3286
Codevs 1038
Codevs 1138
Codevs 1516
Codevs 1696（洛谷 P2759）
Codevs 1766
Codevs 2072
//Codevs1497取余运算 #include<iostream> using namespace std; long long b,p,k; long long ksm(long long p) { if(p==0)return 1; int t=ksm(p/2)%k; t=(t*t)%k; if(p%2==1)t=(t*b)%k; return t; } int main() { cin>>b>>p>>k; int tt=b; b%=k; cout<<tt<<"^"<<p<<" mod "<<k<<"="<<ksm(p)<<endl; } //快速幂 //Codevs 3286 火柴排队2013年NOIP全国联赛提高组 #include<cstdio> #include<iostream> #include<algorithm> #define LL long long #define M 99999997 using namespace std; const int MAXN=100000+10; struct node{int num,c;}l1[MAXN],l2[MAXN]; int N,goal[MAXN],bit[MAXN]; bool cmp(node a,node b){return a.c<b.c;} int lowbit(int k){return k&(-k);} void add(int x){while(x<=N)bit[x]++,x+=lowbit(x);} int sum(int x) { int tot=0; while(x>0) { tot+=bit[x]; x-=lowbit(x); } return tot; } int main() { scanf("%d",&N); for(int i=1;i<=N;i++)scanf("%d",&l1[i].c),l1[i].num=i; for(int i=1;i<=N;i++)scanf("%d",&l2[i].c),l2[i].num=i; sort(l1+1,l1+N+1,cmp);sort(l2+1,l2+N+1,cmp); for(int i=1;i<=N;i++)goal[l1[i].num]=l2[i].num; LL ans=0; for(int i=1;i<=N;i++) { add(goal[i]); ans+=i-sum(goal[i]); ans%=M; } printf("%lld ",ans); return 0; } //树状数组求逆序对orz //Codevs 1038 一元三次方程求解2001年NOIP全国联赛提高组 #include<cstdio> #include<iostream> using namespace std; double a,b,c,d,x1,x2,xx; double f(double x){return a*x*x*x+b*x*x+c*x+d;} int main() { cin>>a>>b>>c>>d; int x; for(x=-100;x<=100;x++) { x1=x;x2=x+1; if(f(x1)==0)printf("%0.2lf ",x1); else if(f(x1)*f(x2)<0) { while(x2-x1>=0.001) { xx=(x1+x2)/2; if(f(x1)*f(xx)<=0)x2=xx; else x1=xx; } printf("%0.2lf ",x1); } } return 0; } //二分水题 //Codevs1138 聪明的质监员2011年NOIP全国联赛提高组 #include<iostream> #include<cstring> #include<cstdio> #define N 200010 using namespace std; long long n,m,s,ll=123456789123456789,rr=-1,mid,ans=123456789123456798; long long w[N],v[N],le[N],ri[N],sum[N],summ[N]; bool check(int x) { long long i,y=0,p; for(i=1;i<=n;i++) { if(w[i]>x) { sum[i]=sum[i-1]+1; summ[i]=summ[i-1]+v[i]; } else { sum[i]=sum[i-1]; summ[i]=summ[i-1]; } } for(i=1;i<=m;i++) y=y+(sum[ri[i]]-sum[le[i]-1])*(summ[ri[i]]-summ[le[i]-1]); if(s>y) { p=s-y; i=0; } else { p=y-s; i=1; } if(p<ans)ans=p; return i; } int main() { std::ios::sync_with_stdio(false); cin>>n>>m>>s; for(long long i=1;i<=n;i++) { cin>>w[i]>>v[i]; if(w[i]<ll)ll=w[i]; if(w[i]>rr)rr=w[i]; } for(long long i=1;i<=m;i++)cin>>le[i]>>ri[i]; while(ll<=rr) { mid=(ll+rr)>>1; if(check(mid))ll=mid+1; else rr=mid-1; } printf("%lld ",ans); return 0; } //二分 //Codevs1516 平均分数 #include<cstdio> #include<cstring> #include<iostream> using namespace std; #define M 1000006 #define LL long long LL a[M],b[M],sum[M],t[M],N,L,R,C,ans,flag,tot; LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);} void merge(LL le,LL mid,LL ri,LL f[]) { LL i=le,j=mid+1,k=le; while(i<=mid&&j<=ri) if(f[i]<f[j]||(f[i]==f[j])*flag)t[k++]=f[i++]; else C+=(mid+1-i),t[k++]=f[j++]; while(i<=mid)t[k++]=f[i++]; while(j<=ri)t[k++]=f[j++]; for(LL o=le;o<=ri;o++)f[o]=t[o]; } void mergesort(LL le,LL ri,LL f[]) { if(le<ri) { LL mid=(le+ri)>>1; mergesort(le,mid,f),mergesort(mid+1,ri,f); merge(le,mid,ri,f); } } int main() { scanf("%lld%lld%lld",&N,&L,&R); for(LL i=1,x;i<=N;i++) { scanf("%lld",&x); sum[i]=sum[i-1]+x; } for(LL i=0;i<=N;i++)a[i]=L*i-sum[i],b[i]=R*i-sum[i]; ans=flag=C=0; mergesort(0,N,a); ans=C,C=0,flag=1; mergesort(0,N,b); tot=N*(N+1)/2,ans-=C; if(ans==tot)printf("1 "); else if(ans==0)printf("0 "); else { LL x=gcd(ans,tot); printf("%lld/%lld ",ans/x,tot/x); } return 0; } //二分 //奇怪的题目 //样例没过，提交上竟然AC了， (☄⊙ω⊙)☄ //洛谷P2759 奇怪的函数 #include<iostream> #include<cmath> using namespace std; int n; bool can(int x) { if(x*(log(x)/log(10))>=n-1)return true; return false; } int findx(int x,int y) { int mid=x+(y-x)/2; if(y-x<=1)return y; if(can(mid))return findx(x,mid); return findx(mid,y); } int main() { cin>>n; int ans=findx(0,1000000000); cout<<ans<<endl; return 0; } //二分答案+一个灰常6的数学公式 //codevs1766装果子 #include<cstdio> #define N 110000 long long n,m,sum=0,ans,max=0,a[N]; void find(long long le,long long ri) { if(le>ri)return; long long mid=(le+ri)>>1,s=0,k=0; for(long long i=1;i<=n;i++) { s+=a[i]; if(s>mid)k++,s=a[i]; } if(s)k++; if(k>m)find(mid+1,ri); else ans=mid,find(le,mid-1); } int main() { scanf("%lld%lld",&n,&m); for(long long i=1;i<=n;i++) { scanf("%lld",&a[i]); if(a[i]>max)max=a[i]; sum+=a[i]; } find(max,sum); printf("%lld ",ans); return 0; } //依旧是二分题…… //Codevs2072 分配房间 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAXN=100000+10; int N,M,barn[MAXN]; bool cmp(int a,int b){return a<b;} bool check(int x) { int last=0; for(int i=1;i<M;i++) { int cnt=last+1; while(cnt<N&&barn[cnt]-barn[last]<x)cnt++; if(cnt==N)return false; last=cnt; } return true; } int main() { scanf("%d%d",&N,&M); for(int i=0;i<N;i++)scanf("%d",&barn[i]); sort(barn,barn+N,cmp); int le=0,ri=barn[N-1]+barn[0]+1,mid; while(ri-le>1) { mid=(le+ri)>>1; if(check(mid))le=mid; else ri=mid; } printf("%d ",le); return 0; }