Leo's blog

建议麦当劳

发表于 更新于 分类于 本文字数： 315 阅读时长 ≈ 1 分钟

CPP 与 C

给算法竞赛入门阶段的同学的快速 c 转 c++ 速效救心丸。不适合系统学习使用。

区别1: 头文件不同

C++头文件没有.h

1
2
3
4
5
6
C语言:
#include <stdio.h>

C++语言:
#include <cstdio>
#include <stack> // C++头文件

如果要在c++代码中引用c语言的库, 去掉.h, 并在最前面加上c.

1
2
3
4
string.h >>> cstring
stdio.h  >>> cstdio
stdlib.h >>> cstdlib
...

区别2: 读入输出方式不同.

c++语言中只要引用了库就仍然可以用c语言的输入输出函数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
C++:
#include <iostream>
using namespace std;
int main(){
    int a;
    char b;
    char str[100] = {0};
    cin>>a>>b>>str;
    // 读入 cin 右箭头 变量名
    // 不需要&
    cout<<a<<b<<str<<endl;
    // 输出 cout 左箭头 变量名
    // endl和输出"\n"几乎等价
}

区别3: 命名空间

死记硬背即可, c++代码需要在引用头文件后添加一行

1
using namespace std;

非竞赛代码不推荐使用，会污染命名空间。

区别4: 布尔类型

c++语言自带布尔类型. 存储的是真和假两种情况.

1
2
3
4
5
6
7
8
bool a = false; //假, 与0等价
a = true; // 真, 与1等价
// 注意不要写为ture和flase
if(a){
    foo();
}else{
    bar();
}

c语言引用stdbool.h后也有, 但是课内不讲

发表于 分类于 本文字数： 589 阅读时长 ≈ 2 分钟

递归

把大问题分解为多个相似的小问题.

电影院问题: 获取人数, 如何获取?

1
2
3
函数 获取人数:
    如果 前面没人 返回1
    否则 问前面的人 前面有几个人 返回这个数+1

汉诺塔问题:

定义一个函数, 移动n个饼. 如果n=1, 直接移动即可. 如果n!=1, 那么对于上面的n-1个饼, 最下面的饼 并不会影响上面n-1个饼的移动. 所以, 可以递归调用此函数, 移动n-1个饼.

1
2
3
4
5
6
7
8
9
定义函数 移动饼(从哪儿,到哪儿,借助哪儿,饼数量):
    如果 饼数量 == 1 
        那么 把这个饼从"从哪儿"移动到"到哪儿"
    否则
        把 n - 1 个饼 从"从哪儿"移动到"借助哪儿"
        这个时候"从哪儿"这根柱子上的最后一个饼可以直接移动到"到哪儿".
        所以这时候, 移动第n个饼从"从哪儿"移动到"到哪儿"
        然后移动 n - 1 个饼从"借助哪儿"到"到哪儿"
        这个时候就完成了移动n个饼.

放苹果问题:

定义一个函数用于解决"n个苹果放到m个盘子里"问题.

那么这个问题, 可以分解为以下两种子情况:

  1. 每一个盘子内都放一个苹果
  2. 接下来不再对某个盘子放苹果
1
2
3
4
5
6
7
8
定义函数 放苹果(苹果数, 盘子数):
    如果 苹果数 == 0 或者 盘子数 == 1
        返回1
    如果苹果数小于盘子数:
        // 肯定至少有盘子数-苹果数个盘子空着
        返回 放苹果(苹果数, 苹果数)
    返回 放苹果(苹果数-盘子数, 盘子数) // 每一个盘子内都放一个苹果
         + 放苹果(苹果数, 盘子-1) // 接下来不再对某个盘子放苹果

括号匹配问题:

给出一个括号序列, 判断是否是匹配的括号序列.

先读入字符串, 每次处理一个字符. 如果是左括号, 就入栈. 如果是右括号, 首先判断栈中是否有元素(s.size() > 0), 如果有元素再判断栈顶元素是否是当前右括号对应的左括号. 如果是, 就把左括号出栈. 如果不是, 说明这个括号序列并不美观.

发表于 更新于 分类于 本文字数： 1.1k 阅读时长 ≈ 4 分钟

指针

说指针, 就不可避免的要和*这个运算符打交道. 因此, 我们首先要说的就是*的意思.

*的意思

第一种用法:

1
int * a = &b;

仅仅表示a是一个指针, 无其他含义

第二种用法:

1
*a = 2;

