刷题日志--2021年02月 - 雨中的博客

本系列记录翀翀😐痛苦的刷题日志,坚持刷题谈起来容易做起来难,希望我可以坚持下去,这里仍然分享一段励志文案:每个人都有梦想,然而有些人把梦想变成了现实,有些人的梦想依旧是梦想,只因为他们为梦想付出的努力程度不一样,他们坚持的时间不一样,最终才有这样的结果。

NC21312-神秘餐馆

题目链接

https://ac.nowcoder.com/acm/problem/21312

题目描述

一家神秘餐馆准备开放N天,牛牛 和 牛妹听到这个消息后,准备尽可能多的一起去吃午饭

餐馆有M道菜,牛牛和牛妹每次来只允许点一道菜,如果在第i天买了第j道菜
那么第i+7天也只能买第j道菜
第i天第j道菜的价格为price[i][j]
‘0’-‘9’代表0-9美元
‘A’-‘Z’代表10-35美元
‘a’-‘z’代表36-61美元

牛牛和牛妹一共只有budget美元,请问他们最多可以吃几天的午饭。

第一行输入3个整数n,m,budget (1 ≤ n ≤ 50, 1 ≤ m ≤ 50, 0 ≤ budget ≤ 10000)
接下来n行每行输入一个字符串,包含m个字符
第i行的第j个字符表示第i天第j道菜的价格。

测试样例

样例1

输入

1
2
3
4
5
6
7
8
7 2 13
26
14
72
39
32
85
06

输出

1
5
样例2

输入

1
2
3
4
5
6
7
8
9
8 2 20
26
14
72
39
32
85
06
91

输出

1
8
样例3

输入

1
2
3
4
5
6
7
8
9
10
11
12
13
12 4 256
Dear
Code
rsHa
veFu
nInT
heCh
alle
ngeP
hase
andb
ecar
eful

输出

1
10

解题思路

实际上唯一需要注意的细节就是一旦确定了星期i吃j号菜品,那么无论以后的菜品有多贵都只能选择这个j号菜品。所以我们需要保证周i所选择的j号菜品加起来的总花费最低。比如我们看样例2,第一天周一我们肯定是选择了一号菜品花费2元,那么也就意味着第八天的周一我们只能选择一号菜品花费9元,这样算周一吃了两次一号菜品总花费11元,然而周一如果我们是根据第八天的周一菜品价格选择二号菜品,那么虽然第一天吃的是6元,但是这也意味着第八天的周一我们可以吃而号菜品1元,加起来8天内两次周一都选择的是二号菜品总花费就是7元小于11元。所以每一次我们都选择当下周i最便宜的菜品后同时要回忆以前的菜品都改成这次选择的最便宜菜品进行重新计算周i所有吃菜品j的总花费保证他是最小。至于第i天是周几,我们只需要i%7即可。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

const int N = 55; //一次性开到最大的数组
int n, m, budget; //天数,每天的菜品数量
string s[N]; //存储一天的各个菜品价格的字符串数组
int meat[7][N]; //星期i选择第j份菜品的总花费
int cost[7]; //已知的最便宜的菜品花费

int main()
{
cin >> n >> m >> budget;
for (int i = 0; i < n; i++)
{
//记录数据并且计算出每一个字符所代表的的相对应的第i天第j份菜品的费用
cin >> s[i];
for (int j = 0; j < m; j++)
{
if (s[i][j] >= '0' && s[i][j] <= '9')
s[i][j] = s[i][j] - '0';
if (s[i][j] >= 'A' && s[i][j] <= 'Z')
s[i][j] = s[i][j] - 'A' + 10;
if (s[i][j] >= 'a' && s[i][j] <= 'z')
s[i][j] = s[i][j] - 'a' + 36;
}
}
//已知的最省钱的花费
int money = 0;
//统计n天的最多吃饭次数
for (int i = 0; i < n; i++)
{
//计算前先减掉这次菜品组合,比如样例2中的星期1我们
//优先选择了花费小的菜品1(即此时会吃两次菜品2花费分
//别是(2,9),那么现在到了第8天即又到
//了周一我们假设现在有更好的更省钱的菜品组合
//(后面确实有更好的即周一时 选择菜品2(6,1),
//所以减去之前的花费(2,9)重新统计星期i的选餐组合
money -= cost[i % 7];
for (int j = 0; j < m; j++)
{
//统计选择了第j件菜品时所有吃第j个菜品的花费
meat[i % 7][j] += s[i][j];
}
//假设选择每天的第一个菜品吃最省钱
cost[i % 7] = meat[i % 7][0];
for (int j = 1; j < m; j++)
{
//统计若选择吃第j件菜品是否比选择吃第1件菜品更省钱
cost[i % 7] = min(cost[i % 7], meat[i % 7][j]);
//保证每一次选择的都一定是一直当前的最省钱组合
}

money += cost[i % 7];

if (money > budget)
{
//在餐厅关闭前花完钱了,那么返还吃了几次
cout << i << endl;
system("pause");
return 0;
}
}
//如果花完钱之前餐厅关闭了,那么必定每天都吃了一次,返还n
cout << n << endl;
system("pause");
return 0;
}

NC21842-正方形检测

题目链接

https://ac.nowcoder.com/acm/problem/21842

题目描述

给你平面直角坐标系中的四个点,判断这四个点是否构成一个正方形 。

第一行输入四个整数xix_ixi (0≤xi≤100000 \le x_i \le 100000≤xi≤10000)
第二行输入四个整数yiy_iyi​ (0≤yi≤100000 \le y_i \le 100000≤yi​≤10000)

测试样例

样例1

输入

1
2
0 0 2 2
0 2 0 2

输出

1
It's a square
样例2

输入

1
2
3
0 1 5 6
1 6 0 5

输出

1
It's a square
样例3

输入

1
2
0 0 7 7
0 3 0 3

输出

1
Not a square

解题思路

实际上是一个规律,只要满足就一定是正方形,可以牢记,规律就是如下图所示:

只有当为正方形时,不重复的对每一个点进行连边,最后我们会得到6条边,进行从小到大排序:a表示一条直角边长度

所以我们使用双重循环判断可以发现刚好6个边可以组成7个相等长度的情况。即

由此就可以判断出结果了。注意不能用有四条边等于a的条件判断,这种条件有bug。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;

int main()
{
int x1, x2, x3, x4;
int y1, y2, y3, y4;
cin >> x1 >> x2 >> x3 >> x4;
cin >> y1 >> y2 >> y3 >> y4;
int length[7];
length[1] = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
length[2] = (x1 - x3) * (x1 - x3) + (y1 - y3) * (y1 - y3);
length[3] = (x1 - x4) * (x1 - x4) + (y1 - y4) * (y1 - y4);
length[4] = (x2 - x3) * (x2 - x3) + (y2 - y3) * (y2 - y3);
length[5] = (x2 - x4) * (x2 - x4) + (y2 - y4) * (y2 - y4);
length[6] = (x3 - x4) * (x3 - x4) + (y3 - y4) * (y3 - y4);
sort(length + 1, length + 7);
int num = 0;
for (int i = 1; i < 7; i++)
{
for (int j = i + 1; j < 7; j++)
{
if (length[i] == length[j])
{
num++;
}
}
}
if (num == 7)
{
cout << "It's a square" << endl;
}
else
cout << "Not a square" << endl;
system("pause");
return 0;
}

NC21613-牛牛的战役

题目链接

https://ac.nowcoder.com/acm/problem/21613

题目描述

牛牛逐渐成长,战斗力也渐渐增加,并可以指挥若干个oier协同作战

给你一个数组a表示我方每个人的战斗力

再给你一个数组b

再给你一个数组c

c[i]表示敌方b[i]战斗力的人有c[i]个

每个oier每次可以选择一名敌方人员进行战斗,如果战斗力大于等于敌方人员,就可以战胜,经验值+1

最开始的时候每个人的经验值都是0

现在牛牛想要打败所有敌方人员,也就是说每个敌方人员都要被一个oier所打败

但是牛牛想要最小化最大的经验值

如果不能打败所有的敌方人员,输出-1

否则输出最小化最大的经验值。

第一行输入一个整数n表示我方人员的数量(1 ≤ n ≤ 50)

第二行输入 n个整数ai表示我方每个人员的战斗力(1 ≤ ai ≤ 10000)

第三行输入一个整数m表示b数组的长度(1 ≤ m ≤ 50)

第四行输入m个整数bi (1 ≤ bi ≤ 10000)

第五行输入m个整数ci (1 ≤ ci ≤ 1014)

测试样例

样例1

输入

1
2
3
4
5
3
2 3 5
3
1 3 4
2 9 4

输出

1
7
样例2

输入

1
2
3
4
5
3
2 3 5
3
1 1 2
2 9 4

输出

1
5
样例3

输入

1
2
3
4
5
3
14 6 22
2
8 33
9 1

输出

1
-1
样例4

输入

1
2
3
4
5
1
1
20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000

输出

1
2000000000000000

解题思路

参考的小毅儿解题思路,这里只是自己总结一下,我们根据样例1不难看出实际上就是尽可能每次都让所有能够比敌人战斗力大的伙伴能够平均收获经验值,如果不能平均收获经验值那么就是在整除的平均值基础上+1,这里主要是要能够找到比敌人战斗力大的我方战斗力最小的伙伴,这样才能够知道这次平均分配经验值要分配给几个人,一开始使用的暴力发现超时,后来发现原来可以用lower_bound返还不小于目标数值的索引值。问题迎刃而解。注意数值范围过大了要使用long long 。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int a[55] = {};

struct enemy
//定义敌人结构体数组
{
//敌人的战斗力
int power;
//power战斗力的人数
long long num;
} b[55];

bool cmp(enemy x, enemy y)
{
//重置比较规则为将敌人按照战斗力从小到大排序
return x.power < y.power;
}

int main()
{
int n, m;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
//将我方按战斗力从小到大排序
sort(a + 1, a + 1 + n);
cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> b[i].power;
}
for (int i = 1; i <= m; i++)
{
cin >> b[i].num;
}
//排序
sort(b + 1, b + 1 + m, cmp);
//敌方人数,我方中比敌方战斗力大的人,平均值
long long sum = 0, s = 0, exper = -1;
if (a[n] < b[m].power)
//我方最强都打不过敌方直接退出
cout << "-1" << endl;
else
{
for (int i = m; i > 0; i--)
{
//每次都加上之前的敌人数量重新算平均经验值
sum += b[i].num;
//lower_bound返还不小于敌方战斗力的我方伙伴
s = n + 1 - (lower_bound(a + 1, a + 1 + n, b[i].power) - a);
//如果刚好平均分配
if (sum % s == 0)
{
//记录平均数大的
exper = max(exper, sum / s);
}
else
{
//如果不能平均分配,那么要+1
exper = max(exper, sum / s + 1);
}
}
cout << exper << endl;
}
system("pause");
return 0;
}

NC50918-递归实现组合型枚举

题目链接

https://ac.nowcoder.com/acm/problem/50918

题目描述

从 1~n 这 n 个整数中随机选出 m 个,输出所有可能的选择方案。

还要注意要求按字典较小的顺序排列所有组合。

测试样例

输入

1
5 3

输出

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

解题思路

dfs深度搜索即可,主要是要注意当x>n时要停止。其实就是按照节点展开,第一行展开的是1->2,1->3,1->4,1->5的所有情况,然后接下来分别将2,3,4,5看成出发起点再次开始搜索,当这一组数值为m时就说明找到了一个组合输出。这样就自动保证了一定是按照字典从小到大的顺序输出组合了。同时要注意这个节点可选可不选,所以递归时有两种情况:

解题代码

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
#include <bits/stdc++.h>
using namespace std;
int n, m, answer[30];

void dfs(int start, int num)
{
if (num == m + 1)
//到达了叶子节点就是一组解输出
{
for (int i = 1; i <= m; i++)
cout << answer[i] << " ";
cout << endl;
return;
}
if (start > n)
//数值超出1~n范围了,退出
return;
//这个值
answer[num] = start;
//以这个节点的下一位为起点开始搜索
dfs(start + 1, num + 1);
//没有选这个节点,继续搜索
dfs(start + 1, num);
}
int main()
{
cin >> n >> m;
//根节点就是从1开始
dfs(1, 1);
system("pause");
return 0;
}

NC21545-牛牛的朋友

题目链接

https://ac.nowcoder.com/acm/problem/21545

题目描述

牛牛有一群牛友,每只小牛都站在坐标轴上的某个位置,这群牛友很听牛牛的话,每当牛牛做个手势,每只小牛都会移动恰好X个单位的距离,要么向左,要么向右,现在告诉你每只小牛在移动前的位置,求移动之后最左边的牛与最右边的牛的最小距离。

第一行输入一个整数n (1 ≤ n ≤ 50),表示牛的数量
第二行输入n个数pi (-1e8 ≤ pi ≤ 1e8),表示每只牛的位置
第三行输入一个整数X (0 ≤ X ≤ 1e8)

测试样例

样例1

输入

1
2
3
3
-3 0 1
3

输出

1
3
样例2

输入

1
2
3
3
4 7 -7
5

输出

1
4
样例3
1
2
3
2
-100000000 100000000
100000000

输出

1
0
样例4

输入

1
2
3
9
3 7 4 6 -10 7 10 9 -5
7

输出

1
7
样例5

输入

1
2
3
4
-4 0 4 0
4

输出

1
4
样例6

输入

1
2
3
1
7
0

输出

1
0

解题思路

我们知道距离肯定是要缩小的,那么起初最左边的牛肯定是要向右走的,最右边的牛肯定是要向左走的。那么接下来我们枚举每一个中间就i的情况,假设向右走,那么在他左边的牛即使也向右走了,也不会比第i头牛的位置更靠右,而对于i+1向左走,那么i+1右边的牛也都向左走即可,因为这样最靠左的位置一定是第i+1头牛的位置。这样我们每次都计算出移动后的距离,选取最小距离的即可。

