0x01 折扣卷
我的原代码：
#include<iostream>
#include<vector>
using namespace std;
const int Max = 100;
int main() {
int N, P, Q;
cin >> N;
cin >> P;
cin >> Q;
int arrD[100];
for (int i = 0; i < N; i++) {
cin >> arrD[i];
}
int now = 0;
int result=0;
for (int i = 0; i < N; i++) {
now = arrD[i] + Q;
if (now >= P) {
result = P;
}
else if(result<=now){
result = now;
}
else {
continue;
}
}
cout << result << endl;
return 0;
}教练的代码：
#include <iostream>
using namespace std;
const int N = 1e2 + 5;
int d[N];
int main() {
int n, p, q;
cin >> n >> p >> q;
int min_d = 2e5;
for (int i = 0; i < n; i++) {
cin >> d[i];
//找出最便宜的商品
min_d = min(min_d, d[i]);
}
cout << min(min_d + q, p);
return 0;
}
总结：
对比教练的代码，我的简直惨不忍睹，不像是人写出来的。这题的思路很简单，两种方案：要么选用原价购买，要么选用折扣价加另一款商品，因此先遍历得到最便宜的额外商品，然后将最便宜的额外商品加上折扣价格，再对比原价，较小的就是最终结果。
而我的思路是：把 额外价和折扣价加起来 跟原价对比，遍历过程中每次都跟原价对比一次，而不是遍历得到最小值后再跟原价对比。这样做时间空间复杂度会更高，而且也更复杂，最关键的是我竟然写错了！！
按照我的思路，我应该这么写
1.对c++中的内置函数不熟练。对于这类对比问题，我下意识就想到的是if else，而c++中内置的函数min(a,b)可以直接返回一个最小值。如果我第一时间想到的是min()函数，而不是if else，是不是就能顺势按照这个思路想了呢
2.按照我的思路，因为是要求一个最小值，那么初始化变量 result 的时候就要设置最大值，因为要在遍历的过程中让result逐渐减小。不是任何变量初始化都是0，根据他的作用和具体情况考虑！
0x02 ABC
我的代码
#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int Max = 100;
int main() {
int N;
char S[Max];
cin >> N;
for (int i = 0; i < N; i++) {
cin >> S[i];
}
int A = 0, B = 0, C = 0;
for (int i = 0; i < N; i++) {
if (S[i] == 'A') {
A++;
}
else if (S[i] == 'B') {
B++;
}
else {
C++;
}
if (A && B && C != 0) {
cout << i + 1 << endl;
break;
}
}
return 0;
}教练的代码
总结：
教练的思路很牛逼，利用ascii码的差值来给数组不同位置赋值为1，当数组flag三个位置都是1时停止循环，输出i值，但我觉得我的思路更好一些。
0x03 最小字典序
我的原代码：
教练代码
没什么好说的，利用sort函数对s字符串进行排序
0x04 一起度假（没时间写）
教练代码
const int Max = 105;
string spare[Max];
int n, d;
bool check(int l, int r) {
for (int k = l; k <= r; k++) {
for (int x = 0; x < n; x++) {
if (spare[x][k] == 'x'){
return false;
}
}
}
return true;
}
int main() {
cin >> n >> d;
for (int i=0; i < n; i++) {
cin >> spare[i];
}
int ans = 0;
for (int i = 0; i < d; i++) {
for (int j = i; j < d; j++) {
if (check(i, j)) {
ans = max(ans, j - i + 1);
}
}
}
cout << ans;
return 0;
}
分析：
1.首先写一个bool类型的函数，用来判断第 l天到r天 中是否全员有空，有空则返回true，放在if的条件中进行下一步；没空则返回false。
2.在main函数中写一个双层循环，用来遍历第 l天到r天 的不同选择：外层控制起始的天数 l 的位置，从0到m-1；内层控制结束的天数 j 的位置，从0到m-1。if 中的条件成立（即在 i 到 j 天全员有空），那么更新此时全员有空总天数。
优化代码
这个代码时间复杂度易得为O(nd^3)，虽然这题能过，但时间复杂度还是比较高的。教练让我们想想有没有办法吧时间复杂度优化到O(nd)呢？
注意到在第二层for循环内部中，当 i 不变，参数 j 变化使得check函数从返回true到返回false时，内层循环就没必要继续了，因为继续对 j 进行++，i 到 j 函数判断怎么样都是返回false。因此我们可以考虑对check函数进行修改，让他直接跳出内层循环
跳出内层循环之后，外层的 i 仅仅是++吗？我们应该记录刚刚过程中 j 到了哪里，这时候外层循环 i 从 j 的值的下一个位置开始向下++。
总得来说，就是当check返回false时，跳出内层循环，同时 i=j+1 继续进行遍历。(有点像 KMP算法 ) 这样修改过的代码很容易得知，时间复杂度为O(nd) !!
优化代码实现 时间复杂度nd
using namespace std;
int main() {
int n, d;
cin >> n >> d;
vector<string>s(n);
long long ans = 0;
for (int i = 0; i < n; i++)cin >> s[i];
long long res = 0;
for (int i = 0; i < d; i++) {
char c = s[0][i];
bool work = 1;
if (c == 'o') {
for (int j = 0; j < n; j++) {
if (s[j][i] != c)work = 0;
}
if (work) {
res++;
ans = max(ans, res);
}
else {
res = 0;
}
}
else {
res = 0;
}
}
cout << ans;
return 0;
}
0x05 串反转 （没时间写）
教练代码：
#include<iostream>
#include<vector>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
const int N = 200005;
string s[N];
int main() {
int n;
cin >> n;
for(int i=0;i<n;i++){
cin >> s[i];
}
set<string> st;
for (int i = 0; i < n; i++) {
string str = s[i];
string re_str = s[i];
reverse(re_str.begin(), re_str.end());
if (str < re_str) {
st.insert(str);
}
else {
st.insert(re_str);
}
}
cout << st.size();
return 0;
}
分析：
首先将字符串数组中每个元素分别赋值到 str 和 re_str (re_str是sp[i]的反转) ，之后对比两者，将较小的一者赋值到 st 有序集合后面，最后输出 st 有序集合
总结：
1.首先是reverse函数，可以将所有 支持迭代器的容器类型 反转，如数组，字符串等
2.其次是set，set 可以存储任何可以比较的类型（即能够支持 < 操作符或者自定义的比较方式的类型），并且进行升序排列，并且会自动剔除相同的元素，用来做这个题最合适不过。
还有两题 周末一起写