*运算符, 表示从指针取值.此处表示将a这个指针指向的变量的值设置为2.

编程语言中, 广义的值分为左值和右值.

变量名字都是左值, 意思是可以放在等号左边的值, 也就是可以被赋值的值.

常量(如123)以及一些运算结果(如b+1)是右值, 只能放在等号右边​, 不能被赋值.

此处的*a是一个左值, 可以被赋值.

编译错误中提到的lvalue和rvalue指左值和右值.

第三种用法:

1
b = 2 * 3;

仅表示乘法运算符.

可以看到, int * a 和 *a中的*的意义完全不同.

指针与变量

  1. 所有变量都存储在内存上的某个地址中, 每一个变量都有一个地址
  2. &运算符可以获取变量的地址, *运算符可以从地址获取值
  3. 地址按照字节编码(如: 地址0x100的值表示内存上的第0x100个字节), 而不是比特.
  4. 变量的值就是普通的值
  5. 指针的值是别的变量的地址
  6. 因此指针的值也可以是指针的地址(指针的指针)
  7. 因为指针存的是地址, 因此具有特殊性, 如果不初始化就访问会产生极其严重的后果, 因此要么初始化为某变量地址要么初始化为NULL.

指针=地址+类型

注: 0x开头的数字是16进制表示的数字, 如0x01 == 1; 0x10 == 16
一个字节是8个比特, 一个16进制数是4个比特(2^4==16), 因此一个16进制的两位数占用的空间大小是一个字节.

如何理解指针=地址+类型? 举个例子, 假设内存中的值是这样的:

值: 0x12 0x34 0x56 0x78
地址: 0x100 0x101 0x102 0x103

同时, 假设以下指针的值(指针中存储的地址)均为0x100:

1
2
3
int * a;
short * b;
char * c;

则有

1
2
3
*a == 0x12345678; //从0x100开始的4个字节
*b == 0x1234; //从0x100开始的2个字节
*c == 0x12; // 从0x100开始的1个字节

因为指针=地址+类型, 以上三个指针指向的地址相同, 但是因为类型不同, 读取到的值也不同. int指针读取到了4个字节的值, short指针读取到了2个字节的值, char指针读取了1个字节的值.

注: 以上均假设程序在运行在大端序的环境下, 如果你不知道啥是大端序请忽略.

再比如, 对于指针的运算, 指针的类型也起到决定性作用. 众所周知, 对于以下代码:

1
int data[100];

data是指向数组首元素的指针, data的值是数组首元素的地址.

data+1是指向数组第2个元素的指针, data+1的值是数组第二个元素的地址.

那么, 假设data=0x100, data+1等于多少?

显然, 一个int类型变量占用4个字节, data[0]占用了0x100, 0x101, 0x102, 0x103 这4个字节, 所以data+1应该等于0x104.

这就体现了一个问题: 指针运算需要知道指向的变量的大小.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int idata[10];
short sdata[10];
char cdata[10];

printf("%p\n", idata);
// 注: printf %p是打印了idata的值, 也就是idata数组的首项的地址.
printf("%p\n", idata + 1);
//会发现, idada+1 比 idata 大4

printf("%p\n", sdata);
printf("%p\n", sdata + 1);
//会发现, sdada+1 比 sdata 大2

printf("%p\n", cdata);
printf("%p\n", cdata + 1);
//会发现, cdada+1 比 cdata 大1

无类型指针

1
void * a = NULL;

a是一个无类型的指针. 因为没有类型, 所以不知道他的大小, 所以无法进行形如a+1的运算.
同样, 因为不知道类型, 也无法对这个指针"取值"(文章开头提到的*的第二个用法).

(c语言中, &运算符的作用是"取地址", *运算符的作用是"取值".)

malloc函数的返回值是void*类型, 这点也很容易理解. 他不知道你申请的内存要存什么类型的数据. 因此, 使用malloc时要进行强制类型转换:

1
int * a = (int*)malloc(10*sizeof(int));

发表于 分类于 本文字数： 1k 阅读时长 ≈ 4 分钟

大概每日N题(非课内难度)

被工大杯的各位julao打击到了的L同学决定大概每天刷题, 绝对不咕, 如果没有人问课内的问题的话就在这里写点竞赛难度的题吧.

题1 P1192 台阶问题

题目描述

有N级的台阶，你一开始在底部，每次可以向上迈最多K级台阶（最少1级），问到达第N级台阶有多少种不同方式。

