CSDN竞赛24期题解
总结
本次竞赛的主要考点在于模拟，而且需要考虑的情况还蛮多，平时复杂点的模拟很少做，这次AC也花了挺长时间，后面还是需要夯实一下基础啊。
题目列表
1.计数问题
题目描述
试计算在区间 1 到 n 的所有整数中，数字 x(0 ≤ x ≤ 9) 共出现了多少次？例如，在 1 到 11 中，即在 1,2,3,4,5,6,7,8,9,10,11 中，数字 1 出现了 4 次。
输入描述：
2 个整数 n,x ，之间用一个空格隔开。
输出描述：
1 个整数，表示 x 出现的次数。
输入样例：
11 1
输出样例：
4
分析
理论上这题应该使用数位DP求解，考虑到是T1，暴力枚举足以解决。枚举下1到n的所有整数，分离出每一位，统计下出现x的次数即可。
代码
#include
#include
#include
#include
using namespace std;
int n,x;
int get(int t) {int q;int res = 0;while(t) {q = t % 10;if (q == x) res++;t /= 10;}return res;
}
int main() {cin>>n>>x;long long res = 0;for (int i = 1; i <= n; i++) {res += get(i);}cout< 2.小艺的英文名
题目描述
小艺酱想给自己起一个英文名字。
小艺酱想要装的自己学识渊博。
所以她想要自己英文名字必须满足：
1.只有字母表中前k个小写字母。
2.必须是回文串。
3.前k个小写字母每个字母至少出现一次。
小艺酱已经自己完成了部分空余的字母部分用’?’代替。
请你帮她完成她的英文名字。
输入描述：
第一行输入一个整数k。(1<=k<=26)
第二行输入小艺酱的英文名字name。(1<=strlen(name)<=1000)
输出描述：
如果小艺的名字不存在输出“QAQ”，
如果存在多组解，输出字典序最小的一个解。
输入样例：
2
a??a
输出样例：
abba
分析
本题乍一看挺难的，其实就是模拟题。
首先判断下有没有解，如果回文串中对应的两个字符不含?且不相等，说明解不存在。
如果其中的一方存在？，就用对应的字符替换它。
我们再来统计下剩下的?个数，由于是回文串，只需要考虑前半部分的问号个数即可，如果剩下的问号个数加上已出现的字母小于k，说明继续填充也不符合条件，也是无解的。
如果剩下的问号足以填充完前k个字符的空白，比如还剩3个字符没有出现，前半部分的问号有5处，出于字典序最小的考虑将前两处用’a’填充，后面自小到大的填充缺失的字符即可。
代码
#include
#include
#include
using namespace std;
bool m[30];
vector v;
int main() {int k;string name;cin>>k>>name;int n = name.size();bool flag = false;int n1 = (n + 1) / 2;for(int i = 0; i < n1; i++) {if(name[i] == '?') {if (name[n-1-i] != '?') {name[i] = name[n-1-i];m[name[i] - 'a'] = true;} else {v.push_back(i);}} else {if (name[n-1-i] == '?') name[n-1-i] = name[i];else {if (name[n-1-i] != name[i]) {flag = true;break;}}m[name[i] - 'a'] = true;}}if (flag) {cout<<"QAQ"<int cnt = 0;int si = v.size();vector tmp;for (int i = 0; i < k; i++) {if(!m[i]) {cnt++;tmp.push_back(i);}}if (cnt > si) {cout<<"QAQ"<for (int i = 0; i < si - cnt; i++) {name[v[i]] = name[n-1-v[i]] = 'a';}int p = 0;for (int i = si - cnt; i < si; i++) {name[v[i]] = name[n-1-v[i]] = 'a' + tmp[p++];}cout< 3.蛇形矩阵
题目描述
给你一个整数n，输出n∗n的蛇形矩阵。
输入描述：
输入一行，包含一个整数n
输出描述：
输出n行，每行包含n个正整数，通过空格分隔。
输入样例：
4
输出样例：
1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16
分析
虽然老早之前做过这题，但是许久没做还是花了不少时间。观察用例可以发现，矩阵数字的走向分为向右、向左下，向下以及向右上。其中向右或者向下方向至多走一步，左下和右上则需要走到头。如果使用一类方向向量，机械的重复最开始的几步，很容易出问题，因为一旦下一步不合法，要走的顺序就会乱掉，这里我使用了两类方向向量。
dx1和dy1来控制向右和向下，dx2和dy2来控制左下和右上。遍历规则如下：
第一类方向向量和第二类方向向量轮流走。
执行第一类向量，下一步合理则走到下一步，同时将控制权交给第二类向量。下一步不合理则第一类向量换个方向继续走，也就是向右走过头了就转而向下走。
执行第二类向量，下一步合理就继续走，一直走到下一步不合理时，将下一步的控制权交给第一类向量。
有一点需要注意，最后一个数字不一定在右下角，所以如果使用坐标作为结束遍历的条件可能会死循环。CSDN这类题目一旦出现一个用例TLE，是没有分数的，所以还是用元素个数作为结束条件比较靠谱。
代码
#include
#include
#include
#include
using namespace std;
const int N = 105;
int g[N][N];
int dx1[] = {0, 1};
int dy1[] = {1, 0};
int dx2[] = {1, -1};
int dy2[] = {-1, 1};
int main() {int n;std::cin>>n;int p = 2;g[0][0] = 1;int x = 0, y = 0;int nx = 0, ny = 0;int p1 = 0,p2 = 0;int t = 1;while(true) {if (t) {nx = x +dx1[p1], ny = y + dy1[p1];} else {nx = x + dx2[p2], ny = y + dy2[p2];}if (nx < 0 || nx >= n || ny < 0 || ny >= n) {if (t) p1 = 1 - p1;else {p2 = 1- p2;t = 1 - t;}continue;}if (t) {t = 1 - t;p1 = 1 - p1;}x = nx, y = ny;g[x][y] = p++;if (p - 1 == n * n) break;}for (int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {cout< 4.放货物
题目描述
小明是一名快递员，他现在手上一共有N个快件需要运送。但是货车有限，所以我们希望用最少的货车来进行工作。现在已知，一辆车的限定额度为最多放置K件货物。此外，小明很不喜欢13这个数字，所以他不希望任何一辆货车中的货物数量为13。
现在小明想要知道，最少使用多少辆货车能够将这N个快件都放置到货车上。
输入描述：
题目包含多组输入
每一组输入一行两个数，分别表示N 和 K
1<=N<=1000
1<=K<=1000
输出描述：
输出一行一个数字，表示最优结果。
输入样例：
13 13
5 2
输出样例：
2
3
分析
貌似是第三期竞赛的原题，这竞赛不出新题也就算了，题目与以往竞赛重复就没啥意思了。本题需要细心的分类讨论。
如果每辆货车的限额k是13，那么我们每辆只放12个，即k–;
满打满算可以先放完n / k辆车，还剩n % k个货物，如果剩下的货物是0，就不需要增加货车了；如果剩下的货物不是13，就放一辆车装；如果剩下的货物是13，原则上也可以放一辆车上，只需要从前面车上再拿一个货物过来，让最后一辆车上数量变成14即可，但是前提是k不为14，否则前面的车上拿掉一个数量就变成13了，拿掉2个最后一辆车就变成15超载了，这种情况就需要放两辆车上了。当然也需要考虑货物总数恰好是13个的情况，这样只能放两辆车。
PS：既然讨厌13这个数字，仅仅每辆车不装13个货物哪够，要是货车总数是13不更闹心嘛。
代码
#include
#include
#include
#include
using namespace std;
int main() {int n, k;while(cin>>n>>k) {if (n == 13 && k >= 13) {cout<<2<