PAT乙群1050.螺旋行列の構想と注意点--『アルゴリズムノート』を補充する
B1050
タイトルリンク
個人的な考え方.
明らかに复雑なシミュレーション问题の个人の考え方とコードの考え方がまだ足りないと感じて、まずテーマを手に入れてまず螺旋式の书き込み行列を考えてから出力して、それから出力して、行列を书かないことができますか?まず各行の出力の规则を见つけて、直接行の出力によって半日考えて、答えの考え方を见てから上下左右の4つの境界を书いて、境界に着いてから境界を更新して、方向を変えて答えを参考にした後素数直接並べ替え出力、そうでなければ適切なm,n を見つける cnt要素カウンタはwhileのサイクル条件 として機能する. dirは現在の記入方向 を示す.異なる方向が境界に達する前に正常に処理し、そうでなければ(このステップから、構想がはっきりしない)4.1.境界4.2を更新するのは初めて境界に着いたと判断して、相応の処理をして、さもなくば****4.2.1.判断は完全な平方数m==nで、相応の処理をして、さもなくば****4.2.2.相応の処理をする.方向転換 個人構想コード
N=39以前の出力が正しいことを保証し、テストポイントに最初に素数に気づかなかった場合、m=N、n=1であるべきである.
本題の考え方
いくつか参考になるところがあります特判N==1 コード中にreturn 0 を繰り上げることができるサイクル体中のi++,j++は内層の左上隅位置を返す.この一歩はちょっと神々しい
ACコード
タイトルリンク
個人的な考え方.
明らかに复雑なシミュレーション问题の个人の考え方とコードの考え方がまだ足りないと感じて、まずテーマを手に入れてまず螺旋式の书き込み行列を考えてから出力して、それから出力して、行列を书かないことができますか?まず各行の出力の规则を见つけて、直接行の出力によって半日考えて、答えの考え方を见てから上下左右の4つの境界を书いて、境界に着いてから境界を更新して、方向を変えて答えを参考にした後
N=39以前の出力が正しいことを保証し、テストポイントに最初に素数に気づかなかった場合、m=N、n=1であるべきである.
#include
", num[i]);
}
}
else//
{
init();
int cnt = 0, i = 1, j = 1;
int dir = 3;//0: ，1： ，2： ，3：
bool isfirR = true, isfirD = true, isfirL = true;
while(cnt < N)
{
matrix[i][j] = num[cnt++];
if(dir == 3)//
{
if(j < R)
{
j++;
}
else// j == R
{
R--;
if(isfirR)
{
j++;
isfirR = false;
}
else
{
if(m == n)
j++;
else
i++;
}
dir = 1;
}
}
else if(dir == 1)//
{
if(i < D)
{
i++;
}
else// j == D
{
D--;
if(isfirD)
{
i++;
isfirD = false;
}
else
{
if(m == n)
i++;
else
j--;
}
dir = 2;
}
}
else if(dir == 2)//
{
if(j > L)
{
j--;
}
else// j == L
{
L++;
if(isfirL)
{
j--;
isfirL = false;
}
else
{
if(m == n)
j--;
else
i--;
}
dir = 0;
}
}
else if(dir == 0)//
{
if(i > U)
{
i--;
}
else// i == U
{
U++;
dir = 3;
j++;
}
}
}
for(int x = 1; x <= m; ++x)
{
for(int y = 1; y <= n; ++y)
{
printf("%d", matrix[x][y]);
if(y < n)
printf(" ");
else
printf("
");
}
}
}
return 0;
}
本題の考え方
いくつか参考になるところがあります
ACコード
#include
", A[0]);
return 0;
}
sort(A, A + N, cmp);
// m,n
int m = (int)ceil(sqrt(1.0 * N));
while(N % m != 0)
{
m++;
}
int n = N / m;
int i = 1, j = 1, pos = 0;
int U = 1, D = m, L = 1, R = n;
while(pos < N)
{
while(pos < N && j < R)//
{
matrix[i][j] = A[pos++];
j++;
}
while(pos < N && i < D)
{
matrix[i][j] = A[pos++];
i++;
}
while(pos < N && j > L)
{
matrix[i][j] = A[pos++];
j--;
}
while(pos < N && i > U)
{
matrix[i][j] = A[pos++];
i--;
}
U++, D--, L++, R--;//
i++, j++;//
if(pos == N - 1)
{
matrix[i][j] = A[pos++];
}
}
for(int i = 1; i <= m; ++i)
{
for(int j = 1; j <= n; ++j)
{
printf("%d", matrix[i][j]);
if(j < n)
printf(" ");
else
printf("
");
}
}
return 0;
}