0x01 P1009 [NOIP1998 普及组] 阶乘之和

这题要用高精度乘法和高精度加法，把每位数字单独存储到一个数组中，每个元素如果大于9再进位，以此类推。这题的乘法是半个高精度，一个是高精度数字，另一个是普通的int数，简单了一点。

不过如果两个都是高精度数的乘法，原理差不多，就是把这个一个高精度一个普通的做好多遍，然后全部加起来再进位就好了，以后有机会再写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int i,sum[1005]={0},one[1005]={0},n,j;
int main(){
    cin >> n;
    sum[0]=one[0]=1;
    for (i=2;i<=n;i++){
        for (j=0;j<100;j++){
            one[j]*=i;
            //乘法操作
        }
        for (j=0;j<100;j++)
            if(one[j]>9){
                one[j+1] += one[j]/10;
                one[j]%=10;
            }
            //进位操作
        for (j=0;j<100;j++){
            sum[j]+=one[j];
            //加法操作
            if (sum[j]>9) {
                sum[j+1] += sum[j]/10;
                sum[j]%=10;
            }
            //进位操作
        }
    }
    i = 100;
    while(i>=0 && sum[i]==0){
        i--;
    }
    //抹0操作
    for (j=i;j>=0;j--){
        printf("%d",sum[j]);
    } 
    //输出
    return 0;
}

0x02 P1217 [USACO1.5] 回文质数 Prime Palindromes

sb题目，老是卡我时间。

先判断回文再判断质数，不然时间不够。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
bool zhi(int x){
    for(int i=2;i*i<=x;i++)
    {
        if(x % i == 0){
            return false;
        }
    }
    return true;
}
bool huiwen(int x){
    int y=0;
    int temp=x;
    while(x>0){
        y = y*10 + x%10;
        x /= 10;
    }
    if(temp==y){
        return true;
    }
    return false;
}
int main(){
    int a,b;
    cin >> a >> b;
    for(int i=a;i<=b;i++){
        if(i==9989900){
            break;
        }
        if(huiwen(i)&&zhi(i)){
            cout << i <<"\n";
        }
    }
    return 0;
}

0x03 P1420 最长连号

超级超级简单的动态规划，把每次最长的连号存储起来，断了就重新计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int a[10005];
int dp[10005];
int main(){
    int n,m = 0;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i];
        dp[i] = 1;
    }
    for(int i=1;i<n;i++){
        if(a[i]==a[i-1]+1){
            dp[i] += dp[i-1];
        }
    }
    for(int i=0;i<n;i++){
        m = max(m,dp[i]);
    }
    cout << m;
    return 0;
}

0x04 P3613 【深基15.例2】寄包柜

初次用容器vector和map解题，挺有意思的，map类似python的字典

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
map<int,map<int,int>> V;
vector<int> ans;
int n,q,i,j,k,opcode=0;
int main(){
    cin >> n >> q;
    for(int t=1;t<=q;t++){
        cin >> opcode >> i >> j;
        if(opcode==1){
            cin >> k;
            V[i][j] = k;
        }
        if(opcode==2){
            ans.push_back(V[i][j]);
        }
    }
    if(ans.size()!=0){
        for(vector<int>::iterator it = ans.begin();it != ans.end(); it++){
            cout << *it << '\n';
        }
    }
    return 0;
}

0x05 U264780 新生杯录取

题目大概的意思就是，再给定的很多数据里，挑选最小的几个然后排序。

由于限制了内存，先排序再取值很难实现，学习了堆排序的知识后，决定先取值再排序。

输入n个数据，然后排k，从小到大。

这里讲一下堆的结构，对于大堆，用完全二叉树的形式表示，他的任意一个节点的值总比他的左右孩子大，这里就隐含了一个信息，二叉树形式的堆的头结点的值是最大的，不管头结点的值怎么被修改，只要在此之后把堆维护一下，头结点的值仍然是最大的。用这个特性，我们在建立了k个元素的大堆后，之后每插入一个元素时先和头结点比较，如果更小就和头结点交换值，然后再维护一下，以此类推，最后堆内的k个元素必定是n个元素中最小的那几个，最后再堆排序一下输出。

