被B题橄榄了🥺,菜枯
A. Make it Beautiful
一开始竟然没看到 ai > 0 😥.
令
如果a是ugly的，那么
即 si = 2si − 1
只需要使数列保证降序即可.
但是最大的两项可能相等，这样就会出现排完序后 a2 = a1.
需要将 a2 与后面一项小于 a2 的项交换，易证这时满足题意.
如果后面找不到比 a2
小的项，那么这时候整个数列每个元素都相等，那这个数列不可能变成beautiful.
AC代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
using namespace std;
typedef long long ll;
const int N=55;
int a[N],sum[N];
bool cmp(int a,int b)
{
return a>b;
}
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
sum[0]=0;
bool flag=false;
bool flag1=false;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
if(sum[i]==2*sum[i-1])
flag=true;
}
for(int i=2;i<=n;i++)
{
if(a[i]!=a[i-1])
flag1=true;
}
if(!flag1)
cout<<"NO"<<'\n';
else
{
cout<<"YES"<<'\n';
if(!flag)
{
for(int i=1;i<=n;i++)
cout<<a[i]<<' ';
cout<<'\n';
}
else
{
sort(a+1,a+1+n,cmp);
int j=2;
while(a[j]==a[j-1])
j++;
swap(a[j],a[2]);
for(int i=1;i<=n;i++)
cout<<a[i]<<' ';
cout<<'\n';
}
}
}
return 0;
}
B. Matrix of Differences
直觉上相邻格子的数的差肯定是可以遍历 1，2，...，n2 − 1 的，毕竟差有 n2 − 1 种，而相邻格子的差有 2(n−1)n 个，苹果数远大于抽屉数，很大概率是可以遍历 1，2，...，n2 − 1 的.
然后就是痛苦的构造了，我是这么构造的：
用两个指针，一个从1递增(记为p)，一个从n递减(记为q)；
奇数行从左向右构造，偶数行从右向左构造；
p和q交替出现.
如 n = 5时
下面证明这样的构造可以遍历所有差
将每一行的相邻两数差写出来，构成一个 (n−1) × (n−1) 的矩阵
距离完全遍历还差 jn(j=1,2,...,n−1)
计算第一列的纵向相邻差，观察第 i 行和第 i + 1 行的首位数的差 d 2 ∤ i 时，
综上，这样构造可以使相邻方格的差遍历 1, 2, ..., n2 − 1
AC代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
using namespace std;
typedef long long ll;
const int N=55;
int a[N][N];
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
int u=1,v=n*n;
int x=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i%2==1)
{
if(x)
a[i][j]=u++;
else
a[i][j]=v--;
}
else
{
if(x)
a[i][n+1-j]=u++;
else
a[i][n+1-j]=v--;
}
x^=1;
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<a[i][j]<<' ';
cout<<'\n';
}
}
return 0;
}