解题代码

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
#include <bits/stdc++.h>
using namespace std;
int arr[55];

int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
sort(arr + 1, arr + 1 + n); //要将初始位置从左到右排序
int x;
cin >> x;
int cnt = arr[n] - arr[1];
int left, right;
for (int i = 1; i < n; i++)
{
//i右边的所有牛左移,i自身以及i左边的所有牛右移
//那么最左边界值只能在1右移和i作业之间产生
left = min(arr[1] + x, arr[i + 1] - x);
//那么最右边界值只能在1右移和i作业之间产生
right = max(arr[n] - x, arr[i] + x);
if (right - left < cnt)
//如果距离更短,更新
{
cnt = right - left;
}
}
cout << cnt << endl;
system("pause");
return 0;
}

NC16694-一元三次方程求解

题目链接

https://ac.nowcoder.com/acm/problem/16694

题目描述

有形如:ax3+bx2+cx+d=0 这样的一个一元三次方程。给出该方程中各项的系数(a,b,c,d 均为实数),并约定该方程存在三个不同实根(根的范围在-100至100之间),且根与根之差的绝对值 ≥ 1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格),并精确到小数点后2位。
提示:记方程f(x) = 0,若存在2个数x1和x2,且x1 < x2,f(x1)*f(x2) < 0,则在(x1,x2)之间一定有一个根。输入样例为a,b,c,d。

测试样例

输入

1
1 -5 -4 20

输出

1
-2.00 2.00 5.00

解题思路

就是按照题干说的思路,不断二分查找即可。当然貌似本体暴力枚举+0.01也可以过。一定要注意将变量声明为double,否则除出来是整数。

解题代码

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
#include <bits/stdc++.h>
using namespace std;
//找到的零点个数
int num = 0;
double a, b, c, d;
double f(double x)
{
//带入x计算
return a * x * x * x + b * x * x + c * x + d;
}

int main()
{
ios::sync_with_stdio(false), cin.tie(0);
cin >> a >> b >> c >> d;
//逐一尝试
for (double i = -100.00; i < 100.00; i++)
{
//二分法查找i~i+1内是否有0点
if (f(i) * f(i + 1) <= 0)
{
//可能i是0点
if (f(i) == 0)
{
cout << fixed << setprecision(2) << i << " ";
num++;
}
//或者i+1是0点,但是i和i+1不可能都是0点,题干说的
else if (f(i + 1) == 0)
{
//保留两位小数
cout << fixed << setprecision(2) << i + 1 << " ";
i++;
num++;
}
else
{
//或者在i和i+1区间内
double l = i, r = i + 1;
double m = (l + r) / 2;
//不断二分直至题干要求的精度
while (r - l >= 0.01)
{
if (f(l) * f(m) <= 0)
{
r = m;
}
else
{
l = m;
}
m = (l + r) / 2;
}
cout << fixed << setprecision(2) << m << " ";
num++;
}
}
//找到3个了就退出
if (num >= 3)
{
cout << endl;
break;
}
}
system("pause");
return 0;
}

NC21783-牛牛的星际旅行

题目链接

https://ac.nowcoder.com/acm/problem/21783

题目描述

在一个遥远的星球上,每周有N天,牛牛去了这个星球旅游,他恰好只带了N件不同的衣服,编号为1到N。每一天他会穿其中的某一件衣服,一周之内不能穿同一件衣服两次,而且假如某件衣服是在第x天穿的,那么下一次最早能穿这件衣服的时期为x+N-1。现在已知牛牛在这个星球第一周穿衣服的顺序以及最后一周穿衣服的顺序,计算牛牛在这个星球上最少居住了几周。

第一行输入一个整数N
第二行输入N个整数表示第一周穿衣服的排列
第三行输入N个整数表示最后一周穿衣服的排列(保证2 ≤ N ≤ 2500)

测试样例

样例1

输入

1
2
3
4
1 2 3 4
4 3 2 1

输出

1
4
样例2

输入

1
2
3
4
1 2 3 4
1 2 3 4

输出

1
1
样例3

输入

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

输出

1
7

解题思路

过程太复杂,很明显不能逐一分析,我们这里以一件衣服的视角来分析,假设对于一件衣服x他在周5穿过,那么他下一次最早在周4串,如果下一周真的周4穿了,那么下下周就是最早周3穿,所以我们可以推断出如果最后一周x所在的顺序靠后了,那么就不用了关心他了,他可以随时换到后面去,但是如果他在最后一周顺序更靠前了,那么我们需要将它向前移,并且每周只能向前移一天,所以我们就逐一暴力查找后来跑到顺序更靠前的衣服,然后相减求出最少(即每次都往前一天穿)需要多少周,最后找出最大值再加1即可输出。

解题代码

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
#include <bits/stdc++.h>
using namespace std;
#define maxn 3000
int a[maxn], b[maxn], c[maxn];

int main()
{
int n;
cin >> n;
memset(c, 0, sizeof(c));
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
}

for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
//寻找后来跑到前面穿的衣服,后面的不关心
{
if (a[i] == b[j])
{
//对于后来衣服穿在更前面的情况,那么至少需要i-j周才可以到
c[i] = i - j;
break;
}
}
}
int r = -1000000;
for (int i = 1; i <= n; i++)
{
if (c[i] > r)
{
r = c[i];
}
}
//注意要+1
cout << r + 1 << endl;
system("pause");
return 0;
}

NC21796-最长公共包含串

题目链接

https://ac.nowcoder.com/acm/problem/21796

题目描述

给你四个字符串,你需要求出包含这四个字符串作为子串的最短字符串长度,并且字符集为’a’-‘z’每个字符串长度在10以内。

测试样例

样例1

输入

1
2
3
4
abc
ab
bc
b

输出

1
3
样例2

输入

1
2
3
4
a
bc
def
ghij

输出

1
10
样例3

输入

1
2
3
4
thereare
arelotsc
lotsof
ofcases

输出

1
19

解题思路

因为必定4个串,也就是说只能用4!=24中排列情况,我们就暴力枚举每一种情况从最开始的第一个串注意向后拼接,所以只需对比前串的后缀和后串的前缀的公共部分,然后对于公共部分不拼接,只拼接非公共串部分,最后拼接完再统计这个拼接串的长度,最终12个串中取最少的串长度输出。

解题代码

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
//参考了大佬的代码,这里给出几个知识点:
// rfind从字符串a末尾开始寻找包含字符串b的第一个位置,没有就返还::npos
// substr(i,j)截取字符串c的起始位置i到结束位置j的部分子串
#include <bits/stdc++.h>
using namespace std;
string arr[5];
void work(string &a, string b)
{
if (a.find(b) != string::npos)
return; //a中包含b,不用拼接了
for (int i = b.size() - 1; i >= 0; i--)
{
if (a.rfind(b.substr(0, i)) != string::npos && a.rfind(b.substr(0, i)) == a.size() - i) //a的后缀等于b的前缀
{
a += b.substr(i, b.size() - i); //a加上b前缀之外的部分
break;
}
}
}

int main()
{
for (int i = 0; i < 4; i++)
cin >> arr[i];
int r = 60;
//随便设一个必定大于最短公共串长度的数字
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++)
{
for (int k = 0; k < 4; k++)
{
for (int l = 0; l < 4; l++)
{
if (i == j || i == k || i == l || j == k || j == l || k == l)
{
//如果是这种情况,那么没有选出4个不同的直接跳过字符串
continue;
}
//应该一共会有4!个情况
string tmp = arr[i];
//tmp分别和另外三个比较寻找,tmp是最开始的串,其他的拼到后面
work(tmp, arr[j]);
work(tmp, arr[k]);
work(tmp, arr[l]); //暴力,把每种组合都试一遍//题目说了只有4个串,其实也可以写4个循环
r = min(r, (int)tmp.size()); //必须要把长度化为整型
}
}
}
}
cout << r << endl;
system("pause");
return 0;
}

NC16422-图书管理员

题目链接

https://ac.nowcoder.com/acm/problem/16422

题目描述

图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个正整数。 每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。小D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他需要的书,请输出-1。

输入的第一行,包含两个正整数 n 和 q,以一个空格分开,分别代表图书馆里书的数量和读者的数量。
接下来的 n 行,每行包含一个正整数,代表图书馆里某本书的图书编码。
接下来的 q 行,每行包含两个正整数,以一个空格分开,第一个正整数代表图书馆里读者的需求码的长度,第二个正整数代表读者的需求码。保证1≤n ≤1,000,1 ≤ q ≤ 1,000,所有的图书编码和需求码均不超过 10,000,000。

测试样例

输入

1
2
3
4
5
6
7
8
9
10
11
5 5
2123
1123
23
24
24
2 23
3 123
3 124
2 12
2 12

输出

1
2
3
4
5
23
1123
-1
-1
-1

解题思路

因为给出了每一个借阅图书的长度,所以我们将图书馆的所有图书按照长度从短到长排序,然后每次都截取这个图书编号的后n为与长度为n的借阅图书编号对比,相同就输出这个图书编号,如果所有图书都不符合条件,就输出-1。

解题代码

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
#include <bits/stdc++.h>
using namespace std;
string book[1005];

bool cmp(string a, string b)
{
if (a.length() != b.length())
{
//a编号长度比b编号长度短
return a.length() < b.length();
}
//否则按照字典序排序即可
return a < b;
}

int main()
{
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
{
//存储图书馆的图书编号
cin >> book[i];
}
//排序
sort(book + 1, book + 1 + n, cmp);
//检验q组借阅情况
while (q--)
{
int len;
string s;
cin >> len >> s;
//假设没有能借的图书
int flag = 0;
for (int i = 1; i <= n; i++)
{
//一定要注意细节,可能这次的图书编号比借阅图书编号短,那么就跳过检验,否则会越界
if (book[i].length() >= s.length())
{
//裁剪出和借阅图书编号相同长度的图书编号后几位,如果相等
if (book[i].substr(book[i].length() - len) == s)
{
//返还这个书就是最短编号的可借阅图书
cout << book[i] << endl;
flag = 1;
break;
}
}
}
if (!flag)
{
//没找到返还-1
cout << -1 << endl;
}
}
system("pause");
return 0;
}

NC21302-被3整除的子序列

题目链接

https://ac.nowcoder.com/acm/problem/21302

题目描述

给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除
答案对1e9+7取模,保证长度小于50

测试样例

样例1

输入

1
132

输出

1
3
样例2

输入

1
9

输出

1
1
样例3

输入

1
333

输出

1
7
样例4

输入

1
123456

输出

1
23
样例5

输入

1
00

输出

1
3

解题思路

参考了adoptions大佬的思路,这里写出自己的见解以便温习。我们定义如下公式:

那么我们i就会由n个,j只能是0,1,2。我们从i=1开始注意向后加下一个字符打表。那么对于dp[i+1][j]就会由以下三种情况:

  1. dp[i+1][j]肯定包含了dp[i][j],因为前i个字符组成的子序列同时也是前i+1个字符组成的子序列。

  2. 单独检验只取第i+1这一个字符模3的余数是多少,那么就在相对应的位置+1。如果余数为m,那么就是dp[i+1][m]+1。

  3. 前i+1个字符任意组合,那么就有对于dp[i+1][j],我们肯定是必须选择第i+1个数,那么假设第i+1个数模3的余数为m,那么前i个字符组成的子序列模3的余数k必须满足:

    我们可以验证一下,比如7模3的余数为1,10模3余数也为1,那么17模3的余数就是2。这里的7的余数就是m,10的余数就是k,17的余数就是j。

得到上面的公式后,我们就打表打到最后一个字符A,那么输出他的dp[A][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
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int dp[55][3];

int main()
{
string s;
cin >> s;
int len = s.length();
//初始化
memset(dp, 0, sizeof(dp));
//初始化个数
int tmp = 0;
//检验第一个数的余数,在相应的位置+1
dp[0][(s[0] - '0') % 3] = 1;
//检验后面的s-1个数,逐一加上
for (int i = 1; i < len; i++)
{
//存储第i+1个数%3的结果
tmp = (s[i] - '0') % 3;
//只检验第i+1%3的余数并在相应的位置+1
dp[i][tmp] = (dp[i][tmp] + 1) % mod;
for (int j = 0; j < 3; j++)
{
//包含了前i个数组成序列的情况,以及第1+1的余数和前i个数组成序列的和数取余为j的情况个数
dp[i][j] += (dp[i - 1][j] + dp[i - 1][(j + 3 - tmp) % 3]) % mod;
}
}
//打印答案,因为从0开始,所以到i-1
cout << dp[len - 1][0] % mod << endl;
system("pause");
return 0;
}

NC16600-接水问题

题目链接

https://ac.nowcoder.com/acm/problem/16600

题目描述

学校里有一个水房,水房里一共装有m个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为1。

现在有n名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号,i号同学的接水量为wi。接水开始时,1到m号同学各占一个水龙头,并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj 后,下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即j同学第x秒结束时完成接水, 则k同学第x+1秒立刻开始接水。 若当前接水人数n不足m,则只有n个龙头供水,其它m−n个龙头关闭。

现在给出n名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。整数n和m,用一个空格隔开,分别表示接水人数和龙头个数。第2行n个整数w1、w2、……、wn,每两个整数之间用一个空格隔开,wi表示i号同学的接水量。请给出接水所需要的的总时间。1<=n<=10000,1<=m<=100并且m<=n,1<=wi<=100。

测试样例

样例1

输入

1
2
5 3 
4 4 1 2 1

输出

1
4

说明

1
2
3
4
5
1 秒,3 人接水。第 1秒结束时,123 号同学每人的已接水量为 13 号同学接完水,4 号同学接替 3 号同学开始接水。
2 秒,3 人接水。第 2 秒结束时,12 号同学每人的已接水量为 24 号同学的已接水量为 1
3 秒,3 人接水。第 3 秒结束时,12 号同学每人的已接水量为 34 号同学的已接水量为 24号同学接完水,5 号同学接替 4 号同学开始接水。
4 秒,3 人接水。第 4 秒结束时,12 号同学每人的已接水量为 45 号同学的已接水量为 1125 号同学接完水,即所有人完成接水。
总接水时间为4 秒。
样例2

输入

1
2
8 4 
23 71 87 32 70 93 80 76

输出

1
163

解题思路

就是正常的模拟,那么对于学生i,他要去接水的水龙头肯定是对于他的视角来说最早时间结束的,那么这个水龙头就要给学生i接水,相应的,他工作的时间就要+wi,所以我们枚举每一个学生i要去的最早结束的水龙头加上这个学生的用水时间w[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
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

const int N = 10005;
const int M = 105;

int a[M] = {}; //存储水龙头结束时间
int w[N] = {}; //存储每一个学生用水时间

int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
cin >> w[i];
}
for (int i = 1; i <= n; i++)
{
//将每一个学生都分给当下最早结束(即a[i]最小)的水龙头
int idx = 1; //一定要注意是1
for (int j = 1; j <= m; j++)
{
if (a[j] < a[idx])
idx = j;
}
a[idx] += w[i];
}
//遍历所有水龙头
int ans = 0;
for (int i = 1; i <= m; i++)
{
//寻找最晚结束的时间
ans = max(ans, a[i]);
}
cout << ans << endl;
system("pause");
return 0;
}

