A 阿伦
题目描述
Aron要去给朋友买礼物。
前面有\(n\)个人在排队，其中有一些独自前来的顾客和一些组团前来的顾客。
相邻的穿着一样的衣服的顾客在同一团队里。
一个团队里只要第一个人买了就会离开。
问Aron会在第几个排到
输入格式
第一行一个\(n\),表示前面有多少个人
接下来共\(n\)行，第\(i\)行一个大写英文字母，表示第\(i\)个人的衣服颜色。
输出格式
一行，表示Aron是第几个排到的
样例1
输入
6
C
C
P
C
Z
Z
输出
5
题解
因为相邻的穿同样衣服的人只要走了一个就会全走，所以我们可以定义一个char数组，只要当前的与上一个不同，答案就加一
ac代码
#include <iostream>
using namespace std;
int main() {
int n, ans = 0;
char c0 = ' ', c1;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> c1;
if (c0 != c1)
ans++;
c0 = c1;
}
cout << ans + 1;
return 0;
}
B 二八杠
题目描述
乐乐在春节期间，围观了很多赌局。他觉得赌博不好，如果能有程序分析赌局结果，那应该挺有意思的，请你帮助他。
二八杠是江浙地区广泛流传的一种民间游戏，又称掐二八。参与游戏者可为2 - 4人，采用一副扑克牌张牌去除K,Q,J,A以及 大小王后的36张数字牌。
本题中，2个人参与游戏，需要里分析出结果。
游戏开始时，每人发两张牌，每张是2-10中的一个。
比较输赢时，大小顺序是：
1：两张牌是2和8，最大。
2：对子，从小到大是：对2...对10。
3：将两张牌的值加起来，取个位数，大的赢。如果相同，再比较两张牌中，较大的，较大的赢。如 “5 4” 比“6 3”小。
输入格式
第一行一个正整数\(n\)，表示游戏的局数。\(n\leq100\)
接下来n行，每行四个整数，\(x1,x2,y1,y2\)表示两个人发到的牌。
输出格式
输出\(n\)行，first,second,tie表示第一个人赢，第二个人赢和平局。
样例1
输入
5
2 8 4 6
6 6 6 7
4 5 5 5
6 3 9 10
7 2 2 7
输出
first
first
second
second
tie
题解
由于本题需要判断的东西非常多，非常容易遗漏，如果使用常用的if else可能会有遗漏导致错误，所以我们可以给每种操作赋一个权值，这样在判断是就会非常方便，但是要注意关于权值的问题
注：\((x+y)\%10*10\)的原因是因为\(x,y\)的和的个位数有可能小于原本的数
#include <iostream>
using namespace std;
int cal(int x, int y) {
if (x > y)
swap(x, y);
if (x == 2 && y == 8)
return 1000;
else if (x == y)
return 900;
else
return (x + y) % 10 * 10 + y;
}
int main() {
int n;
cin >> n;
while (n--) {
int a1, a2, b1, b2;
cin >> a1 >> a2 >> b1 >> b2;
if (cal(a1, a2) == cal(b1, b2))
puts("tie");
else if (cal(a1, a2) > cal(b1, b2))
puts("first");
else
puts("second");
}
return 0;
}
C 编程考试
题目描述
Little Leticija 正在准备编程考试，向你寻求帮助。
给定字符串 S 及\(Q\)次查询。
每次查询给定正整数\(A,B,C,D\) ，令字符串 X 由 S 中位置 到 之间的字符组成，Y 由 S 中位置 到 之间的字符组成，你需要判断能否以某种方式重新排列 Y 中的字符使 X 与 Y 相同。若可以，则输出 DA，否则输出 NE。
输入格式
第一行输入包含字符串\(S(1\leq|S|\leq50000)\) ，由英文字母的小写字母组成。
第二行输入包含正整数\(Q(1\leq Q\leq50000)\)。接下来的$ Q$行，每行给定正整数 ，描述一次询问。
输出格式
对于每个查询，如果可能，输出 DA；如果不可能，则输出 NE。
样例1
输入
kileanimal
2
2 2 7 7
1 4 6 7
输出
DA
NE
样例2
输入
abababba
2
3 5 1 3
1 2 7 8
输出
DA
DA
样例3
输入
vodevovode
2
5 8 3 6
2 5 3 6
输出
NE
DA
题解
我们可以使用前缀和优化这个问题，首先开一个二维数组，存储每个位置上的字母，用string读入，注意string的下标是从0开始的
ac代码
#include <iostream>
using namespace std;
int word_count[50005][26];
string s;
int q;
int main() {
cin >> s;
for (int i = 1; i <= s.length() - 1; i++) {
for (int j = 0; j < 26; j++) {
word_count[i][j] = word_count[i - 1][j];
}
word_count[i][s[i - 1] - 'a']++;
}
cin >> q;
while (q--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
bool flag = true;
for (int i = 0; i < 26; i++) {
if (word_count[b][i] - word_count[a - 1][i] != word_count[d][i] - word_count[c - 1][i]) {
flag = false;
break;
}
}
puts(flag ? "DA" : "NE");
}
return 0;
}
D 01反转
题目描述
有一个长为\(n\)的字符串\(s\) ，只含\(0\)和\(1\) 。
你可以进行最多\(k\)次如下操作（\(0\)次也可以）：
- 选择字符串\(s\)的一个子串，将其中的字符反转（\(0\)变成\(1\)， \(1\)变成\(0\)）。
进行不超过\(k\)次操作后，求最长的连续的\(1\)的长度。
输入格式
第一行，\(2\)个正整数\(n,k\)；
第二行，字符串\(s\)。
输出格式
输出不超过\(k\)次操作后，最长的连续的\(1\)的长度。
数据约定
对于\(100%\)的数据：\(1\leq n,k\leq10^5\)。
字符串\(s\)只由\(0\)和\(1\)组成，长度为\(n\)。
样例1
输入
5 1
00010
输出
4
样例2
输入
14 2
11101010110011
输出
8
样例3
输入
1 1
1
输出
1
题解
首先我们可以先定义一个数组，意在获得连续的一段数字有几个，这样可减低我们的时间复杂度
接下来我们将这个数组进行累加，两个之间夹着的就是我们的答案，我们要先判断一下是从0还是1开始，如果是1，遍历的时候i要加一
我们的数组要另开2*k个，原因如下图：
ac代码
#include <iostream>
#include <cstring>
using namespace std;
const int M = 2e5 + 7;
int n, k, cnt = 0, pre[M], ans = 0;
string s;
int main() {
cin >> n >> k;
cin >> s;
pre[++cnt] = 1;
for (int i = 1; i < n; i++) {
if (s[i] != s[i - 1])
pre[++cnt] = 1;
else
pre[cnt]++;
}
for (int i = 1; i <= cnt + 2 * k; i++) pre[i] += pre[i - 1];
int i = 0 + ((s[0] - '0') == 1);
while (i <= cnt) {
ans = max(ans, pre[i + 2 * k] - pre[i - 1]);
i += 2;
}
cout << ans;
return 0;
}
E 愉悦的晚餐
题目描述
yy是ZL大食堂的常客,他熟悉菜单上所有的N道菜,并且对每道菜给出了色,香,味三个数的评价,以整数表示.
某天他的朋友从远方来到,yy要请客.他决定点M道菜.同一道菜至多点1次.
yy想了一个公式,计算这顿饭的愉悦程度.S=|色度之和|+|香度之和|+|味度之和|.其中|a|表示取a的绝对值.
你问为啥要取绝对值?因为yy认为请朋友吃一顿超难吃的饭也很愉悦啊
现在请计算S能达到的最大值
输入格式
第一行为\(N,M\)。 \((1≤M≤N≤1000)\)
接下来\(N\)行,每行三个整数\(x_i,y_i,z_i\)。\((-10^9≤x,y,z≤ 10^9)\)
输出格式
一个整数表示S的最大值
样例1
输入
5 3
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
输出
56
样例2
输入
5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15
输出
54
样例3
输入
10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82
输出
638
数据范围与提示
样例2:点第1,3,5道菜,色度和=1+6+13=21,香度和=-2-8-14=-24,味度和=3-9+15=9
50%数据: \(n≤10\)
题解
这个问题\(n\)的范围很大，用dfs或二进制枚举只能拿到50%的分，所以我们要进行优化
进过枚举我们可以发现值的排列一共有8种，这对于我们后面求绝对值有帮助
之后我们根据初中数学可以得知，绝对值的结果分为两种，之后我们便可简单解答
如下图：
所以我们算的时候直接分8种：
calc(1, 1, -1);
calc(1, -1, -1);
calc(1, -1, 1);
calc(1, 1, 1);
calc(-1, 1, 1);
calc(-1, -1, 1);
calc(-1, -1, -1);
calc(-1, 1, -1);
ac代码
#include <bits/stdc++.h>
using namespace std;
long long n, m, a[1005], b[1005], c[1005], s[1005];
long long ans = -1e15;
bool cmp(long long x, long long y) { return x > y; }
void calc(int af, int bf, int cf) {
long long ret = 0;
for (int i = 1; i <= n; i++) {
s[i] = af * a[i] + bf * b[i] + cf * c[i];
}
sort(s + 1, s + n + 1, cmp);
for (int i = 1; i <= m; i++) ret += s[i];
ans = max(ans, ret);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> c[i];
}
calc(1, 1, -1);
calc(1, -1, -1);
calc(1, -1, 1);
calc(1, 1, 1);
calc(-1, 1, 1);
calc(-1, -1, 1);
calc(-1, -1, -1);
calc(-1, 1, -1);
cout << ans;
return 0;
}
F 买蛋糕
题目描述
AT 小卖部从下学期开始售卖带有数字形状的蛋糕，\(X\)，\(Y\) 和 种蛋糕分别带有\(1\)形，\(2\)形和\(3\)形蜡烛，而且每个蛋糕都有美味值，如下所示：
- 带有\(1\)形蜡烛的美味值有： \(A_1,A_2,...A_x\)
- 带有\(2\)形蜡烛的美味值有： \(B_1,B_2,...B_Y\)
- 带有\(3\)形蜡烛的美味值有： \(C_1,C_2,...,C_Z\)
你决定购买三个蜡烛不同的蛋糕，请你将每种方案的美味值由大到小排序，依次打印前\(K\)种方案的美味值。
输入格式
一行四个整数\(X,Y,Z,K\)如题
一行\(X\)个整数，表示第一种蛋糕的美味值
一行\(Y\)个整数，表示第二种蛋糕的美味值
一行\(Z\)个整数，表示第三种蛋糕的美味值
输出格式
\(K\)行，从大到小输出前\(K\)种方案的美味值
样例1
输入
2 2 2 8
4 6
1 5
3 8
输出
19
17
15
14
13
12
10
8
样例2
输入
3 3 3 5
1 10 100
2 20 200
1 10 100
输出
400
310
310
301
301
样例3
输入
10 10 10 20
7467038376 5724769290 292794712 2843504496 3381970101 8402252870 249131806 6310293640 6690322794 6082257488
1873977926 2576529623 1144842195 1379118507 6003234687 4925540914 3902539811 3326692703 484657758 2877436338
4975681328 8974383988 2882263257 7690203955 514305523 6679823484 4263279310 585966808 3752282379 620585736
输出
23379871545
22444657051
22302177772
22095691512
21667941469
21366963278
21287912315
21279176669
21160477018
21085311041
21059876163
21017997739
20703329561
20702387965
20590247696
20383761436
20343962175
20254073196
20210218542
20150096547
数据范围与提示
对于\(30\%\)的数据，\(1\leq X,Y,Z\leq200\)
对于\(100\%\)的数据 ，\(1\leq X,Y,Z\leq1000\)，\(1\leq K\leq min(3000,X×Y×Y)\)，\(1\leq A_i,B_i,C_i\leq10000000000\)
题解
首先我们用暴力是解决不了这个问题的，我们要优美地解决
考虑到最终答案要求我们从大到小输出，我们自然就能想到优先队列的大根堆
这样最大值就直接输出根就可以了
另外我们需要定义一个结构体方便我们的存储，并在里面重载运算符，否则会导致stl的使用报错
bool operator < (const cake &A) const
{
return a[x]+b[y]+c[z]<a[A.x]+b[A.y]+c[A.z];
}
关于优先队列如何使用可以参考 c++优先队列(priority_queue)用法详解
排序完之后便开始输出答案，首先输出根部，然后再进行拓展，分别是\(x+1,y+1,z+1\)，记得用map打上标记，以免重复
ac代码
#include <iostream>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;
const int N = 1e3 + 10;
long long a[N], b[N], c[N];
int x, y, z, k;
struct cake {
int x, y, z;
bool operator<(const cake &A) const { return a[x] + b[y] + c[z] < a[A.x] + b[A.y] + c[A.z]; }
};
priority_queue<cake> q;
map<pair<pair<int, int>, int>, bool> mp;
bool cmp(long long a, long long b) { return a > b; }
int main() {
scanf("%d%d%d%d", &x, &y, &z, &k);
for (int i = 1; i <= x; i++) cin >> a[i];
for (int i = 1; i <= y; i++) cin >> b[i];
for (int i = 1; i <= z; i++) cin >> c[i];
sort(a + 1, a + x + 1, cmp);
sort(b + 1, b + x + 1, cmp);
sort(c + 1, c + x + 1, cmp);
q.push((cake){ 1, 1, 1 });
mp[make_pair(make_pair(1, 1), 1)] = true;
for (int i = 1; i <= k; i++) {
cake t = q.top();
q.pop();
printf("%lld\n", a[t.x] + b[t.y] + c[t.z]);
if (!mp.count(make_pair(make_pair(t.x + 1, t.y), t.z)) && t.x < x) {
mp[make_pair(make_pair(t.x + 1, t.y), t.z)] = true;
q.push((cake){ t.x + 1, t.y, t.z });
}
if (!mp.count(make_pair(make_pair(t.x, t.y + 1), t.z)) && t.y < y) {
mp[make_pair(make_pair(t.x, t.y + 1), t.z)] = true;
q.push((cake){ t.x, t.y + 1, t.z });
}
if (!mp.count(make_pair(make_pair(t.x, t.y), t.z + 1)) && t.z < z) {
mp[make_pair(make_pair(t.x, t.y), t.z + 1)] = true;
q.push((cake){ t.x, t.y, t.z + 1 });
}
}
return 0;
}
![原来你是这样的JAVA–[07]聊聊Integer和BigDecimal](https://img2024.cnblogs.com/blog/37001/202402/37001-20240224171021931-593439949.png)
