花生_TL007

这个屌丝很懒，什么也没留下！

热门标签

程序设计综合实践

作者：花生_TL007 | 2024-03-17 02:45:33

踩

程序设计综合实践

第一周

1. 买卖牛奶

早晨，去批发市场买牛奶。第i个牛奶卖主允许以所需价格购买任意数量的牛奶，每瓶牛奶的价格为si。（每个卖主的牛奶都一样）
傍晚，有m个出售牛奶的地方。第i个地方允许以bi的价格出售任意数量的牛奶。您所卖出的牛奶数量不能超过自己已有的牛奶数量。
现在是早晨，您拥有r元而没有牛奶。晚上之后您可以拥有最多多少钱？

输入格式:

输入共三行。
第一行包含三个整数n，m，r（1≤n≤30，1≤m≤30，1≤r≤1000），分别表示市场上牛奶卖主数目、出售牛奶的地方数以及您现在拥有的钱数；
第二行有n个整数s1，s2，…，sn（1≤si≤1000），si表示有机会以si的价格购买牛奶；
第三行有m个整数b1，b2，…，bm（1≤bi≤1000），bi表示有机会以bi的价格出售牛奶。

输出格式:

晚上之后，卖主最多可以拥有的钱数。

输入样例:

1 2 10
3
2 4

输出样例:

13

思路：

最小值买入，最大值卖出，简单的排序就能搞定。

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, m, r;
    int s[1001], b[1001];
    cin >> n >> m >> r;
    int i, j;
    for (i = 0; i < n; i++)
        cin >> s[i];
    for (i = 0; i < m; i++)
        cin >> b[i];
    int num, money = 0;
    sort(s, s + n);
    sort(b, b + m);
    num = r / s[0];
    money = r % s[0];
    money += b[m - 1] * num;
    if (money >= r)
        cout << money;
    else
        cout << r;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.航船

航船游戏中，风向每个单位时间会改变一次，每次航船可以选择顺风前行一个单位距离，也可以选择原地不动。游戏时长为 t，请你计算从起点出发，最终到达终点所需要的最少移动次数。如果游戏结束也到达不了终点，则输出-1。

输入格式:

第一行包括一个正整数 t（1<=t<=100000）。
第二行为起点坐标（x1 , y1）。
第三行为终点坐标（x2 , y2）。
接下来 t 行，每行输入一个单词，表示风向。

输出格式：

输出为一个整数，为到达终点所需移动的最少步数；如果无法到达，输出-1。

输入样例:

5
1 1
2 2
east
north
west
west
north

输出样例：

2

思路：

累加四个方向的步数，算出起点与终点之间横向与纵向的距离，判断此方向的步数是否大于距离。

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int t, x1, x2, y1, y2;
    int ans, step = 0;
    int e = 0, n = 0, w = 0, s = 0;
    int i;
    char a[10];
    cin>>t;
    cin>>x1>>y1;
    cin>>x2>>y2;
    ans=abs(x1-x2)+abs(y1-y2);
    for (i = 0; i < t; i++) {
        memset(a,'\0',sizeof(a));
        scanf("%s",a);
        if (a[0] == 'e')
            e++;
        if (a[0] == 'w')
            w++;
        if (a[0] == 'n')
            n++;
        if (a[0] == 's')
            s++;
    }
    if (x2-x1 >= 0 && e >= abs(x1-x2))
        step++;
    if (x2-x1 < 0 && w >= abs(x1-x2))
        step++;
    if (y2-y1 >= 0 && n >= abs(y1-y2))
        step++;
    if (y2-y1 < 0 && s >= abs(y1-y2))
        step++;
    if (step == 2)
        printf("%d",ans);
    else
        printf("-1");
    return 0;
}
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

3.多项式

相信大家都学过一元n次多项式的书写规则，现在给出多项式的系数，请让你帮忙写出这个多项式。

多项式中自变量为 x，从左到右按照次数递减顺序给出多项式。多项式中只包含系数不为 0 的项。保证n次项系数不为0。
如果多项式n次项系数为正，则多项式开头不出现“+”号。
如果 x 的指数大于 1，则接下来紧跟的指数部分的形式为“x^b”，其中 b 为 x 的指数；如果 x 的指数为1，则接下来紧跟的指数部分形式为“x”；如果 x 的指数为 0，则仅需输出系数即可。
多项式中，多项式的开头、结尾不含多余的空格。

输入格式:

输入共有两行。第一行 1 个整数n，表示一元多项式的次数（0<=n<=100）。第二行有 n+1 个整数，其中第 i 个整数表示第 n-i+1 次项的系数，每两个整数之间用空格隔开(-100<=系数<=100)。

输出格式:

输出共 1 行，按题目所述格式输出多项式。

输入样例1:

5
10 -1 1 -3 0 10

输出样例1:

10x⁵-x⁴+x³-3x²+10

输入样例2

3
-5 0 0 1

输出样例2:

5x³+1

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    int a[200];
    cin >> n;
    int i;
    for (i = 0; i <= n; i++) {
        cin >> a[i];
    }
    if (n < 2) {
        if (n == 1) {
            if (a[0] != 0) {
                if (a[0] != -1 && a[0] != 1)
                    cout << a[0] << "x";
                if (a[0] == 1)
                    cout << "x";
                if (a[0] == -1)
                    cout << "-x";
            }
            if (a[1] > 0)
                cout << "+" << a[1];
            if (a[1] < 0)
                cout << a[1];
        }
        if (n == 0) {
            cout << a[0];
        }
    }
    else {
        if (a[0] != 0) {
            if (a[0] != -1 && a[0] != 1)
                cout << a[0] << "x^" << n;
            if (a[0] == 1)
                cout << "x^" << n;
            if (a[0] == -1)
                cout << "-x^" << n;
        }
        for (i = 1; i < n - 1; i++) {
            if (a[i] > 0) {
                if (a[i] != 1)
                    cout << "+" << a[i] << "x^" << n - i;
                else
                    cout << "+" << "x^" << n - i;
            }
            if (a[i] < 0) {
                if (a[i] != -1)
                    cout << a[i] << "x^" << n - i;
                else
                    cout << "-" << "x^" << n - i;
            }
        }
        if (a[n - 1] > 0) {
            if (a[n - 1] != 1)
                cout << "+" << a[n - 1] << "x";
            else
                cout << "+x";
        }
        if (a[n - 1] < 0) {
            if (a[n - 1] != -1)
                cout << a[i] << "x";
            else
                cout << "-x";
        }
        if (a[n] > 0)
            cout << "+" << a[n];
        if (a[n] < 0)
            cout << a[n];
    }
    return 0;
}
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
66
67
68
69
70
71

4.兼容任务

设有n个任务，其中每个任务有一个起始时间si和一个结束时间ei，且si<ei，同一时间只能完成一个任务。如果选择了任务i ，则它在时间区间 [si ,ei) 内占用资源。若区间 [si ,ei) 与区间 [sj, ej)不相交，则称任务 i 与任务 j 是相容的。那么，对于给定的任务时间区间，能互相兼容的最大任务个数是多少呢？

输入格式:

第一行一个整数n （1<=n<=1000）；
接下来n行，每行两个整数si 和 ei。

输出格式:

互相兼容的最大任务个数。

输入样例:

4
1 3
4 6
2 5
1 7

输出样例:

2

思路：

结构体中存储开始与结束时间，按照结束时间排序，第一个即为任务1，接着循环找出开始时间在此之后的任务2，以此类推，累加任务数。

代码：

#include<bits/stdc++.h>
using namespace std;
struct work {
    int a;//开始时间
    int b;//结束时间
}f[2000];
bool cmp(work x, work y) {
    return x.b < y.b;
}
int main() {
    int n, sum = 1;
    int flag;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> f[i].a >> f[i].b;
    }
    sort(f, f + n, cmp);//按结束时间从小到大排序
    flag = f[0].b;
    for (int i = 1; i < n; i++) {
        if (f[i].a >= flag) {
            sum++;//任意一个任务开始时间大于结束时间 兼容任务数+1
            flag = f[i].b;//更新结束时间
        }
    }
    cout << sum;
    return 0;
}
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

5.致死一击

Kunkun最近热爱rpg闯关游戏，经常带着他的舍友打各种boss。但是随着舍友装备的逐渐升级，kunkun发现他给予boss最后一击的机会越来越少（给boss最后一击的玩家稀有装备爆率会大幅度提升）。所以kunkun联系到了一个神秘人，他可以利用时停来让boss躲过舍友的攻击，每次时停只能躲避一次攻击。假设kunkun和他的舍友都采取轮流攻击战术（kunkun率先攻击，kunkun的攻击力为a；舍友的攻击力为b，玩家每次都只进行一次攻击）去刷n个boss。如果最多只能使用k次时停，那么kunkun能造成致死伤害的boss最多有几个？

输入格式:

输入共两行。
第一行包括4个正整数 n，a，b，k (1≤n≤2*1e5, 1≤a,b,k≤1e9)，n表示boss的数量，a为kunkun的攻击力，b为kunkun舍友的攻击力，k为时停的最大次数。
第二行输入n个正整数h1,h2,…,hn (1≤hi≤1e9)，表示每个boss的血量。

输出格式:

输出一个整数，即kunkun造成致死伤害的boss的最大个数。

输入样例1:

6 2 3 3
7 10 50 12 1 8

输出样例1:

5

输入样例2

7 4 2 1
1 3 5 4 2 7 6

输出样例2

6

思路：

削减boss血线直到最后一次合击即可打死，判断此时血量需不需要时停。
若剩余血量恰好被攻击力a整除，则时停次数 = 剩余血量 / a - 1；
若不能整除，则时停次数 = 剩余血量 / a；
将时停次数从小到大排序，计算能杀死的boss数。

代码：

#include<bits/stdc++.h>
using namespace std;
int f[200000], g[200000];// f数组存boss剩余血量，g 数组存时所需停次数
int main() {
    int n, a, b, k, c;
    cin >> n >> a >> b >> k;
    for (int i = 0; i < n; i++)
        cin >> f[i];
    c = a + b;
    for (int i = 0; i < n; i++) {
        if (f[i] % c == 0)
            f[i] = c;
        else
            f[i] = f[i] % c;
    }//boss经受kunkun与其舍友联合攻击后剩余血量（恰好kunkun + 舍友一次攻击可以致死）
    for (int i = 0; i < n; i++) {
        if (f[i] <= a) {
            g[i] = 0;
        }//若剩余血量小于kunkun攻击力，则不用时停，直接致死
        else {
            if (f[i] % a == 0)
                g[i] = f[i] / a - 1;
            else
                g[i] = f[i] / a;
        }//否则算出所需时停数目
    }
    sort(g, g + n);//将时停数从小到大排序
    int ans = 0;
    for (int i = 0; i < n; i++) {
            k = k - g[i];
            ans++;
            if (k < 0) {
                ans--;
                break;
            }
    }//遍历计算答案
    cout << ans;
    return 0;
}
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

6.顺序的分数

输入一个自然数 n，对于一个最简分数 a/b（分子和分母互质的分数），满足 1≤b≤n，0≤a/b≤1，请找出所有满足条件的分数，并按分数值递增的顺序输出这些分数。

输入格式:

输入一个正整数 n（1≤n≤160)。

输出格式：

每个分数单独占一行，按照分数值递增的顺序排列。

输入样例:

5

输出样例：

0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

思路：

两重循环遍历分子与分母，同时除以最大公约数（若分子分母均为偶数则必不互质，减少循环次数），再按分数值从小到大排序输出即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, flag = -1;
struct fenshu {
    int x;//分子
    int y;//分母
    double z;//分数值
}a[1000001];
int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}//求最大公约数
int cmp(fenshu x,fenshu y){
    return x.z < y.z;
}
int main() {
    cin >> n;
    cout << "0/1" << endl;//输出最小
    if (n != 1) {
        for (int i = 1; i <= n; i++) {//遍历分子
            for (int j = i + 1; j <= n; j++) {//遍历分母
                if (i % 2 == 0 && j % 2 == 0)
                    continue;//偶数直接排除
                else {
                    int maxyue = gcd(i, j);
                    flag++;
                    a[flag].x = i / maxyue;
                    a[flag].y = j / maxyue;
                    a[flag].z = (i / maxyue * 1.0) / (j / maxyue * 1.0);
                }
            }
        }
        sort(a, a + flag, cmp);//按分数值从小到大排序
        for (int i = 0; i <= flag; i++) {
            if (a[i].z != a[i + 1].z) {
                cout << a[i].x << "/" << a[i].y << endl;
            }
        }
    }
    cout << "1/1";//输出最大
    return 0;
}
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

7.德州扑克

最近，阿夸迷于德州扑克。所以她找到了很多人和她一起玩。由于人数众多，阿夸必须更改游戏规则：
所有扑克牌均只看数字，不计花色。
每张卡的值为1、2、3、4、5、6、7、8、9、10、11、12、13 中的一种（对应A，2、3、4、5、6、7， 8、9、10，J，Q，K）
每位玩家从一副完整的扑克牌（没有大小王）中抽出五张扑克牌，可能出现的手牌的值从低到高排列如下：

高牌：不包含以下牌的牌。对于都是高牌的牌，按照五张牌的值的和进行从大到小排序。
对子：手中的5张牌中有2张相同值的牌。对于都拥有对子的牌，按构成该对子的牌的值进行从大到小地排序。如果这些都相同，则按手牌中余下3张牌的值的和进行从大到小排序。
两对：手中拥有两对不同的对子。对于都包含两对的手牌，按其最高对子的值进行从大到小排序。如果最高对子相同，则按另一个对子的值从大到小地进行排序。如果这些值相同，则按剩余牌的值从大到小地进行排序。
三条：手中拥有3张相同值的牌。对于都包含三条的手牌按构成三条的牌的值进行从大到小地排序。如果这些值相同，则按剩余牌的值从大到小地进行排序。
满堂红：手中拥有一个三条和一个对子。同理，先按三条大小排序，如果三条大小相同，则按对子大小进行排序。
四条：手中拥有4张相同值的牌。对于都包含四条的手牌按构成四条的牌的值进行从大到小地排序。如果这些值相同，则按剩余牌的值从大到小地进行排序。
顺子：手中拥有5张连续值的卡。对于都包含顺子的手牌按顺子最大的牌进行排序。
皇家同花顺：手中拥有10到A（10、J、Q、K、A）。是最大的手牌！
现在，阿夸已经知道了每个人的手牌，她想要知道所有人的排名列表。如果玩家的手牌大小相等，则按玩家名字的字典序输出。保证没有重复的名字。你能帮帮她吗？

输入格式：

第一行包含一个正整数 N (1<=N<=100000) ，表示玩家的人数。
接下来 N 行，每行包含两个字符串：m (1<=|m|<=10 ) ，表示玩家的名字；s (1<=|s|<=10)，表示玩家的手牌。

输出格式:

输出 N个玩家的排名列表。

输入样例：

3
Alice AAA109
Bob 678910
Boa 678910

输出样例:

Boa
Bob
Alice

思路;

设定七位数分值，设定每种牌型的底分，用函数解决每种牌型的判断，最后按分值输出即可。

代码：

#include<bits/stdc++.h>
using namespace std;
struct person {
	char name[20] = {'\0'};//名字
	char pai[20] = { '\0' };//手牌
	int num[15] = { -1,0,0,0,0,0,0,0,0,0,0,0,0,0,-1 };//每种牌的数目
	int len = 0;//手牌长度
	int score = 0;//等级分数
}a[100050];
int gaopai(person x) {
	int he = 0;
	for (int i = 1; i <= 13; i++) {
		he += i * x.num[i];//遍历手牌，算出所有手牌和；
	}
	x.score = he;
	if (x.score != 0)
		return x.score;
	else
		return 0;
}//高牌
int dui(person x) {
	int duishu = 0;
	int dd[2] = { 0,0 }, j = 0;//dd数组表示对子的牌值
	int he = 0;//剩余手牌之和
	for (int i = 1; i <= 13; i++) {
		if (x.num[i] == 2) {
			duishu++;
			dd[j] = i;
			j++;
		}//若某种牌数量为2，对数增加，记录牌值
	}
	if (duishu == 1) {
		for (int i = 1; i <= 13; i++) {
			if (i != dd[0])
				he += i * x.num[i];
		}
		x.score = 1000000 + dd[0] * 10000 + he *100;
	}//一对
	if (duishu == 2) {
		for (int i = 1; i <= 13; i++) {
			if (i != dd[0] && i != dd[1])
				he += i * x.num[i];
		}
		x.score = 2000000 + dd[1] * 10000 + dd[0] * 100 + he;
	}//两对
	if (x.score != 0)
		return x.score;
	else
		return 0;
}//对子（一对，两对）
int tiao(person x) {
	int tiaoshu = 0;
	int k = 0;//标记
	int nn = 0, mmm = 0;//nn记录对子的值，mmm记录条的值
	int he = 0;//记录剩余手牌和
	for (int i = 1; i <= 13; i++) {
		if (x.num[i] == 2) {
			k = 1;
			nn = i;
		}//若手牌中有对子，则记录对子的值
		if (x.num[i] >= 3) {
			tiaoshu = x.num[i];
			mmm = i;
		}//记录条数与条值
	}
	for (int i = 1; i <= 13; i++) {
		if (i != mmm) {
			he += i * x.num[i];
		}
	}//计算剩余手牌和
	if (tiaoshu == 3) {
		if (k == 1) {
			x.score = 4000000 + mmm * 10000 + nn * 100;
		}//若有对子，则为满堂红
		else {
			x.score = 3000000 + mmm * 10000 + he * 100;
		}//只有三条
	}//含三条的情况
	if (tiaoshu == 4) {
		x.score = 5000000 + mmm * 10000 + he * 100;
	}//四条
	if (tiaoshu == 5) {
		x.score = 5000000 + mmm * 10000 + mmm * 100;
	}//本题最后两个测试点含5张牌一样的情况
	if (x.score != 0)
		return x.score;
	else
		return 0;
}//条（三条 满堂红 四条）
int shun(person x) {
	for (int i = 1; i <= 9; i++) {
		if (x.num[i] == 1 && x.num[i + 1] == 1 && x.num[i + 2] == 1 && x.num[i + 3] == 1 && x.num[i + 4] == 1) {
			x.score = 6000000 + i * 10000;
		}
	}//暴力判断，起始手牌从1-9
	if (x.score != 0)
		return x.score;
	else
		return 0;
}//顺子
int huangjia(person x) {
	if (x.num[1] == 1 && x.num[10] == 1 && x.num[11] == 1 && x.num[12] == 1 && x.num[13] == 1)
		x.score = 7000000;//暴力判断10 J Q K A
	if (x.score != 0)
		return x.score;
	else
		return 0;
}//皇家同花顺
int cmp(person x,person y) {
	if (x.score == y.score)
		return strcmp(x.name, y.name) < 0;
	else
		return x.score > y.score;
}//sort的比较（先按分数值从大到小排列 在分数值相同情况下按字典序输出玩家名字）
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%s %s", a[i].name, a[i].pai);
		a[i].len = strlen(a[i].pai);
	}//输入手牌并计算手牌长度
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < a[i].len; j++) {
			if (a[i].len > 5) 
				a[i].num[10] = a[i].len - 5;//若手牌长度大于5，则说明含10
			if (a[i].pai[j] == 'A') 
				a[i].num[1]++;
			if (a[i].pai[j] == '2') 
				a[i].num[2]++;
			if (a[i].pai[j] == '3') 
				a[i].num[3]++;
			if (a[i].pai[j] == '4') 
				a[i].num[4]++;
			if (a[i].pai[j] == '5') 
				a[i].num[5]++;
			if (a[i].pai[j] == '6') 
				a[i].num[6]++;
			if (a[i].pai[j] == '7') 
				a[i].num[7]++;
			if (a[i].pai[j] == '8') 
				a[i].num[8]++;
			if (a[i].pai[j] == '9') 
				a[i].num[9]++;
			if (a[i].pai[j] == 'J') 
				a[i].num[11]++;
			if (a[i].pai[j] == 'Q') 
				a[i].num[12]++;
			if (a[i].pai[j] == 'K') 
				a[i].num[13]++;
		}//记录手牌中每种牌的张数
		int ss[5];//用于判断牌型并记录分值
		ss[0] = gaopai(a[i]);
		ss[1] = dui(a[i]);
		ss[2] = tiao(a[i]);
		ss[3] = shun(a[i]);
		ss[4] = huangjia(a[i]);
		sort(ss, ss + 5);//原始sort函数，将数组中数据按非降序排列
		a[i].score = ss[4];
	}//计算分值
	sort(a, a + n, cmp);//按自定义排序排列分数
	for (int i = 0; i < n; i++) {
		if (i != n - 1)
			printf("%s\n", a[i].name);
		else
			printf("%s", a[i].name);
	}//输出结果
	return 0;
}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

第二周

1.正确答案

二维平面上，对于坐标分别为（x1 , y1）和（x2 , y2）的两点 p、q，它们之间的曼哈顿距离为 | x1 - x2 | + | y1 - y2 |。给出 n 个点，猫日的作业是计算出这 n 个点中每两点之间的曼哈顿距离。但是，猫日只会计算点和点之间的直线距离。如果猫日每答对一题可以获得一块小鱼干，那么它最后能蒙对多少题？拿到多少小鱼干呢？

输入格式:

第一行包括一个正整数 n（1<=n<=50000）。
接下来有 n 行，每行两个正整数 xi 和 yi表示二维平面上点的坐标。

输出格式:

输出一个整数，为猫日蒙对的题数。数据保证答案在 int 范围内。

输入样例:

3
1 1
7 5
1 5

输出样例:

2

思路：

遍历任意两个点，若这两个点的x相同或者y相同则这两点曼哈顿距离等于直线距离。

代码：