NC19909-涂色PAINT

题目链接

https://ac.nowcoder.com/acm/problem/19909

题目描述

假设你有一条长度为5的木版,初始时没有涂过任何颜色。你希望把它的5个单位长度分别涂上红、绿、蓝、绿、红色,用一个长度为5的字符串表示这个目标:RGBGR。 每次你可以把一段连续的木版涂成一个给定的颜色,后涂的颜色覆盖先涂的颜色。

例如第一次把木版涂成RRRRR,第二次涂成RGGGR,第三次涂成RGBGR,达到目标。 用尽量少的涂色次数达到目标。

输入仅一行,包含一个长度为n的字符串,即涂色目标。
字符串中的每个字符都是一个大写字母,不同的字母代表不同颜色,相同的字母代表相同颜色。

输出一个数表示需要的最少涂色次数。

测试样例

样例1

输入

1
AAAAA

输出

1
1
样例2

输入

1
RGBGR

输出

1
3

解题思路

区间dp,我们规定dp[l][r]表示为从左端点l涂色到右端点r的最少次数。那么就有以下规律:

  • 如果l==r,即就一个字符,那么就涂色一次即可

  • 如果l!=r,则l一定在r的左边

    1. 如果s[l]==s[r]即这个区间的字符串左端点颜色和右端点颜色相同,那么若要产生最少涂色次数,肯定是一次将左端点和右端点都涂色了,所以可以看成是给[l+1,r]区间涂色时顺带涂上了l,或者[l,r+1]区间涂色时顺带涂上了r,所以取这两个的最小值即可。公式为

    2. 如果s[l]!=s[r],那么不可能一次将l,r全部涂色,肯定存在了一个后来被覆盖掉了的中间过渡节点k,填涂时是涂色[l,k]和[k+1,r]形成的,所以是两者之和,又因为k是l,r之间的节点,所以枚举k的情况,公式为

解题代码

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
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e3 + 7; //最大值
const int INF = 0x3f3f3f3f; //无穷大
int dp[MAXN][MAXN]; //从做端点到右端点区间部分填涂的最少次数

int main()
{
string s; //存入字符串
cin >> s;
int len = s.length(); //字符串长度
s = ' ' + s; //将字符串预处理前面加一个字符,这样l从1开始更舒服
memset(dp, INF, sizeof(dp)); //将所有区间的填涂次数初始化为无穷大
for (int length = 1; length <= len; length++) //枚举区间长度从1开始到len
{
for (int l = 1; l + length - 1 <= len; l++) //枚举左端点的开始处
{
//右端点就是左端点+长度-1
int r = l + length - 1;
//如果左右端点恰巧相同,那么就是一个字符,填涂一次即可
if (length == 1)
dp[l][r] = 1;
else
{
//如果左端点,右端点颜色相同
if (s[l] == s[r])
//那么填涂次数就等于dp[l+1][r]与dp[l][r-1]的最小者
dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]);
else
{
//否则必定逐渐还有一个过渡的填色点且他后来要被覆盖所以必定在l,r之间,枚举尝试
for (int k = 1; k < r; k++)
{
dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
}
}
}
}
}
cout << dp[1][len] << endl;
system("pause");
return 0;
}

NC21800-最佳射击

题目链接

https://ac.nowcoder.com/acm/problem/21800

题目描述

平面直角坐标系上有一些点,你可以进行0或者若干次操作
每次操作可以将所有的点往某个方向平移也可以将所有的点绕着(0,0)旋转任意角度你射击一枪能够射到x轴与y轴上的所有点,你希望经过若干次操作后,射击一枪能击中尽可能多的点,求最多可以击中几个点。

第一行输入一个整数n (1 ≤ n ≤ 50)
第二行输入n个整数表示x坐标
第三行输入n个整数表示y坐标
(坐标的范围在[-1000000,1000000]之间)

测试样例

样例1

输入

1
2
3
2
0 5
0 5

输出

1
2
样例2

输入

1
2
3
5
0 -1 1 1 -1
0 -1 -1 1 1

输出

1
5
样例3

输入

1
2
3
9
0 -3 3 3 -3 0 0 3 -3
0 -3 -3 3 3 3 -3 0 0

输出

1
5

解题思路

我们任取两个点组成x轴,在取一个点向x轴做垂线形成y轴,然后对于所有剩余的点暴力枚举是否在x轴或者y轴的延长线上。如果在,那么这个点就可以被射中,最后输出最好情况即可。细节1在于做x,y轴的三个点必须是不同的点,且检验的其余点也必须和着三个点不同,细节2发现当点的个数不多于3个时,那么必定可以一次射中这三个点,直接输出n值即可。检验被检验点是否在x轴的延长线上很简单,使用x轴的两个组成点和被检验点组成两个斜率即可进行检验,若相同,就在x轴延长线上,但是检验是否在y轴延长线上时,因为只有一个已知组成点,垂足坐标(或者x,y轴相较的原点)我们不知道也不好求,我们可以让被检验点和y轴上的已知点形成向量1,x轴的两个组成点形成向量2,如果向量1和向量2满足x1x2+y1y2=0也可以证明被检验点在y轴延长线上。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int num = 0; //答案初始化
int x[55], y[55]; //x,y坐标存储

int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> x[i];
}
for (int i = 1; i <= n; i++)
{
cin >> y[i];
}
if (n <= 3)
{
//点数少于三个必定可以全部射中,即两个点做x轴,第三个点引垂线做y轴即可
cout << n << endl;
system("pause");
return 0;
}
//点数多于3个
for (int i = 1; i <= n; i++)
{
//先选一个点i
for (int j = 1; j <= n; j++)
{
//和j不同的点i,ij组成x轴
if (i == j)
continue;
for (int k = 1; k <= n; k++)
{
//k不同于i,j,引垂线垂直于ij作为y轴
if (k == i || k == j)
continue;
int ans = 3;
for (int f = 1; f <= n; f++)
{
//检验剩余的f点,肯定是不同于i,j,k
if (f == i || f == j || f == k)
continue;
//在y轴延长线上,使用向量检查
int vec1_x = x[i] - x[j]; //向量1(ij向量)X
int vec1_y = y[i] - y[j]; //向量1Y
int vec2_x = x[k] - x[f]; //向量2(kf向量)X
int vec2_y = y[k] - y[f]; //向量2Y
//向量检验:X,Y向量满足x1x2+y1y2=0即证明在
if (vec1_x * vec2_x + vec1_y * vec2_y == 0)
//f添加
ans++;
//或者f与组成的x轴共线,使用斜率检验
else if ((x[i] - x[f]) * (y[f] - y[j]) == (x[f] - x[j]) * (y[i] - y[f]))
ans++;
}
num = max(num, ans);
}
}
}
cout << num << endl;
system("pause");
return 0;
}

NC16639-奖学金

题目链接

https://ac.nowcoder.com/acm/problem/16639

题目描述

某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学 排在前面,这样,每个学生的排序是唯一确定的。
任务:先根据输入的3门课的成绩计算总分,然后按上述规则排序,最后按排名顺序输出前五名名学生的学号和总分。注意,在前5名同学中,每个人的奖学金都不相同,因此,你必须严格按上述规则排序。例如,在某个正确答案中,如果前两行的输出数据(每行输出两个数:学号、总分) 是:
7 279
5 279
这两行数据的含义是:总分最高的两个同学的学号依次是7号、5号。这两名同学的总分都是 279 (总分等于输入的语文、数学、英语三科成绩之和) ,但学号为7的学生语文成绩更高一些。如果你的前两名的输出数据是:
5 279
7 279
则按输出错误处理,不能得分。

第1行为一个正整数n,表示该校参加评选的学生人数。
第2到n+1行,每行有3个用空格隔开的数字,每个数字都在O到100之间z第1行的3个数 字依次表示学号为j-1的学生的语文、数学、英语的成绩。每个学生的学号按照输入顺序编号为l~n (恰好是输入数据的行号减1)。
所给的数据都是正确的,不必检验。保证6<=n<=300。

测试样例

样例1

输入

1
2
3
4
5
6
7
6 
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

输出

1
2
3
4
5
6 265
4 264
3 258
2 244
1 237
样例2

输入

1
2
3
4
5
6
7
8
9
8 
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

输出

1
2
3
4
5
6
7
8
9
8 
80 89 89
88 98 78
90 67 80
87 66 91
78 89 91
88 99 77
67 89 64
78 89 98

解题思路

主要就是要声明一个学生结构体即可,然后重置一下sort()比较规则。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

struct Student
{
int Ch;
int Math;
int Eng;
int sum;
int id;
} s[305];

bool cmp(Student a, Student b)
{
if (a.sum != b.sum)
{
return a.sum > b.sum;
}
else
{
if (a.Ch != b.Ch)
{
return a.Ch > b.Ch;
}
else
{
return a.id < b.id;
}
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> s[i].Ch >> s[i].Math >> s[i].Eng;
s[i].id = i;
s[i].sum = s[i].Ch + s[i].Math + s[i].Eng;
}
sort(s + 1, s + n + 1, cmp);
for (int i = 1; i <= 5; i++)
{
cout << s[i].id << " " << s[i].sum << endl;
}
system("pause");
return 0;
}

NC109-岛屿数量

题目链接

https://www.nowcoder.com/questionTerminal/0c9664d1554e466aa107d899418e814e

题目描述

给一个01矩阵,1代表是陆地,0代表海洋, 如果两个1相邻,那么这两个1属于同一个岛。我们只考虑上下左右为相邻。岛屿: 相邻陆地可以组成一个岛屿(相邻:上下左右) 判断岛屿个数。

测试样例

输入

1
[[1,1,0,0,0],[0,1,0,1,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,1,1,1]]

输出

1
3

解题思路

dfs,从为1大陆块为起点,一直沿着1走,顺便把走过的标记为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
class Solution
{
public:
/**
* 判断岛屿数量
* @param grid char字符型vector<vector<>>
* @return int整型
*/
int m, n;
//地图
int Map[205][205];
//四个方向向量
int dir[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
void dfs(int x, int y)
{
//越界了就停止
if (x < 0 || x >= m || y < 0 || y >= n || Map[x][y] == 0)
{
return;
}
//走过的大陆标记为0,防止再次走过
if (Map[x][y] == 1)
Map[x][y] = 0;
//四个方向均再次尝试
for (int i = 0; i < 4; i++)
{
dfs(x + dir[i][0], y + dir[i][1]);
}
}
int solve(vector<vector<char>> &grid)
{
//m行n列
m=grid.size();
n = grid[0].size();
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
//因为给的是字符,所以要转换成整型
Map[i][j] = grid[i][j]-'0';
}
}
// for(int i=0;i<m;++i){
// for(int j=0;j<n;++j)
// cout<<Map[i][j];
// cout<<endl;
// }
//岛屿数量初始化为0
int num=0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
//当时大陆时,可以作为起点
if (Map[i][j] == 1)
{
//必定走完一个道岛
dfs(i, j);
//增加岛的数量
num++;
}
}
}
return num;
}
};

NC20035-打鼹鼠

题目链接

https://ac.nowcoder.com/acm/problem/20035

题目描述

鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏:在一个n*n的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。 你可以控制一个机器人来打鼹鼠,如果i时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的话,那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。 机器人的移动是指从当前所处的网格移向相邻的网格,即从坐标为(i,j)的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格,机器人不能走出整个n*n的网格。游戏开始时,你可以自由选定机器人的初始位置。 现在你知道在一段时间内,鼹鼠出现的时间和地点,希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。

第一行为n(n ≤ 1000), m(m ≤ 10000),其中m表示在这一段时间内出现的鼹鼠的个数,
接下来的m行每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻,在第x行第y个网格里出现了一只鼹鼠。
Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠,但同一时刻同一地点只可能出现一只鼹鼠。

测试样例

输入

1
2
3
2 2
1 1 1
2 2 2

输出

1
1

解题思路

这道题一开始想使用bfs来做,但是超时严重,并且难以存储,后来查看题解后才知道是使用dp来做,因为时间给的是默认递增排序。我们声明dp[i]表示为在抓到第i只小鼠时最多之前能抓到多少只小鼠。所以