知道思路后，关于堆，有建立堆，维护堆，堆排序三个操作，这里贴代码都有实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
int heap[105];
int n,k,temp;
void swap(int heap[],int a, int b){
    heap[0] = heap[a];
    heap[a] = heap[b];
    heap[b] = heap[0];
}
void correctHeap(int heap[],int index, int len){//维护堆的函数，始终保持大堆
    while(2 * index <= len){//如果index有孩子
        int l = 2*index, r = 2*index+1 ;
        int maxIndex = l;
        if(r <= len && heap[r] > heap[l]){
            maxIndex = r;
        }//判断左右孩子谁大
        if(heap[index] >= heap[maxIndex]){//如果双亲更大
            return;
        }
        swap(heap, index, maxIndex);
        index = maxIndex;
    }
}
void heapSort(int heap[], int len){//堆排序，从小到大
    int s = len;
    while(s > 1){
        swap(heap,1,s);
        s--;
        correctHeap(heap, 1, s);
    }
}
void heapCreate(int heap[], int len){
    int index = len/2;
    while(index >= 0){
        correctHeap(heap, index, len);
        index--;
    }
}
int main(){
    //改善输入输出流时间效率的代码，具体含义可以查一下
    std::ios_base::sync_with_stdio(false);std::cin.tie(0);
    cin >> n >> k;
    for(int i=1;i<=k;i++){
        cin >> heap[i];
    }
    //先建一个k大堆
    heapCreate(heap,k);
    //插入数据和堆顶比较，小就交换，大就舍去
    for(int i=1;i<=n-k;i++){
        cin >> heap[104];
        if(heap[104] < heap[1]){
            swap(heap,104,1);
            correctHeap(heap,1,k);
        }
    }
    //最后排序
    heapSort(heap,k);
    for(int i=1;i<=k;i++){
        cout << heap[i] << " ";
    }
    return 0;
}

堆的维护操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void correctHeap(int heap[],int index, int len){//维护堆的函数，始终保持大堆
    while(2 * index <= len){//如果index有孩子
        int l = 2*index, r = 2*index+1 ;
        int maxIndex = l;
        if(r <= len && heap[r] > heap[l]){
            maxIndex = r;
        }//判断左右孩子谁大
        if(heap[index] >= heap[maxIndex]){//如果双亲更大
            return;
        }
        swap(heap, index, maxIndex);
        index = maxIndex;
    }
}

堆的维护操作（这里以大堆为例子），其实就是让某个结点index和左右孩子结点比较，若双亲节点大则不用维护，若双亲节点小，交换双亲节点和值较大的那个孩子节点，之后有index 的节点继续作为双亲节点和他的孩子节点比较，直到叶子结点，或者双亲节点大。

堆的建立

1
2
3
4
5
6
7
void heapCreate(int heap[], int len){
    int index = len/2;
    while(index >= 0){
        correctHeap(heap, index, len);
        index--;
    }
}

堆的建立其实就是，把每个节点（叶子外）全都做一遍堆的维护，而且要自下而上（i—就可以实现)。这样做就能保证每个节点的左右孩子均比这个节点小。

堆排序

1
2
3
4
5
6
7
8
void heapSort(int heap[], int len){//堆排序，从小到大
    int s = len;
    while(s > 1){
        swap(heap,1,s);
        s--;
        correctHeap(heap, 1, s);
    }
}

堆排序，其实就是将堆顶元素一个一个取出来的操作，将堆顶元素和堆底元素交换，然后堆的大小减一，然后再把缩小后的堆维护一下，最后原先的那个堆，从堆底到堆顶，就是从大到小排序的数了，正着输出就是从小到大排序。

0x06 P1449 后缀表达式

这是一道用栈（stack）模拟算术的题，非常经典，故记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
char c;
int num = 0;
stack<int> sta;
void run_code(char code){
    int fir,sec;
    fir = sta.top();
    sta.pop();
    sec = sta.top();
    sta.pop();
    switch(code){
        case '+':
            sec += fir;
            break;
        case '-':
            sec -= fir;   
            break;
        case '*':
            sec *= fir;
            break;
        case '/':
            sec /= fir; 
            break;      
        default:
            break;
    }
    sta.push(sec);
}
int main(){
    while(true){
        cin >> c;
        if(c=='@'){
            break;
        }
        else if(c>='0' && c<='9'){
            num = 10*num + (c-'0');
        }
        else if(c=='.'){
            sta.push(num);
            num = 0;
        }
        else{
            run_code(c);
        }
    }
    cout << sta.top();
    return 0;
}

