【计蒜客】ACM程序设计课程-快速提升代码能力
目录
前言
2019年4月6日，终于赶上了大佬们一周以前的刷题进度。算是一个小小阶段的结束，因此将这一部分的题目总结一下，也算是做一个ACM's milestone。
正文
1.a+b问题
没什么好说的，权当是测试代码。
2.斐波那契数列
在常规的斐波那契基础上取余，为了防止溢出，对每一步的结果都取余即可。
3.矩阵旋转
二维数组存储数据，输出的时候推导旋转后的矩阵的行、列坐标与原矩阵的坐标的关系直接输出即可。注意输出格式，行尾不要有多余的space，要不然会“格式错误”（计蒜客真的很严格，手动滑稽）。
4.最大子阵
这应该是前几道题里比较难的一道了。我的做法是DP+降阶。
大的思路是将矩阵的二维数组，对行或列求和累加，转换为一位数组，然后对一位数组求最大子集即可。
求一位数组最大子集的时候进行DP，状态无非两种，当下一个元素为正数，累加（子集继续扩大）；否则，子集重新计算求和。然后不断比较当前的和与最大值之间的大小，取最大值即可。
#include<bits/stdc++.h>
using namespace std;
int dp[55][55];
int maxsub(int a[],int n)
{
int i,max=-0x3f3f3f3f,b=0;// 注意max的初始值，防止数组全为负数
for(i=0;i<n;i++)
{
if(b > 0)
b += a[i];
else
b = a[i];
if(b > max)
max = b;
}
return max;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
cin>>dp[i][j];
}
}
int arr[55];
int result = -0x3f3f3f3f;
for(int i=0; i<n; i++){ // i为开始累加的行的起点
memset(arr,0,sizeof(arr));// i变化->子阵大小变化
for(int j=i; j<n; j++){ // 从第i行开始视为一个子阵
for(int k=0; k<m; k++){
// arr[k]表示第j行前k个元素的和
arr[k] += dp[j][k];
}
int max = maxsub(arr,m);
if(max > result){
result = max;
}
}
}
cout<<result;
return 0;
}
5.四平方和
枚举。以题目给定的数据范围，如果直接暴力四层循环嵌套，有一组数据是会超时的。因此，可以从遍历的范围和循环的层数两方面来进行优化。
遍历范围：题目要求给定的是“字典序”输出，那么后一个循环变量的起点可以是前一个循环变量。这样既减少了循环的次数，也能保证结果是按字典顺序；如果仅优化起点，这还是远远不够的，因此，每层循环的终点也要进行优化。缩小范围的方式也很简单：对于每层循环的终点，即为给定正整数N减去已经确定的变量的平方的和。例如，最外层循环变量a的起点为0，终点应该为sqrt（N），因为此时a已经确定，最差的情况是其余三个数都取0；第二层循环变量b的起点为a，保证字典序，终点为sqrt（N-a*a），因为a和b都已经确定，最坏的情况是其与两个数取0，c和d的范围以此类推。
遍历层数：当遍历到c的时候，完全可停止遍历，因为a,b,c,d和N之间存在等式，可以用计算的方式求的d的取值，然后代入等式验证即可。但要注意d应该也为整数，可以先对差开方，然后相乘验证是否相等，以此判断是否为整数。
PS感谢lxdl的指点。
6.A+B问题
大数加法。因此只需模拟竖式运算的过程：先将所有对应位置的数字相加，然后再次遍历处理进位。
需要注意的点是数据类型的转换、数字存储顺序、以及最高位是否有进位（改变输出结果的长度）。
7.A*B问题
大数乘法。跟第6题相似的处理方法，模拟竖式计算。不同的是乘法需要二维矩阵来模拟竖式。
提交时有一组用例没过，原因是乘数中有一个为0，而输出结果中把所有的0都输出了。
#include<bits/stdc++.h>
using namespace std;
char num1[1000],num2[1000];
int numa[1000],numb[1000],ans[1000][1000],res[1000];
int main() {
// 输入数字
scanf("%s",num1);
getchar();
scanf("%s",num2);
// 数字长度
int la = strlen(num1);
int lb = strlen(num2);
// 字符转数字，并倒序存放
int t=0;
for(int i=la-1; i>=0; i--) {
numa[t++] = num1[i]-'0';
}
t = 0;// 别忘初始化
for(int i=lb-1; i>=0; i--) {
numb[t++] = num2[i]-'0';
}
// 模拟竖式运算过程
int p=0,q=0;
for(int i=0; i<la; i++) {
for(int j=0; j<lb; j++) {
ans[p][q++] = numa[i]*numb[j];
}
p++;
q = 0;
q += i+1; // 相当于乘法里的进位
}
int max = la>lb?la:lb;
// 竖式的累加
for(int j=0; j<la+lb-1; j++) {
for(int i=0; i<max; i++) {
res[j] += ans[i][j];
}
}
int len = la+lb-1; // 结果的长度
bool flag = false; // 最高位进位标志
// 处理进位
for(int j=0; j<la+lb-1; j++) {
if(res[j]>=10) {
res[j+1] += res[j]/10;
res[j] = res[j]%10;
// 最高位有进位
if( j==la+lb-2) {
flag = true;
}
}
}
// 结果长度+1
if(flag) {
len++;
}
//最高位是0，说明乘数中有一个为0，直接输出结果
if(res[len-1]==0) {
cout<<"0";
} else {
for(int j=len-1; j>=0; j--) {
cout<<res[j];
}
}
return 0;
}8.蒜头君的随机数
我怀疑这题就是为了C++的STL准备的。
set<int> 在输入数据的时候自动去重和从小到大排序了，所以输入完后，直接输出set<int>里的元素个数和具体元素就好。
C++中的std::set自定义去重和排序函数 https://www.cnblogs.com/litaozijin/p/6665595.html
9.交叉排序
同STL，输入完数据之后，直接sort()，注意下标关系即可。
C++中的sort函数使用总结 https://www.cnblogs.com/TX980502/p/8528840.html
10.进制转换
十进制转任意进制。对于十进制转R进制数，直接模拟模R取余法即可实现转换。
11.回文数
直接模拟题意即可，不同的点是要输出每一步的步骤。将判断回文单独拿出来写成函数，我采用的方法是将数字的各个位数分离存到字符数组中，然后首尾两个指针向中间遍历判断。数据范围很友好。
12.机器人
一开始我以为是单纯的计算坐标的问题，但是仔细读几遍题之后发现，这个题的麻烦点在于机器人有“方向”，因此要实现方向和坐标变化之间的对应关系。解决的方法是将指令的方向转化为“需要在当前方向旋转的角度”，因为题目中只给了四个方向，因此可以将角度用4个数字代替，这样数字的含义就是“与初始方向所成的夹角（统一顺时针或者逆时针）”，读入新的指令之后，只需将指令转化为需要旋转的角度，然后转化为数字累加到当前的数字之上（若越界，则取模，实际意义是转过了一圈之后相当于角度-360°）。
这是我第一次遇到这种方法，有趣而且巧妙。
#include<bits/stdc++.h>
using namespace std;
int nowx=0,nowy=0;
int main(){
int N;
cin>>N;
string direction;
int dir=0; // 旋转角度 1代表顺时针旋转90°
int x;
while(N--){
cin>>direction>>x;
if(direction == "forward"){
dir = dir;
}
if(direction == "right"){
dir = (dir+1)%4;
}
if(direction == "back"){
dir = (dir+2)%4;
}
if(direction == "left"){
dir = (dir+3)%4;
}
switch(dir){
case 0:
nowx += x;
break;
case 1:
nowy -= x;
break;
case 2:
nowx -= x;
break;
case 3:
nowy += x;
break;
}
}
cout<<nowx<<" "<<nowy;
return 0;
} 13.表达式求值
stack的典型应用。
设立一个数字栈和一个运算符栈，扫描表达式之前在运算符栈内放入开始符，并在表达式串后加结束符（同一个）作为标记：
数字入栈
运算符与运算符栈顶元素比较优先级：
若当前运算符优先级大于栈顶运算符优先级，入栈；
否则栈顶运算符出栈，并与数字栈栈顶两个元素运算，将运算结果放入数字栈中，再次比较，直至遇到结束符。
对于比较运算符优先级，可以单独封装成一个函数。
#include<bits/stdc++.h>
using namespace std;
stack<char> ch;
stack<long long> n;
long long ans;
int len;
int priority(char si) {
int big = 0;// 当前运算符优先级大
char topch = ch.top();
if(si == '+' && topch =='#') {
big = 1;
}
if(si=='*' && topch =='#') {
big = 1;
}
if(si=='*' && topch=='+') {
big = 1;
}
return big;
}
int main() {
string s;
cin>>s;
ch.push('#');
//cout<<"s--->"<<s<<endl;
int num1,num2;
int temp =0;
char topch;
int numlen = 0;
for(int i=0; i<s.size(); i++) {
if(s[i]>='0' && s[i]<='9') {
temp = temp*10 + (s[i]-'0'); // 转换为数
} else {
// cout<<temp<<" "<<endl;
n.push(temp%10000); // 把数字入栈
temp = 0;
numlen = 0; // 数字长度初始化
// 遇到运算符, 如果当前优先级大于栈顶字符优先级，入栈
// 如果当前优先级小于等于栈顶运算符优先级，栈顶运算符出栈，数字栈出栈两个，运算后入栈
// 再次判断栈顶运算符与当前运算符的关系，重复上两步
while(!priority(s[i]) && ch.top()!='#'){
topch = ch.top();
ch.pop();
num1 = n.top()%10000;
n.pop();
num2 = n.top()%10000;
n.pop();
if(topch == '+') {
ans = num1+num2;
} else if( topch=='*') {
ans = num1*num2;
}
n.push(ans%10000);
}
ch.push(s[i]);
}
}
cout<<n.top()<<endl;
return 0;
}14.HZF爱斗牛
直接按题目条件模拟即可。
需要注意的是各种情况的优先级，优先级高的先判断，条件成立立即返回就好；对于几个数之和的问题，先判断3个数的和是不是10个的正数倍，再判断2个数的和是不是正数倍，因为当出现3个10相加的情况，会导致2个数判断已经符合条件返回了，但优先级更高的三个数还没有判断，从而WA。
15.显示屏输出
最后提交的代码438行…也是没谁了。
直接模拟。将数字从上到下拆分成5个部分。“行”方向上放大时，每个部分内部循环输出；“列”方向上放大时，将每一行看做一个整体，循环输出每一行，达到“列放大”的效果。然后直接循环，按行打印。
注意的点是字符的大小，一定要数清楚space的个数，不要弄混。
（番外：最后提交的时候，“看起来”我的输出和标准输出相同，但是还是“格式错误”，原因还是因为每行最后我多输出了一个space，计蒜客真的很严格）
16.得到整数X
二进制枚举
#include<bits/stdc++.h>
using namespace std;
int num[25];
int main(){
int n,X;
cin>>n>>X;
for(int i=0; i<n; i++){
cin>>num[i];
}
int sum = 0;
int ans = 0;
for(int i=0; i<(1<<n); i++){
// i对应的是二进制状态
// 共有000..0（n位）~111..1（n位）2^n种状态
// 每种状态中，1代表选中，0代表不选
sum = 0;
for(int j=0; j<n; j++){
// j为对应输入的数字的下标
if(i&(1<<j)){
// 从右边开始搜索，如果是1，代表这个数字被选中
sum += num[j];
}
}
if(sum==X){
ans++;
}
}
cout<<ans;
return 0;
} 17.幼儿园买玩具
二进制枚举
#include <bits/stdc++.h>
using namespace std;
struct s {
int num; // 第i个小朋友想玩的玩具数量
int toy[15];// 玩具编号
} kid[100];
int main(int argc, char const *argv[]) {
int n, m, k;
cin>>n>>m>>k;
for (int i = 0; i < n; ++i) {
cin>>kid[i].num;
for(int j=0; j<kid[i].num; j++) {
cin>>kid[i].toy[j];
}
}
int max=0;
for (int i = 0; i < (1<<k); ++i) {
int salenum=0; // i对应状态下，玩具店出售的数目
int saletoy[15]; // 标记玩具店出售的玩具
memset(saletoy,0,sizeof(saletoy));
for (int j = 0; j < k; ++j) {
if(i&(1<<j)) {
salenum++;
saletoy[j]=1;
}
int sum = 0; // 小朋友数目
for (int x = 0; x < n; ++x) {
int flag = 1;
for (int y = 0; y<kid[x].num; y++) {
if(saletoy[kid[x].toy[y]-1]==0) {
// 玩具店没有小朋友想要的玩具
flag = 0;
}
}
if(flag == 1) {
sum++;
}
}
if(sum>max && m>=salenum) {
max = sum;
}
}
}
cout<<max<<endl;
return 0;
}18.islands打炉石传说
二进制枚举
#include<bits/stdc++.h>
using namespace std;
struct card {
int cost; // 活力消耗
int d; // 卡牌种类
int attack; // 攻击力
} card[10];
int main() {
int n;
cin>>n;
for(int i=0; i<n; i++) {
cin>>card[i].cost>>card[i].d>>card[i].attack;
}
int max=0;
int attacksum;//攻击力
int mp; // 法力
bool flag; // 是否存在随从
for(int i=0; i<(1<<n); i++) {
mp = 10;
flag=false;
attacksum=0;
for(int j=0; j<n; j++) {
if(i&(1<<j)) {
if(card[j].d==0){
flag=true;
}
mp -= card[j].cost;
attacksum+=card[j].attack;
}
}
if(flag && attacksum>max && mp>=0) // 有随从&&攻击力大于max&&法力没耗尽
max=attacksum;
}
cout<<max;
return 0;
}
连续三道题，都考查二进制枚举。（什么是二进制枚举？）
1.什么时候采用二进制枚举？
（1）题目表述中要求查询某一集合的子集，并且这些子集往往都需要满足一些条件。比如，第16题中数字集合的子集需要满足和等于X，第17题中玩具集合的子集需要满足小朋友喜欢&&不超过最大数目m，第18题中卡牌集合的子集需要满足有随从&&攻击力最大&&法力没有耗尽。
（2）变量的数据范围较小，较容易列举其状态。比如，第16题中数字集合n的取值范围为[1,20]，第17题中玩具集合的元素取值范围为[1,15]，第18题中卡牌集合的取值范围为[1,10]。
2.个人对于二进制枚举的理解？
所谓二进制枚举，本质还是“枚举”，也是暴力解法的一种。“二进制”决定了这种枚举方法比较适合表达状态（因为每个二进制位只有0/1）两个表示与很多种状态都刚好符合。
for(int i=0; i<(1<<n); i++){
// code
}循环变量i的值表示每一种“枚举状态”。（1<<n）通过位运算移位表达式表示“枚举状态”的上限，即保证遍历上限的二进制位有n位，这样就保证了i的取值可以取遍000...0（n位）~11...1（n位）的所有状态。对于每个状态i，其二进制表达中，1/0又分别对应有/无等含义，因此每个i都是一种子集的组合，通过i的遍历，就可以取遍每一个子集。
for(int j=0; j<n; j++) {
if(i&(1<<j)) {
if(condition) {
// code
}
}
}
内层循环变量j表示“位数”，表达式（1<<j）的值只有最高位（第j+1位）为1，其余全是0，与枚举状态i按位与（&）的结果是判断i的二进制表达形式中，从右边数第j+1位是不是1，它的实际意义是“枚举状态”i所代表的子集中，从右边数第j+1位的状态（true/false）。j从0~n-1，就保证了i&（1<<j）刚好可以判断完i的每一位二进制位的状态，即判断完子集的状态。
有了子集的状态，在辅助以if（condition）进行标记，或者在一个子集的状态全部被判断完成之后，进行其他操作，便可以判断该子集是否满足要求，从而达到筛选子集的目的。
后话
终于算是勉强跟上了大佬们的脚步，也算是取得了一点点阶段性胜利，后面的路只会越来越难，应该做好付出更多、牺牲更多的准备
每个ACMer都任重道远。