常见问题
输入输出
程序竞赛题目的特点是只做三件事：1. 读入数据。2. 计算结果 。3. 打印输出。所以竞赛中需要使用标准的输入输出方法，避免多余的信息。
标准输入输出
C语言的标准输入函数一般为 scanf() 或 gets() 或 getchar()
标准输出函数一般为 printf() 或 sprintf()
在本次比赛中，部分选手使用了 scanf_s() 函数，这个函数是微软开发的一个输入函数，主要是提高了程序的安全性，此函数不属于标准库中，因此比赛时无法使用。
同时，由于C语言需要指定输入输出的格式，相对C++而言更加繁琐，这也是算法竞赛中C++使用频率更高的原因之一，因此在后面的学习过程中，我们也会以C++为主。
多余的输入提示
在接收输入时不要输出相关的提示信息
错误示例
#include <stdio.h>
int main()
{
int a,b,c;
printf("请输入数字a:\n"); // 不要输出多余提示信息
scanf("%d",&a);
printf("请输入数字b:\n"); // 不要输出多余提示信息
scanf("%d",&b);
c = a+b;
printf("%d",c);
return 0;
}
正确示例
#include <stdio.h>
int main()
{
int a,b,c;
scanf("%d",&a);
scanf("%d",&b);
c = a+b;
printf("%d",c);
return 0;
}
多余的输出信息
在输出时同理，只需要输出计算结果，不需要输出其他信息，同时也不需要等待用户按键，直接结束程序即可。
错误示例
#include <stdio.h>
int main()
{
int a,b,c;
scanf("%d",&a);
scanf("%d",&b);
c = a+b;
printf("请输入数字b:%d",c); // 不要输出多余信息
system("pause"); // 不要让程序等待
return 0;
}
正确示例
#include <stdio.h>
int main()
{
int a,b,c;
scanf("%d",&a);
scanf("%d",&b);
c = a+b;
printf("%d",c);
return 0;
}
骗分
有点惊讶，在比赛过程中部分选手出现了”骗分“行为（“骗分”行为是中性的，可以算做一种技巧）。即，在程序设计题中通过输出固定答案来获取部分分数。
这在本次比赛中是不可行的，因为本次比赛的程序设计题均有多个测试用例，因为本次比赛使用的是ACM赛制：提交后反馈结果，需要通过全部用例。但蓝桥杯使用的是OI赛制：提交无反馈，根据通过的测试用例个数给分。（完整的ACM赛制要求选手编写一个完整的代码文件，而完整的OI赛制只要求选手编写一个函数即可。可以看出蓝桥杯其实是两者的结合，经考量后本次比赛使用了ACM赛制）
因此，“骗分”在蓝桥杯中是可行的。这意味着，对于一些难度较大的题目，可以先使用暴力解法，后续再进行修改。暴力解法或许无法通过数据规模较大的测试用例，但可以在那些数据规模小的测试用例上为你得分。
有趣的是，对于数据小又容易超时的题，有专门的打表法，本质就是”骗分“。打表就是将所有输入情况的答案保存在代码中，输入数据后直接输出就可以了。当然，这在蓝桥杯中也比较少见，感兴趣的选手可以自行了解。
参考代码
A：带宽
#include<iostream>
using namespace std;
int main()
{
cout<<500*8/200;
return 0;
}
蓝桥杯第一道结果填空题常常会对选手的计算机基础知识进行考察，本题主要考察 1Byte=8bit 这一知识点。
B：质数
#include<iostream>
#include<vector>
using namespace std;
vector<int> prime;
bool isPrime(int n)
{
for(int i=0;i<prime.size();i++)
{
if(n/prime[i]*prime[i]==n) return false;
}
prime.push_back(n);
return true;
}
int main()
{
int n=2022;
int i=1;
while(n>0)
{
i++;
if(isPrime(i)) n--;
}
cout<<i;
}
质数的判断等在蓝桥杯中也经常出现，只要进行遍历即可。这里用了prime数组作为记录，每次只要遍历小于自身的质数即可，这里的记录思想可用于动态规划算法的改进。
C：质数日期
#include <iostream>
#include<vector>
#include <unordered_map>
using namespace std;
int y, m, d;
int dom[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
unordered_map<int,int> c;
vector<int> prime;
int sum(int num)
{
int result = 0;
while(num)
{
result += num%10;
num /= 10;
}
return result;
}
bool isPrime(int n)
{
for(int i=0;i<prime.size();i++)
{
if(n/prime[i]*prime[i]==n) return false;
}
prime.push_back(n);
return true;
}
int main()
{
for(int i=0;i<50;i++)
{
if(isPrime(i))
{
c[i]=1;
}else
{
c[i]=0;
}
}
int result = 0;
y=2001;m=1;d=1;
while(true)
{
if(c[ sum(y)+sum(m)+sum(d) ]==1){result++;}
if(y==2022 && m==12 && d==04){break;}
if(++d>dom[m])
{
d=1;
if(++m>12)
{
m = 1;
y++;
if((y%4==0 && y%100!=0)||y%400==0)
{dom[2]=29;}
else
{dom[2]=28;}
}
}
}
cout<<result;
return 0;
}
日期模拟同样是经久不衰的经典模拟问题，具体对日期的操作上可能会有差别，但整体的框架是不变的。这里利用哈希表来记录质数，使得查寻某个数是否是质数时更加快捷。
D：签到
#include<iostream>
using namespace std;
int main()
{
string name;
cin>>name;
cout<<"Hello"<<name<<endl;
return 0;
}
考察对字符串的拼接，以及输入输出，可以看到C++对字符串的输入输出其实更加便捷一些。
E：迟到的选手
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
int main()
{
int m,n;
unordered_map<int,int> map;
vector<int> result;
cin>>n>>m;
for(int i=0;i<n;i++)
{
int k;
cin>>k;
map[k]=1;
}
for(int i=0;i<=m;i++)
{
if(map[i]==1) continue;
result.push_back(i);
}
for(int i=1;i<result.size()-1;i++)
{
cout<<result[i]<<" ";
}
cout<<result[result.size()-1];
return 0;
}
使用哈希表记录即可，同样可以用一个一维数组来记录。这种记录数组的思想在很多题目中都是适用的，如果数据规模非常大的话还会使用 bit-map 这样极端的方法，不过 bit-map 在蓝桥杯中其实不太常见。
F：拥堵的街道
#include<iostream>
#include<vector>
using namespace std;
int m,n;
vector<vector<int>> map;
int dp(int x, int y)
{
if(x==0&&y==0) return map[x][y];
if(x==0) return dp(x,y-1)+map[x][y];
if(y==0) return dp(x-1,y)+map[x][y];
return min(dp(x,y-1), dp(x-1,y))+map[x][y];
}
int main()
{
cin>>m>>n;
for(int i=0;i<m;i++)
{
vector<int> temp;
for(int j=0;j<n;j++)
{
int k;
cin>>k;
temp.push_back(k);
}
map.push_back(temp);
}
cout<<dp(m-1,n-1);
return 0;
}
典型的动态规划算法，可以看出转移函数为： $dp(x,y)=min(dp(x-1,y), dp(x,y-1))+map(x,y)$ 边界条件为： $dp(0,0)=map(0,0)$
这里使用了最原始的动态规划算法，代码更加清晰。感兴趣的同学可以试着修改成带备忘录的动态规划算法或者状态压缩动态规划算法
文章评论
666
厉害