算法
一.java高精度
问题来说有封装好的两种类分别对应高精度整数和高精度浮点数,分别为BigInteger和BigDecimal。封装好的方法有add(), multiply(), subtract(), divide(), abs(), pow(), mod(), negate(), compareTo(), valueOf(), max(), min()。
代码:
package com.wzj.luogu;
import java.math.BigInteger;
import java.util.Scanner;
public class P1009x {
public static BigInteger Num(int n){
BigInteger result=new BigInteger("1");
for(int i=1;i<=n;i++){
result=result.multiply(new BigInteger(Integer.toString(i)));
}
return result;
}
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
BigInteger sum=new BigInteger("0");
int n=input.nextInt();
for(int i=n;i>0;i--){
sum=sum.add(Num(i));
}
System.out.println(sum);
input.close();
}
}
BigInteger和BigDecimal两者的相互转化:
BigDecimal x1 = in.nextBigDecimal();
BigInteger xx1 = x1.toBigInteger();
BigDecimal result1 = new BigDecimal(xx1.toString());
代码:
package com.wzj.luogu;
import java.util.Scanner;
import java.math.BigInteger;
public class P2142 {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
BigInteger a=input.nextBigInteger();
BigInteger b=input.nextBigInteger();
System.out.println(a.subtract(b));
input.close();
}
}
代码:
二.查找之二分法;
1.无重复数据且满足单调递增;
无限分割在[m,n],所以while(left<=right);
#include<stdio.h>
int BinarySearch(int A[],int left,int right,int num)
{
int mid;
while(left<=right)
{
mid=left+(right-left)/2;
if(A[mid]==num)
{
return mid+1;
}
else if(A[mid]>num)
{
right=mid-1;
}
else
{
left=mid+1;
}
}
return -1;
}
int main()
{
const int n=10;
int A[n]={1,3,4,6,7,9,10,12,33,77};
printf("%d %d\n",BinarySearch(A,0,n-1,4),BinarySearch(A,0,n-1,32));
return 0;
}
2.求序列中第一个大于等于x的元素的位置:
[m,n)左开右闭;
代码:
#include<stdio.h>
const int maxn=1e6+10;
int n,m,x;
int a[maxn];
int binary(int left,int right,int num)
{
int mid,flag=0;
while(left<=right)
{
mid=left+(right-left)/2;
if(a[mid]>num)
{
right=mid-1;
}
else if(a[mid]<num)
{
left=mid+1;
}
else
{
flag=mid,right=mid-1;
}
}
if(flag!=0)
{
return flag;
}
else
{
return -1;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
while(m--){
scanf("%d",&x);
printf("%d ",binary(1,n,x));
}
return 0;
}
1e6+10;(10的六次方加10)
1e-5;(10的负五次方)
自己写的代码:( Time Limit Exceeded.有很大的问题)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int m=input.nextInt();
int n=input.nextInt();
int school[]=new int[m];
int student[]=new int[n];
int result[]=new int[n];
int sum=0;
for(int i=0;i<m;i++){
school[i]=input.nextInt();
}
for(int i=0;i<n;i++){
student[i]=input.nextInt();
}
for(int j=0;j<n;j++){
int min=Integer.MAX_VALUE;
for(int i=0;i<m;i++){
int temp=Math.abs(student[j]-school[i]);
if(temp<min){
min=temp;
}
}
result[j]=min;
}
for(int i=0;i<n;i++){
sum+=result[i];
}
System.out.println(sum);
input.close();
}
}
网上给的代码:
#include<iostream>
#include<algorithm>
#include<cmath>
int m,n,a[100010],b[100010];
using namespace std;
int main()
{
cin>>m>>n;
for(int i=1;i<=m;i++)
{
cin>>a[i];
}
sort(a+1,a+m+1);
for(int i=1;i<=n;i++)
{
cin>>b[i];
}
int result=0;
for(int i=1;i<=n;i++)
{
int l=0,r=m+1;
while(l<r)
{
int mid=(l+r)/2;
if(a[mid]<=b[i])
l=mid+1;
else
r=mid;
}
if(b[i]<=a[1])
{
result+=a[1]-b[i];
}
else
{
result+=min(abs(a[l]-b[i]),abs(a[l-1]-b[i]));
}
}
cout<<result;
return 0;
}
代码:
#include<cstdio>
#include<cmath>
#include<iostream>
using std::cin;
const double eps = 1e-5;
const double PI = acos(-1.0);//返回一个数的反余弦
double f(double R,double h)
{
double alpha = 2 * acos((R - h) / R);
double L = sqrt(R * R - (R - h) * (R - h));
double s1 = alpha * R * R / 2 - L * (R - h) / 2;
double s2 = PI * R * R / 2;
return s1 / s2;
}
double solve(double R,double r)
{
double left = 0, right = R, mid;
while (right-left>eps)
{
mid = (left+right) / 2;
if (f(R,mid) > r)
right=mid;
else
left=mid;
}
return mid;
}
int main()
{
double R,r;
cin >> R >> r;
printf("%.4f\n", solve(R, r));
return 0;
}
代码:
1 | import java.util.Arrays; |
代码:
#include<iostream>
using namespace std;
typedef long long LL;
LL solvePower(int a,int b,int m)
{
if (b == 0)
return 1;
if (b % 2 == 1)
return a * solvePower(a,b-1,m)%m;
else
{
LL mul = solvePower(a,b/2,m);
return mul * mul % m;
}
}
int main()
{
int a, b, m;
cin >> a >> b >> m;
cout << solvePower(a, b, m);
return 0;
}
修改1(有问题)
int solve(char *p) { SqStack opnd; InitStack(opnd); while (*p != '@')
{
if (*(p+1)=='.'&&(*p!='.'))
{
int x = (int)(*p - '0'); Push(opnd,x); } else if (*p=='.')
{
p++;
continue;
}
else
{
int a, b, r;
Pop(opnd,a);
Pop(opnd,b);
r=operation(b,a,*p);
Push(opnd,r);
}
p++;
}
return GetTop(opnd);
}
修改2(有问题)
int solve(char *p) { SqStack opnd; InitStack(opnd); while (*p != '@')
{
int x=0,num=0;
if(Judge(*p)==1) { while(*p!='.')
{
x=(int)(*p-'0')+x*pow(10,num);
num++;
p++;
}
}
else if(Judge(*p)==2) { int a,b,r; Pop(opnd,a); Pop(opnd,b); r=operation(b,a,*p);
Push(opnd,r);
}
if(x!=0)
{
Push(opnd,x);
}
if(*p=='.')
{
p++;
continue;
}
p++;
}
return GetTop(opnd);
}
通过代码:
1 |
|
通过代码:
1 |
|
问题代码:
1 |
|
问题代码:
1 |
|
洛谷P1908
问题代码:
1 |
|