Leo's blog

建议麦当劳

发表于 更新于 分类于 本文字数： 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

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

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

各类排序算法及比较

选择排序:

每次选择还未排序的值中最小的一个, 和第一个交换.

思路很清晰, 代码很好写, 时间复杂度为O(n^2).

伪代码:

1
2
3
4
5
6
7
8
9
// 要排序的数组: data[n]
循环i从0到n-1:
    min = 0x7fffffff
    pos = 0
    循环j从i到n-1:
        如果 min > data[j]:
            pos = j
            min = data[j]
    交换data[pos]与data[i]

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int i,j,min,pos,t;
for(i = 0; i < n; ++ i){
    min = 0x7fffffff;
    pos = 0;
    for(j = i; j < n; ++ j){
        if(min > data[j]){
            pos = j;
            min = data[j];
        }
    }
    t = data[i];
    data[i] = data[pos];
    data[pos] = t;
}

冒泡排序

枚举相邻的两个, 如果前者大于后者, 交换.

经过每一轮比较, 最大的一个一定会跑到数组最后面, 就像气泡浮出水面的过程, 因此叫做冒泡排序.

思路简单, 代码好写, 时间复杂度O(n^2).

伪代码:

1
2
3
4
5
// 要排序的数组: data[n]
循环i从0到n-2:
    循环j从0到n-i-2:
        如果 data[j] > data[j+1]:
            交换data[j], data[j+1];

代码1:

1
2
3
4
5
6
7
8
9
10
int i,j,t;
for(i = 0; i < n-1; ++ i){
    for(j = 0; j < n-i-1; ++ j){
        if(data[j] > data[j+1]){
            t = data[j];
            data[j] = data[j+1];
            data[j+1] = t;
        }
    }
}

代码2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sorted = 0;
int t = 0;
while( !sorted ){ //当还没排序好
    sorted = 1; //先认为已经排序好
    for( int i = 1; i < n; ++ i ){
        if( data[i - 1] > data[i] ){
            t = data[i - 1];
            data[i - 1] = data[i];
            data[i] = t;
            sorted = false;// 还没排序完毕
        }
    }
    n--; // 最后一位已经排序好, 可以不用管它了
}

借助标志位sorted, 能使得程序在已经排序完毕之后提前退出.

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

代码的格式与变量的命名

(今天没题了)

正确的代码格式能够让你一眼就看清楚代码的架构, 同时, 当你拿着你的代码问别人的时候, 正确的代码格式会让别人更愿意回答你的问题, 别人也能更轻松找到你代码中的错误.

那么, 如何才是正确的代码格式呢?

大括号与缩进

大括号的风格有两种: 换行与不换行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 换行
for(...)
{
    blah;
    blah;
    if(foo)
    {
        blah;
    }
    else
    {
        blah;
    }
}
// 不换行
for(...){
    blah;
    blah;
    if(foo){
        blah;
    }else{
        blah;
    }
}

个人更习惯后者. 需要注意的就是 每遇到一个左大括号, 下一行一定要多缩进一格, 遇到一个右大括号, 下一行少缩进一格. 这样的结构能够让我们更清楚地看到多层if与for之间的层次结构关系.

在一般的IDE上, 选中多行代码按Tab键(Q左边的)即可给这几行代码的开头添加一个锁紧, 按shitf-Tab即可去掉一个缩进.

同时, 大部分IDE的默认设置均是使用空格缩进, 每次缩进4个空格. 在某些IDE上(比如DevCPP)默认设置是使用制表符缩进, 这种设置的代码在粘贴到别的地方的时候可能出现格式错位, 建议修改为空格缩进.

修改方式: Devcpp中依次打开工具(Tools)-编译器选项(Compiler Options), 把左下角的"标签"(tab)选项卡中的"使用tab字符"去掉, 将tab位置(Tab size)修改为4.

其他IDE的修改方式大同小异.

空格

在< > = != == ^ * + - &&等运算符的左右加上空格,如:

1
2
3
4
5
6
7
8
9
10
if(a < 1){
    ;
}
if(a != 1){
    ;
}
if(foo ^ bar){
    ;
}
foo = bar;

在每一个逗号的后面添加一个空格,如:

1
printf("%d%d%d%d", a, b, c, d);

在for循环中的分号后面加一个空格, 如:

1
2
3
for(int i = 1; i < 0; ++i){ // PS: 在某些环境下, for循环中使用++i比i++快一丢丢

}

在! &等一元运算符(只有一个参数的运算符)后不加空格,如:

1
2
3
4
scanf("%d%d%d", &a, &b, &c);
if(!a){
    ;
}

变量和函数的命名

有意义的变量名字能够让阅读你代码的人立刻理解变量的意义是什么, 方便代码交流.

变量命名并没有清晰的规范, 以下的都是作者的个人经验

循环变量命名: i j k

和总量大小有关的变量命名: m n

数组的命名: data[MAXN][MAXN] array[MAXN][MAXN]

标志的命名: flag
如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int isPrime(int n){
    int flag = 0;
    for(int i = 2; i * i <= n; ++ i){
        if(n % i == 0){
            flag = 1; // 表明找到因子
            break;
        }
    }
    if(flag){
        // 如果有因子
        return 0;
    }else{
        return 1;
    }
}

字符串命名: str1 str2

用英文单词命名: scores[MAXN] students[MAXN]

如果名字中要有多个英文单词, 有两种命名方式:

  1. 驼峰命名法(camel case) 第一个字母小写, 之后每个单词的首字母大写:
    thisIsAVeryLongVariableNameForSomeVeryStupidReason
  2. 蛇形命名法(snake case) 单词和单词之间用下滑线连接
    this_is_a_very_long_variable_name_for_some_very_stupid_reason

两种命名方式均被广泛使用, 根据个人习惯选择即可. 作者印象里c语言常用的是蛇形命名法, 但不确定

(不推荐, 但是比无意义命名好)汉语拼音命名: xueshengfenshu[MAXN]

函数命名:

英文单词命名, 尽量动词开头, 如:
is_prime get_numbers solve

算法名字命名, 如:
dfs dfs prim dijkstra

绝对不能用的命名: mian

0%