Asswei's blog
0%

OJ基础

Posted on Edited on In Views:
Symbols count in article: 466 Reading time ≈ 1 mins.

常见的评测结果

-AC:accept
-CE:compile error
-WA:wrong answer
-TLE:time limit exceeded
-RE:runtime error:数组越界，指针乱指，
-MLE:memory limit exceeded
-PE:presentation error

基础知识

int:-210^9~210^9
long long:-910^18~910^18
char:-128~127
int占4Byte，10^9以内的数都可以int型
long long型赋值大于2^31的初值，需要在后面加上LL，否则编译出错

1
long long bignum = 123456789012345LL;

浮点型用double存储，占64位，printf(“%f”,c);
1
2
3
4
#define pi 3.14
const double pi = 3.14
#define ADD(a,b) ((a)+(b))
#define MAX(a,b) ((a)>(b)?(a):(b))

位运算符：
int型上限是2^31-1，所以INF可以设置为(1<<31)-1,**这里必须加括号，因为位运算符优先级没有算术运算符高** 但是一般更常用的是2^30-1，避免相加超过int，写成二进制是0x3fffffff 
1
2
const int INF = (1<<30)-1
const int INF = 0x3fffffff

scanf(“%lld”,&long); printf(“%lld”,long);
scanf(“%lf”,&db); printf(“%f”,db);
scanf(“%s”,str);
scanf可以不加空格的原因，对于其他格式符的输入以空白符(空格、tab)作为结束标志
使用%s读入以空格和换行作为读入结束标志。

想要输出%和\在前面加上一个相应符号
printf(“%%”);
printf(“\“);
%md右对齐，补空格
%0md右对齐，补0

typedef给复杂的类型起一个别名
typedef long long LL;
LL a = 12134;
数学函数：
fabs(double x)
floor(double x) ceil(double x)
pow(double r,double p) round(double x)

对数组中每一个元素赋相同的值，memset按字节赋值

1
2
#include <cstring>
memset(a,0,sizeof(a))  //只建议赋值为0或-1，赋值为其他的建议fill

strlen(str) strcmp(s1,s2)返回负数，0，正数
strcmp(s1,s2) 把s2的值赋值给s1
strcat(s1,s2) 把字符数组2接到字符1后面

sscanf把字符数组str中的内容以%d形式写到n中

1
2
int n; char str[10]="233";
sscanf(str,"%d",n);

sprintf把n以%d的形式写到字符数组中（从右至左）
1
2
int n=233; char str[10];
sprintf(str,"%d",n);

如果自己重新定义了构造函数，则不能不经初始化就定义结构体变量，
可以手动再加上默认的构造函数
1
2
3
4
5
6
7
8
9
10
struct studentInfo{
    int id;
    char gender;
    studentInfo(){}
    studentInfo(int _id,char _gender){
        id = _id;
        gender = _gender;
    }

}

1
studentInfo(int _id,char _gender):id(_id),gender(_gender){}

补充
1
2
3
const double eps = 1e-8;
const double Pi = acos(-1.0)
#define Equ(a,b) ( (fabs((a)-(b)))<(eps) )

scanf函数的返回值为成功读入的参数的个数，读入失败时会返回-1，即EOF
while(scanf(“%s”,str) != EOF)
while(gets(str) != NULL)
当输入的a,b都为0时结束
while(scanf(“%d%d”,&a,&b),a||b)

判断闰年:是4的倍速但不是100倍数，或者是400的倍数

1
2
3
bool isLeap(int year){
    return (year%4==0 && year%100!=0) || (year%400==0);
}

进制转换
（1）将P进制数x转换为十进制数y
1
2
3
4
5
6
7
8
9
int transform2ten(int P,int x){
    int y=0,product=1;
    while(x!=0){
        y += (x%10) * product;  加上这个数乘权重
        x/=10;                   去掉个位
        product *= P;            权重数
    }
    return y;
}

(2)将十进制数y转换为Q进制数z
除基取余法，Q即为基，余数保存到地位中，
1
2
3
4
5
int num=0,z[40];
do{
    z[num++] = y%Q;
    y/=Q;
}while(y!=0);

从z[num-1]到z[0]即转换完成。采用do-while是当y=0时，while会直接退出，
导致错误，应当是z[0]=0。

