2_04

辽宁师范大学 • 张大为@https://daweizh.github.io/noip/

2.4 基本算法之分治(7)

2011，http://noi.openjudge.cn/ch0204/2991/[+]

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

char s[210];
int k,n;

long long powm(int a,int n,int m){
  if(n==0) return 1;
  long long x =powm(a,n/2,m);
  long long ans = ((x%m)*(x%m))%m;
  if(n%2!=0) ans = ans*a%m;
  return ans;
}
int main(){
  cin >> k;
    
  for(int i=0;i<k;i++){
    cin>>s;
    if(strlen(s)<=4) n=atoi(s);
    else n=atoi(s+strlen(s)-4);
    cout << powm(2011,n,10000)<< endl;
  }
  
  return 0;
}

输出前k大的数，http://noi.openjudge.cn/ch0204/7617/[+]

#include <iostream>
#include <algorithm>
using namespace std;
int n,a[100005],k;

bool comp(int a,int b){
  return a>b;
}
int main(){
  cin >> n;
  for(int i=0;i<n;i++)
    cin >> a[i];
  cin >> k;
  sort(a,a+n,comp);
  for(int i=0;i<k;i++)
    cout << a[i] << endl;

  return 0;
}

区间合并，http://noi.openjudge.cn/ch0204/7620/[+]

#include <iostream>
#include <algorithm> 
using namespace std;

struct region{
  int left;
  int right; 
}rgn[50005];

int n,lft,rgt;

bool comp(region a,region b){
  return a.left < b.left;
}

int main(){
  cin >> n; 
  for(int i=0;i<n;i++){
    cin >> rgn[i].left >> rgn[i].right;
  }
  
  sort(rgn,rgn+n,comp);
  
  int flag = 1;
  for(int i=1;i<n;i++){
    if(rgn[i].left>=rgn[i-1].left && rgn[i].left<=rgn[i-1].right){
      rgn[i].left = rgn[i-1].left;
      if(rgn[i].right < rgn[i-1].right)
        rgn[i].right = rgn[i-1].right;
    }else{
      cout << "no" << endl;
      flag = 0;
      break;
    }
  }
  
  if(flag)
    cout << rgn[n-1].left << " " << rgn[n-1].right << endl;
    
  return 0;
}

求排列的逆序数，http://noi.openjudge.cn/ch0204/7622/[+]

#include <iostream>
using namespace std;

int n,a[100005],r[100005];
long long ans = 0;

void merge(int lft,int rgt){
  if(lft==rgt) return;
  int mid = (lft+rgt)/2;
  merge(lft,mid);
  merge(mid+1,rgt);
  int i=lft,j=mid+1,k=lft;
  while(i<=mid && j<=rgt){
    if(a[i]<=a[j]){
      r[k]=a[i]; k++; i++;
    }else{
      r[k]=a[j]; k++; j++;
      ans = ans + mid-i+1;
    }
  }
  while(i<=mid){
    r[k]=a[i];i++;k++;
  }
  while(j<=rgt){
    r[k]=a[j];k++;j++;
  }
  for(int i=lft;i<=rgt;i++)
    a[i]=r[i];
}

int main(){

  cin >> n;
  for(int i=0;i<n;i++)
    cin >> a[i];
  
  merge(0,n-1);
  
  cout << ans << endl;	

  return 0;
}

一元三次方程求解，http://noi.openjudge.cn/ch0204/7891/[+]

#include <iostream>
using namespace std;

double a,b,c,d;

double f(double x){
  return a*x*x*x+b*x*x+c*x+d;
}

double F(double l,double r){
  double lft=l,rgt=r;
  while(lft<rgt){
    double mid=(lft+rgt)/2;
    double ans1 = f(lft);
    double ans2 = f(mid);
    
    if(ans1*ans2<=0){
      rgt=mid;
    }else{
      lft=lft+0.0001;
    }
  }
  return rgt;
}

int main(){
  
  cin >> a >> b >> c >> d;
  
  for(double i=-100;i<100;i++){
    double ans1 = f(i);
    double ans2 = f(i+1);
    if(ans1==0) 
      printf("%.2f ",i);
    if(ans1*ans2<0){
      printf("%.2f ",F(i,i+1));
    }		
  }
  cout << endl;
  
  return 0;
}

统计数字，http://noi.openjudge.cn/ch0204/7909/[+]

#include <iostream>
#include <map>
#include <set>
using namespace std;

int n,x;
map<int,int> a;
set<int> b; 

int main(){
  cin >> n;

  for(int i=0;i<n;i++){
    cin >> x;
    a[x]++;
    b.insert(x);
  }
  for(set<int>::iterator it=b.begin();it!=b.end();it++)
    printf("%d %d\n",*it,a[*it]);
    
  return 0;
}

Stupid cat & Doge，http://noi.openjudge.cn/ch0204/8463/[+]

#include <cmath>
#include <iostream>
using namespace std;
struct E {long long x,y;};
E fenzhi(long long n,long long x){
  E e;
  if(n==1) {
    e.x=1;
    e.y=1;
    return e;
  }
  if(x>n*n/4 && x<=n*n/2){
    e=fenzhi(n/2,x-n*n/4);
    e.y+=n/2;
  }else if(x>n*n/2 && x<=n*n/4*3){
    e=fenzhi(n/2,x-n*n/2);
    e.x+=n/2;
    e.y+=n/2;
  }else if(x>0 && x<=n*n/4){
    e=fenzhi(n/2,n*n/4-x+1);
    long long t=n/2-e.x+1;e.x=e.y;e.y=t;
  }else{
    e=fenzhi(n/2,n*n-x+1);
    long long t=n/2-e.y+1;e.y=e.x;e.x=t;e.x+=n/2;
  }
  return e;
}
int main(){
  int $,i,j,k;
  long long n,x,y;
  cin>>$;
  for(i=1;i<=$;i++){
    cin>>k>>x>>y;
    n=pow(2,k);
    E x1=fenzhi(n,x),y1=fenzhi(n,y);
    long double da=(x1.x-y1.x)*(x1.x-y1.x);
    long double db=(x1.y-y1.y)*(x1.y-y1.y);
    long double dc=da+db;
    long double dis=sqrt(dc)*10;
    long long dr=dis+0.5;
    cout<<dr<<endl;
  }
  return 0;
}

参考网址

http://noi.openjudge.cn