dp[j]是上一只抓到的小鼠。所以一开始就将所有的dp[i]初始化为1即都原地守株待兔必定可以抓到一只。又因为此题涉及到了能否到达的问题,所以需要满足曼哈顿距离小于等于时间差才可以。

解题代码

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
#include <bits/stdc++.h>
using namespace std;
int dp[10005], n, m, _time[10005], _x[10005], _y[10005], ans; //dp[i]表示到第i只时能打多少只
int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
cin >> _time[i] >> _x[i] >> _y[i];
}
for (int i = 1; i <= m; i++)
{
dp[i] = 1;
}
for (int i = 1; i <= m; i++)
{
for (int j = 1; j < i; j++)
{
//如果曼哈顿距离小于时间差
if (abs(_x[i] - _x[j]) + abs(_y[i] - _y[j]) <= abs(_time[i] - _time[j]))
{
//那么可以抓到这只小鼠,比较dp[i]和通过dp[j]+1得到的哪个方法更好
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
for (int i = 1; i <= m; i++)
{
ans = max(ans, dp[i]);
}
cout << ans << endl;
system("pause");
return 0;
}

NC21669-牛牛与牛妹

题目链接

https://ac.nowcoder.com/acm/problem/21669

题目描述

给你一个网格,有些点被#覆盖了不能再走,其他点是空地,现在牛牛和牛妹轮流开始将空地变成#。 如果当前轮到的人操作之后左上角到右下角不存在通路了,当前操作的人就输了通路只能是从左上角到右下角往右或者往下走的路径牛牛先开始操作,如果双方都是绝顶聪明,输出最后谁赢保证一开始给你的网格是存在一条左上角到右下角的通路的,当然,左上角与右下角都是空地。

第一行输入两个整数n,m(2≤ n,m ≤ 20),接下来n行每行输入m个字符用来描述网格。

测试样例

样例1

输入

1
2
3
2 2
..
..

输出

1
niuniu
样例2

输入

1
2
3
4
5
4 3
...
.#.
.#.
...

输出

1
niumei
样例3

输入

1
2
3
4
3 3
.##
..#
#..

输出

1
niumei
样例4

输入

1
2
3
4
5
4 4
....
...#
#...
....

输出

1
niuniu

解题思路

因为两个牛都很聪明,不会提前自杀式下棋。那么我们假设有一条通路,那么这个通路很显然长n+m,那么两个聪明的牛都不会提前在这个通路上下棋,除非他只能迫不得已下在这里,那么他就输家。又因为牛牛先下,所以如果剩下的.个数是奇数,那么最终一定是牛牛迫不得已下棋下在通路上,即输家。否则是牛妹。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int main()
{
int n, m;
cin >> n >> m;
char s;
int num = 0;
for (int i = 0; i < n*m; i++)
{
cin >> s;
if (s == '.')
{
num++;
}
}
int cnt = num - n - m + 1;
if (cnt % 2 == 1)
cout << "niuniu" << endl;
else
cout << "niumei" << endl;
system("pause");
return 0;
}

NC21653-巨型迷宫

题目链接

https://ac.nowcoder.com/acm/problem/21653

题目描述

一个n行数字迷宫,每行都有无穷多个数,问你从起点走到终点经过的数字和的最小值,包括起点终点上面的数字。每一次可以走上下左右相邻的任意一个格子。这个数字迷宫比较特殊,每一列都是一模一样的。现在给你一个数组a,a[i] 表示第i行的数字是什么,再给你sx,sy, ex,sy分别表示起点与终点。

第一行输入一个整数n,sx,sy,ex,ey表示行数与起点终点

第二行输入n个数表示每一行的数字。1<=n<=50, 1<=a[i]<=10000<=sx,ex<=n-1, 0<=sy,ey<=109。

测试样例

样例1

输入

1
2
3 2 0 2 2
5 3 10

输出

1
29
样例2

输入

1
2
3 0 2 0 0
5 3 10

输出

1
15
样例3

输入

1
2
1 0 0 0 0
1

输出

1
1

解题思路

因为行数很少,所以直接暴力枚举就可以,主要就是模拟中有一点小细节即节点个数不要算多或算少即可。我们暴力枚举的思路是,每次必须经过第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
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define LL long long
#define INF 99999999999999

using namespace std;
const int N = 1e5 + 7;

int f(int a[], int i, int j)
{
LL sum = 0;
//必须是从最小行到最大行,所以比较起点和终点x
int begin = min(i, j); //起点行数
int end = max(i, j); //终点行数
while (begin <= end)
{
sum += a[begin]; //求解跨行的值之和
begin++;
}
return sum;
}
int main()
{
int a[N], sx, sy, ex, ey, n;
cin >> n;
cin >> sx >> sy >> ex >> ey;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
LL y = abs(ey - sy) + 1; //跨的行数,细节:取绝对值后必须加1
LL ans = INF; //一开始初始化ans为最大值无穷
for (int i = 0; i < n; i++) //遍历所有行,算的时候必须经过这个行
{
LL sum = y * a[i]; //横向相加
sum += f(a, i, sx); //以sx为起点,竖向相加
sum -= a[i]; //去掉当前行的值,因为上面已经加过了
sum += f(a, i, ex); //ex为起点,竖向相加
sum -= a[i]; //去掉当前行的值,因为上面已经加过了(最终以sx,ex为两端点,呈U型走向)
ans = min(ans, sum); //更新最小值
}
cout << ans << endl;
return 0;
}

NC22169-回文对称数

题目链接

https://ac.nowcoder.com/acm/problem/22169

题目描述

今天牛牛学到了回文串,他想在数字里面找回文,即回文数,回文数是正着读与倒着读都一样的数,比如1221,343是回文数,433不是回文数。请输出不超过n的回文数。输入就是给出一个n,检验1~n中的回文对称数。

测试样例

输入

1
10

输出

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

解题思路

对于3435,我们逐位取余10,然后再乘10,这样就得到了另一个数5343,如果这个新的数和之前的数一样,那么就是回文对称数。说白了就是用之前数的数尾作为数首,数首作为数尾,如果倒戈以后还是一样的数就是回文对称数,比如52125,那么结果就是52125。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int main()
{
int n, tmp, num;
cin >> n;
for (int i = 1; i <= n; i++)
{
tmp = 0;
num = i;
//将tmp按照数i的从后到前写一遍
while (num != 0)
{
tmp *= 10;
tmp += num % 10;
num /= 10;
}
//如果一样,那么就是回文数
if (tmp == i)
{
cout << i << endl;
}
}
return 0;
system("pause");
return 0;
}

NC21579-牛牛学括号

题目链接

https://ac.nowcoder.com/acm/problem/21579

题目描述

牛牛最近在学习括号匹配问题给你一个合法的括号序列,每次操作分两步,第一步删除第一个左括号,第二步删除某一个右括号,要保证删除之后的括号序列还是合法的,求将括号删到空为止一共有多少种不同的删除方法,两种方法不同当且仅当存在某一步右括号的删除位置不同,答案膜1e9+7。

测试样例

样例1

输入

1
()()()()()

输出

1
1
样例2

输入

1
(((())))

输出

1
24
样例3

输入

1
((()))(()(()))((()))

输出

1
432

解题思路

因为是合法的序列,所以第一个一定是左括号,对于后面我们定义如下规则,如果是左括号就放到栈中,如果是右括号就可以和此时栈中的任意一个左括号相抵消,所以可以任选一个左括号,所以定义sum初始化为1,每次遇到右括号sum就乘以此时栈中左括号的数量即栈的大小,最后不要忘记pop一个左括号,因为右括号抵消了一个左括号所以左括号数量要减少一个。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int main()
{
//以字符串形式存入
char s[2505];
//结果初始化为1
int sum = 1;
cin >> s;
//声明一个栈p
stack<char> p;
//先放入一个左括号
p.push(s[0]);
//剩下的位置进行检验
for (int i = 1; i < strlen(s); i++)
{
//如果是左括号就加入栈中
if (s[i] == '(')
{
p.push(s[i]);
}
else
{
//如果是右括号,那么他可以与栈中的任意一个左括号相抵消,所以可选择的方法数就是此时栈中左括号的数量
sum = (sum * p.size()) % mod;
//因为抵消了一个左括号,所以栈中弹出一个左括号,数量减一
p.pop();
}
}
cout << sum << endl;
system("pause");
return 0;
}

NC16429-组合数问题

题目链接

https://ac.nowcoder.com/acm/problem/16429

题目描述

组合数表示的是从 n 个物品中选出 m 个物品的方案数。举个例子,从 (1, 2, 3) 三个物品中选择两个物品可以有 (1, 2),(1, 3),(2, 3) 这三种选择方法。
根据组合数的定义,我们可以给出计算组合数的一般公式:

小葱想知道如果给定 n,m 和 k,对于所有的 0 ≤ i ≤ n, 0 ≤ j ≤ min(i,m) 有多少对 (i, j) 满足Cij是 k 的倍数。第一行有两个整数 t,k,其中 t 代表该测试点总共有多少组测试数据,k 的意义见 「题目描述」。接下来 t 行每行两个整数 n,m,其中 n,m 的意义见「题目描述」。输出是k行,每一行对应着不同的情况中k的倍数的个数。

测试样例

样例1

输入

1
2
1 2
3 3

输出

1
1
样例2

输入

1
2
3
2 5
4 5
6 7

输出

1
2
0
7

解题思路

首先我们使用打表分别计算每一个Cij的情况是否能够整除k,使用如下递推式:

然后使用S[i][j]来表示统计的i,j情况下的所有整除k的个数。我们也可以通过上面的递推式来统计。一定要注意Cij是为了计算对于i=i,j=j时是否整除k,而Sij是为了统计i<=i,j<=j的所有情况中整除k的个数。最终给出任意的n,m我们直接查表即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

const int N = 2010;
//c[i][j]表示的是Cij取余K的余数
int c[N][N];
//s[i][j]表示的是Cij中是k整数倍的个数
int s[N][N];

int main()
{
int t, k;
cin >> t >> k;
//对每种情况的c[i][j]进行预处理检验其模k的余数
for (int i = 0; i < N; i++)
{
for (int j = 0; j <= i; j++)
{
//如果j是0,那么c[i][j]一定是1
if (!j)
c[i][j] = 1 % k;
else
{
//否则按照递推式由前两项的和推得的结果c[i][j]模k记录余数
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
}
//如果刚好c[i][j]是0,那么也就是说此时的Cij情况是k的整数倍
if (!c[i][j])
//那么就增加一种整除k的情况
s[i][j] = 1;
}
}
//整理对于不同的i,j能够整除k的情况个数
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (i)
s[i][j] += s[i - 1][j];
if (j)
s[i][j] += s[i][j - 1];
//这里要注意如果i,j都是非零,那么前面的两次累加,多加了一次s[i-1][j-1],要减去一次
if (i && j)
s[i][j] -= s[i - 1][j - 1];
}
}
while (t--)
{
int n, m;
cin >> n >> m;
//直接输出事先打表出的不同i,j对应的整除k的情况数量即可
cout << s[n][m] << endl;
}
system("pause");
return 0;
}

NC16596-计算系数

题目链接

https://ac.nowcoder.com/acm/problem/16596

题目描述

给定一个多项式(ax+by)\^k,请求出多项式展开后x\^ny^m项的系数。共一行,包含5个整数,分别为a,b,k,n,m,每两个整数之间用一个空格隔开。这个系数可能很大,输出对10007取模后的结果。

测试样例

输入

1
1 1 3 1 2

输出

1
3

解题思路

我们首先需要知道二项式定理,可知系数的计算公式为:

所以接下来我们只要计算这个式即可了,并且还要模10007,因为系数会很大。a\^n和b\^m我们都使用快速幂的方法计算然后模10007,而对于Ckn我们计算完以后在取模10007不现实,因为会很大已经超过了long long int的范围,只能对于每一次的中间结果取模,又因为是相除的形式,不能直接分子分母分别取模再相除,需要对于其进行逆元变形。具体的细节如下:

问题一:快速幂的计算原理

我们假设计算2^5,那么我们常规思路是计算5次2累成即可,但是这太复杂,因此就有了快速幂,使用二进制位权的计算方法:

次数5在计算机中默认就是使用的二进制数101表示的,所以我们只需每一次都取次数的最低位,如果是0就跳过累成,如果是1,那么就累乘位权代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int qmi(int a, int k)
{
a %= mod;
//ans是结果值
int ans = 1;
//采用的是二进制的计算方法
while (k)
{
//这里k在机器中是二进制表示,与1相与,只有k的最后一位是1才能使得if条件成立
if (k & 1)
//此时ans就乘以一个基数a
ans = ans * a % mod;
//每一次a都要扩大一倍表示下一位的位权
a = a * a % mod;
//k右移一位取最低位
k >>= 1;
}
return ans;
}

其中我们可以通过k&1检验k的最低位是否为1。并且每一次基数a都要扩大一倍来表示下一位的位权,而k每一次也要右移一位。

问题二:为什么要引入逆元?

我们知道对于加减乘除都是可以使用这个取模的定理的:

可以自己验证,但是唯独除法是不允许这样使用的,因为结果会错误,比如

所以我们需要进行一定的转换才可以进行上面分子分母取模再相除。我们先来学习一下逆元,假如(b*c)%k==1,那么c就是b的逆元。所以我们转换一下

并且我们根据费马小定理可以知道对于k如果是质数,且a是正整数,那么a的逆元就是a\^(k-2)。所以上式中的c就可以根据已知b求解出来是b^(k-2)。

问题三:求解Ckn取模10007的值

我们根据公式可以知道

我们转换一下上式,将n!每一项转化为逆元:

也就是

所以刚好需要for循环n次即可,所以计算代码如下:

1
2
3
4
5
6
7
8
for (int i = 1, j = k; i <= n; i++, j--)
//一共分子和分母只需要计算n次
{
//这里用来计算Ckn
ans = ans * j % mod;
//这里是求n!的逆元,以便能够取模
ans = ans * qmi(i, mod - 2) % mod;
}

这样我们就可以计算出答案了。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

//好巧,mod还真是素数,可以使用费马定理
#define mod 10007

//快速幂计算a^k
int qmi(int a, int k)
{
a %= mod;
//ans是结果值
int ans = 1;
//采用的是二进制的计算方法
while (k)
{
//这里k在机器中是二进制表示,与1相与,只有k的最后一位是1才能使得if条件成立
if (k & 1)
//此时ans就乘以一个基数a
ans = ans * a % mod;
//每一次a都要扩大一倍表示下一位的位权
a = a * a % mod;
//k右移一位取最低位
k >>= 1;
}
return ans;
}

int main()
{
int a, b, k, n, m;
cin >> a >> b >> k >> n >> m;
//快速幂计算a^n和b^m
int ans = qmi(a, n) * qmi(b, m) % mod;
for (int i = 1, j = k; i <= n; i++, j--)
//一共分子和分母只需要计算n次
{
//这里用来计算Ckn
ans = ans * j % mod;
//这里是求n!的逆元,以便能够取模
ans = ans * qmi(i, mod - 2) % mod;
}
cout << ans << endl;
system("pause");
return 0;
}

NC16642-Hanoi双塔问题

题目链接

https://ac.nowcoder.com/acm/problem/16642

题目描述

给定A、B、C三根足够长的细柱,在A柱上放有2n个中间有孔的圆盘,共有n个不同的尺寸,每个尺寸都有两个相同的圆盘,注意这两个圆盘是不加区分的(下图为n=3的情形)。现要将这些圆盘移到C柱上,在移动过程中可放在B柱上暂存。要求:
(1)每次只能移动一个圆盘;
(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序;

任务:设An为2n个圆盘完成上述任务所需的最少移动次数,对于输入的n,输出An。

输入一个正整数n,表示在A柱上放有2n个圆盘。输出最少的移动次数。

测试样例

样例1

输入

1
1

输出

1
2
样例2

输入

1
2

输出

1
6

解题思路

实际上这就是移到汉诺塔的变式题+大数运算模拟。我们先来讲解一下汉诺塔问题。

汉诺塔问题

假设现在有n个盘子从高到低从小到大排列在A,我们要移动到C,且还有一个辅助柱子B,那么很明显我们只需要先将前n-1个盘子移动到B,再将第n个盘子移动到C,然后再将前n-1个盘子从B移动到C,依次递归,直到只剩下一个盘子时,那么直接将它从A移动到B即可。伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
Function Hanoi(n,a,b,c)
if n==1 then
//如果就一个盘子就直接移动到C即可
print(a+'->'+c)
else
//否则前n-1个先借助C移动到B
Hanoi(n-1,a,c,b)
//第n个盘子移动到C
print(a+'->'+c)
//前n-1个盘子从B移动到C,此时B看成原先的A,A看成原先的辅助柱子
Hanoi(n-1,b,a,c)
end if
end Function

所以我们就得到了如下的递推式:

这就是一个等比数列的递推式我们可以将它转换一下:

所以我们就得到了对于n个盘子时汉诺塔的最少移动次数的规律。点这里看讲解视频

本题推导

那么此题只不过是变成了每一种大小的盘子有两个,所以每次都是移动一对。我们也不难推导出如下规律:

所以可以推出an的等比通项公式是

那么接下来我们就是带入n即可,但是发现n最大是200,而long long int只能表示2^64-1,超范围了,所以我们使用大数模拟,这里套用了大佬的板子,使用的是重载运算符,使用模10来模拟大数高精度运算(也有的板子使用的是字符串)。这样我们就可以输出结果了。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

//大数运算模拟,摘自https://ac.nowcoder.com/acm/contest/profile/827921411大佬
void trunc_zero(vector<int> &num)
{
while (num.empty() == false && num.back() == 0)
{
num.pop_back();
}
}

class Big_uint
{
friend ostream &operator<<(ostream &os, Big_uint const &a);
vector<int> digits;

public:
Big_uint(string const &str)
{
digits.resize(str.size());
auto i = digits.begin();
auto ed = digits.end();
auto j = str.rbegin();
while (i != ed)
{
*i++ = *j++ - '0';
}
}
Big_uint(vector<int> &&n) : digits(n) {}

Big_uint operator*(int const a) const
{
vector<int> num(digits.size() + 10, 0);
size_t i = 0;
for (; i < digits.size(); ++i)
{
num[i] += digits[i] * a;
if (num[i] >= 10)
{
num[i + 1] += num[i] / 10;
num[i] %= 10;
}
}
while (num[i] >= 10)
{
num[i + 1] += num[i] / 10;
num[i] %= 10;
++i;
}
trunc_zero(num);
return {std::move(num)};
}
Big_uint &operator-=(int const a)
{
digits[0] -= a;
size_t i = 0;
while (digits[i] < 0)
{
digits[i] += 10;
--digits[++i];
}
trunc_zero(digits);
return *this;
}
};

ostream &operator<<(ostream &os, Big_uint const &a)
{
if (a.digits.empty())
{
os << '0';
}
else
{
auto i = a.digits.rbegin(), j = a.digits.rend();
while (i != j)
{
os << *i++;
}
}
return os;
}

int main()
{
int n;
cin>>n;
Big_uint ans("2");
//使用前面的递推式an=2^n+1-2,大数模拟运算就是解决n>=64时超过了long long int后计算结果输出的问题
for(int i=0;i<n;i++){
ans=ans*2;
}
ans-=2;
cout<<ans<<endl;
system("pause");
return 0;
}

NC21781-牛兄牛弟

题目链接

https://ac.nowcoder.com/acm/problem/21781

题目描述

一群牛兄牛弟准备去一家餐厅吃饭,已知他们是按照某个顺序先后到达餐厅的,第i个到达餐厅的要求坐在离门口至少a[i]的距离。牛兄牛弟们不准备让别人知道他们是兄弟,虽然他们长得比较像,他们决定任意两个兄弟之间的距离都要大于等于d。餐厅服务员记录下他们的需求之后,开始陆续给到来的牛兄弟们排座位,服务员每次会指定一个满足要求的离门口最近的座位给新到的牛。第一行输入两个整数n,d。第二行输入n个数a[i]。1 ≤ n ≤ 1000, 1 ≤ d,a[i] ≤ 106。输出n个数表示每头牛要做的位置。

测试样例

样例1

输入

1
2
4 10
1 21 11 7

输出

1
1 21 11 31
样例2

输入

1
2
4 11
1 21 11 7

输出

1
1 21 32 43
样例3

输入

1
2
4 1000000
1000000 1000000 1000000 1

输出

1
1000000 2000000 3000000 4000000

解题思路

首先我们要读懂题干,每一个牛都有自己至少要坐的位置,可以大于这个位置,但是不能小于他,同时还要满足和其他的每一个牛兄弟间距至少为d。那么为了保证得到的是最小的位置,我们就有以下两种情况(这里以样例1为例):

第一头牛就坐在题干给出的位置即可所以坐在位置1,而牛2至少要坐在21,同时检验确实和牛1间距大于10,所以21就是牛2能做的最小位置了。而牛3坐在了牛2的内侧11,我们对其位置进行逐一检验,他和牛1牛2确实间距都为10满足条件,所以牛2坐在11即可。然而牛4坐在7明显与牛3间距小于10,那么无论怎么坐,他都不可能坐在牛3内侧了,所以他要坐在牛3外侧11+10=21,发现和牛2冲突,所以还要继续向外走一个d,所以坐在21+10=31处。自此我们总结出来一个规律:

  1. 第一个牛直接坐下就行
  2. 其他的牛如果能够坐在内侧,那么就坐在内侧
  3. 如果不能坐在内侧,那么就只能不断的向外移,移动距离为d
  4. 如果坐在外侧仍然不满足条件,那么继续向外移

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int main()
{
int n, d;
//存入牛数量,和最小距离
cin >> n >> d;
int arr[10000] = {}; //题干的最小距离
int ans[10000] = {}; //答案数组
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
//第一个牛就做到题干给出的位置即可
ans[1] = arr[1];
for (int i = 2; i <= n; i++)
{
//其他的牛先做到题干给出位置
ans[i] = arr[i];
//排序
sort(arr + 1, arr + i);
for (int j = 1; j < i; j++)
{
//如果第i头牛做的位置在j的内侧且不满足条件,那么就只能做到a[j]+d
//同理如果坐到外侧不满足条件,也是做到a[j]+d
if (abs(arr[i] - arr[j]) < d)
{
arr[i] = arr[j] + d;
ans[i] = arr[i];
}
else
//满足条件直接坐下即可
ans[i] = arr[i];
}
}
for (int i = 1; i <= n; i++)
{
cout << ans[i] << " ";
}
cout << endl;
system("pause");
return 0;
}

NC13222-音乐研究

题目链接

https://ac.nowcoder.com/acm/problem/13222

题目描述

美团外卖的品牌代言人袋鼠先生最近正在进行音乐研究。他有两段音频,每段音频是一个表示音高的序列。现在袋鼠先生想要在第二段音频中找出与第一段音频最相近的部分。具体地说,就是在第二段音频中找到一个长度和第一段音频相等且是连续的子序列,使得它们的 difference 最小。两段等长音频的 difference 定义为:difference = SUM(a[i] - b[i])2 (1 ≤ i ≤ n),其中SUM()表示求和 。其中 n 表示序列长度,a[i], b[i]分别表示两段音频的音高。现在袋鼠先生想要知道,difference的最小值是多少?数据保证第一段音频的长度小于等于第二段音频的长度。

第一行一个整数n(1 ≤ n ≤ 1000),表示第一段音频的长度。 第二行n个整数表示第一段音频的音高(0 ≤ 音高 ≤ 1000)。 第三行一个整数m(1 ≤ n ≤ m ≤ 1000),表示第二段音频的长度。 第四行m个整数表示第二段音频的音高(0 ≤ 音高 ≤ 1000)。

测试样例

输入

1
2
3
4
2
1 2
4
3 1 2 4

输出

1
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
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int a[N], b[N];

int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
int m;
cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> b[i];
}
int ans = 1e9;
for (int i = 1; i <= m - n + 1; i++)
{
int sum = 0;
for (int j = i; j <= i + n - 1; j++)
{
sum += (a[j - i + 1] - b[j]) * (a[j - i + 1] - b[j]);
}
ans = min(ans, sum);
}
cout << ans << endl;
system("pause");
return 0;
}

NC13591-主持人的烦恼

题目链接

https://ac.nowcoder.com/acm/problem/13591

题目描述

一天zzq主持一项游戏,共n位同学,需要两两同学为一组来上台来玩一项游戏。但是,众所周知,玩游戏的时候,如果两个人的颜值差距>=m,就会互相嫌弃。 所以,为了游戏能够好玩。在游戏开始前,zzq已经调查了所有n个同学的颜值。但是现在问题又来了,zzq想知道,最多能凑出多少组同学一起上台? 需注意一人只能出现在一个组中。多组输入 第一行两个正整数n m(n<=1e5,m<=1e9),意义见描述 第二行有n个由空格分开的正整xi(xi<=1e9),第i个同学的颜值。我们需要输出一个数表示最多可以组成多少个组合。

测试样例

输入

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

输出

1
2
2
1

说明

1
第二组样例中,编号为1的同学(颜值是1)与编号为4的同学(颜值是2),颜值差距为1,可以组成一组

解题思路

贪心解决,我们将颜值从小到大排序,i和i+1检验能否组成一组,如果可以,那么i+2,即这两个人组成一组,i和i+1就不再参与组合选拔了,此时组数加一。如果i和i+1都不能组成一组,那么i++,即i没有可以组合的伙伴了,不参与选拔了,但是此时i+1还可以尝试选拔。

解题代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int ans = 0;
//存取学生的颜值
int s[N];

int main()
{
int n, m;
while (cin >> n >> m)
{
ans = 0;
//每次都要初始化为全0
memset(s, 0, sizeof(s));
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
//排序
sort(s, s + n);
for (int i = 0; i < n - 1;)
{
//当相邻的两个可以组合(最好情况了)
if (s[i + 1] - s[i] < m)
{
//这两个人不再参与选拔
i += 2;
//组数加一
ans++;
}
else
{
//没有人可以和他组合了,所以跳过他
i++;
}
}
cout << ans << endl;
}
system("pause");
return 0;
}

NC13585-安卓图案解锁

题目链接

https://ac.nowcoder.com/acm/problem/13585

题目描述

栗主席(lizi)是某xxxx大学的一个不得了的程序猿,然而没想到吧,他竟然有女盆友,我们假设为QAQ!!!

那天,QAQ问栗子:你的小米5s的图像解锁密码到底是多少?

栗子:嘛?我仔细想想…

QAQ:你仿佛在逗我…

栗子:我的图像解锁用过好多次密码,后来都是用指纹解锁,所以忘记密码辣。但是我记得可能是那几个密码

QAQ:那你务必告诉我…

栗子: …

然后,栗子就写下了一堆可能的密码,安卓图案解锁中,数字对应的位置已经标出。

但是栗子当然不想把真正的密码告诉QAQ,所以给QAQ的一系列的密码中,甚至有一些密码,是不符合安卓图案解锁的规则的。

QAQ也知道栗子肯定不老实,给了很多错的密码,甚至不符合规则的密码,所以想请你来找出,哪些密码是不符合规则的。

安卓图案解锁的密码有这样的一些特点:

1.每个数字最多只会被使用一次。