输入格式

两个正整数N，K。

输出格式

一个正整数，为不同方式数，由于答案可能很大，你需要输出ansbmod 100003后的结果。

题解

复杂度O(nk).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
#define MAXN 100010
#define MOD 100003
int n,k;
int data[MAXN] = {1, 0};
int main(){
    cin>>n>>k;
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j <= k; ++ j){
            if(i-j>=0){
                data[i] += data[i-j];
            }
        }
        data[i] %= MOD;
    }
    cout<<data[n]<<endl;
    return 0;
}

题2 P1025 数的划分

题目描述

1
2
3
4
5
6
7
8
9
将整数n分成k份，且每份不能为空，任意两个方案不相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1,1,5;
1,5,1;
5,1,1;

问有多少种不同的分法。

输入格式

n,kn,k (6<n≤200, 2≤k≤6)

输出格式

1个整数，即不同的分法。

题解

DFS暴搜即可, 划分的时候保证升序防止出现重复.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
#define MAXN 210
#define MAXM 7
int n,k;
int classmateL(int n, int k, int min){
    //cout<<"Stepping In "<<n<<" "<<k<<endl;
    if(k == 1){
        return 1;
    }
    int ans = 0;
    for(int i = min; i <= n / k; ++ i ){
        ans += classmateL(n - i, k - 1, i);
    }
    //cout<<"Stepping Out "<<n<<" "<<k<<" "<<ans<<endl;
    return ans;
}
int main(){
    cin>>n>>k;
    cout<<classmateL(n,k,1);
    return 0;
}

题3 P1057 传球游戏

题目描述

1
2
3
4
5
上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。

游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没有传出去的那个同学就是败者，要给大家表演一个节目。

聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了mm次以后，又回到小蛮手里。两种传球方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有三个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。

输入格式

一行，有两个用空格隔开的整数n,m(3≤n≤30,1≤m≤30)。

输出格式

1个整数，表示符合题意的方法数。

题解

先想着DFS暴搜, 发现T了, 才想起来复杂度是O(m^2).

于是DP:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int n,m,dp[50][50];
int main() {
    cin>>n>>m;
    dp[0][0]=1;
    for(int i=0;i<m;i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][j]) {
                dp[i + 1][(j - 1 + n) % n] += dp[i][j];
                dp[i + 1][(j + 1) % n] += dp[i][j];
            }
        }
    }
    cout<<dp[m][0];
    return 0;
}

题4 P1996 约瑟夫问题

题目描述

n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号.

输入格式

n m

输出格式

出圈的编号

题解

本身想暴力, 结果莫名re和tle, 只得使用队列.

STL大法好

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <queue>
using namespace std;
int main() {
    int n,m;
    cin>>n>>m;
    queue<int> que;
    for(int i = 1; i <= n; ++ i){
        que.push(i);
    }
    for(int i = 1; i <= n; ++ i){
        for(int j = 1; j < m; ++ j){
            que.push(que.front());
            que.pop();
        }
        cout<<que.front()<<" ";
        que.pop();
    }
    return 0;
}

发表于 分类于 本文字数： 852 阅读时长 ≈ 3 分钟

"工大杯"程序设计竞赛 罚时之旅

大家好, 我就是L·罚时一年·同学.

A题

DFS会WA.
题目有点问题, 没说明一定是一颗树, 但是数据太水, 导致直接求直径就能A. 正解是先判环在DFS, 可是我并没有写出来.

B题

乍一看还以为是表达式求值, 仔细看发现不考虑符号优先级. 注意从右往左结合, 因此读入所有数字到数字栈, 符号到符号栈, 每次取栈顶运算输出结果即可.
正解是直接倒序遍历字符串, 可是STL大法好

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
#include <iostream>
#include <string>
#include <sstream>
#include <cstdlib>
#include <stack>
using namespace std;

#define DEBUG 1