#include<bits/stdc++.h>
using namespace std;
struct dian {
    int x;
    int y;
}a[50050];
int main() {
    int n;
    cin >> n;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y;
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i].x == a[j].x || a[i].y == a[j].y) {
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.日期差值

现在有两个不同的日期，你能告诉我它们之间差几天吗？

输入格式:

有多行数据，每行数据包含6个数字，中间用空格分隔，每3个数字代表一个日期。

输出格式:

对应于输入数据，输出数据有相同的行数，每行表示对应的两个日期相差的天数。

输入样例:

1934 2 4 2047 11 30
2192 10 3 1921 5 8

输出样例:

-41572
99130

代码：

#include<stdio.h>
int main()
{
	int run(int y1);
	int month(int y1, int m1, int d1);
	int y1, y2, m1, m2, d1, d2;
	while (scanf("%d %d %d %d %d %d", &y1, &m1, &d1, &y2, &m2, &d2) != EOF)
	{
		if (y1 == y2)
		{
			printf("%d\n", month(y1, m1, d1) - month(y2, m2, d2));
		}
		if (y1 < y2)
		{
			long long int days = 0;
			if (run(y1))
				days -= (long long int)366 - month(y1, m1, d1);
			else
				days -= (long long int)365 - month(y1, m1, d1);
			for (y1++; y1 != y2; y1++)
			{
				if (run(y1))
					days -= 366;
				else
					days -= 365;
			}
			days -= month(y2, m2, d2);
			printf("%lld\n", days);
		}
		if (y1 > y2)
		{
			long long int days = 0;
			if (run(y2))
				days += (long long int)366 - month(y2, m2, d2);
			else
				days += (long long int)365 - month(y2, m2, d2);
			for (y2++; y1 != y2; y2++)
			{
				if (run(y2))
					days += 366;
				else
					days += 365;
			}
			days += month(y1, m1, d1);
			printf("%lld\n", days);
		}
	}
	return 0;
}
int month(int y1, int m1, int d1)
{
	int a = 0;
	int run(int y1);
	if (run(y1))
	{
		switch (m1)
		{
		case 1:break;
		case 2:a += 31; break;
		case 3:a += 31 + 29; break;
		case 4:a += 31 + 29 + 31; break;
		case 5:a += 31 + 29 + 31 + 30; break;
		case 6:a += 31 + 29 + 31 + 30 + 31; break;
		case 7:a += 31 + 29 + 31 + 30 + 31 + 30; break;
		case 8:a += 31 + 29 + 31 + 30 + 31 + 30 + 31; break;
		case 9:a += 31 + 29 + 31 + 30 + 31 + 30 + 31 + 31; break;
		case 10:a += 31 + 29 + 31 + 30 + 31 + 30 + 31 + 31 + 30; break;
		case 11:a += 31 + 29 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31; break;
		case 12:a += 31 + 29 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + 30; break;
		}
		a += d1;
	}
	else
	{
		switch (m1)
		{
		case 1:break;
		case 2:a += 31; break;
		case 3:a += 31 + 28; break;
		case 4:a += 31 + 28 + 31; break;
		case 5:a += 31 + 28 + 31 + 30; break;
		case 6:a += 31 + 28 + 31 + 30 + 31; break;
		case 7:a += 31 + 28 + 31 + 30 + 31 + 30; break;
		case 8:a += 31 + 28 + 31 + 30 + 31 + 30 + 31; break;
		case 9:a += 31 + 28 + 31 + 30 + 31 + 30 + 31 + 31; break;
		case 10:a += 31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30; break;
		case 11:a += 31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31; break;
		case 12:a += 31 + 28 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + 30; break;
		}
		a += d1;
	}
	return a;
}
int run(int y1)
{
	return (y1 % 4 == 0 && y1 % 100 != 0) || (y1 % 100 == 0 && y1 % 400 == 0);
}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

3.最少分成几组

给定一个包含n个数的数列，由a1,a2,…,an组成，现在将这n个数分成若干组，使得每组中任意两个数|ai-aj|>1，（i!=j）。这个数列中的n个数最少可以分成几组呢？

输入格式:

第一行包含一个整数n（1≤n≤1000）。第二行包含n个整数a1，a2，…，an（1≤ai≤10000，所有ai互不相同）。

输出格式:

输出仅一个整数，表示数列中n个数最少可以分成的组数。

输入样例:

2
1 2

输出样例:

2

思路：

数组排序，计算相邻两数之差，若含差大于1的两个数，则分为两组，否则分为1组。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    int flag=0;
    int a[1010];
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    sort(a,a+n);
    for(int i=1;i<n;i++){
        if(a[i]-a[i-1]==1)
            flag=1;
    }
    if(flag)
    cout<<2;
    else
    cout<<1;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.美丽数列

小明是个普通的计算机本科生，很喜欢研究数组相关的问题。在他的认知里，美丽的数组是这样的，对于一个长度为n的数组a，存在一个下标i（1<=i<=n)使得1_{i之间的数是严格递增的，i+1}n之间的数是严格递减的。现在这个数组a里的元素是随机给定的（这个数组可能是不美丽的），对于数组a内的任意一个元素ai我们可以进行若干次ai=ai-1(ai>0)的操作，问能否通过若干次操作使得这个数组变得美丽。

输入格式:

第一行输入数组长度n (1≤n≤3*1e5)，第二行输入n个整数a1,…,an (0≤ai≤1e9)。

输出格式:

输出“Yes”表示这个数组可以变美丽，输出“No”表示不可以。

输入样例:

3
1 0 1

输出样例:

No

思路：