2.如果想直接连接两个数字,但是线段中会经过另一个数字,当且仅有那个数字已经在之前就被使用过了,才会合法。(比如你想从1直接连接到9,那么要么是1->3->9,要么是3在之前已经被使用过了,然后才能直接从1->9)。

多组输入,每组输入占一行,包含一串数字(1~9),长度不超过30

输出这个安卓图案解锁是否合法,如果合法输出”YES”,反之输出”NO” (请参照样例输出,不要输出引号)

测试样例

输入

1
2
3
4
14569
1953
15963
15953

输出

1
2
3
4
YES
NO
YES
NO

解题思路

我们需要将不能直接相连点的情况标记出来,如下:

1,3,7,9四个点不能直接相连,2,8不能直接相连,4,6不能直接相连,这三种情况都需要先保证他们的中间均值节点相连,如1和3的均值节点2被使用了,或者2,8均值节点5倍使用了才可以。对这三种不能直接相连点的情况赋予不同的标记权重值1(黄),2(绿),3(蓝)。所以我们需要逐位检验两个相邻的点,如果相等或者其中一个被使用过了,或者这两个点是不能直接相连的但是他们的中间均值点还没有使用过,那么这个密码就是不合法的。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
#include <bits/stdc++.h>
using namespace std;

int main()
{
//标记数组,0表示未使用过,1表示使用过
int vis[9] = {};
//对不同的不能直接相连情况的点赋值不同的权重
int pri[9] = {1, 2, 1, 3, 0, 3, 1, 2, 1};
string s;
while (cin >> s)
{
//默认都可以
bool ok = true;
//一定要初始化标记数组全0
memset(vis, 0, sizeof(vis));
//对每一个点逐一检验
for (int i = 0; i < s.size() - 1; i++)
{
//两个相邻点的值
int a = s[i] - '0';
int b = s[i + 1] - '0';
if (a == b)
{
//相邻两个点相同,如3321
ok = false;
break;
}
if (vis[a - 1] == 1 || vis[b - 1] == 1)
{
//或者当前点被使用过,如1232
ok = false;
break;
}
//标记这个点被使用过了
vis[a - 1] = 1;
//如果两个相邻点是不能直接相连的且他们中间节点还未使用过如139
if (pri[a - 1] == pri[b - 1] && !vis[(a + b) / 2 - 1])
{
//那么不符合题干
ok = false;
break;
}
}
if (ok)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
system("pause");
return 0;
}

NC13592-武藏牌牛奶促销

题目链接

https://ac.nowcoder.com/acm/problem/13592

题目描述

武藏牌牛奶为了吸引顾客,推出优惠活动,可以使用x个空的瓶身,或者y个瓶盖,去商店换一瓶全新的武藏牌牛奶。注意,一瓶牛奶包含了瓶身和瓶盖。 现在小萌老师有a个空的瓶身和b个瓶盖,她想喝到尽可能多的牛奶,你知道她到底能喝到多少瓶完整的牛奶吗?多组输入 每组数据第一行包含4个正整数x y a b(1<=x,y,a,b<=100),意义见题目描述。对于每组数据,输出一行,表示小萌老师最多能喝多少瓶完整的牛奶。如果能喝无数瓶,输出”INF”(不要输出引号)。

测试样例

输入

1
2
1 3 1 1
4 3 6 4

输出

1
2
INF
4

说明

1
对于第二组测试样例,小萌老师有6个空的瓶身和4个瓶盖,她用4个瓶身和3个瓶盖换了2瓶牛奶并喝完,此时她就有4个空的瓶身和3个瓶盖。之后她再换2瓶牛奶并喝完,此时只有2个空的瓶身和2个瓶盖,就无法继续兑换了,所以答案是4

解题思路

对于有限次兑换,很简单,就是用空瓶和瓶盖尽可能多兑换就好了,只要注意每次兑换一瓶奶以后空瓶和瓶盖都会加1即可。难点在于无限次兑换的条件,有两个,一种是x=1或者y=1的情况即可,另一种是x=2&&y=2且a+b>2。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int main()
{
int x, y, a, b;
while (cin >> x >> y >> a >> b)
{
int ans = 0;
if ((x == 1 || y == 1) || ((x == 2 && y == 2) && (a + b >= 2)))
{
cout << "INF" << endl;
continue;
}
else
{
//否则有限次兑换
while (a >= x || b >= y)
{
//用x个瓶子兑换
if (a >= x)
{
int tmp1 = a / x;
a = a % x;
a += tmp1;
b += tmp1;
ans += tmp1;
}
//用y个瓶盖兑换
if (b >= y)
{
int tmp2 = b / y;
b = b % y;
a += tmp2;
b += tmp2;
ans += tmp2;
}
}
cout << ans << endl;
}
}
system("pause");
return 0;
}

NC13253-子串

题目链接

https://ac.nowcoder.com/acm/problem/13253

题目描述

给出一个正整数n,我们把1..n在k进制下的表示连起来记为s(n,k),例如s(16,16)=123456789ABCDEF10, s(5,2)=11011100101。现在对于给定的n和字符串t,我们想知道是否存在一个k(2 ≤ k ≤ 16),使得t是s(n,k)的子串。第一行一个整数n(1 ≤ n ≤ 50,000)。 第二行一个字符串t(长度 ≤ 1,000,000)。”yes”表示存在满足条件的k,否则输出”no”

测试样例

输入

1
2
8
01112

输出

1
yes

解题思路

我们就是暴力枚举对于不同k进制下的1~n的字符串即可,难点在于要自己手写以下进制转换,同时最后要注意字符串是反的,需要手动翻转。最后再用find函数寻找子串即可。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int main()
{
int n;
string t, s, tmp;
cin >> n;
cin >> t;
//逐一尝试1~n的k进制串表示
for (int k = 2; k < 17; k++)
{
//记录1~n的k进制串
s = "";
for (int i = 1; i <= n; i++)
{
//从1~n枚举整数值
int num = i;
//临时存储i的k进制串,最后不断拼接成为1~n的k进制串
tmp = "";
//使用循环取余的方法模拟转换进制
while (num)
{
int cnt = num % k;
if (cnt < 10)
{
tmp += cnt + '0';
}
else
{
//大于9的时候用ABCDE等表示
tmp += 'A' + cnt - 10;
}
num /= k;
}
//最后得到的是反的,要翻转一下字符串
reverse(tmp.begin(), tmp.end());
s += tmp;
}
//find()函数寻找子串在母串中出现的第一次位置,没有则返还-1
if (s.find(t) != -1)
{
cout << "yes" << endl;
system("pause");
return 0;
}
}
cout << "no" << endl;
system("pause");
return 0;
}

蓝桥杯1261-移动距离

题目链接

http://oj.ecustacm.cn/problem.php?id=1261&csrf=bcupvEZe4bjudajPwEvj88NJnrXQ6IWD

题目描述

X星球居民小区的楼房全是一样的,并且按矩阵样式排列。
其楼房的编号为1,2,3… 当排满一行时,从下一行相邻的楼往反方向排号。
比如:当小区排号宽度为6时,开始情形如下:

1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 …..

我们的问题是:已知了两个楼号m和n,需要求出它们之间的最短移动距离。(不能斜线方向移动)。输入存在多组测试数据,输入为3个整数w m n,空格分开,都在1到10000范围内。w为排号宽度,m,n为待计算的楼号。

测试样例

输入

1
2
6 8 2
4 7 20

输出

1
2
4
5

解题思路

实际上就是曼哈顿距离,根据给定的m,n,w两个地点的位置已经确定了,我们只需要能够找到他们的位置并求出曼哈顿距离即可。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int main()
{
int w, m, n;
while (cin >> w >> m >> n)
{
//m必须保证小于n
if (m > n)
{
int tmp = n;
n = m;
m = tmp;
}
//特例
if (m == n)
{
cout << 0 << endl;
return 0;
}
int i = 0;
int j = 0;
int num = 1;
//位置1用(a,b),位置二用(c,d)
int a, b, c, d;
//是否向右填写
bool dirr = true;
while (num <= n)
{
//找到了位置记录下来
if (num == m)
{
a = i;
b = j;
}
if (num == n)
{
c = i;
d = j;
}
num++;
if (dirr)
{
j++;
}
else
{
j--;
}
//切换方向的条件
if (j == w)
{
dirr = false;
i++;
j = w - 1;
}
if (j == -1)
{
j = 0;
dirr = true;
i++;
}
}
//曼哈顿距离计算公式
cout << abs(a - c) + abs(b - d) << endl;
}
// system("pause");
return 0;
}

解题反思

上面的方法太笨了,使用模拟枚举,时间长,这里其实完全可以使用模m商为行数,余数为列数即可迅速锁定两个位置。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bitsdc++.h>
using namespace std;
typedef long long ll;

int getl(int x, int w, int h) {
if (h % 2 != 0) //正向
return (x % w);
return w - (x % w) + 1;
}

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int w, m, n;
while (cin >> w >> m >> n) {
if (m > n) swap(m, n);
int h1 = m / w + (m % w ? 1 : 0), h2 = n / w + (n % w ? 1 : 0);
int l1 = getl(m, w, h1), l2 = getl(n, w, h2);
cout << h2 - h1 + abs(l2 - l1) << endl;
}
// system("pause");
return 0;
}

蓝桥杯1263-打印大X

题目链接

http://oj.ecustacm.cn/problem.php?id=1263&csrf=DeGbAGWXj3yK3LtbE6TRFrSp0zKd37xP

题目描述

小明希望用星号拼凑,打印出一个大X,他要求能够控制笔画的宽度和整个字的高度。
为了便于比对空格,所有的空白位置都以句点符来代替。要求输入两个整数m n,表示笔的宽度,X的高度。输入存在多组数据,每组测试数据输入一行,包含两个整数,用空格分开,(0<m<n, 3<n<1000, 保证n是奇数)。要求输出一个大X。

测试样例

输入

1
2
3 9
4 21

输出

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
***.....***
.***...***.
..***.***..
...*****...
....***....
...*****...
..***.***..
.***...***.
***.....***
****................****
.****..............****.
..****............****..
...****..........****...
....****........****....
.....****......****.....
......****....****......
.......****..****.......
........********........
.........******.........
..........****..........
.........******.........
........********........
.......****..****.......
......****....****......
.....****......****.....
....****........****....
...****..........****...
..****............****..
.****..............****.
****................****

解题思路

我们分两种情况,先打印上半部分,再打印下半部分。这里使用一个小方法简化输出,即先把这一行全部填写成.,然后设置左右*字符串的起始位置,再循环m次替换.为*即可。难点主要是寻找起始位置。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int main()
{
int m, n;
while (cin >> m >> n)
{
//计算一行的字符串长度
int len = m + n - 1;
//左、右端起始位置
int l = 1;
int r = len - m + 1;
char s[len + 5];
//上半部分包括中间行的打印
for (int i = 0; i < (n - 1) / 2 + 1; i++)
{
//初始化全部填写.
memset(s, '.', sizeof(s));
int ll = l;
int rr = r;
//*替换.
for (int i = 0; i < m; i++)
{
s[ll + i] = '*';
s[rr + i] = '*';
}
//输出这一行
for (int i = 1; i <= len; i++)
{
cout << s[i];
}
//下一行左起始位置右移,右起始位置左移
l++;
r--;
//换行输出下一行
cout << endl;
}
// l = (n - 1) / 2;会wa
// r = (len - 1) / 2 + 1;会wa,貌似是起点位置不够具有普遍性
//正确的起始位置,就是相较于刚刚的中间行的左右起始位置分别左移1个和右移1格
l-=2;
r+=2;
//特判,不加貌似也对
if(m==1){
r=(len+1)/2+1;
}
//打印下半部分
for (int i = 0; i < (n - 1) / 2; i++)
{
memset(s, '.', sizeof(s));
int ll = l;
int rr = r;
for (int i = 0; i < m; i++)
{
s[ll + i] = '*';
s[rr + i] = '*';
}
for (int i = 1; i <= len; i++)
{
cout << s[i];
}
l--;
r++;
cout << endl;
}
}
// system("pause");
return 0;
}

NC13228-倒水

题目链接

https://ac.nowcoder.com/acm/problem/13228

题目描述

有一个大水缸,里面水的温度为T单位,体积为C升。另有n杯水(假设每个杯子的容量是无限的),每杯水的温度为t[i]单位,体积为c[i]升。
现在要把大水缸的水倒入n杯水中,使得n杯水的温度相同,请问这可能吗?并求出可行的最高温度,保留4位小数。
注意:一杯温度为t1单位、体积为c1升的水与另一杯温度为t2单位、体积为c2升的水混合后,温度变为(t1*c1+t2*c2)/(c1+c2),体积变为c1+c2。

第一行一个整数n, 1 ≤ n ≤ 10^5
第二行两个整数T,C,其中0 ≤ T ≤ 10^4, 0 ≤ C ≤ 10^9
接下来n行每行两个整数t[i],c[i]
0 ≤ t[i], c[i] ≤ 10^4

如果非法,输出“Impossible”(不带引号)否则第一行输出“Possible”(不带引号),第二行输出一个保留4位小数的实数表示答案。

测试样例

输入

1
2
3
4
5
3
10 2
20 1
25 1
30 1

输出

1
2
Possible
20.0000

说明

1
2
3
往第二杯水中倒0.5升水
往第三杯水中到1升水
三杯水的温度都变成了20

解题思路

