学习C++从娃娃抓起！记录下CSP-J备考学习过程中的题目，记录每一个瞬间。
附上汇总贴：历年CSP-J初赛真题解析 | 汇总_热爱编程的通信人的博客-CSDN博客
矩阵变幻
有一个奇幻的矩阵，在不停的变幻，其变幻方式为：数字0变成矩阵 [ 0 0 0 1 ] \begin{bmatrix} 0&0\\ 0&1\end{bmatrix} [0001]，数字1变成矩阵 [ 1 1 1 0 ] \begin{bmatrix} 1&1\\ 1&0\end{bmatrix} [1110]
最初矩阵只有一个元素0，变幻n次后，矩阵会变成什么样？
例如，矩阵最初为[0]；变幻1次后： [ 0 0 0 1 ] \begin{bmatrix} 0&0\\ 0&1\end{bmatrix} [0001]；变幻2次后： [ 0 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 ] \begin{bmatrix} 0&0&0&0\\ 0&1&0&1\\ 0&0&1&1\\ 0&1&1&0\end{bmatrix} 0000010100110110
输入一行一个不超过10个正整数n，输出变幻n次后的矩阵。试补全程序。
提示："<<"表示二进制左移运算符，例如 ( 11 ) 2 < < 2 = ( 1100 ) 2 (11)_2<<2 = (1100)_2 (11)2<<2=(1100)2
#include <cstdio>
using namespace std;
int n;
const int max_size = 1 << 10;
int res[max_size][max_size];
void recursive(int x, int y, int n, int t) {
if (n==0) {
res[x][y] = __1__;
return;
}
int step = 1 << (n-1);
recursive(__2__, n-1, t);
recursive(x, y+step, n-1, t);
recursive(x+step, y, n-1, t);
recursive(__3__; n-1, !t);
}
int main()
{
scanf("%d", &n);
recursive(0, 0, __4__);
int size = __5__;
for (int i=0; i<size; ++i) {
for (int j=0; j<size; ++j)
printf("%d", res[i][j]);
put("");
}
return 0;
}
第34题
1处应该填（ ）。
A.n%2
B.0
C.t
D.1
【答案】：C
【解析】
填入res[x][y]的值，不可能全为0或全为1，只能为t
第35题
2处应该填（ ）。
A.x-step, y-step
B.x, y-step
C.x-step, y
D.x, y
【答案】：D
【解析】
左上角就是原来的坐标
第36题
3处应该填（ ）。
A.x-step, y-step
B.x+step, y+step
C.x-step, y
D.x, y-step
【答案】：B
【解析】
右下角左边，所以x+step，y+step
第37题
4处应该填（ ）。
A.n-1, n%2
B.n, 0
C.n, n%2
D.n-1, 0
【答案】：B
【解析】
可以带入n,0和n,1，观察结果发现n,0为正确答案
第38题
5处应该填（ ）。
A.1<<(n+1)
B.1<<n
C.n+1
D.1<<(n-1)
【答案】：B
【解析】
1的边长是2，2的边长是4，n的边长是 2 n 2^n 2n，即1<<n
计数排序
计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将n对10000以内的整数，从小到大排序。
例如有三对整数(3,4)、(2,4)、(3,3)，那么排序之后应该是(2,4)、(3,3)、(3,4)。
输入第一行为n，接下来n行，第i行有两个数a[i]和b[]，分别表示第i对正整数的第一关键字和第二关键字。
从小到大排序后输出。数据范围 1 ≤ n ≤ 1 0 7 , 1 ≤ a [ i ] , b [ i ] ≤ 1 0 4 1\le n\le 10^7, 1\le a[i],b[i]\le 10^4 1≤n≤107,1≤a[i],b[i]≤104
提示：应先对第二关键字排序， 再对第一关键字排序。数组ord[]存储第二关键字排序的结果， 数组res[]存储双关键字排序的结果。
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;
int n;
unsigned a[maxn], b[maxn], res[maxn], ord[maxn];
unsigned cnt[maxs+1];
int main()
{
scanf("%d", &n);
for (int i=0; i<n; ++i)
scanf("%d%d", &a[i], &b[i]);
memset(cnt, 0, sizeof(cnt));
for (int i=0; i<n; ++i)
__1__; // 利用cnt数组统计数量
for (int i=0; i<maxs; ++i)
cnt[i+1] += cnt[i];
for (int i=0; i<n; ++i)
__2__; // 记录初步排序结果
memset(cnt, 0, sizeof(cnt));
for (int i=0; i<n; ++i)
__3__; // 利用cnt数组统计数量
for (int i=0; i<maxs; ++i)
cnt[i+1] += cnt[i];
for (int i=n-1; i>=0; --i)
__4__; // 记录最终排序结果
for (int i=0; i<n; ++i)
printf("%d %d\n", __5__);
return 0;
}
第39题
1处应该填（ ）。
A.++cnt[i]
B.++cnt[b[i]]
C.++cnt[a[i] * max + b[i]]
D.++cnt[a[i]]
【答案】：B
【解析】
因为要先对第二关键字（b[i]）排序，所以选B
第40题
2处应该填（ ）。
A.ord[–cnt[a[i]]] = i
B.ord[–cnt[b[i]]] = a[i]
C.ord[–cnt[a[i]]] = b[i]
D.ord[–cnt[b[i]]] = i
【答案】：D
【解析】
第20行是为了计算cnt[b[i]]的前缀和，即每个b[i]数字的排名，所以A、C错误
ord[x]记录第x名所对应的下标
第41题
3处应该填（ ）。
A.++cnt[b[i]]
B.++cnt[a[i] * maxs + b[i]]
C.++cnt[a[i]]
D.++cnt[i]
【答案】：C
【解析】
统计第1关键字，所以选C
第42题
4处应该填（ ）。
A.res[–cnt[a[ord[i]]]] = ord[i]
B.res[–cnt[b[ord[i]]]] = ord[i]
C.res[–cnt[b[i]]] = ord[i]
D.res[–cnt[a[i]]] = ord[i]
【答案】：A
【解析】
这题的排序思路：十位数相同的个位数大的先放，在对应的十位数区间从后向前放
第28行之前ord[]={21,31,11,32,122,22}
倒序查找ord[5]为22，a[22]为2，cnt[2]为4，先–cnt[2]得3，然后res[3]=ord[5]=22，即把22放到res数组中下标为3的位置。
依此类推，最后res[]={11,12,21,22,31,32}
第43题
5处应该填（ ）。
A.a[i], b[i]
B.a[res[i]], b[res[i]]
C.a[ord[res[i]]], b[ord[res[i]]]
D.a[res[ord[i]]], b[res[ord[i]]]
【答案】：B
【解析】
res[i]记录第i个数的在原序列的位置。且a、b数组内容必然成对输出，下标必须一致，也可以简单猜测选B
标签：cnt,真题,int,res,初赛,step,ord,排序,CSP From： https://blog.csdn.net/guolianggsta/article/details/143475691