遍历数组，若a[i]>=i，则a[i]=i,以此构造递增数列；
若a[i]<i，则此时a[i]为递减数列的起始，之后的a[i]=a[i-1]-1,若某个a[i]<0,则不能构成美丽数列,反之若能遍历完数组，则可以构成美丽数列。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[300050];
int main()
{
	int n;
	cin>>n;
	for (int i=0;i<n;i++){
	    cin>>a[i];
	}
	int i=0;
	for (i=0;i<n;i++){
		if (a[i]>i)
		    a[i]=i;
		if (a[i]<i)
		    break;
	}
	for (i=i+1;i<n;i++){
		if (a[i-1]<a[i])
		    a[i]=a[i-1]-1;
		if (a[i]<0){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	return 0;
 }
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

5.最长公共子串

给定两个字符串a、b，现有k次机会对字符串中的字符进行修改，使修改后两个字符串的最长公共子串最长。每一次修改，可以选择a、b字符串中某一个串的任意位置修改成任意字符。

输入格式:

第一行包括一个正整数 k。
第二行和第三行分别输入字符串a、b。（每个串的长度不超过500）

输出格式:

输出为一个整数，表示修改后的两个串的最长公共子串长度。

输入样例:

5
aaaaa
bbbbb

输出样例:

思路：

遍历数据，直到有k个不一样的字符时，结束，比较长度，存储最长的一条。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    string a,b;
    int k;
    cin>>k;
    getchar();
    getline(cin,a);
    getline(cin,b);
    int l1=a.length();
    int l2=b.length();
    int ans=-1;
    for(int i=0;i<l1;i++){
        for(int j=0;j<l2;j++){
            int step=0,cuo=k;
            for(int m=i,n=j;m<l1&&n<l2;m++,n++){
                if(a[m]==b[n]){
                    step++;
                }
                if(a[m]!=b[n]){
                    if(cuo>0){
                        step++;
                        cuo--;
                    }
                    else
                        break;
                }
            }
            ans=max(ans,step);
        }
    }
    printf("%d",ans);
    return 0;
}
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

6.旋转骰子

玛莎有n个骰子，每个骰子的6个面上都恰好有一个0到9之间的数字。
现在玛莎将利用这n个筛子来制作新数字。她把n个骰子摆成一排，然后从左到右查看骰子的上表面并读取，即可得到一个新数字。随后她不断的旋转每个骰子的面就可以得到不同的新数字。旋转骰子需要满足以下规则： 1、制作的数字不能包含前导零； 2、制作新数字时不需要使用所有的骰子； 3、使用骰子旋转，无法将数字9转换为数字6，反之亦然。
给定n个骰子，玛莎可以用它们构成从1到x的所有整数。玛莎想知道，对于给定的n个骰子，这个x的最大取值是多少呢？

输入格式:

第一行仅一个整数n，表示骰子的数量（1≤n≤3）。
接下来n行，每行包含6个整数a[i][j]（0≤a[i][j]≤9），表示第i个骰子的第j个面上的数字。

输出格式:

输出一个整数，即最大数x，玛莎可以使用她的骰子构成数字从1到x。如果无法构成1，则输出0。

输入样例:

3
0 1 3 5 6 8
1 2 4 5 7 8
2 3 4 6 7 9

输出样例:

思路：

首先，骰子一共最多只有18个数字，最大只能达到98；所以只要从1开始遍历到98即可；
判断1-9时：双重循环遍历所有骰子的所有面，查找数字。
判断10-98时：双重循环遍历所有骰子，查找十位数字，存在时，再双重循环遍历剩余骰子所有面，查找个位数字。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[3][6];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 6; j++) {
            cin >> a[i][j];
        }
    }
    int i, x, y, z, w;
    for (i = 1; i <= 99; i++) {
        int flag = 0;
        if (i < 10) {
            for (x = 0; x < n; x++) {
                for (y = 0; y < 6; y++) {
                    if (a[x][y] == i) {
                        flag = 1;
                    }
                }
            }
        }
        else {
            int aa = i / 10;
            int bb = i % 10;
            for (x = 0; x < n; x++) {
                for (y = 0; y < 6; y++) {
                    if (a[x][y] == aa) {
                        for (z = 0; z < n; z++) {
                            if (z != x) {
                                for (w = 0; w < 6; w++) {
                                    if (a[z][w] == bb) {
                                        flag = 1;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        if (flag == 0) {
            cout << i - 1;
            return 0;
        }
    }
}
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

7.均等笔

n个人围成一圈，每人有ai支笔。每人可以向左右相邻的人传递笔，每人每次传递一支笔消耗的能量为1。求使所有人获得均等数量的笔的最小能量。

输入格式:

第一行一个整数n ，表示人的个数（30%的数据，n<=1000；100%的数据，n<=1e6）。
接下来n行，每行一个整数 ai。

输出格式:

输出一个整数，表示使所有人获得均等笔的最小能量。（答案保证可以用64位有符号整数存储）

输入样例:

4
1
2
5
4

输出样例:

4

思路：

首先，计算平均值，用ave表示。

假设标号为i的小朋友开始有Ai颗糖果，Xi表示第i个小朋友给了第i-1个小朋友Xi颗糖果，如果Xi<0，说明第i-1个小朋友给了第i个小朋友Xi颗糖果，X1表示第一个小朋友给第n个小朋友的糖果数量。所以最后的答案就是ans=|X1| + |X2| + |X3| + ……+ |Xn|。对于第一个小朋友，他给了第n个小朋友X1颗糖果，还剩A1-X1颗糖果；但因为第2个小朋友给了他X2颗糖果，所以最后还剩A1-X1+X2颗糖果。根据题意，最后的糖果数量等于ave，即得到了一个方程：A1-X1+X2=ave。

同理，对于第2个小朋友，有A2-X2+X3=ave。最终，我们可以得到n个方程，一共有n个变量，但是因为从前n-1个方程可以推导出最后一个方程，所以实际上只有n-1个方程是有用的。

尽管无法直接解出答案，但可以用X1表示出其他的Xi，那么本题就变成了单变量的极值问题。

对于第1个小朋友，A1-X1+X2=ave >>> X2=ave-A1+X1 = X1-C1(假设C1=A1-ave，下面类似）

对于第2个小朋友，A2-X2+X3=ave >>> X3=ave-A2+X2=2ave-A1-A2+X1=X1-C2

对于第3个小朋友，A3-X3+X4=ave >>> X4=ave-A3+X3=3ave-A1-A2-A3+X1=X1-C3

对于第n个小朋友，An-Xn+X1=ave。
我们希望Xi的绝对值之和尽量小，即|X1| + |X1-C1| + |X1-C2| + ……+ |X1-Cn-1|要尽量小。注意到|X1-Ci|的几何意义是数轴上的点X1到Ci的距离，所以问题变成了：给定数轴上的n个点，找出一个到他们的距离之和尽量小的点，而这个点就是这些数中的中位数。

来源：洛谷P2512

代码：

#include <bits/stdc++.h>  
using namespace std; 
long long a[1000010],b[1000010]; 
int main() { 
    long long n,sum=0,avg=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    avg=sum/n;
    b[0]=a[0]-avg;
    for(int i=1;i<n;i++)
        b[i]=b[i-1]+a[i]-avg;
    sort(b,b+n);
    long long min=0;    
    for(int i=0;i<n;i++)
        min+=abs(b[n/2]-b[i]);
    cout<<min;
    return 0;
}  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

第三周

1.郭老师的冰糖葫芦

郭老师有草莓和山楂两种水果共计n个，她打算用这些水果做一串冰糖葫芦。她会把这串冰糖葫芦的水果组成用字符串的形式告诉你，其中’B’表示草莓，’W’表示山楂，例如：BBW，表示这串冰糖葫芦的水果按照顺序是草莓、草莓、山楂。郭老师想知道这串冰糖葫芦上的草莓串有几串，按照从左到右的顺序，这些草莓串的长度分别是多少？例如，冰糖葫芦WBBBBWWBWBBBW中共有3个草莓串它们的长度分别是4、1、3。

输入格式:

第一行包含一个整数为n (1 ≤ n ≤ 100)，表示郭老师拥有的水果总数。第二行为一串只包含字符’B’和’W’的字符串，即糖葫芦的水果组成。

输出格式:

第一行输出一个整数，表示糖葫芦中包含的草莓串个数。第二行有多个整数，分别表示糖葫芦中按从左到右顺序各个草莓串中草莓的个数。

输入样例:

13
WBBBBWWBWBBBW

输出样例:

3
4 1 3

代码：

#include<iostream>
using namespace std;
int main() {
	char a[150]={"\0"};
	int n;
	int len[150]={0};
	cin >> n;
	scanf("%s", a);
	int sum = 0;
	int k = 0, j, i;
	for (i = 0; i < n;i++) {
		if (a[i] == 'B') {
			len[k] = 1;
			sum++;
			for (j = i + 1; j < n&&a[j]!='W'; j++) {
				if (a[j] == 'B') 
					len[k]++;
			}
			i = j;
			k++;
		}
	}
	cout << sum << endl;
	for (int i = 0; i < k; i++) {
			cout << len[i] << " ";
		
	}
	return 0;
}
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

2.下次一定

你是一个bilibili的六级号，由于经常一键三连，所以一个硬币都没有，现在你做了个梦，在梦中你制定了一个投币规则：一个用户共有s个币，他每次选择x个硬币投出去（1<=x<=s），并且会得到x/10（向下取整）的找零。用户一直重复这个过程，最终把所有的硬币全都投完。按照这个规则，用户可以达到的最大投币数是多少呢？
举个例子，如果你有19个币，一开始，你投了10个币，得到1一个币的找零，然后你又投了10个币，得到1个币的找零，最后你把这1个币也投出去。这样你就可以达到最大投币数21。

输入格式:

第一行包含一个整数t（1<=t<=10^4），表示有t个用户。
接下来的t行，每行一个整数，表示某个用户的硬币数s（1<=s<=10^9）。

输出格式:

输出t行，每行一个整数，表示对应用户最多能投出的硬币数。

输入样例:

6
1
10
19
9876
12345
1000000000

输出样例:

1
11
21
10973
13716
1111111111

思路：

由题意可知，整10的硬币数投入，收益最大。

代码：

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

3.不诚实的卖家

伊戈尔发现有一家商店正在打折，所以决定在这家商店购买n件商品。商店的打折活动会持续一周，打折期间每件商品的价格是ai，等打折活动结束后，商品的价格变为bi。但是并非所有卖家都诚实，因此打折期间某些商品的价格可能会比折扣活动结束后的价格更贵。
伊戈尔决定现在至少购买k件商品，剩下的商品等活动结束后再购买。你的任务是帮伊戈尔计算一下用于购买n件商品的最低费用。

输入格式:

第一行包含两个正整数n和k（1≤n≤2e5，0≤k≤n），分别表示伊戈尔要购买的商品数量和他现在只少要买的商品数。
第二行包含n个整数 a1，a2，…，an（1≤ai≤1e4），分别表示折扣期间各个商品的价格。
第三行包含n个整数 b1，b2，…，bn（1≤bi≤1e4），分别表示折扣结束后商品的价格。

输出格式:

伊戈尔购买n件商品所需的最低金额。

输入样例:

3 1
1 3 5
6 4 2

输出样例:

6

思路:

建立结构体(分别为折扣价,原价,差价),遍历所有商品;
若折扣价低于原价直接买入,必买商品数-1,差价与原价置为0;
若折扣价高于原价,则计算差价;
将所有商品的非0差价按从小到大排序,差价为0的后置;
若此时必买商品数为0,则将剩下的原价商品买入;
若不为0,则按排序后的商品买入折扣价商品,并将原价置为0,直到必买商品数为0时;此时再将所有原价商品买入。

代码：

#include<bits/stdc++.h>
using namespace std;
struct goods{
	int a;//折扣价
	int b;//原价
	int c;//差价
}f[10000];
int cmp(goods x, goods y){
    if(x.c!=0&&y.c!=0)
        return x.c<y.c;
    else
        return x.c>y.c;
}//非0的差价按从小到大排序
int main(){
	int n, k;
    int sum=0;
	cin>>n>>k;
	for (int i = 0; i < n; i++){
		cin>>f[i].a;
    }
	for (int i = 0; i < n; i++){
		cin>>f[i].b;
	}
	for (int i = 0; i < n; i++){
		if (f[i].a <= f[i].b){
            sum += f[i].a;
            f[i].c = 0;
            f[i].b = 0;
            k--;
        }
		else
			f[i].c = f[i].a - f[i].b;
	}
    sort(f,f+n,cmp);
    if(k<=0){
        for(int i=0;i<n;i++){
            sum+=f[i].b;
        }
        cout<<sum<<endl;
        return 0;
    }
    else{
        for(int i=0;i<n&&k>0;i++,k--){
            sum+=f[i].a;
            f[i].b=0;
        }
        for(int i=0;i<n;i++){
            sum+=f[i].b;
        }
        cout<<sum<<endl;
        return 0;
    }
}
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

4.回文数

对于一个自然数n，若将n的各位数字反向排列所得的数n1与n相等，则称n为回文数，例如2332。
若给定一个N( 2<=N<=16)进制数M（M的长度在一百位以内），如果M不是回文数，可以对其进行N进制加法，最终得到回文数。
例如对于十进制数79 STEP1 : 79 + 97 = 176 STEP2 : 176 + 671 = 847 STEP3 : 847 + 748 = 1595 STEP4 : 1595 +5951 = 7546 STEP5 : 7546 + 6457 = 14003 STEP6 : 14003 + 30041 = 44044
那么对于给定的N进制数M，请判断其能否在30步以内（包括30步）得到回文数。

输入格式:

第一行包括一个正整数 N（2<=N<=16）。
第二行包括一个正整数M（一百位以内）。

输出格式:

如果可以在n步内得到回文数，输出“STEP=n”，否则输出“NO”。

输入样例1:

10
79

输出样例1:

STEP=6

输入样例2:

8
665556

输出样例2:

NO

思路:

题目难点在于n进制加法如何表示，按题目意思，将数组正序与逆序的各位上数字相加即可得到结果，按照竖式计算的步骤进行，注意10进制以上的数字需要特别表示。用一个函数判断此时数据是否是回文数。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, len=0, step=0, a[10000];
string x;
int judge(int len){
	for (int i = 0; i <= len / 2; i++)
		if (a[i] != a[len - i - 1])
			return 0;
	return 1;
}//判断回文数

int fun(int len){
	int c[10000] = { 0 }, k = 0;
	for (int i = 0; i < len; i++) {
		c[i] = a[i] + a[len - i - 1] + c[i];//正序逆序各位数字相加
		c[i + 1] += c[i] / n; //进位
		c[i] %= n;
	}
	if (c[len] != 0)
		len++;//更新数组长度
	for (int i = len - 1; i >= 0; i--)
	{
		a[k++] = c[i];//逆序更新数字
	}
	return len;
}
int main(){
	cin >> n;
	cin >> x;
	len = x.length();
	for (int i = 0; i < len; i++){
		if (x[i] < 'A')  
			a[i] = x[i] - '0';
		else
			a[i] = x[i] - 'A' + 10;
	}
    if(judge(len)){
        cout<<"STEP=0"<<endl;
        return 0;
    }
	while (step <= 30){
		step++;
		len = fun(len);
		if (judge(len)) {
			cout << "STEP=" << step << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
	return 0;
}
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

5.数楼梯

楼梯有N阶，上楼可以一步上一阶，也可以一步上两阶。那么走到第N阶楼梯共有多少种不同的走法呢？

输入格式:

一个正整数 N（1<=N<=5000），表示楼梯阶数。

输出格式:

输出一个数，表示走到第N阶楼梯有多少种走法。
注意，数据范围很大，即使是64位也可能不够存。

输入样例1:

4

输出样例1:

5

输入样例2:

400

输出样例2:

284812298108489611757988937681460995615380088782304890986477195645969271404032323901

思路：

二维数组f[x][i],储存每一级阶梯f[x]走法的种类数；
其f[x]满足f[1]=1，f[2]=2，f[x]=f[x-1]+f[x-2]的递推公式；
所以可将问题转化为高进度加法。

代码：

#include<bits/stdc++.h>
#define MAXN 5050
using namespace std;
int len = 1;
int f[MAXN][MAXN];
void fun(int x) {
	for (int i = 0; i < len; i++) {
		f[x][i] = f[x - 1][i] + f[x - 2][i];
	}
	for (int i = 0; i < len; i++) {
		if (f[x][i] > 9) {
			f[x][i + 1] += f[x][i] / 10;
			f[x][i] = f[x][i] % 10;
		}
		if (f[x][len] != 0)
			len++;
	}
}
int main() {
	int n;
	cin >> n;
	f[1][0] = 1;
	f[2][0] = 2;
	for (int i = 3; i <= n; i++) {
		fun(i);
	}
	for (int i = len-1; i >= 0; i--) {
		cout << f[n][i];
	}
}
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

6.A-B

已知两个数A和B，求A-B的运算结果。

输入格式:

输入包括两个正整数A和B 。（0<A，B≤1e10086）

输出格式:

输出A-B的运算结果。

输入样例1:

3
2

输出样例1:

1

输入样例2:

11102356985410
2356985410235698

输出样例2:

-2345883053250288

思路：

高精度减法，模拟竖式运算。

代码：

#include<bits/stdc++.h>
#define MAXN 1000086 
using namespace std;
string a, b;
int na[MAXN], nb[MAXN], ans[MAXN]; 
int main() {
    int flag = 0;
    cin >> a >> b;
    if((a < b && a.size() == b.size()) || a.size() < b.size()){
        swap(a, b);
        flag = 1;
    }
    for(int i = a.size(); i > 0; i --)
        na[i] = a[a.size() - i] - '0';
    for(int i = b.size(); i > 0; i --)
        nb[i] = b[b.size() - i] - '0';
    int maxl = max(a.size(), b.size());
    for(int i = 1; i <= maxl; i ++){
        if(na[i] < nb[i]){
            na[i + 1] --;
            na[i] += 10;
        }
        ans[i] = na[i] - nb[i];
    }
    while(ans[maxl] == 0)
        maxl --;
    if(flag == 1)
        cout << "-";
    for(int i = maxl; i > 0; i --)
        cout << ans[i];
    if(maxl < 1)
        cout << "0";
    return 0;
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

7.高精度除法

给两个正整数 a,b，求 a/b的整数部分。

输入格式:

输入共两行，每行一个正整数，分别表示 a和b。 50%数据，a,b均小于1e18， 50%数据，a,b均小于1e500。

输出格式:

输出一个整数，表示a/b的整数部分。

##输入样例1:

3
2

输出样例1:

1

输入样例

24781236498237462378425347823652387423654238752372365327862
8934457724628746

输出样例2:

2773669903874014740488146558678531750078864

思路：

高精度除法，用减法代替除法运算。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000], b[1000], c[1000];//a存被除数与余数;b存除数;c存整除结果
string aa, bb;

int compare(int a[], int b[]) {
	if (a[0] > b[0])
		return 1;
	if (a[0] < b[0])
		return -1;
	if (a[0] == b[0]) {
		for (int i = a[0]; i > 0; i--) {
			if (a[i] > b[i])
				return 1;
			if (a[i] < b[i])
				return -1;
		}
		return 0;
	}
}//a<b为-1,a>b为1,a=b为0

void move(int b[], int tmp[], int w) {
	for (int i = 1; i <= b[0]; i++) {
		tmp[w + i - 1] = b[i];
	}
	tmp[0] = b[0] + w - 1;
}//将除数b右移，存于tmp中；

void jian(int a[], int tmp[]) {
	int pd, i;
	pd = compare(a, tmp);
	if (pd == 0) {
		a[0] = 0;
	}
	if (pd == 1) {
		for (i = 1; i <= a[0]; i++) {
			if (a[i] < tmp[i]) {
				a[i + 1]--;
				a[i] += 10;
				a[i] -= tmp[i];
			}
			else {
				a[i] -= tmp[i];
			}
		}
		while ((a[a[0]] == 0) && a[0] > 0)
			a[0]--;
	}
}

void chufa(int a[], int b[], int c[]) {
	int i;
	int tmp[1000];//存除数与被除数对齐的结果
	c[0] = a[0] - b[0] + 1;//c[0]存整除结果的长度
	for (i = c[0]; i > 0; i--) {
		memset(tmp, 0, sizeof(tmp));
		move(b, tmp, i);
		while (compare(a, tmp) >= 0) {
			c[i]++;
			jian(a, tmp);
		}
	}
	while ((c[c[0]] == 0) && c[0] > 0)
		c[0]--;
}

int main(){
	int pd;
	cin >> aa;
	a[0] = aa.length();//a[0]存数组长度
	for (int i = 01; i <= a[0]; i++) {
		a[i] = aa[a[0] - i] - '0';
	}
	cin >> bb;
	b[0] = bb.length();//b[0]存数组长度
	for (int i = 1; i <= b[0]; i++) {
		b[i] = bb[b[0] - i] - '0';
	}
	//输入
	pd = compare(a, b);
	if (pd == -1) {
		cout << 0 << endl;
	}
	if (pd == 0) {
		cout << 1 << endl;
	}
	if (pd == 1) {
		chufa(a, b, c);
		for (int i = c[0]; i > 0; i--) {
			cout << c[i];
		}
	}
	return 0;
}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

第四周

1.两个整数的除数

给你一个混排的数列，其中包含x的所有除数（包括1和x）和y的所有除数（包括1和y）。如果d同时是x和y的除数，则列表中d将会出现两次。

例如，x = 4，y = 6，则给定列表可以是列表[1,2,4,1,2,3,6]的任何排列。一些可能的列表是：[1,1,2,4,6,3,2]，[4,6,1,1,2,3,2]或[1,6,3,2,4,1,2]。

现在给定一个数列，它是某两个正整数x和y的所有除数列表。请你帮忙找出这两个正整数x和y。

输入格式:

第一行包含一个整数n（2≤n≤128），表示数列包含的数的个数。

第二行包含n个整数d1，d2，…，dn（1≤di≤10^4），其中di是x的除数或y的除数。如果一个数字同时是x和y的除数，则数组中有两个该数字。

输入保证答案存在。

输出格式:

输出仅一行，包含两个正整数x和y （x>=y），以空格分隔。

输入样例:

10
10 2 8 1 2 4 1 20 4 5

输出样例:

20 8

思路：

记录x,y所有除数的值，统计每个值出现的次数，把所有除数按从小到大排列，则最大的数即为x；再遍历数组，把是x除数且出现次数不为0的值置为0，且将出现次数置为0；保证将x除数消去的同时，只将x,y的公约数消去一个，再次排序，此时最大值即为y。

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	int a[200], b[10050] = { 0 };
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		b[a[i]]++;
	}
	sort(a, a + n);
	int x, y;
	x = a[n - 1];
	for (int i = 0; i < n; i++) {
		if (a[i] != 0 && x % a[i] == 0) {
			if (b[a[i]] != 0) {
				b[a[i]] = 0;
				a[i] = 0;
			}
		}
	}
	sort(a, a + n);
	y = a[n - 1];
	cout << x << " " << y;
	return 0;
}
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

2.出色的物理引擎

卡罗拉最近沉迷于ark游戏，游戏中的地图上有n个浮空的石头围成了一圈，在优秀的物理引擎支持下，这些石头会自动落下。她发现石头落下的顺序是有规律的。一共有n个石头，从第一块石头开始数，数到第m个石头，那块就是第一个落下的石头；之后从第一个落下的石头后一个重新从1开始数，同样数到第m个石头，那个就是第二个落下的石头；以此类推。为了方便，对这些石头从1开始编号。卡罗拉现在想知道最后落下的是那一块石头？

输入格式:

输入包含两个整数n和m (1<=m,n<=1000)。

输出格式:

输出一个整数，代表最后落下的石头的编号。

输入样例:

10 3

输出样例:

4

思路：

约瑟夫环问题，用链表将所有数据连接成环。

代码:

#include<bits/stdc++.h>
using namespace std;
struct person {
    person* former;
    int num;
    person* latter;
}a[1050];
void out(person* now) {
    now->former->latter = now->latter;
    now->latter->former = now->former;
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        a[i].num = i;
        if (i != n && i != 1) {
            a[i].latter = &a[i + 1];
            a[i].former = &a[i - 1];
        }
    }
    a[n].former = &a[n - 1];
    a[n].latter = &a[1];
    a[1].former = &a[n];
    a[1].latter = &a[2];
    //初始化链表
    person* now = &a[1];
    int k = 1;
    int nownumber = 1;
    while (n) {
        if (nownumber == m) {
            if (n == 1)
                cout << now->num << endl;
            k++;
            out(now);
            nownumber = 1;
            n--;
            now = now->latter;
        }
        else {
            nownumber++;
            now = now->latter;
        }
    }
    return 0;
}
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

3.开机方案

h学长有个机器用来完成任务。现在有n个任务，第i个任务（1<= i <= n)在ti时刻开始，并在ti + 1时刻结束。同一时刻不会有多个任务。 h学长可以在任何时刻开启机器，不过每一次开启机器都会消耗1点能量。h学长只有k点能量可以用于开启机器。但是机器开着的时候需要消耗燃料，显然让机器一直开着并不一定是最好的选择。现在h学长想利用自己具备的k点能量，有效的控制机器的开启，使得机器完成n个任务消耗的燃料尽可能的少。那么对应给出的n个任务以及h学长拥有的能量数，你能帮帮他吗？提示：消耗的燃料要尽可能的少，即机器工作的时间尽可能的短。

输入格式:

第一行包括两个整数 n和k（1<= n <= 1e5, 1<= k <=n），表示有 n个任务和h学长拥有k点能量。

接下来 n行，每行一个整数ti（1<= ti <=1e9），表示第 i 个任务在ti 时刻开始，并在ti + 1时刻结束。

输出格式:

输出一行包含一个整数，表示机器工作的最少时间。

输入样例1:

3 2
1
3
6

输出样例1:

4

样例1说明：
h学长有2点能量，可以用于两次机器的开启。 h学长会在时刻1 即第一个任务开始时开启机器，并在第二个任务结束时关闭机器； h学长会在时刻6 即第三个任务开始时开启机器，并在第三个任务结束时关闭机器。机器总工作时间为（4-1）+（7-6）=4 。

输入样例2:

10 5
1
2
5
6
8
11
13
15
16
20

输出样例2:

12

样例2说明：
h学长有5点能量，可以用于5次机器的开启。 h学长会在时刻1 即第1个任务开始时开启机器，并在第2个任务结束时刻3关闭机器； h学长会在时刻5 即第3个任务开始时开启机器，并在第4个任务结束时刻7关闭机器; h学长会在时刻8 即第5个任务开始时开启机器，并在第5个任务结束时刻9关闭机器; h学长会在时刻11 即第6个任务开始时开启机器，并在第9个任务结束时刻17关闭机器; h学长会在时刻20 即第10个任务开始时开启机器，并在第10个任务结束时刻21关闭机器; 机器总工作时间为（3-1）+（7-5）+（9-8）+（17-11）+（21-20）=12 。开机、关机时刻不唯一。

思路：

将两相邻任务的间隔时间排序，将开机次数用再间隔时间最长的任务中。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[100050], b[100050];
int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n - 1; i++) {
		b[i] = a[i + 1] - a[i] - 1;
	}
	sort(b, b + n - 1);
	int sum = 0;
	for (int i = 0; i < n - k; i++) {
		sum += b[i];
	}
	cout << sum + n;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4.特殊的翻译

小明的工作是对一串英语字符进行特殊的翻译：当出现连续且相同的小写字母时，须替换成该字母的大写形式，在大写字母的后面紧跟该小写字母此次连续出现的个数；与此同时，把连续的小写字母串的左侧和右侧的字符串交换位置；重复该操作，直至没有出现连续相同的小写字母为止。现在小明想请你帮他完成这种特殊的翻译。

输入格式:

输入一串由小写字母构成的字符串。（字符串长度不大于250）

输出格式:

输出翻译后的字符串。

输入样例1:

dilhhhhope

输出样例1:

opeH4dil

输入样例2:

lodnkmgggggggoplerre

输出样例2:

eG7lodnkmR2ople

思路：

遍历字符串，若遇到连续的小写字母则记录下第一个的下标j;
循环计算连续小写字母的长度，记下最后一个的下标i（此时相同字符长度为j到i）;
将相同字符之后的字符串，也就是i以后的字符用substr函数返回并用append函数连接到一个空字符串s中，将此时的相同字符转化为一个大写字母用append函数连接到s中，再用sprintf函数将整型数字i-j+1转化为字符型储存并连接到s中，再将0到j的子字符串连接到s之后，完成前后倒置。
循环以上操作，直到字符串中没有连续的小写字母为止。

代码：

#include<bits/stdc++.h>
using namespace std;
string a, s;
char s1[1000];
int i, j;
bool f;
int main(){
    cin >> a;
    while (1)
    {
        f = false;
        while (a[i] != a[i + 1] && a[i + 1] != 0 && a[i] >= 'a' && a[i] <= 'z')
            i++;
        j = i;
        while (a[i] == a[i + 1] && a[i + 1] != 0 && a[i] >= 'a' && a[i] <= 'z'){
            i++;
            f = true;
        }//出现连续小写字母
        if (f == false)
            break;//若不出现连续小写字母则跳出循环
        if (i < a.length())
            s.append(a.substr(i + 1));//substr返回i+1之后的所有字符，再用append连接到s中
        string str1(1, a[i] - 32);//将小写的a[i]转化为大写字母存放入字符串str1中
        s.append(str1);//将str1连接到s末尾
        sprintf(s1, "%d", i - j + 1);//将整型数字i-j+1转化为字符型存放在字符数组s1中
        string str2(s1);//构造s1为string型str2
        s.append(str2);//将str2连接到s末尾
        if (j > 0)
            s.append(a.substr(0, j));//将连续小写字母之前的所有字符连接到s末尾，完成倒置
        a = s;//a赋值为新生成的字符串s
        s = "";//s置空
        i = 0;
        j = 0;
    }
    cout << a;
    return 0;
}
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

5.好吃的巧克力

超市正在特价售卖巧克力，正好被贪吃的Lucky_dog看见了。

巧克力从左到右排成一排，一共有N个，M种。

超市有一个很奇怪的规定，就是你在购买巧克力时必须提供两个数字a和b，代表你要购买第 a 个至第 b 个巧克力(包含 a 和 b)之间的所有巧克力。

假设所有巧克力的单价均为1元。Lucky_dog想吃所有种类的巧克力，但又想省钱。作为Lucky_dog的朋友，他请你来帮他决定如何选择购买巧克力时的 a 和 b。

输入格式:

第一行包含两个正整数 N 和 M（M<=N, N<=10^6 , M<=2000），分别代表巧克力的总数及种类数。

第二行包含 N 个整数，这些整数均在1 至 M 之间，代表对应的巧克力所属的种类。

输出格式:

输出仅一行，包含两个整数a和 b(a<=b) ，由一个空格隔开，表示花费最少且包含所有种类巧克力的购买区间。

数据保证有解，如果存在多个符合条件的购买区间，输出a最小的那个。

输入样例:

12 5
2 5 3 1 3 2 4 1 1 5 4 3

输出样例:

2 7

思路:

用a数组储存每个巧克力，用b数组储存区间LR中每种巧克力有几个，遍历数组，右移右端点R直到出现的巧克力种类数等于m。（确定右端点）
判断左端点L的巧克力所对应的该种类的个数，若大于1，则左端点右移，区间内该种类巧克力数减少，将此时的LR区间保存。（确定左端点）
遍历剩余数组，将区间扩大，右端点逐步右移，每右移一个单位，记录区间内各种巧克力的数目，重复第二步骤确定下一个左端点，确定新的LR区间，与原LR区间比较长短，将答案更新为较短的LR区间。
最后遍历完整个数组即可找到最小区间LR。

代码:

#include<bits/stdc++.h>
using namespace std;
int a[1000000], b[2001];//a储存巧克力总数，b储存每种巧克力的个数
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int i = 1;
	int R = 0, L = 1;
	int sum = 0;//种类数
	while (sum != m) {
		if (b[a[i]] == 0)
			sum++;
		b[a[i]]++;
		R++;
		i++;
	}
	while (b[a[L]] > 1) {
		b[a[L]]--;
		L++;
	}
	int ansL = L, ansR = R;
	while (i <= n) {
		b[a[i]]++;
		R++;
		i++;
		if(a[L]==a[R]) {
			L++;
		}
		if (ansR - ansL > R - L) {
			ansR = R;
			ansL = L;
		}
	}
	cout << ansL << " " << ansR;
	return 0;
}
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

6.下次一定（续）

你是一个bilibili的六级号，由于经常一键三连，所以一个硬币都没有，现在你又做了个梦，在梦中你制定了一个硬币增加规则：

第一天登陆后硬币总数1个，第二天登陆后硬币总数112个，第三天登陆硬币总数112123个…，以此类推，梦中不知日月，你瞬间拥有了11212312341234512345612345671234567812345678912345678910123456789101112345678910…无穷多个硬币。

常年维护B站秩序的百漂怪看不下去了，决定随机挑一个数x，作为这个无穷数的第x位，如果你能正确答对这第x位上的数是什么，就赠送给你与这个数等量的硬币。

百漂怪总共会挑t次。

你决定编程模拟一下，搏一搏，单车变摩托。

输入格式:

第一行包含一个正整数t(1≤t≤10)，表示百漂怪挑了t次。接下来t行，每行一个正整数x (1 ≤ x≤ 2^31-1)，表示第i次，百漂怪挑的是第x位。

输出格式:

输出共t行，每行输出对应第x位上的数。

输入样例1:

2
3
8

输出样例1:

2
2

输入样例2:

6
222
66666
99999999
66656565
22222
2

输出样例2:

6
4
9
4
1
1

思路：

记第一组为1，第二组为12，第三组为123，打表预处理计算除第2147482647位在第31268组，然后预处理计算前31268组的位数，存储在sum数组中，其中(int)log10((double)i)+1表示数据 i 的位数。然后模拟就行了，计算出当前要计算的第x位处在第k组中，然后找到所求位数位于整数 i 中，把 i 后面的数字除掉，取模之后即所求结果。
来源：POJ1019

代码：

#include<bits/stdc++.h>
using namespace std;
long int a[31270], b[31270];
void start() {
	int i;
	a[1] = 1;
	b[1] = 1;
	for (i = 2; i < 31270; i++) {
		a[i] = a[i - 1] + (int)log10((double)i) + 1;
		b[i] = b[i - 1] + a[i];
	}
}
int res(int n) {
	int i = 1, j = 1, len = 0;
	for (i = 1; i < 31270; i++) {
		if (b[i] >= n)
			break;
	}
	int s = n - b[i - 1];
	for (j = 1; len < s; j++) {
		len += (int)log10((double)j) + 1;
	}
	return ((j - 1) / (int)pow(10.0, len - s)) % 10;
}
int main() {
	start();
	int t, x;
	cin >> t;
	while (t--) {
		cin >> x;
		cout << res(x) << endl;
	}
	return 0;
}
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

7.走迷宫

你正在玩一个迷宫游戏，迷宫有n×n格，每一格有一个数字0或1，可以从某一格移动到相邻四格中的一格上。为了消磨时间，你改变了玩法，只许从0走到1或者从1走到0。

现在给你一个起点，请你计算从这个格子出发最多能移动多少个格子（包含自身）。

输入格式:

第1行包含两个正整数n和m（1≤n≤1000,1≤m≤10000）。

接下来n行，对应迷宫中的n行，每行n个字符，字符为0或者1，字符之间没有空格。

接下来m行，表示m次询问。每行2个正整数i，j，表示从迷宫中第i行第j列的格子开始走。

输出格式:

输出共m行，每行一个整数，分别对应于输入数据中的m次询问，给出最多能移动的格子数。

输入样例:

2 2
01
10
1 1
2 2

输出样例:

4
4

思路：

连接在一起的格子的答案是一样的，所以不需要多次搜索，DFS找连通块即可。
来源：洛谷P1141

代码：

#include<bits/stdc++.h>
using namespace std;
char maze[2000][2000];//记录迷宫
int flag[2000][2000];//判断该点是否走过
int n, m;
int x, y;
int ans[20000];
void dfs(int xx, int yy, int zz,int ii) {
	if (xx > 0 && yy > 0 && xx <= n && yy <= n && flag[xx][yy] == -1 && maze[xx][yy] - '0' == zz) {
		flag[xx][yy] = ii;
		ans[ii]++;
		dfs(xx + 1, yy, !zz, ii);
		dfs(xx - 1, yy, !zz, ii);
		dfs(xx, yy + 1, !zz, ii);
		dfs(xx, yy - 1, !zz, ii);
	}
}
int main() {
	memset(flag, -1, sizeof(flag));
	memset(ans, 0, sizeof(ans));
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> maze[i] + 1;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		if (flag[x][y] == -1) {
			dfs(x, y, maze[x][y] - '0', i);
		}
		else {
			ans[i] = ans[flag[x][y]];
		}
	}
	for (int i = 0; i < m; i++) {
		cout << ans[i] << endl;
	}
}
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

第五周

1.移动圆盘

给出n个圆盘的半径，现在要把这些圆盘依次放在柱子上，当准备把第i个半径为ai的圆盘放置到柱子上时，如果柱子顶部的圆盘半径小于ai，那么将柱子顶部的圆盘拿出，如果顶部的盘子半径仍然小于ai，那么继续拿出，直到顶部圆盘半径大于或等于ai为止，此时才把第i个盘子放到柱子上。那么，最后从下往上输出柱子上的圆盘半径依次是什么？

输入格式:

第一行包含一个整数n（n<=100000），表示有n个圆盘要依次放到柱子上。接下来n行，每行一个整数，表示第i个圆盘的半径ai (ai<=100000)。

输出格式:

输出多行，表示最后柱子上中的圆盘半径。

输入样例:

5
5
3
2
4
1

输出样例:

5
4
1

思路：

模拟过程，先输入第一个盘子，而后依次输入盘子半径，若半径大于前一个的盘子，则将前一个盘子拿出，循环过程直到前一个盘子半径比该盘子大或前面没有盘子。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[100050];
int main() {
	int n;
	cin >> n;
	cin >> a[0];
	int i = 1, j = 1;
	int r;
	while (j < n) {
		cin >> r;
		while (r > a[i - 1] && i != 0) {
			a[i - 1] = 0;
			i--;
		}
		a[i] = r;
		i++;
		j++;
	}
	for (int i = 0; a[i] != 0; i++) {
		cout << a[i] << endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.微信号

小明刚认识了新同学小红，他想要小红的微信号，小红不想直接告诉他，所以给了小明一串加密了的数字，并且把解密规则告诉了小明。

解密规则是：首先删除第1个数，接着把第2个数放在这串数的最后面，再删除第3个数，并把第4个数放在这串数的最后面……直至只剩最后一个数，把最后一个数也删除。

按照删除的顺序，把这些数字连在一起就是小红的微信号。请你按照解密规则帮小明得到小红的微信号。

输入格式:

第一行包括一个正整数n（1 < n < 500），表示这串微信号的长度；

第二行包括n个数字，即加密的小红的微信号。

输出格式:

输出解密后的微信号，相邻数字之间有空格。

输入样例:

9
1 2 3 4 5 6 7 8 9

输出样例:

1 3 5 7 9 4 8 6 2

思路：

设置头尾两个下标，将数组的第一个元素输出，头下标后移，将此时第一个元素放置末尾，尾下标后移，头下标后移，循环操作直到头尾下标重合。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[500000], b[500000];
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int head = 0, tail = n;
	while (head < tail) {
		cout << a[head]<<" ";
		head++;
		a[tail] = a[head];
		tail++;
		head++;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3.糖果

学校里有n个孩子，从1到n对这些孩子进行编号。老师将给孩子们分发糖果，第i个孩子希望至少获得ai个糖果。

老师要求孩子们排队。最初，第i个孩子站在队伍的第i个位置。然后，老师开始分发糖果。分发糖果的规则是：将m个糖果给队伍中的第一个孩子，如果这个孩子没有得到足够的糖果，那么这个孩子会走到队伍的尽头；否则这个孩子就回家了。当队伍不为空时，重复这个规则一直分发糖果。如果考虑所有孩子回家的顺序。老师想知道，哪个孩子将是这个顺序中的最后一个？

输入格式:

第一行包含两个整数n，m（1≤n≤100; 1≤m≤100）。第二行包含n个整数a1，a2，…，an（1≤ai≤100）。

输出格式:

输出一个整数，代表最后一个孩子的编号。

输入样例:

3 3
2 4 3

输出样例:

2

思路:

建立结构体（包含：当前已有糖果数，所需糖果数，编号）
设置头尾下标，模拟题目操作即可。

代码：

#include<bits/stdc++.h>
using namespace std;
struct kid {
	int have = 0;
	int need;
	int index;
}a[100000];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].need;
		a[i].index = i;
	}
	int head = 1, tail = n + 1;
	while (1) {
		a[head].have += m;
		if (a[head].have >= a[head].need) {
			head++;
		}
		else {
			a[tail].have = a[head].have;
			a[tail].need = a[head].need;
			a[tail].index = a[head].index;
			tail++;
			head++;
		}
		if (tail - head == 1) {
			cout << a[head].index << endl;
			break;
		}
	}
	return 0;
}
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

4.谁比我大

给定一个含有n个整数的数列a1,a2,…an。定义函数 f(ai)表示数列中第i个元素ai之后第一个大于ai的元素的下标，若这样的元素不存在，则f(ai)=0。

输入格式:

第一行包含一个正整数n（n<=1e6）；

第二行包含n个正整数 a1,a2,…an（1<=ai<=1e9）。

输出格式:

输出仅一行包含 n个整数，分别代表 f(ai) 的值。

输入样例:

5
1 4 2 3 5

输出样例:

2 5 4 5 0

思路：

双重循环，遍历数组，找到比当前元素大的第一个下标输出，若未找到，则输出0。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000050];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	int i = 1, j;
	for (i = 1; i <= n; i++) {
		for (j = i + 1; j <= n; j++) {
			if (a[j] > a[i]) {
				cout << j << " ";
				break;
			}
			if (j == n) {
				cout << 0 << " ";
			}
		}
		if (i == n) {
			cout << 0 <<" ";
		}
	}
	return 0;
}
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

5.后缀表达式

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右进行（不用考虑运算符的优先级）。

如：中缀表达式 3*(5–2)+7 对应的后缀表达式为：352-*7+ 。

请将给出的中缀表达式转化为后缀表达式并输出。

输入格式:

输入仅一行为中缀表达式，式中所有数字均为个位数，表达式长度小于1000。

输出格式:

输出一行，为后缀表达式，式中无空格。

输入样例:

2+4×8+(8×8+1)/3

输出样例:

248×+88×1+3/+

思路：

设置优先级，将操作数直接输出，操作符判断优先级后再输出，括号需要特别判断。

代码：

#include<bits/stdc++.h>
using namespace std;
stack<char>q;
int level(char x) {
	int ll;
	if (x == '*' || x == '/')
		ll = 2;
	if (x == '+' || x == '-')
		ll = 1;
	return ll;
} //判断优先级 

int main() {
	int i;
	char s[1000];
	memset(s, '\0', sizeof(s));
	cin >> s;
	int l = strlen(s);
	for (i = 0; i < l; i++) {
		if (s[i] >= '0' && s[i] <= '9')
			cout << s[i]; //如果是操作数直接输出操作数 
		if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') {
			while (1) {
				if (q.empty() || q.top() == '(') {
					q.push(s[i]);
					break;
				}//空栈或为括号内的直接入栈；
				else if (level(s[i]) > level(q.top())) {
					q.push(s[i]);
					break;
				}//当前运算符优先级大于栈顶则入栈
				else {
					cout << q.top();
					q.pop();
				}//优先级小于栈顶则弹出栈顶
			}
		}
		if (s[i] == '(') {
			q.push(s[i]);
		}//左括号压入 
		if (s[i] == ')') { //遇到右括号 
			while (q.top() != '(') {
				cout << q.top();
				q.pop();
			} //将除左括号以外的操作符全部输出 
			q.pop(); //弹出左括号 
		}
		if (i == l - 1) { //数据到底了，输出栈中剩余所有操作符 
			while (!q.empty()) {
				cout << q.top();
				q.pop();
			}
		}
	}
	return 0;
}
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