选择排序

首先从待排序中找到最小元素A[k]，与待排序第一个元素A[i]交换

1
2
3
4
5
6
7
8
9
10
11
for(int i=1;i<=n;i++){
    int k=i;
    for(int j=i;j<=n;j++){
        if(A[j]<A[k])
            k=j;
    }
    //交换A[k]与A[i]
    int temp = A[i];
    A[i]=A[k];
    A[k]=temp;
}

插入排序

将未排序的第一个元素插入到已经排序好的合适的位置

1
2
3
4
5
6
7
8
9
10
11
12
int A[maxn],n;   //数组下标为1~n
void insertSort(){
    for(int i=2;i<=n;i++){
        int temp=A[i],j=i;
        while(j>1 && temp<A[j-1]){
            A[j] = A[j-1];
            j--;
        }
        A[j] = temp;
    }
}

归并排序

先对两个进行排序

1
//

结构体排序，先按照分数排序，然后姓名字典序小的在前

1
2
3
4
bool cmp(Student a,Student b){
    if(a.score!=b.score) return a.score>b.score;
    else return strcmp(a.name,b.name)<0;
}

结构体的排名
1
2
3
4
5
6
7
stu[0].r=1;
for(int i=1;i<n;i++){
    if(stu[i].score == stu[i-1].score)
        stu[i].r = stu[i-1].r;
    else
        stu[i].r = i+1;
}

散列

将元素通过一个函数转换为整数，使得该整数可以尽量唯一地代表这个元素。
将字符串转换为一个整数，判断该整数位置是否有元素

分治可以采用递归的方法实现，也可以采用非递归方法实现。

1
2
3
4
int F(int n){
    if(n==0 || n==1) return 1;
    else return F(n-1)+F(n-2);
}

全排列

区间贪心

区间不相交问题，

快速幂，二分幂

1
2
3
4
5
6
7
8
9
10
11
typedef long long LL;
LL binaryPow(LL a, LL b,LL m){
    if(b==0) return 1;
    if(b%2==1) return a*binaryPow(a,b-1,m)%m;
    else{
        LL mul = binaryPow(a,b/2,m);
        return mul*mul%m;
    }
}


vector
(1)push_back(1)
(2)pop_back()
(3)v.size()
(4)v.clear()
(5)v.insert(v.begin()+2, 8);
(6)v.erase(v.begin()+3) 删除v[4]
v.erase(v.begin()+1,v.begin()+4) 删除v[1],v[2],v[3]
v.erase(v.begin(),v.end()) 删除所有元素，v.end()是尾元素地址的下一个地址
Set内部自动有序且不含重复元素

map
同一个键，不同的值被后一个赋的值覆盖

1
2
mp['m'] = 20;
mp['m'] = 30; //20被覆盖

it->first输出顺序按照键的大小

queue
q.push(i) 将i压入队列 q.pop()将队首元素弹出
q.front() q.back() 获取队列队首和队尾元素
使用这两个操作前，先对队列判空

pair

1
2
3
4
5
6
7
8
#include <utility>
添加map时自动添加了utiliy
(1)pair<string,int>p
   p = make_pair("xixi",5);
(2)pair<string,int>p1("xixi",5);

map<string,int>mp;
mp.insert(make_pair("haha",5));

p1\<\p2先比较p->first，

algorithm
max(),min()可以整数和浮点数，但是参数只能两个
abs()必须整数，浮点数取绝对值用math下的fabs()
swap()交换两个数的值
reverse() 对数组合字符串进行翻转
next_permutation()
do{
printf(“%d%d%d\n”,a[0],a[1],a[2]);
}while(next_permutation(a,a+3));
fill() fill(a,a+5,233);
lower_bound(first,last,val) 寻找第一个大于等于val值位置
upper_bound(first,last,val) 寻找第一个大于val值位置
printf(“%d,%d\n”,lower_bound(a,a+10,3)-a,upper_bound(a,a+10,3)-a )

栈

清空：top=-1
size:top+1;

链表
1.malloc函数 stdlib.h free(p)
int p =(int)malloc(sizeof(int));
node p =(node)malloc(sizeof(node));
2.new delete(p)
int p =new int;
node p =new node;
静态链表