【补题系列】2020USST算法竞赛练习场7
题解
题意：构造出一个n行m列的矩阵，其中有k个元素是‘’nice‘’的，一个元素是“nice”的当且仅当这个元素等于上下左右四个元素的和
算法：想象力
可以想象，一开始矩阵全是0，则nice的元素个数为(n-2)*(m-2)，我们从第一行第二列开始一次往后填1（或别的数），就会使得nice数减少1
需要特判一下从第二行往后的第二列的数为1而第三列不为1的情况（是nice的），因此需要把这一行的第一列置为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
46
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[20][20];
int main(){
int t;cin>>t;
while(t--){
memset(a,0,sizeof(a));
int n,m,k;
cin>>n>>m>>k;
int tot=(n-2)*(m-2)-k;
a[1][1]=0;
for(int j=2;j<m;j++){
if(tot>0){
a[1][j]=1;
tot--;
}else{
a[1][j]=0;
}
}
a[1][m]=0;
for(int i=2;i<=n;i++){
for(int j=2;j<m;j++){
if(tot>0){
a[i][j]=1;
tot--;
}else{
a[i][j]=0;
}
}
}
for(int i=2;i<=n;i++){
if(a[i][2]==1&&a[i][3]==0){
a[i][1]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j!=m) cout<<a[i][j]<<" ";
else cout<<a[i][j]<<endl;
}
}
}
return 0;
}
|
题意：定义一个数列$ti=\frac{1}{2}i(i+1)$，给定N，求满足$t{\tau}$为完全平方数且$\tau \geq N$的最小的$\tau$
算法：打表
首先暴力打表观察一下规律
| i |
t_i |
| 1 |
1 |
| 8 |
36 |
| 49 |
1225 |
| 288 |
41616 |
| … |
… |
发现每个$t_i$可以拆分成两个数的平方数，且第一个数等于上一个$t_i$的两个数之和，第二个数根据奇偶性来判断，然后就有了如下打表程序
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
freopen("biao.out","w",stdout);
ll a=1,b=1;
for(int i=1;i<=50;i++){
if(i&1){
ll giao=(a+b)*(a+b)*2;
b=giao+1;
a=giao/2;
cout<<b-1<<","<<endl;
b=sqrt(b);
a=sqrt(a);
}else{
ll giao=(a+b)*(a+b)*2;
b=giao-1;
a=giao/2;
cout<<b<<","<<endl;
b=sqrt(b);
a=sqrt(a);
}
}
return 0;
}
|
然后就可以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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[21]={
1,
8,
49,
288,
1681,
9800,
57121,
332928,
1940449,
11309768,
65918161,
384199200,
2239277041,
13051463048,
76069501249,
443365544448,
2584123765441,
15061377048200,
87784138523761,
511643454094368,
2982076586042449
};
int main(){
int t ;
cin>>t;
for(int o=1;o<=t;o++){
ll n;
scanf("%lld",&n);
if(n>a[20]){
cout<<-1<<endl;
continue;
}
for(int i=0;i<21;i++){
if(a[i]>=n){
printf("Case #%d: %lld\n",o,a[i]);
break;
}
}
}
return 0;
}
|