6.后缀表达式计算

Kunkun学长觉得应该让学弟学妹了解一下这个知识点：后缀表达式相对于中缀表达式更容易让计算机理解和学习。现在kunkun学长给出一串后缀表达式，你能帮他算出这个后缀表达式的值吗？

输入格式:

第一行输入后缀表达式长度n（1<=n<=25000）；

第二行输入一个字符串表示后缀表达式（每个数据或者符号之间用逗号隔开，保证输入的后缀表达式合法，每个数包括中间结果保证不超过long long长整型范围）

输出格式:

输出一个整数，即后缀表达式的值。

输入样例1:

6
10,2,+

输出样例1:

12

输入样例2:

14
2,10,2,+,6,/,-

思路：

遇到操作数，存入数组，注意多位数；遇到操作符，将数组中的最后两个数进行运算，两个操作数弹出，将结果存入数组。
循环操作，数组中最后一个数即为答案。

代码：

#include<bits/stdc++.h>
using namespace std;
long long int a[2000000];
char op[1000000];
int main() {
	long long int n, k = 0;
	long long int num = 0;
	cin >> n;
	for (long long int i = 0; i < n; i++) {
		cin >> op[i];
	}
	for (long long int i = 0; i < n; i++) {
		if (op[i] >= '0' && op[i] <= '9') {
			if (op[i - 1] == '-') {
				num = num * 10 + (op[i] - '0');
				num = -num;
			}
			else {
				if (num < 0) {
					num = num * 10 - (op[i] - '0');
				}
				else {
					num = num * 10 + (op[i] - '0');
				}
			}
		}
		else if (op[i] == ',') {
			if (num != 0) {
				a[k] = num;
				num = 0;
				k++;
			}
		}
		else if (op[i] == '+') {
			a[k - 2] = a[k - 2] + a[k - 1];
			a[k - 1] = 0;
			k--;
		}
		else if (op[i] == '-') {
			if (op[i + 1] == ',' || i == n - 1) {
				a[k - 2] = a[k - 2] - a[k - 1];
				a[k - 1] = 0;
				k--;
			}
		}
		else if (op[i] == '*') {
			a[k - 2] = a[k - 2] * a[k - 1];
			a[k - 1] = 0;
			k--;
		}
		else if (op[i] == '/') {
			a[k - 2] = a[k - 2] / a[k - 1];
			a[k - 1] = 0;
			k--;
		}
	}
	cout << a[k - 1];
	return 0;
}

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

