问题 A: 多维下标向一维下标的换算
题目描述
多维数组的元素标识通常是用多维下标(i0, i1, i2, .., in-1)，而多维数组以顺序方式存储在内存中，内存的地址空间是一维的，要操作多维数组就需要计算从多维下标向一维下标的换算。
输入格式
输入的每一行为一个测试用例。
每一行由一组非负整数组成，第一个数是多维数组的维数n(211)，从第二个数开始的n个数是从高维到低维每一维的维长(120)，接着的n个数是一个n维下标。下标起始从0开始。
输出格式
对每一个测试样例，计算给定多维下标按行优向顺序对应的一维下标，并输出这个一维下标的值。每个测试样例输出一行。
输入样例
3 1 2 3 1 0 0
2 3 4 1 1
输出样例
6
5
AC代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n;
while(scanf("%d",&n)!=EOF){
ll sum=0;
int a[25],b[25];
ll flag=1;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
flag*=a[i];
}
for(int i=0;i<n;i++){
scanf("%d",&b[i]);
}
sum+=b[n-1];
flag/=a[0];
for(int i=0;i<n-1;i++){
sum+=b[i]*flag;
flag/=a[i+1];
}
printf("%lld\n",sum);
}
return 0;
}
**问题 B: 算法5-2：稀疏矩阵快速转置 **
题目描述
稀疏矩阵的存储不宜用二维数组存储每个元素，那样的话会浪费很多的存储空间。所以可以使用一个一维数组存储其中的非零元素。这个一维数组的元素类型是一个三元组，由非零元素在该稀疏矩阵中的位置（行号和列号对）以及该元组的值构成。
而矩阵转置就是将矩阵行和列上的元素对换。参考算法5.1中的具体做法，令mu和nu分别代表稀疏矩阵的行数和列数，不难发现其时间复杂度为O(mu×nu)。而当非零元的个数tu与mu×nu同数量级时，算法5.1的时间复杂度将上升至O(mu×nu2)。因此，需要采用快速的稀疏矩阵转置算法。
现在就请你实现一个快速的对稀疏矩阵进行转置的算法。以下是稀疏矩阵快速转置的算法描述：
输入格式
输入的第一行是两个整数r和c（r<300, c<300, r*c <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r行，每行有c个整数，用空格隔开，表示这个稀疏矩阵的各个元素。
输出格式
输出为读入的稀疏矩阵的转置矩阵。输出共有c行，每行有r个整数，每个整数后输出一个空格。请注意行尾输出换行。
输入样例
6 7
0 12 9 0 0 0 0
0 0 0 0 0 0 0
-3 0 0 0 0 14 0
0 0 24 0 0 0 0
0 18 0 0 0 0 0
15 0 0 -7 0 0 0
输出样例
0 0 -3 0 0 15
12 0 0 0 18 0
9 0 0 24 0 0
0 0 0 0 0 -7
0 0 0 0 0 0
0 0 14 0 0 0
0 0 0 0 0 0
AC代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int r, c;
scanf("%d%d", &r, &c);
int a[r + 5][c + 5];
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 0; i < c; i++) {
for (int j = 0; j < r; j++) {
printf("%d ", a[j][i]);
}
printf("\n");
}
return 0;
}
问题 C: 算法5-3：带行向量的稀疏矩阵相乘
题目描述
请使用带行向量的三元组法存储的稀疏矩阵，实现矩阵乘法。
本题为附加代码模式，以下代码会自动附加在提交的代码后面，请同学们注释之后提交
输入格式
输入的第一行是两个整数r1和c1（r1<200, c1<200, r1c1 <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r1行，每行有c1个整数，用空格隔开，表示第一个稀疏矩阵的各个元素。 之后的一行有两个整数r2和c2（c1=r2<200, c2<200, r2c2 <= 12500），分别表示一个包含很多0的稀疏矩阵的行数和列数。接下来有r2行，每行有c2个整数，用空格隔开，表示第二个稀疏矩阵的各个元素。
输出格式
输出两个矩阵的乘积。输出共有r1行，每行有c2个整数，每个整数后输出一个空格。请注意行尾输出换行。
输入样例
4 5
0 0 0 69 78
0 0 5 0 0
0 0 0 0 0
0 91 2 0 82
5 6
0 18 0 0 0 0
0 0 67 0 0 0
0 0 0 0 0 41
0 0 47 62 0 0
0 0 0 0 0 35
输出样例
0 0 3243 4278 0 2730
0 0 0 0 0 205
0 0 0 0 0 0
0 0 6097 0 0 2952
AC代码：
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
// 三元组结构体
struct TriNode{
// 行，列，值
int r,c,v;
};
// 输出单个非零元
void PrintTriNode(const TriNode& T){
cout << T.r << " " << T.c << " " << T.v << endl;
}
// 稀疏矩阵
struct TriMatrix{
// 行数，列数，非零元个数
int mu,nu,tu;
vector<TriNode> data; // 三元组法表示的非零元
vector<int> rsum; // 每行非零元个数
vector<int> rpos; // 行向量
};
void InputMatrix(TriMatrix& M){
cin >> M.mu >> M.nu;
M.tu = 0;
for(int i=0;i<M.mu;i++){
for(int j=0;j<M.nu;j++){
int t; cin >> t;
if(t != 0){
M.data.push_back({i,j,t});
M.tu++;
}
}
}
}
// 计算三元组法表示的稀疏矩阵的每行非零元个数和行向量
void CalcRPosMatrix(TriMatrix& M){
// 第一步：计算每行非零元个数
// 第二步：计算行向量
// 请同学们完成这个函数的功能
for(int i=0;i<M.mu;i++)M.rsum.push_back(0);
for(int i=0;i<M.tu;i++)M.rsum[M.data[i].r]++;
M.rpos.push_back(0);
for(int i=1;i<M.mu;i++)M.rpos.push_back(M.rsum[i-1]+M.rpos[i-1]);
}
// 输出三元组法表示的稀疏矩阵，用于辅助调试
void PrintMatrix(const TriMatrix& M){
cout << "================================================" << endl;
cout << "mu=" << M.mu << ",nu=" << M.nu << ",tu=" << M.tu << endl;
for(int i=0;i<M.tu;i++){
PrintTriNode(M.data[i]);
}
cout << "rsum:";
for(int i=0;i<M.mu;i++) cout << M.rsum[i] << " ";
cout << endl;
cout << "rpos:";
for(int i=0;i<M.mu;i++) cout << M.rpos[i] << " ";
cout << endl;
cout << "================================================" << endl;
}
// 用二维数组的形式输出三元组法表示的稀疏矩阵
void PrintMatrixArray(const TriMatrix& M){
int array[M.mu][M.nu] = {0};
for(int i=0;i<M.mu;i++){
for(int j=0;j<M.nu;j++){
array[i][j] = 0;
}
}
for(int i=0;i<M.tu;i++){
array[M.data[i].r][M.data[i].c] = M.data[i].v;
}
for(int i=0;i<M.mu;i++){
for(int j=0;j<M.nu;j++){
cout << array[i][j] << " ";
}
cout << endl;
}
}
// 三元组法表示的稀疏矩阵，添加非零元
void AddNode(TriMatrix& M, int r, int c, int v){
// 1、如果已存在行列相同的节点，追加值
// 2、否则，将该非零元按行优先的顺序找到合适的位置，插入节点
// 请同学们完成这个函数的功能
int flag=0;
for(int i=0;i<M.tu;i++){
if(M.data[i].r==r&&M.data[i].c==c){
M.data[i].v+=v;
flag=1;
}
}
if(flag==0){
M.data.push_back({r,c,v});
M.tu++;
}
}
// ！！！！！以下代码会自动附加，请同学注释之后提交
// 两个三元组法表示的矩阵相乘
TriMatrix Mul(const TriMatrix& M1, const TriMatrix& M2){
TriMatrix M;
M.mu = M1.mu; M.nu = M2.nu; M.tu = 0;
for(int i=0;i<M1.tu;i++){
int c = M1.data[i].c;
for(int j=M2.rpos[c];j<M2.rpos[c]+M2.rsum[c];j++){
AddNode(M,M1.data[i].r,M2.data[j].c,M1.data[i].v * M2.data[j].v);
}
}
return M;
}
int main(){
// freopen("/config/workspace/answer/test.in","r",stdin);
// freopen("/config/workspace/answer/test.out","w",stdout);
TriMatrix M1, M2;
InputMatrix(M1);
InputMatrix(M2);
CalcRPosMatrix(M1);
CalcRPosMatrix(M2);
// PrintMatrix(M1);
// PrintMatrix(M2);
TriMatrix M = Mul(M1,M2);
CalcRPosMatrix(M);
// PrintMatrix(M);
PrintMatrixArray(M);
return 0;
}
问题 D: 五子棋-五子连线
题目描述
在一个10行10列的棋盘上，有四颗棋子，需要你再增加一颗棋子，使得这五颗棋子连成一条连续的直线。
输入格式
输入包含一组测试数据，包括四行，每行是两个整数i和j（0<=i,j<=9），分别表示棋子的行和列。
输入保证再增加的棋子只有放在一个唯一的位置才能连成一条连续的直线。
输出格式
输出包括一行，两个整数，表示增加的棋子的行和列。
输入样例
0 0
0 1
0 3
0 4
输出样例
0 2
AC代码：
#include<bits/stdc++.h>
using namespace std;
struct node{
int r,c;
};
bool cmp(node a,node b){
if(a.r==b.r)return a.c<b.c;
return a.r<b.r;
}
int main(){
node a[4];
for(int i=0;i<4;i++){
scanf("%d%d",&a[i].r,&a[i].c);
}
sort(a,a+4,cmp);
if(a[0].r==a[1].r){//同行
for(int i=1;i<4;i++){
if(a[i-1].c+2==a[i].c){
printf("%d %d",a[i].r,a[i].c-1);
return 0;
}
}
if(a[0].c==0){
printf("%d 4",a[0].r);
return 0;
}else{
printf("%d 5",a[0].r);
return 0;
}
}else if(a[0].c==a[1].c){//同列
for(int i=1;i<4;i++){
if(a[i-1].r+2==a[i].r){
printf("%d %d",a[i].r-1,a[i].c);
return 0;
}
}
if(a[0].r==0){
printf("4 %d",a[0].c);
return 0;
}else{
printf("5 %d",a[0].c);
return 0;
}
}else if(a[0].c+a[0].r==a[1].c+a[1].r){//反斜
for(int i=1;i<4;i++){
if(a[i-1].r+2==a[i].r){
printf("%d %d",a[i].r-1,a[i].c+1);
return 0;
}
}
if(a[0].r==0){
printf("%d %d",a[3].r+1,a[3].c-1);
return 0;
}else{
printf("%d %d",a[0].r-1,a[0].c+1);
return 0;
}
}else if(a[0].c-a[0].r==a[1].c-a[1].r){//正斜
for(int i=1;i<4;i++){
if(a[i-1].r+2==a[i].r){
printf("%d %d",a[i].r-1,a[i].c-1);
return 0;
}
}
if(a[0].r==0){
printf("%d %d",a[3].r+1,a[3].c+1);
return 0;
}else{
printf("%d %d",a[0].r-1,a[0].c-1);
return 0;
}
}
return 0;
}
问题 E: 五子棋-AI对战
题目描述
ACM-ICPC程序设计方法与实践这门课就要结束了,然而还有很多人都没有机会写一个简单的五子棋对战AI
所以这题就是要你写一个五子棋的对战AI
不过由于五子棋本身没有一个标准解,难以评判对错
所以这题只需要你解决五子棋中最简单的一个问题,若当前轮到你落子,你需要判断你是否能够在这次落子后赢得这场比赛
输入格式
第一行一个整数T(T<100)代表有T组数据
每组数据第一行两个整数n,c(0<n<20),棋盘大小为n*n,若c为1则你是黑子,若c为2则你是白子
接下来n行每行一个长度为n的由012构成的字符串,0代表尚未落子,1代表黑子,2代表白子
数据保证当前棋盘上不存在超过四个同色棋子连线的情况
输出格式
对于每组数据,若你能在这次落子后赢得比赛则输出"YES",否则输出"NO"
输入样例
2
5 1
11110
22220
00000
00000
00000
5 1
11112
22200
00000
00000
00000
输出样例
YES
NO
tip:因为这道题写了挺久（不想让你们直接抄）， 简单讲一下做题思路，判断落子能否胜利，对于棋子来说，我分为横排、竖排、正斜（平行于正对角线）、反斜（平行于反对角线），而对于一排棋子，又可以分为三种情况：连续的四个，有一边贴着边界线，和不贴边界线；或者不连续。我将竖、正斜、反斜都转化为横排放入一个game1矩阵中，这样就只需要判断一排棋子的连续与否了。
AC代码：
#include <bits/stdc++.h>
using namespace std;
struct node {
int r, c, count, size;
};
int check(int game[25][25], node a[1005], int len) { //检查是否同行
int flag = 0;
for (int i = 0; i < len; i++) {
if (a[i].count == 4) { //连续4个
if (a[i].c == 3 && game[a[i].r][4] == 0 || a[i].c == a[i].size - 1 && game[a[i].r][a[i].size - 5] == 0) { //贴边
flag = 1;
break;
} else if (a[i].c != 3 && a[i].c != a[i].size - 1 && (game[a[i].r][a[i].c + 1] == 0
|| game[a[i].r][a[i].c - 4] == 0)) { //不贴边
flag = 1;
break;
}
} else if (i + 3 < len && a[i].count == 1 && a[i + 3].count == 3 && game[a[i].r][a[i].c + 1] == 0
|| i + 2 < len && a[i].count == 2 && a[i + 2].count == 2 && game[a[i].r][a[i].c + 1] == 0
|| i + 1 < len && a[i].count == 3 && a[i + 1].count == 1 && game[a[i].r][a[i].c + 1] == 0) { //不是连续四个
flag = 1;
break;
}
}
return flag;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, c, flag = 0, len = 0;
scanf("%d%d", &n, &c);
int game[25][25];
node a[1005];
//输入
for (int i = 0; i < n; i++) {
char s[25];
scanf("%s", s);
for (int j = 0; j < n; j++) {
game[i][j] = s[j] - '0';
}
}
//棋盘过小
if (n <= 4) {
printf("NO\n");
continue;
}
//检查行
a[0].count = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (game[i][j] == c) {
a[len].r = i;
a[len].c = j;
a[len].size = n;
if (a[len].r == a[len - 1].r && a[len].c == a[len - 1].c + 1) {
a[len].count = a[len - 1].count + 1;
} else {
a[len].count = 1;
}
len++;
}
}
}
flag = check(game, a, len);
//检查列
int game1[25][25];
if (flag == 0) {
a[0].count = 1;
len = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
game1[i][j] = game[j][i];//创建列矩阵，用于check函数
if (game[j][i] == c) {
a[len].r = i;
a[len].c = j;
a[len].size = n;
if (a[len].r == a[len - 1].r && a[len].c == a[len - 1].c + 1) {
a[len].count = a[len - 1].count + 1;
} else {
a[len].count = 1;
}
len++;
}
}
}
} else {
printf("YES\n");
continue;
}
flag = check(game1, a, len);
//检查正斜
memset(game1, 0, sizeof(game1));
if (flag == 0) {
a[0].count = 1;
len = 0;
for (int i = 0; i < n; i++) {//创建正斜矩阵，用于check函数
for (int j = 0; j < n; j++) {
if (abs(i - j) < n - 4) {
game1[n - 5 - j + i][min(i, j)] = game[i][j];
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (abs(i - j) < n - 4 && game[i][j] == c) {
a[len].r = n - 5 - j + i;
a[len].c = j;
a[len].size = n - abs(j - i);
if (a[len].r == a[len - 1].r && a[len].c == a[len - 1].c + 1) {
a[len].count = a[len - 1].count + 1;
} else {
a[len].count = 1;
}
len++;
}
}
}
} else {
printf("YES\n");
continue;
}
flag = check(game1, a, len);
//检查反斜
memset(game1, 0, sizeof(game1));
for (int i = 0; i < n; i++) {//创建反斜矩阵，用于check函数
for (int j = 0; j < n; j++) {
if (i + j >= 4 && i + j <= 2 * n - 6) {
if (i + j <= n - 1)
game1[i + j - 4][i] = game[i][j];
else
game1[i + j - 4][n - 1 - j] = game[i][j];
}
}
}
if (flag == 0) {
a[0].count = 1;
len = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i + j >= 4 && i + j <= 2 * n - 6 && game[i][j] == c) {
a[len].r = i + j - 4;
if (i + j <= n - 1)
a[len].c = i;
else
a[len].c = n - 1 - j;
a[len].size = i + j + 1;
if (a[len].r == a[len - 1].r && a[len].c == a[len - 1].c + 1) {
a[len].count = a[len - 1].count + 1;
} else {
a[len].count = 1;
}
len++;
}
}
}
} else {
printf("YES\n");
continue;
}
flag = check(game1, a, len);
if (flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
因为萌芽杯和可恶的最后一道题，现在才发出来😅
写作业创作不易，点个赞再走吧🥹
本文转载自: https://blog.csdn.net/weixin_73558212/article/details/133961834
版权归原作者 Solen.& 所有， 如有侵权，请联系我们删除。
版权归原作者 Solen.& 所有， 如有侵权，请联系我们删除。