NC244816. 俄罗斯方块
描述
输入描述
第一行一个整数n(1≤n≤200)，表示等腰直角三角形的边长
输出描述
如可以填充，第一行输出"YES"，接下来n行输出任一可行方案第i行输出i个以空格分隔的整数，同一俄罗斯方块用4个相同整数表示。整数须从1开始依次使用，不可重复不可遗漏（可参考样例2，使用整数1-7）如不能填充，输出一行"NO"（输出均不包含引号）
示例1
输入:
4
输出:
NO
示例2
输入:
7
输出:
YES 1 1 1 1 2 2 3 2 2 4 3 3 4 4 4 3 5 6 6 6 7 5 5 5 6 7 7 7
pypy3 解法, 执行用时: 100ms, 内存消耗: 22796K, 提交时间: 2023-03-29 12:43:49
s7 = '''1
1 1
1 2 2
3 2 2 4
3 3 4 4 4
3 5 6 6 6 7
5 5 5 6 7 7 7'''
s8 = '''1
1 1
1 2 2
3 2 2 4
3 3 4 4 4
3 5 5 5 6 6
7 7 5 8 6 6 9
7 7 8 8 8 9 9 9'''
a8 = '''1 1 2 2 3 3 4 4
1 1 2 2 3 3 4 4
5 5 6 6 7 7 8 8
5 5 6 6 7 7 8 8
9 9 10 10 11 11 12 12
9 9 10 10 11 11 12 12
13 13 14 14 15 15 16 16
13 13 14 14 15 15 16 16'''
s7 = s7.split("\n")
for i in range(len(s7)):
s7[i] = list(map(int, s7[i].split()))
s8 = s8.split("\n")
for i in range(len(s8)):
s8[i] = list(map(int, s8[i].split()))
a8 = a8.split("\n")
for i in range(len(s8)):
a8[i] = list(map(int, a8[i].split()))
n = int(input())
if n % 8 != 0 and n % 8 != 7:
print("NO")
exit(0)
print("YES")
def add(a, b, idx):
n = len(a)
m = len(b)
res = 0
for i in range(m):
a[i-m] += [i+idx for i in b[i]]
res = max(res, max(b[i]))
return res + idx
ans = []
if(n % 8 == 0) :
t = n // 8
now = 0
for i in range(t):
for j in range(8):
ans.append([])
for j in range(i):
now = add(ans,a8, now)
now = add(ans, s8, now)
else:
t = n // 8 + 1
now = 0
for i in range(t):
for j in range(8 if i != 0 else 7):
ans.append([])
for j in range(i):
now = add(ans,a8, now)
now = add(ans, s7, now)
for i in ans:
print(" ".join(list(map(str, i))))
C++(clang++ 11.0.1) 解法, 执行用时: 5ms, 内存消耗: 1060K, 提交时间: 2022-10-24 16:06:57
#include<iostream>
#include<stdio.h>
using namespace std;
const long long base[3][9][9]=
{
{
{1},
{1,1},
{1,2,2},
{3,2,2,4},
{3,3,5,4,4},
{3,5,5,4,6,6},
{7,7,5,8,6,6,9},
{7,7,8,8,8,9,9,9}
},
{
{1},
{1,1},
{1,2,2},
{3,2,2,4},
{3,3,4,4,4},
{3,5,6,6,6,7},
{5,5,5,6,7,7,7},
{}
},
{
{1,1,2,2,3,3,4,4},
{1,1,2,2,3,3,4,4},
{5,5,6,6,7,7,8,8},
{5,5,6,6,7,7,8,8},
{9,9,10,10,11,11,12,12},
{9,9,10,10,11,11,12,12},
{13,13,14,14,15,15,16,16},
{13,13,14,14,15,15,16,16}
}
};
long long n,i,j,answer[350][350],k;
void triangle (long long x,long long y)
{
for (long long j=0;j<8;j++)
for (long long k=0;k<8;k++)
answer[x+j][y+k]=i+base[n&1][j][k];
i+=9-((n&1)<<1);
}
void square (long long x,long long y)
{
for (long long j=0;j<8;j++)
for (long long k=0;k<8;k++)
answer[x+j][y+k]=i+base[2][j][k];
i+=16;
}
int main ()
{
scanf("%lld",&n);
if (n&7&&7-(n&7))
puts("NO");
else
{
puts("YES");
for (j=1;j<=n;j+=8)
triangle(j,j);
for (j=9-(n&1);j<=n;j+=8)
for (k=8;k<=j;k+=8)
square(j,k-7);
for (j=1;j<=n;j++)
for (k=1;k<=j;k++)
printf(j>k?"%lld ":"%lld\n",answer[j][k]);
}
}
C++(g++ 7.5.0) 解法, 执行用时: 5ms, 内存消耗: 772K, 提交时间: 2022-11-01 18:00:07
#include<bits/stdc++.h>
using namespace std;
int cnt;
int a[333][333];
int d7[7][7]={
{0},
{0,0},
{0,1,2},
{1,1,2,2},
{4,1,2,3,3},
{4,4,5,3,3,6},
{4,5,5,5,6,6,6}
};
int d8[8][8]={
{0},
{0,0},
{0,1,1},
{2,1,1,3},
{2,2,4,3,3},
{2,4,4,3,5,5},
{6,6,4,7,5,5,8},
{6,6,7,7,7,8,8,8}
};
int main()
{
int n;
scanf("%d",&n);
if(n%8!=0&&n%8!=7){
puts("NO");
return 0;
}
puts("YES");
cnt=1;
if(n%8==7){
for(int z=1;z<=n;z+=8){
for(int i=0;i<7;i++){
for(int j=0;j<=i;j++){
a[i+z][j+z]=d7[i][j]+cnt;
}
}
cnt+=7;
}
}else{
for(int z=1;z<=n;z+=8){
for(int i=0;i<8;i++){
for(int j=0;j<=i;j++){
a[i+z][j+z]=d8[i][j]+cnt;
}
}
cnt+=9;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
if(!a[i][j]){
a[i][j]=cnt;
a[i+1][j]=cnt;
a[i][j+1]=cnt;
a[i+1][j+1]=cnt++;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
printf("%d%c",a[i][j]," \n"[j==i]);
}