用贪心不用二分,我们直接计算大缸里的水和所有杯中的水融合在一起的平均水温,然后就有以下三种情况:

  1. 平均水温小于等于杯中水的最低温度,那么大缸中的水是降温的,那么可以调节并且可调节的最高温度就是杯中水的最低温度
  2. 平均水温大于等于杯中水的最高温度,那么大缸中的水是升温的,那么可以调节并且可调节的最高温度就是平均水温
  3. 平均水温介于最低温度和最高温度之间,说明大缸中的水也是结余最低温度和最高温度之间,那么不可以调节,因为无论如何调节,最低温度只会无限趋近于平均水温而不会等于平均水温,最高温度只会无限趋近于平均水温而不会等于平均水温,因此杯中的水不可能温度相等。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
double t[N], c[N];

int main()
{
double T, C;
int n;
cin >> n;
cin >> T >> C;
double v = 0.0;
v += T * C;
double tmax = 0.0, tmin = 1e9, c1 = C;
for (int i = 1; i <= n; i++)
{
cin >> t[i] >> c[i];
v += t[i] * c[i];
c1 += c[i];
tmax = max(t[i], tmax);
tmin = min(t[i], tmin);
}
//求平均值
double aver = v / c1;
//小于最小温度,那么可以调节的最大温度就是最小值
//大缸中的水是降温的,比杯中最低温的水温度还低
if (aver <= tmin)
{
cout << "Possible" << endl;
//保留小数点4位
cout << fixed << setprecision(4) << tmin << endl;
}
//能够大于那么就输出平均值
//大缸的水是升温的,比杯中最高温度的水温度还高
else if (aver >= tmax)
{
cout << "Possible" << endl;
cout << fixed << setprecision(4) << aver << endl;
}
//否则不可能调节
else
{
//原因很简单对于tmin<aver<tmax
//再怎么加水tmin只会无限趋于aver而不会等于aver
//再怎么加水tmax也只会无限趋近于aver而不会等于aver
cout << "Impossible" << endl;
}
system("pause");
return 0;
}

NC14134-生物课程

题目链接

https://ac.nowcoder.com/acm/problem/14134

题目描述

𝑅𝑒𝑘𝑖是一名武侦高狙击科的学生,武侦高也设有基础学科,现在她正
在完成生物课的作业。
给出一张𝑛个点𝑚条边的无向图,这张无向图描述了一个细胞,细胞有三种:X型、Y型还是I型。如下图:

如图,虚线方向的链可以无限延伸,现在需要判断给定的图是哪一种细胞,或者都不是。

第一行,两个正整数𝑛,𝑚。接下来𝑚行,每行两个正整数𝑢, 𝑣描述一条无向边。输出这种细胞的类型,若都不是输出NotValid。对于100%的数据,2 ≤ 𝑛 ≤ 500,0 ≤ 𝑚 ≤ 𝑛*(𝑛−1)/2,没有重边和自环。

测试样例

样例1

输入

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

输出

1
X
样例2
1
2
3
4
5
6
7
7 6
1 2
1 3
3 4
1 5
5 6
6 7

输出

1
Y
样例3

输入

1
2
2 1
1 2

输出

1
I
样例4

输入

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

输出

1
NotValid

解题思路

我们可以根据上面的题干总结一下各种情况的特点:

  1. X型:点的边数只能为1,2,4并且边数为4的点只能有一个
  2. Y型:点的边数只能为1,2,3并且边数为3的点只能有一个
  3. I型:点的边数只能为1,2

非法情况有:

  1. 有孤立点(坑点)
  2. 有多个X或Y中心点
  3. 中心点边数>4

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int p[505]; //记录各个点的边数

int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
//两个点各加一条边
p[u]++;
p[v]++;
}
//对1到n顶点排序,按照边数从小到大排序
sort(p + 1, p + n + 1);
int min = p[1];
int max = p[n];
//非法的几种情况
//1.有的点无边相连,孤立点,非法
//2.中心点边数大于4
//3.X,Y中心点都有,或者有多个X中心点
//4.有多个Y中心点
if (min == 0 || max > 4 || (max == 4 && p[n - 1] >= 3) || (max == 3 && p[n - 1] >= 3))
{
cout << "NotValid" << endl;
system("pause");
return 0;
}
else
{
//否则就是X,Y,I中的一个
if (max == 4)
cout << "X" << endl;
else if (max == 3)
cout << "Y" << endl;
else
cout << "I" << endl;
}
system("pause");
return 0;
}

NC14370-入学考试

题目链接

https://ac.nowcoder.com/acm/problem/14370

题目描述

马云是个聪明的孩子,他想成为世界上最伟大的医师。所以他想拜附近最有威望的张丹成为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”如果你是马云,你能完成这个任务吗?(注:马云啥的是编的 。。)第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

第一行有两个整数T(1 <= T <= 1000)和M(1 <= M <= 100),用一个空格隔开,T代表总共能够用来采药的时间,M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间(包括1和100)的整数,分别表示采摘某株草药的时间和这株草药的价值。

测试样例

输入

1
2
3
4
70 3
71 100
69 1
1 2

输出

1
3

解题思路

贪心和k-优化算法不好实现,典型的0/1背包动态规划板子题,如果使用二维数组请参考本篇文章《动态规划》,但是这里又学习到了二维到一维数组优化的算法,请参考本篇文章《浅谈用一维数组dp解决0/1背包问题》。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int f[1005], t[1005], v[105];

int T, n, i, j;
int main()
{
cin >> T >> n;
for (i = 1; i <= n; i++)
cin >> t[i] >> v[i];
//f[i]物品1~i范围选取
for (i = 1; i <= n; i++)
//注意,逆序是逆序的即背包容量从大到小,fot已经特判能否装入
for (j = T; j >= t[i]; j--)
//右边的都是第i-1次循环的结果
f[j] = max(f[j], f[j - t[i]] + v[i]);
cout << f[T] << endl;
system("pause");
return 0;
}

NC14381-蝴蝶

题目链接

https://ac.nowcoder.com/acm/contest/profile/126727419/practice-coding

题目描述

给定一个 n*m 的矩阵,矩阵元素由X和O构成,请求出其中最大的蝴蝶形状。
蝴蝶形状的定义如下:
存在一个中心点(必须为X),并且其往左上(必须为X)、左下(必须为X)、右上(必须为O)、右下(必须为O)四个方向扩展相同的长度,且左上顶点与左下顶点之间全由X填充,右上顶点与右下顶点之间全由O填充。我们不在意在蝴蝶形状内部是X还是O。例如:

是一个蝴蝶形状(其中A表示X或O)。并且X是大小为1的蝴蝶。而、

不是(不存在中心点)。

第一行两个整数n, m表示矩阵的大小 (1 <= n, m <= 500),接下来 n 行,每行一个长度为 m 的字符串表示矩阵,矩阵元素保证由X和O构成。一行一个整数表示最大的蝴蝶形状的对角线的长度。

测试样例

输入

1
2
3
4
5
6
5 5
XOOOO
XXOOO
XOXOO
XXOOO
XOOOO

输出

1
5

解题思路

该死,这题一开始读错题意了。一定要注意他要求的是顶点之间的字符必须相同,即如样例1的蝴蝶左上角顶点和左下角顶点之间也要都为X,右上角顶点和右下角顶点也要为O才可以。

即红色线部分要满足左半部分全是X,右半部分全是O,同时蓝线的左半部分要全部是X,右半部分全是O。我们只需要先逐一枚举中心点,如果满足中心点为X,那么沿四个方向延伸检验是否红色线满足题意,如果满足再检验蓝色线部分是否满足。最会取得最大值的情况就可以了。

解题代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char Map[505][505];
int n, m;

bool flag(int x, int y)
{
//检验是否越界的函数
if (x >= 0 && x < n && y >= 0 && y < m)
return 1;
else
return 0;
}

int main()
{

cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
cin >> Map[i][j];
}
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
//因为是四个方向检查,所以需要四个方向临时点
int x1, y1, x2, y2, x3, y3, x4, y4;
//寻找中心点
if (Map[i][j] != 'X')
continue;
ans = max(ans, 1);
for (int len = 1; len <= min(n, m) / 2; len++)
{
int valid = 1;
//算出四个方向的从中心点移动后的顶点位置
x1 = i - len;
y1 = j - len;
x2 = i + len;
y2 = j - len;
x3 = i - len;
y3 = j + len;
x4 = i + len;
y4 = j + len;
//检验是否越界
if (flag(x1, y1) && flag(x2, y2) && flag(x3, y3) && flag(x4, y4))
{
//如果都不越界,那么检验顶点值是否满足题意
if (Map[x1][y1] == 'X' && Map[x2][y2] == 'X' && Map[x3][y3] == 'O' && Map[x4][y4] == 'O')
{
//满足以后分别检验顶点中间的值是否满足题意
for (int l = x1; l <= x2; l++)
{
if (Map[l][y1] != 'X')
{
valid = 0;
break;
}
}
for (int l = x3; l <= x4; l++)
{
if (Map[l][y3] != 'O')
{
valid = 0;
break;
}
}
//满足题意就为斜边长的2倍再+1(因为有一个中心点)
if (valid)
ans = max(ans, len * 2 + 1);
}
else
break;
}
else
break;
}
}
}
cout << ans << endl;
system("pause");
return 0;
}

NC14386-水仙花数

题目链接

https://ac.nowcoder.com/acm/problem/14386

题目描述

水仙花数是指一个N位正整数(N≥3),它的每个位上的数字的N次幂之和等于它本身。例如:

这道题请写出程序判断输入的数是否为水仙花数。首先输入正整数 n,表示需要判断的数的个数 (1<=n<=100)。随后每一行输入一个数 Ai,对于每次输入判断 Ai 是否为水仙花数。每次判断 Ai 输出判断结果:如果是,输出 yes;否则输出 no

测试样例

输入

1
2
3
4
3
111
153
222

输出

1
2
3
no
yes
no

说明

1
111不是水仙花数,输出no,153是水仙花数,输出yes,222不是水仙花数,输出no

解题思路

两个思路,一个是存为整型,然后不断地模10取最后一位即可,还有一种思路是存为字符串,这样我们可以直接调用size()函数获得幂数。但是这样最终比较时需要将整型结果转换为字符串。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int main()
{
int n;
cin >> n;
while (n--)
{
string num;
cin >> num;
int len = num.size();
int ans = 0;
for (int i = 0; i < len; i++)
{
ans = ans + pow(num[i] - '0', len);
//自己在本地vscode上测试153居然会输出No!
// cout << "pow:" << pow(num[i] - '0', len) << endl;
// cout << ans << endl;
}
string s = to_string(ans);
if (s == num)
cout << "yes" << endl;
else
cout << "no" << endl;
}
system("pause");
return 0;
}

NC14399-素数判断

题目链接

https://ac.nowcoder.com/acm/problem/14399

题目描述

给出一个数x,判断它是否为素数,并输出所有它的素因子。第1行输入组数T,代表有T组数据。第2-T+1行输入一个数x。数据保证:2≤x≤109。每行输出两行,对应输入行的结果。第1行,如果x是素数,输出“isprime”(不含双引号),否则输出“noprime”(不含双引号)。第2行,输出x的素因子。

测试样例

输入

1
2
3
4
3
2
9
10

输出

1
2
3
4
5
6
isprime
2
noprime
3
noprime
2 5

解题思路

这里记录一下解题方法,是一个快速寻找质因子的方法。就是从2到根号x注意枚举除数,那么对于除数i满足x%i==0一定是质因子(注意必须是保证从小到大找),然后x不断除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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

int main()
{
int T;
cin >> T;
int x;
while (T--)
{
cin >> x;
bool flag = true;
vector<int> ans;
//i从2到根号x枚举检验
int n = sqrt(x);
for (int i = 2; i <= n; ++i)
{
//如果当前的最小i是因子,那么就一定是质因子
if (x % i == 0)
{
flag = false;
ans.push_back(i);
//关键步骤,循环除去i,这样保证下一个因子仍然是质因子
while (x % i == 0)
x /= i;
}
//退出代码,不要忘记
if (x == 1)
break;
}
if (flag)
{
cout << "isprime" << endl;
cout << x << endl;
}
else
{
cout << "noprime" << endl;
for (int i = 0; i < ans.size() - 1; ++i)
{
cout << ans[i] << " ";
}
cout << ans.back();
if (x != 1)
//注意最后一个质因子没有存到答案数组中
//比如10,那么i从2到根号10
//i无法检验到5,所以10/2=5最后一个质因子5还赋值在x上,未存储到答案数组中
cout << " " << x;
cout << endl;
}
}
system("pause");
return 0;
}

NC14346-凌波微步

题目链接

https://ac.nowcoder.com/acm/problem/14346

题目描述

小Z的体型实在是太胖了,每次和小D一起出门都跟不上小D的脚步,这让小Z很气馁,于是小Z跋山涉水,仿名山,遍古迹,终于找到了逍遥派。掌门看小Z求师虔诚,决定传小Z一套《凌波微步》。这种腿法可以无视距离的行进,但缺点是只能走向高处,否则强行发功极易走火入魔。一天,练习《林波微步》的小Z来到一处练武场,这里从左到右,共有n个木桩,这些木桩有高有低,在这里小Z勤奋的练习着凌波微步,你知道小Z在这处练武场最多能练习多少次么?

本题有T组数据。
对于每组数据第一行有一个正整数n表示有多少个木桩。
第二行有n个数 a_i,表示木桩与水平地面的相对高度。
1≤T≤10,1≤n≤100000,1≤a_i≤1000000000

测试样例

输入

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

输出

1
2
6
4

说明

1
2
第一组:  1->2->3->4->5->66
第二组: 1->3->5->64

解题思路

注意题干只是要求从低到高走,没说是从左往右走,所以每次小Z都跳当前高木桩中的最低木桩即可。所以只需要将木桩高度从低到高排序,然后去掉重复高度的木桩,剩余的木桩数量就是可以走的最多次数。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int a[100005];