void solve(){
    string tmp;
    cin>>tmp;
    stack<int> nums;
    stack<char> ops;
    istringstream sin(tmp);
    int temp = 0;
    sin>>temp;
    char op;
    nums.push(temp);
    while((op = sin.get()) != EOF){
        ops.push(op);
        sin>>temp;
        nums.push(temp);
    }
    int ans = nums.top();
    nums.pop();
    int b;
    while(!ops.empty()){
        op = ops.top();
        b = nums.top();
        ops.pop();
        nums.pop();
        if(op == '+'){
            ans += b;
        }
        else if(op == '-'){
            ans -= b;
        }
        else if(op == '*'){
            ans *= b;
        }
        else if(op == '/'){
            ans /= b;
        }
    }
    cout<<ans<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C题

网络流, 可是我并不会

D题

最开始还以为是数论, 用gcd推了半天, 没推出来. 然后发现是裸的初中数学.

a*b = a+b = i, 消元, 列二次方程, 得到a^2 - a*i + i = 0. 判别式大于等于0只需 i*i - 4*i>=0.

当然也可以简单地判断 n 是否在(0,4)内

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <cstdio>
using namespace std;
int main(){
    long long n;
    cin>>n;
    cout<<((n*n-4*n>=0)?"YES":"NO")<<endl;
    return 0;
}

E题

板子里有, 可是我不会高静模, 于是 GG.

正解并不需要高静. 每次读入 n 的一位, 分别模 p 和 p-1, 算2^(n-1%(p-1))*n%p即可.

F题

不会

G题

水题, 暴力即可. 看错题了导致WA一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int ans = 0;
    while(n != 1){
        if(n%2){
            n = 3 * n + 1;
        }else{
            n = n / 2;
        }
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}

H题

并不会, 正解是摩尔投票算法.

I题

DP, 用 count[x][i] 表示第 x 位涂色为 i 所花费的最少钱数.
转移方程: count[x][i] = min(count[x-1][j] + cost[x][j], j!=i) cost[x][j] 表示将 x 涂为颜色 j 所花费的钱.
是线性递推, 可以压缩至一维 dp, 但没必要.

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
#include <iostream>
using namespace std;
#define MAXN 1010
#define min(a,b) ((a)<(b)?(a):(b))
int n;
int R[MAXN] = {0};
int B[MAXN] = {0};
int G[MAXN] = {0};
int coust[MAXN][4] = {0};
int main(){
    cin>>n;
    for(int i = 0; i < n; ++ i){
        cin>>R[i]>>G[i]>>B[i];
    }
    //R 1 G 2 B 3
    coust[0][1] = R[0];
    coust[0][2] = G[0];
    coust[0][3] = B[0];
    for(int i = 1; i < n; ++ i){
        coust[i][1] = min(R[i] + coust[i-1][2],R[i]+coust[i-1][3]);
        coust[i][2] = min(G[i] + coust[i-1][1],G[i]+coust[i-1][3]);
        coust[i][3] = min(B[i] + coust[i-1][1],B[i]+coust[i-1][2]);
    }
    int minn = 0x7fffffff;
    minn = min(minn,coust[n-1][1]);
    minn = min(minn,coust[n-1][2]);
    minn = min(minn,coust[n-1][3]);
    cout<<minn<<endl;
    return 0;
}

J题

大水题, 详情请见本公众号推送的"每日一题-每位数字问题".
记得特判0.
如果使用数字解法, 则不需要处理前导0. 如果使用字符串需要处理前导0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n == 0){
        cout<<0<<endl;
        return 0;
    }
    while(n){
        cout<<n%10;
        n/=10;
    }
    cout<<endl; 
    return 0;
}

部分题解和官方正解雷同, 并不是我抄袭, 正解就是我写的.

发表于 分类于 本文字数： 271 阅读时长 ≈ 1 分钟

大概每日一题-较大的正整数的因子

今天的题

题目描述

1
求正整数n(<2 000 000 001)的所有因子

输入

1
一个小于 2 000 000 001 的正整数

输出

1
2
按从小到大的顺序输出这个整数的所有因子，不包含1和它本身
每个因子占一行

做题思路1:

遍历0到sqrt(n)的每一个数, 判断是否是n的因子, 如果是, 就存起来, 之后遍历存起来的数, 输出一对因子中的另一个.

伪代码:

1
2
3
4
5
6
7
8
输入n
循环i从2到sqrt(n):
    如果n % i == 0:
        输出i
        data[count++] = i
循环i从count-1到0:
    如果data[i]!=sqrt(n):
        输出n/data[i]

伪代码2

1
2
3
4
5
6
7
8
9
循环i从2到sqrt(n)-1:
    如果n%i==0:
        输出i
如果(int)(sqrt(n))*(int)(sqrt(n)) == n
    意味着n是完全平方数, sqrt(n)也是一个因子
    输出sqrt(n)
循环i从sqrt(n)-1到i
    如果n%i==0:
        输出n/i

后者相较前者省略了一个数组.

0%