第一周

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;elsecout << r;return 0;
}

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);elseprintf("-1");return 0;
}

3.多项式

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

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

输入格式:

输入共有两 行。 第一行 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;elsecout << "+" << "x^" << n - i;}if (a[i] < 0) {if (a[i] != -1)cout << a[i] << "x^" << n - i;elsecout << "-" << "x^" << n - i;}}if (a[n - 1] > 0) {if (a[n - 1] != 1)cout << "+" << a[n - 1] << "x";elsecout << "+x";}if (a[n - 1] < 0) {if (a[n - 1] != -1)cout << a[i] << "x";elsecout << "-x";}if (a[n] > 0)cout << "+" << a[n];if (a[n] < 0)cout << a[n];}return 0;
}

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++;//任意一个任务开始时间大于结束时间 兼容任务数+1flag = f[i].b;//更新结束时间}}cout << sum;return 0;
}

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;elsef[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;elseg[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;
}

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;
}

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;elsereturn 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;elsereturn 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;elsereturn 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-9if (x.score != 0)return x.score;elsereturn 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 Aif (x.score != 0)return x.score;elsereturn 0;
}//皇家同花顺
int cmp(person x,person y) {if (x.score == y.score)return strcmp(x.name, y.name) < 0;elsereturn 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，则说明含10if (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);elseprintf("%s", a[i].name);}//输出结果return 0;
}

第二周

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;
}

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);elsedays -= (long long int)365 - month(y1, m1, d1);for (y1++; y1 != y2; y1++){if (run(y1))days -= 366;elsedays -= 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);elsedays += (long long int)365 - month(y2, m2, d2);for (y2++; y1 != y2; y2++){if (run(y2))days += 366;elsedays += 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);
}

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;elsecout<<1;return 0;
}

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;}

5.最长公共子串

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

输入格式:

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

输出格式:

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

输入样例:

5
aaaaa
bbbbb

输出样例:

5

思路：

遍历数据，直到有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--;}elsebreak;}}ans=max(ans,step);}}printf("%d",ans);return 0;
}

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

输出样例:

98

思路：

首先，骰子一共最多只有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;}}
}

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.郭老师的冰糖葫芦

郭老师有草莓和山楂两种水果共计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;
}

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;
}

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;elsereturn 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--;}elsef[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;}
}

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';elsea[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;
}

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];}
}

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;

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为0void 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.两个整数的除数

给你一个混排的数列，其中包含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;
}

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;
}

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;
}

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型str2s.append(str2);//将str2连接到s末尾if (j > 0)s.append(a.substr(0, j));//将连续小写字母之前的所有字符连接到s末尾，完成倒置a = s;//a赋值为新生成的字符串ss = "";//s置空i = 0;j = 0;}cout << a;return 0;
}

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;
}

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;
}

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.移动圆盘

给出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;
}

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;
}

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;
}

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;
}

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;
}

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.括号匹配检测

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

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;
}

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;
}

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;
}

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;
}

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;
}

6. 最大积分

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

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

输入格式:

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

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

输出格式:

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

输入样例:

2
9 11 1 12 5 8 9 10 6

输出样例:

33

思路:

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

代码:

#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;
}

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;
}