int main()
{
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
//木桩从小到大排序
sort(a + 1, a + n + 1);
int ans = 0, tmp = 0;
// for (int i = 1; i <= n; i++)
// {
// //记录增大木桩的数量
// if (a[i] > tmp)
// {
// tmp = a[i];
// ans++;
// }
// }
//实际上也可以使用数组去重更简单,只需要把相同高度的木桩去重
ans = unique(a + 1, a + n + 1) - (a+1);
cout << ans << endl;
}
system("pause");
return 0;
}

NC14347-珠宝店

题目链接

https://ac.nowcoder.com/acm/problem/14347

题目描述

小Z向女神告白成功,成功脱单,为了庆祝,小Z决定送女神一个礼物。在珠宝店,小Z终于发现一种既便宜又大气的手链。手链的价格是看手链上的宝石决定的,每一种宝石的价值不一样。具体规则如下:宝石A的价值是1、宝石B的价值是2、宝石C的价值是3·····宝石Z的价值是26。为了防止被销售员虚报价格,小Z决定请你帮忙计算一下手链的价值。

本题有T组数据。对于每组数据只有一行。1≤T≤20,1≤手链长度≤100000。

测试样例

输入

1
2
3
2
ABCD
LOVELOVE

输出

1
2
10
108

解题思路

水题,就是字符ASCII码均减’A’再加一即可。然后累加求总价值即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main()
{
int n;
cin >> n;
while (n--)
{
string s;
cin >> s;
int ans = 0;
for (int i = 0; i < s.size(); i++)
{
ans += s[i] - 'A' + 1;
}
cout << ans << endl;
}
system("pause");
return 0;
}

NC14345-布置会场(1)

题目链接

https://ac.nowcoder.com/acm/problem/14345

题目描述

今天是Tabris和mengxiang000来到幼儿园的第3天,mengxiang000接到了一个布置会场的任务。他需要将贵宾观众席的椅子排成一排,一共需要N个。幼儿园只有两种椅子,所以他也只能使用两种椅子。(A类型和B类型)并且假设每种椅子的数量都是无限的。而其如果想要摆置一个B类型的椅子,对应就需要必须有连续两个一起布置。换句话说,就是如果出现了B类型的椅子,其必须且只有两个连着B类型的椅子。mengxiang000突然想知道对应N个椅子排成一列,他能够有多少种布置的方式。

本题包含多组输入第一行输入一个整数t,表示测试数据的组数
每组测试数据包含一行,输入一个整数N,表示一共需要摆放的椅子数量
t<=30,1<=N<=30。

测试样例

输入

1
2
3
2
2
4

输出

1
2
2
5

解题思路

一开始想的是直接对于每一种情况进行计算,使用排列组合的方法写,但是实现很难,并且时间复杂度高,会超时。后来发现枚举以下n=2,3,4的情况不难看出就是斐波那契数列的dp,所以问题迎刃而解。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

int t, n, dp[50];

void init()
{
dp[0] = 0, dp[1] = 1;
for (int i = 2; i < 50; i++)
dp[i] += dp[i - 1] + dp[i - 2];
}

int main(void)
{
init();
cin >> t;
while (t--)
{
cin >> n;
cout << dp[n + 1] << endl;
}
system("pause");
return 0;
}

NC13223-锦标赛

题目链接

https://ac.nowcoder.com/acm/problem/13223

题目描述

组委会正在为美团点评CodeM大赛的决赛设计新赛制。比赛有 n 个人参加(其中 n 为2的幂),每个参赛者根据资格赛和预赛、复赛的成绩,会有不同的积分。比赛采取锦标赛赛制,分轮次进行,设某一轮有 m 个人参加,那么参赛者会被分为 m/2 组,每组恰好 2 人,m/2 组的人分别厮杀。我们假定积分高的人肯定获胜,若积分一样,则随机产生获胜者。获胜者获得参加下一轮的资格,输的人被淘汰。重复这个过程,直至决出冠军。现在请问,参赛者小美最多可以活到第几轮(初始为第0轮)?

第一行一个整数 n (1≤n≤ 2^20),表示参加比赛的总人数。接下来 n 个数字(数字范围:-1000000…1000000),表示每个参赛者的积分。小美是第一个参赛者。小美最多参赛的轮次。

测试样例

输入

1
2
4
4 1 2 3

输出

1
2

解题思路

我们统计一下小于等于小妹积分的人数,对于每一次比赛,都是人数/2,所以每一次比赛后小于等于小妹积分的人数也会减小2倍,这样当没有小于等于小妹积分的人时小妹就该淘汰了,所以只需检验人数是2的几次方即可。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;

int main()
{
int a, b, n, j = 1;
cin >> n;
cin >> a;
for (int i = 1; i < n; i++)
{
cin >> b;
//找出所有小于mei积分的人数
if (b <= a)
j++;
}
//最后求出取2对数的向下取整即为答案,小美可以进行的最多轮数
cout << (int)log2(j) << endl;
system("pause");
return 0;
}

NC14503-晨跑

题目链接

https://ac.nowcoder.com/acm/problem/14503

题目描述

“无体育,不清华”、“每天锻炼一小时,健康工作五十年,幸福生活一辈子”。在清华,体育运动绝对是同学们生活中不可或缺的一部分。为了响应学校的号召,模范好学生王队长决定坚持晨跑。不过由于种种原因,每天都早起去跑步不太现实,所以王队长决定每a天晨跑一次。换句话说,假如王队长某天早起去跑了步,之后他会休息a-1天,然后第a天继续去晨跑,并以此类推。王队长的好朋友小钦和小针深受王队长坚持锻炼的鼓舞,并决定自己也要坚持晨跑。为了适宜自己的情况,小钦决定每b天早起跑步一次,而小针决定每c天早起跑步一次。某天早晨,王队长、小钦和小针在早起跑步时相遇了,他们非常激动、相互鼓励,共同完成了一次完美的晨跑。为了表述方便,我们把三位同学相遇的这天记为第0天。假设三位同学每次晨跑的时间段和路线都相同,他们想知道,下一次三人在跑步时相遇是第几天。由于三位同学都不会算,所以希望由聪明的你来告诉他们答案。

输入共一行,包含三个正整数a,b,c,表示王队长每隔a天晨跑一次、小钦每隔b天晨跑一次且小针每隔c天晨跑一次。输出共一行,包含一个正整数x,表示三位同学下次将在第x天相遇。

测试样例

输入

1
2 3 5

输出

1
30

解题思路

实际上就是求解a,b,c三者的最小公倍数。可以先对a,b求最小公倍数,再求ab的最小公倍数与c的最小公倍数即可。这里主要是记录一下板子。并且最小公倍数=两个数相乘/最大公约数。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

//最小公倍数=两数乘积/最大公约数
long f(long a, long b)
{
long m = a * b;
//最大公约数--相减法
// while(a<b || a>b){
// if(a<b)b=b-a;//此时最终b是最大公约数
// if(a>b)a=a-b;//此时最终a是最大公约数
// }

/*最大公约数--辗转相除法*/
if (b > a)
swap(a, b);
long c = a % b;
while (c != 0)
{
a = b;
b = c;
c = a % b;
}//此时b是最大公约数

return m / b;
}
int main()
{
long a, b, c;
cin >> a >> b >> c;
long cnt = f(a, b);
long ans = f(cnt, c);
cout << ans << endl;
system("pause");
return 0;
}

NC14547-苦逼的单身狗

题目链接

https://ac.nowcoder.com/acm/problem/14547

题目描述

双11又到了,小Z依然只是一只单身狗,对此他是如此的苦恼又无可奈何。 为了在这一天脱单小Z决定向女神表白,但性格腼腆的小Z决定隐晦一点,截取一段包含’L’、’O’、’V’、’E’的英文。(顺序不限)。小Z想起之前小D送给他一本英文书,决定在这里面截取一段话,小Z发现有好多种方案来截取这段话。 你能知道小Z能有多少种方案截取这段话么? 为了简化问题,英文文本讲不会出现空格、换行、标点符号及只有大写的情况。

本题有T组数据。对于每组数据只有一行文本。1≤T≤20,1≤文本长度≤100000。

测试样例

输入

1
2
3
4
3
ILOVEACM
LOVELOVE
ALBECVOD

输出

1
2
3
8
15
4

解题思路

我们以LOVELOVE为例分析一下,每次我们都找到含有LOVE(顺序随意)的子串,然后记录这四个字符最早出现的位置,然后左边的字符数+1就包含这个子串的所有情况。比如现在从i=1开始向右查找。

  1. i=0(L),i=1(O),i=2(V),i=3(E),那么最早出现的位置是i=0,左边无字符,所以字符数是0,那么包含这个子串的情况就是有一种即子串自身LOVE
  2. i=1(O),i=2(V),i=3(E),i=4(L),那么最早出现的位置是i=1,左边有一个字符L,所以字符数是1,那么包含这个子串的情况就有2种即LOVEL和OVEL
  3. i=2(V),i=3(E),i=4(L),i=5(O),那么最早出现的位置是i=2,左边有两个字符L,O,所以字符数是2,那么包含这个子串的情况3种即LOVELO,OVELO和VELO

依次类推,所以我们就找到了规律,即每次获取刚好出现LOVE的子串,然后比较获得四个字符最先出现的位置,查看左边的字符数即可。

解题代码

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
#include <bits/stdc++.h>
using namespace std;

int main()
{
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
//记录四个字符出现的坐标
int l = -1, o = -1, v = -1, e = -1;
long long ans = 0;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == 'L')
l = i;
else if (s[i] == 'O')
o = i;
else if (s[i] == 'V')
v = i;
else if (s[i] == 'E')
e = i;
//取一个含有字符串的love的子串并且比较四个坐标取最小值
int cnt = min(min(l, o), min(v, e));
if (cnt != -1)
{
//包含本次子串的情况数量为左边的字符数+1
ans += cnt + 1;
}
}
cout << ans << endl;
}
system("pause");
return 0;
}

NC14545-B-经商

题目链接

https://ac.nowcoder.com/acm/problem/14545

题目描述

小d是一个搞房地产的土豪。每个人经商都有每个人经商的手段,当然人际关系是需要放在首位的。 小d每一个月都需要列出来一个人际关系表,表示他们搞房地产的人的一个人际关系网,但是他的精力有限,对应他只能和能够接触到的人交际。比如1认识2,2认识3,那么1就可以接触3进行交际,当然1和2也可以交际。 小d还很精明,他知道他和谁交际的深获得的利益大,接下来他根据自己的想法又列出来一个利益表,表示他和这些人交际需要耗用多少精力,能够获得的利益值为多少。小d想知道,他在精力范围内,能够获得的利益值到底是多少。 设定小d自己的编号为1.并且对应一个人的交际次数限定为1。

本题包含多组输入,第一行输入一个数t,表示测试数据的组数
每组数据的第一行输入三个数,N,M,C,表示这个人际关系网一共有多少个人,关系网的关系数,以及小d的精力值
接下来N-1行,每行两个数ai,bi。这里第i行表示和编号为i+1的人认识需要花费ai的精力,能够获得的利益值为bi。
再接下来M行,每行两个数x,y,表示编号为x的人能够和编号为y的人接触
t<=50
2<=N<=10000
1<=M<=10*N
1<=ai,bi<=10
1<=C<=500
1<=x,y<=N

测试样例

输入

1
2
3
4
5
6
7
8
9
1
5 3 7
5 10
3 2
4 3
1 100
1 2
2 3
1 4

输出

1
10

解题思路

这是一道并查集+0/1背包dp题,可以参考学习笔记《浅谈用一维数组dp解决0/1背包问题》《浅谈并查集解决分组问题》。这里就是纯板子题,但是一定要注意读懂题干,是要求只有两个人有直接关系或者间接关系才可以认识,例如样例1中的1和5是不能认识的,虽然给出了1认识5的精力消耗和收益,但是由于1和5没有直接关系并且1也不能通过该其他人认识5。所以这道题就是先试用并查集建立分组关系网,然后使用0/1背包dp解决。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define close_stdin ios::sync_with_stdio(false)
int n, m, c;
const int maxn = 10005;
int a[maxn], b[maxn];
int fa[maxn];
int dp[505];

int find(int x)
{
//寻找最深层祖先,同时压缩更新x的祖先为最深层祖先
return (fa[x] == x ? x : fa[x] = find(fa[x]));
}

void merge(int x, int y)
{
//x的最深层祖先的祖先更新为y,这样x和y就有关系了,同时y会成为更深层的根本祖先
if (find(x) != find(y))
fa[find(x)] = find(y);
}

void my_input()
{
cin >> n >> m >> c;
for (int i = 2; i <= n; i++)
{
cin >> a[i] >> b[i];
}
}

void solve()
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++)
{
//初始时默认是独立节点,无祖先,所以各节点无关系
fa[i] = i;
}
while (m--)
{
int x, y;
cin >> x >> y;
//x和y建立关系同时默认y是更深层的祖先
//所以此时fa[x]=y即x的最根本祖先是y
//同时fa[find(X)]=y即x的祖先的最根本祖先也会是y
merge(x, y);
}
//关系网建立完成后进行0/1dp
for (int i = 2; i <= n; i++)
{
//讨论每一个对于1~i每一个节点是否放入
//首先需要满足有关系才可以认识
//一定要注意例如样例1中1和5就不能认识,因为他们没有共同认识的人且两者也不认识
if (find(i) == find(1))
{
//能够认识,讨论是否认识
for (int j = c; j >= a[i]; j--)
{
//板子
dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
}
}
}
cout << dp[c] << endl;
}

int main()
{
close_stdin;
int t;
cin >> t;
while (t--)
{
my_input();
solve();
}
system("pause");
return 0;
}



©2020 - 2021 By wenchong
津ICP备2021009044号

本站总访问量为 访客数为

本站使用 Volantis 作为主题|借助hexo强力驱动|由腾讯云提供云服务