第六周

1.括号匹配检测

给出一串包含 ( 、 ) 、[ 和 ] 的字符串，字符串在以下三种情况下为合法的：

1）字符串为空；

2）如果A和B都是合法的，那么AB也是合法的；

3）如果A是合法的，那么(A)和[A]也是合法的。

试判断输入的字符串是否合法。

输入格式:

输入包括一串由若干个 ( 、 ) 、 [ 或 ] 组成的字符串，字符串长度不超过100。

输出格式:

如果该字符串合法，输出“Yes”；否则输出“No”。

输入样例:

([])

输出样例:

Yes

思路:

遇到左括号直接入栈，遇到右括号判断与栈顶是否匹配，若匹配则弹出栈顶，若不匹配则输出No，结束。

代码:

#include<bits/stdc++.h>
using namespace std;
char a[1000];
stack<char>q;
int main() {
    memset(a, '\0', sizeof(a));
    cin >> a;
    int l = strlen(a);
    for (int i = 0; i < l; i++) {
        if (a[i] == '(' || a[i] == '[')
            q.push(a[i]);
        if (a[i] == ')') {
            if (q.empty() == true) {
                cout << "No";
                return 0;
            }
            else {
                if (q.top() == '(')
                    q.pop();
                else {
                    cout << "No";
                    return 0;
                }
            }
        }
        if (a[i] == ']') {
            if (q.empty() == true) {
                cout << "No";
                return 0;
            }
            else {
                if (q.top() == '[')
                    q.pop();
                else {
                    cout << "No";
                    return 0;
                }
            }
        }
    }
    cout << "Yes";
    return 0;
}
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

