总结

CS行业隔行如隔山，基本用不上的书籍又又又增加了，刷刷做过的题目减缓下算法遗忘的速度吧。

比较有趣的一点是，有同学做完，会故意等很长时间再交卷；而有的做完发现排名不够就直接开小号再提交一遍刷排名，小号的昵称和代码都不改下，多少是有点瞧不起官方的审核了。

题目列表

1.订班服

题目描述

小A班级订班服了！
可是小A是个小糊涂鬼，整错了好多人的衣服的大小。
小A只能自己掏钱包来补钱了。
小A想知道自己至少需要买多少件衣服。

输入描述：

第一行输入一个整数n。(1<=n<=100)表示衣服的数量。
以下n行输入n个尺码。表示订单中衣服的尺码。
接下来n行输入n个尺码。小A订的衣服尺码。
尺码表:M,S,L,XL,XLL,XLLL,XLLLL,XLLLLL。

输出描述：

输出至少需要买多少件衣服。

输入样例：

2
XL
X
M
X

输出样例：

1

分析

本题的题目还是有一定歧义的，订单中衣服的尺码与小A订的衣服尺码语义差不多，不如直接说同学实际的衣服尺码和小A订的衣服尺码。虽然用例里每种尺码的衣服只出现了一次，但是后台用例里应该会出现很多重复尺码的衣服，因此不能使用set求差集大小的思路，可以使用map统计下每个尺码实际需要的数量，然后遍历小A订的尺码，只要实际的数量未达标，小A每订一件该尺码的衣服，还需要订的尺码数量就减一，最后统计下未达标尺码衣服的数量即可。

代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
using namespace std;
map<string,int> m;
int main() {int n;cin>>n;for(int i = 0; i < n; i++) {string s1;cin>>s1;m[s1]++;}for(int i = 0; i < n; i++) {string s;cin>>s;if(m.count(s) && m[s]) {m[s]--;}}int res = 0;for(auto x : m) {res += x.second;}cout<<res<<endl;return 0;
}

2.异或和

题目描述

小张找到了一个整数 N，他想问问你从 1 到 N 的所有不同整数的异或和是多少， 请你回答他的问题。

输入描述：

第一行包含一个整数 N (1 <= N <= 100000)。

输出描述：

第一行输出一个整数， 代表从 1 到 N 的所有不同整数的异或和。

输入样例：

5

输出样例：

1

分析

虽然从二进制的角度分析，有更高效的做法可以快速统计出前N个整数的异或和，但是这么小的数据规模遍历一遍求下异或和，几十秒就可以AC了。

代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;
int solution(int N) {int res = 0;for(int i = 1; i <= N; i++) res ^= i;return res;
}
int main() {int N;std::cin>>N;int result = solution(N);std::cout<<result<<std::endl;return 0;
}

3.零钱兑换

题目描述

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
如果无解，请返回-1.

数据范围：数组大小满足 0 <= n <=10000 ， 数组中每个数字都满足 0 < val <=10000，0 <= aim <=100000

要求：时间复杂度 O(n×aim) ，空间复杂度 O(aim)。

输入描述：

无

输出描述：

无

输入样例：

[5,2,3],20

输出样例：

4

分析

又是考过的题目，再刷一遍加深下印象。首先吐槽下输入，输入数组写成python列表的形式，给的c++或者python模板都只是读取了下字符串，没有很好的处理输入。上次做是直接用getchar和cin逐个读取的，这次是读取字符串后将前面数字部分切分为数组，处理输入大概还是写了一两分钟，有待提高。

状态表示：$f[i][j]$表示前$i$个货币面值组成$j$元钱需要的最少货币数。

状态转移方程：$f[i][j]=max(f[i-1][j],f[i-1][j-k\ast w[i]]+k)$，表示第$i$个货币面值选$k$次加上前面其它面值的货币可以达到$j$元。

优化：$f[i][j-w[i]]=max(f[i-1][j-w[i]],f[i-1][j-(k+1)\ast w[i]]+k)$，假设$j$是$w[i]$的$t$倍，那么枚举$f[i][j]$状态时，需要枚举

$$f[i-1][j],f[i-1][j-w[i]]+1,...,f[i-1][j-t\ast w[i]]+t$$.

而枚举$f[i][j-w[i]]$状态时，需要枚举

$$f[i-1][j-w[i]],f[i-1][j-2w[i]]+1,...,f[i-1][j-t\ast w[i]]+t-1$$.

可以发现$f[i][j]=max(f[i-1][j],f[i][j-w[i]]+1)$，由于每层状态仅用到上一层相同列的状态和当前层左边的状态，所以可以使用滚动数组，顺序遍历枚举状态即可。

代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10005;
int a[N];
int f[100005];
int main() {std::string s;getline(std::cin, s);int n = s.size();int idx = 0;int t = 0;for(int i = 1; i < n; i++) {if (s[i]==',') {a[idx++]=t;t = 0;} else if (s[i]!=']') {t = t * 10 + s[i] - '0';}}memset(f,0x3f,sizeof f);f[0]=0;for(int i = 0; i < idx; i++) {for(int j = a[i]; j <= t; j++) {f[j]=min(f[j],f[j-a[i]]+1);}}if (f[t]==0x3f3f3f3f) cout<<-1<<endl;else cout<<f[t]<<endl;return 0;
}

4.小艺照镜子

题目描述

已知字符串str。
输出字符串str中最长回文串的长度。

输入描述：

输入字符串s.(1<=len(str)<=10000)

输出描述：

输出答案

输入样例：

abab

输出样例：

3

分析

比赛时扫了眼题目以为是补充最少字符串使得原字符串变成回文串的问题，正写着LCS的DP解法发现理解错了，就是最简单的最长回文串长度的问题。这个问题题解写过很多了，马拉车算法和字符串哈希的线性解法固然复杂，但是平方级别的暴力解法还是可以秒掉的，基本不需要思考。

代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 10005;
int main() {std::string s;getline(std::cin, s);;int n = s.size();int res = 1;for(int i = 0; i < n; i++) {int p = i,q = i + 1;while(p>=0&&q<n&&s[p]==s[q]) p--,q++;res = max(res,q-p-1);p = i - 1,q = i + 1;while(p>=0&&q<n&&s[p]==s[q]) p--,q++;res = max(res,q-p-1);}cout<<res<<endl;return 0;
}