0x07 P1996 约瑟夫问题

刚开始学C语言时碰到的难题，现在看来豁然开朗，记录一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
vector<int> ans,people(101,0);
int n,m,cnt = 0,i=1;
int main(){
    cin >> n >> m;
    while(ans.size()!=n){
        if(people[i]==0){
            cnt++;
        } 
        if(cnt == m){//假如数到m了
            cnt =0;
            people[i] = 1;//赋值1代表出局
            ans.push_back(i);
        }  
        i = (i%n) + 1;       
    }
    for(vector<int>::iterator it=ans.begin();it!=ans.end();it++){
        cout << *it << " ";
    }
    return 0;
}

我用了模拟的方法，模拟这个过程进行。

0x08 P1160 队列安排

我真没想到我写的这一坨式能跑过，记录留念一下。

这题用链表查找，跑的内存真大，我以后看能不能优化一下这个思路。

内存爆满，有一说一，处理得不太好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<list>
#include<map>
using namespace std;
list<int> student;
map<int,list<int>::iterator> id; 
list<int>::iterator it;
int n,m,loc,stu_id;//学生数，去掉学生数

int main(){
    cin >> n;
    student.push_front(1);
    id[1] = student.begin();
    for(int i=2;i<=n;i++){
        cin >> stu_id >> loc;
        if(loc == 0){//插入左边
            id[i] = student.insert(id[stu_id],i);
        }
        if(loc == 1){//插入右边
            it = next(id[stu_id]);
            id[i] = student.insert(it,i);
        }
    }
    //删除操作
    cin >> m;
    for(int i=1;i<=m;i++){
        cin >> stu_id;
        if(*id[stu_id]!=0){
            *id[stu_id] = 0;
            student.erase(id[stu_id]);
        }
    }
    //输出
    for(it = student.begin();it!=student.end();it++){
        cout << *it << " ";     
    }
    //清空容器
    id.clear();
    map<int,list<int>::iterator>().swap(id);
    student.clear();
    list<int>().swap(student);
    return 0;
}

后来我写着写着发现，这题感觉根本就不用map这个东西，map容器id下标是int，完全用普通数组就可以胜任这个记录的工作。

后面看别人写的才发现insert操作会返回插入值位置的迭代器。。。。我还一直在搞什么it++，it—操作，搞得像个啥乱一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<list>
using namespace std;
list<int> student;
vector<list<int>::iterator> id;
list<int>::iterator it;
int n,m,loc,stu_id;//学生数，去掉学生数

int main(){
    cin >> n;
    id.resize(100005);
    student.push_front(1);
    id[1] = student.begin();
    for(int i=2;i<=n;i++){
        cin >> stu_id >> loc;
        if(loc == 0){//插入左边
            id[i] = student.insert(id[stu_id],i);
        }
        if(loc == 1){//插入右边
            it = next(id[stu_id]);
            id[i] = student.insert(it,i);
        }
    }
    //删除操作
    cin >> m;
    for(int i=1;i<=m;i++){
        cin >> stu_id;
        if(*id[stu_id]!=0){
            *id[stu_id] = 0;
            student.erase(id[stu_id]);
        }
    }
    //输出
    for(it = student.begin();it!=student.end();it++){
        cout << *it << " ";     
    }
    //清空容器
    id.clear();
    vector<list<int>::iterator>().swap(id);
    student.clear();
    list<int>().swap(student);
    return 0;
}

优化了一下，不使用map，而使用vector存取，内存消耗减少了一倍。

0x09 P1540 [NOIP2010 提高组] 机器翻译

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
using namespace std;
int m,n;//m是内存容量，n是单词个数
int cnt = 0, word;
vector<int> mem;
int main(){
    cin >> m >> n;
    mem.reserve(10000);
    for(int i=0;i<n;i++){
        cin >> word;
        if(find(mem.begin(),mem.end(),word) == mem.end()){
            mem.push_back(word);
            cnt++;
        }
        if(mem.size() > m){
            mem.erase(mem.begin());
        }
    }
    mem.clear();
    vector<int>().swap(mem);
    cout << cnt;
    return 0;   
}

队列问题，不过需要常常遍历这个队列，所以不用queue而用vector代替了。