2.选座位

已知公交车中有n排座位，每排都有2个座位。第i排的两个座位的宽度均为wi厘米。没有相同宽度的两排座位。

公共汽车最初是空的。有2n位乘客按顺序先后进入公共汽车。乘客分为两种类型：

内向者：总是选择两个座位都没人的一排。在这些排中，他选择座位宽度最小的，并占据了其中的一个座位; 外向型：总是选择有人的一排。在这些排中，他选择座位宽度最大的那个，并占据了空位。

你会得到每排座位的宽度和乘客进入公共汽车的顺序。请你帮忙确定每位乘客将乘坐哪一排座位。

输入格式:

第一行包含一个整数n（1 ≤ n ≤ 200），表示公共汽车上座位的总排数。

第二行是一个包含n个整数的序列w 1，w 2，…，w n（1 ≤ w i ≤ 10000），其中wi是第i行中每个座位的宽度。保证所有 w i 都不同。

第三行包含一个长度为 2n 的字符串，由数字“0”和“1”组成，该字符串描述了乘客进入公共汽车的顺序。如果第j个字符是 ‘0’，那么说明第 j 个进入公共汽车的乘客是内向型的；如果第j个字符是 ‘1’，则表示第j个进入公交车的乘客是外向型的。保证外向者的数量等于内向者的数量（即’0’和’1’的个数均为 n），并且对于每个外向者总是有合适的行。

输出格式:

打印 2n 个整数，整数之间以空格分隔，表示乘客将坐的排。乘客的顺序应与输入的顺序相同。

输入样例1:

2
3 1
0011

输出样例1:

2 1 1 2

输入样例2:

6
10 8 9 11 13 5
010010011101

输出样例2:

6 6 2 3 3 1 4 4 1 2 5 5

代码:

#include<bits/stdc++.h>
using namespace std;
char s[500];
struct seat {
    int w;//座位宽度
    int p;//排
}a[250];
stack<int>q;
int cmp(seat a, seat b) {
    return a.w < b.w;
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].w;
        a[i].p = i;
    }
    sort(a + 1, a + n + 1, cmp);
    cin >> s;
    int k = 1;
    for (int i = 0; i < 2 * n; i++) {
        if (s[i] == '0') {
            cout << a[k].p << " ";
            q.push(a[k].p);
            k++;
        }
        if (s[i] == '1') {
            cout << q.top() << " ";
            q.pop();
        }
    }
    return 0;
}
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

3.括号匹配调整

如果通过插入“ +”和“ 1”可以从中得到格式正确的数学表达式，则将带括号的序列称为正确的。

例如，序列 “(())()”，"()“和 “(()(()))“是正确的，而”)(”，”(()))(“和”(()" 不是。

定义重新排序操作：选择括号序列的任意连续子段（子字符串），然后以任意方式对其中的所有字符进行重新排序。

当重新排序的子段的长度为t时，重新排序操作需要耗时t秒。

例如，对于“))((”，他可以选择子字符串“)(”并重新排序“)()(”（此操作将花费2秒）。

不难看出，重新排序操作不会改变左括号和右括号的数量。

现在，LD想花费最少的时间，通过任意次数（可能为零）执行重新排序操作来使括号序列变成正确的。

输入格式:

第一行包含一个整数n（1≤n≤1e6），表示序列的长度；

第二行包含一个长度为n的字符串，仅由字符‘(’和‘)’组成。

输出格式:

输出一个整数，表示使括号序列正确的最小秒数；如果不可能实现，则输出-1。

输入样例:

8
))((())(

输出样例:

6

思路:

遍历字符串，若栈为空，遇到左括号直接压入；遇到右括号则秒数+1，再压入。若栈非空，遇到左括号判断栈顶是否为右括号，若是则需要重新排列，秒数+1，若否则直接压入；遇到右括号，判断栈顶是否为左括号，若是则匹配，弹出栈顶，若否则需要重新排列，秒数+1，压入。

代码:

#include<bits/stdc++.h>
using namespace std;
int n, ans = 0;
char s[1000050];
stack<char>q;
int main(){
    cin >> n;
    cin >> s;
    for (int i = 0; i < n; i++) {
        if (q.empty()) {
            if(s[i]=='(')
                q.push(s[i]);
            else {
                q.push(s[i]);
                ans++;
            }
        }
        else {
            if (s[i] == '(') {
                if (q.top() == ')') {
                    ans++;
                    q.pop();
                }
                else {
                    q.push(s[i]);
                }
            }
            if (s[i] == ')') {
                if (q.top() == '(') {
                    q.pop();
                }
                else {
                    q.push(s[i]);
                    ans++;
                }
            }
        }
    }
    cout << ans;
    return 0;
}
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

4.堆放石子

有N堆石子，每堆石子有若干石头，所有石头的总数是N的倍数。

可以在任意一堆上取若干石头，进行移动。移动规则是：在第一堆上取的石子，只能移到第二堆；在第N堆上取的石子，只能移到N-1堆；其他堆上取的，可以移到相邻左边或者右边。如何用最少的移动次数使得每堆石子的数量一样多呢？

当N=4时，4堆石子数为：9、8、17、6

移动3次可以使4堆数目一样多：

从第3堆取4个石子放到第4堆（9、8、13、10）

从第3堆取3个放到第2堆（9、11、10、10）

从第2堆取1个放到第1堆（10、10、10、10）

输入格式:

第一行包含一个整数N（1<= N <=100），表示有N堆石子；

接着有N行，每行一个整数ai（1<= ai <=10000)，表示第i堆石子的数量。

输出格式:

输出一个整数，表示使所有石子堆的石子均达到相等时需要的最少移动次数。

输入样例:

4
9 8 17 6

输出样例:

3

来源：

洛谷P1031

代码：

#include<bits/stdc++.h>
using namespace std;
int main() {
	int a[200];
	int n, avg = 0, ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		avg += a[i];
	}
	avg /= n;
	for (int i = 1; i < n; i++) {
		if (a[i-1] != avg) {
			a[i] += a[i - 1] - avg;
			ans++;
		}
	}
	cout << ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

5.一键三连

你已经两个月没有出门了，无聊到自己和自己玩“一键三连”的游戏。这个游戏很简单，你制作了规格为4×4的棋盘，一开始棋盘中所有格子都是空的，全为‘.’，紧接着你一人分饰两角，一个画‘x’填到一个为空的格子里，另一个画‘o’填到另一个为空的格子，这个过程交替进行。如果一方先使横的、竖的或斜的有连续的三个格子都是属于自己的标记，那么就赢了。

你刚刚看完一个视频，现在准备开始玩“一键三连”，于是你拿出了很久之前的棋盘，它可能下过，也可能没有（即全部填‘.’），但保证此时没有达到画‘o’的胜局。你选择在一个为空的格子里画‘x’后马上停止，看看是否能构成画‘x’的胜局。

输入格式:

输入共四行四列，表示由“.”（表示空的），“x”（小写字母x）或“o”（小写字母o）组成棋盘。

输出格式:

如果你一键三连了，输出“YES”，否则输出“NO”。

输入样例1:

xx…
.oo.
x…
oox.

输出样例1:

YES

输入样例2:

x.ox
ox…
x.o.
oo.x

输出样例2:

NO

思路：

遍历二维数组，暴力判断。

代码：

#include<bits/stdc++.h>
using namespace std;
char mp[10][10];
int judge() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            if (mp[i][j] == 'x' && mp[i][j + 1] == 'x' && mp[i][j + 2] == 'x' && j + 2 <= 4) {
                return 1;
            }
        }
    }
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            if (mp[i][j] == 'x' && mp[i + 1][j] == 'x' && mp[i + 2][j] == 'x' && i + 2 <= 4) {
                return 1;
            }
        }
    }
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            if (mp[i][j] == 'x' && mp[i + 1][j + 1] == 'x' && mp[i + 2][j + 2] == 'x' && i + 2 <= 4 && j + 2 <= 4) {
                return 1;
            }
        }
    }
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            if (mp[i][j] == 'x' && mp[i + 1][j - 1] == 'x' && mp[i + 2][j - 2] == 'x' && i + 2 <= 4 && j - 2 >= 1) {
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            cin >> mp[i][j];
        }
    }
    for (int i = 1; i <= 4; i++) {
        for (int j = 1; j <= 4; j++) {
            if (mp[i][j] == '.') {
                mp[i][j] = 'x';
                if (judge()) {
                    cout << "YES";
                    return 0;
                }
                mp[i][j] = '.';
            }
        }
    }
    cout << "NO";
	return 0;
}
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

6. 最大积分

给你一罐颜料，并规定写出1-9每个数字所用的颜料是指定量的，当你用这罐颜料写下的数字越大，你得到的积分越多。

那么，你能得到的最大积分是多少呢？

输入格式:

第一行包含一个整数n（0≤n≤1000），表示给定颜料量。

第二行包含九个正整数a1，a2，… ，a9,分别表示写下数字1-9所需要的颜料量。

输出格式:

输出一个数，表示你能得到的最大积分；如果颜料连一个数字都不够写，那么输出-1。

输入样例:

2
9 11 1 12 5 8 9 10 6

输出样例:

思路:

贪心，先找出最大位数，再从最高位开始，找每一位上的最大数字。

代码:

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, a[10], min;
    cin >> n;
    for (int i = 1; i < 10; i++) {
        cin >> a[i];
        if (i == 1) {
            min = a[1];
        }
        else {
            if (a[i] <= min) {
                min = a[i];
            }
        }
    }
    if (n < min) {
        cout << "-1";
        return 0;
    }
    else {
        int w = n / min;//最大能写的位数
        for (int i = w; i > 0; i--) {
            for (int j = 9; j >= 1; j--) { 
                if (n >= a[j] && (n - a[j]) / min >= i - 1) {
                    cout << j;
                    n -= a[j];
                    break;
                }//从9开始，若能将当前位数的最高位替代，则用该数字替代，保证最大
            }
        }
    }
    return 0;
}
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

7.168

汉堡包在大街上大摇大摆的走着,看着手机上一道难倒数万人的小学数学题:

1 + 1 = 0

1 + 6 = 1

6 + 6 = 2

8 + 1 = 2

8 + 6 = 3

汉堡包看完之后发现上面这些加法的答案就是看1,6,8中圈圈的个数嘛！

突然之间,所有大厦上的LED屏幕上的广告全部变成数字1,6,8三个数字的随机闪现。

现给你一块n*m的LED屏幕，上面有且仅有一个数字(1,6,or 8)，请你输出你看见的那个字母。

输入格式:

第一行输入两个整数n，m(2<= m, n <= 1000)；

接下来n行，每行由m个数字0和1组成，其中1表示数字1，6，8的组成部分。

输出格式:

输出一个整数，代表图形表示的数字。

输入样例:

7 7
0 0 0 0 0 0 0
0 0 1 1 1 0 0
0 0 1 0 1 0 0
0 0 1 1 1 0 0
0 0 1 0 1 0 0
0 0 1 1 1 0 0
0 0 0 0 0 0 0

输出样例:

8

思路：

从最后一行遍历至第一行，
若构成数字为1，每行1的个数都相同；
若构成数字为6，每行1的个数会出现两次减少；
若构成数字为8，每行1的个数会出现一次减少。

代码：

#include<bits/stdc++.h>
using namespace std;
int a[1000][1000];
int b[1000] = { 0 };//记录每行1的个数
int c[1000];
int main() {
	int n, m, i, j, count = 0, min;
	cin >> n >> m;
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			if (a[i][j] == 1)
				b[i]++;
		}
	}
	for (i = 0, j = 0; i < n; i++) {
		if (b[i] != 0)
			c[j++] = b[i];
	}
	min = c[j - 1];
	for (i = j - 2; i >= 0; i--) {
		if (c[i] < min) {
			min = c[i];
			count++;
		}
	}
	if (count == 0)
		cout << "1";
	if (count == 1)
		cout << "8";
	if (count == 2)
		cout << "6";
	return 0;
}
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/253535?site

程序设计综合实践

目录

第一周

1. 买卖牛奶

输入格式:

输出格式:

输入样例:

输出样例:

思路：

代码：

2.航船

输入格式:

输出格式：

输入样例:

输出样例：

思路：

代码：

3.多项式

输入格式:

输出格式:

输入样例1:

输出样例1:

输入样例2

输出样例2:

代码：

4.兼容任务

输入格式:

输出格式:

输入样例:

输出样例:

思路：

代码：

5.致死一击

输入格式:

输出格式:

输入样例1:

输出样例1:

输入样例2

输出样例2

思路：

代码：

6.顺序的分数

输入格式:

输出格式：

输入样例:

输出样例：

思路：

代码：

7.德州扑克

输入格式：

输出格式:

输入样例：

输出样例:

思路;

代码：

第二周

1.正确答案

输入格式:

输出格式:

输入样例:

输出样例:

思路：

代码：

2.日期差值

输入格式:

输出格式:

输入样例:

输出样例:

代码：

3.最少分成几组

输入格式:

输出格式:

输入样例:

输出样例:

思路：

代码：

4.美丽数列

输入格式:

输出格式:

输入样例: