2023 春季测试 题解
幂次
这道题写了暴力，但是超时了。这道题难度还行，来分析一下。首先很显而易见，当
k
≥
3
k≥3
k≥3时，是可以通过枚举底数来暴力解决的。定义
a
a
a作为底数，定义
b
b
b作为指数。通过
w
h
i
l
e
while
while循环每次枚举
a
a
a的
b
b
b次方
(
b
≥
2
)
(b≥2)
(b≥2)，外部通过循环枚举
a
a
a。
我们首先需要特判一下，如果k=1，那么答案一定是n，直接输出即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int> vis;
int cnt=0;
signed main(){
int n,k;
cin>>n>>k;
if(k==1){//不用说了吧
cout<<n;
return 0;
}
int a,b;
for(int i=2;i*i*i<=n;i++){//枚举底数，只看3次方就够了
a=i*i;
b=2;
while(a<=n/i){
a*=i,b++;
if(vis[a]){//已经有了
continue;
}
if(b<k){//次数不够
continue;
}
vis[a]=1;
cnt++;
}
}
if(k>=3){
cout<<cnt+1;//加1，因为1没有被判断过
return 0;
}
return 0;
}
接下来我们要考虑怎样找平方数：
我们知道，n个数里，有
n
\sqrt{n}
n个平方数，其中肯定有与可以表示成其他方式的表示方法，所以我们需要特判一下，来将多余的答案记录下来，最后减去即可。
if((int)sqrtl(a)*(int)sqrtl(a)==a){
sum++;
}
c o d e code code
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int> vis;
int cnt=0;
int sum=0;
signed main(){
int n,k;
cin>>n>>k;
if(k==1){
cout<<n;
return 0;
}
int a,b;
for(int i=2;i*i*i<=n;i++){//枚举底数，只看3次方就够了
a=i*i;
b=2;
while(a<=n/i){
a*=i,b++;
if(vis[a]){//已经有了
continue;
}
if(b<k){//次数不够
continue;
}
if((int)sqrtl(a)*(int)sqrtl(a)==a){
sum++;
}
vis[a]=1;
cnt++;
}
}
if(k>=3){
cout<<cnt+1;//加1，因为1没有被判断过
return 0;
}
cout<<(int)sqrtl(n)+cnt-sum;
return 0;
}
涂色游戏
这道题还是挺简单的，我们知道一个格子的颜色是由他的行和列决定的，由于是先后涂色，所以我们用结构体记录每一行或者每一列的颜色，我们还需要记录每一行或者每一列叠加的时间，最终每个格子的颜色是由叠加的时间决定的，我们需要枚举
t
，
q
t，q
t，q。由于时间复杂度不是很大，还能接受，所以我们可以直接输出。
c
o
d
e
code
code
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct maxtr{
int ys,tt;
}h[maxn],l[maxn];
int t,n,m,q;
int main(){
scanf("%d",&t);
for(int k=1;k<=t;k++){
scanf("%d%d%d",&n,&m,&q);
memset(h,0,sizeof h);
memset(l,0,sizeof l);
for(int j=1;j<=q;j++){
int op,a,b;
scanf("%d%d%d",&op,&a,&b);
if(op==0){
h[a].ys=b;
h[a].tt=j;
}
if(op==1){
l[a].ys=b;
l[a].tt=j;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
if(h[i].tt>l[j].tt){
cout<<h[i].ys<<" ";
}else{
cout<<l[j].ys<<" ";
}
cout<<endl;
}
}
return 0;
}
圣诞树
我想，我有生之年怕是不会活到3202年的圣诞节了哎，不装了，我摊牌了，我是修道者，但我不过圣诞节，大家要相信科学哦
题意：给你一个平面上的
n
n
n个点的凸包，求 TSP 路线，即从最高点出发并遍历所有点的最短的路径。
n
≤
1000
。
n\le 1000。
n≤1000。
来看思路：
结论：路线不会交叉。
证明：因为凸四边形对角线长度和一定大于一组对边的长度和，所以如果
(
i
,
j
)
(i,j)
(i,j)与
(
a
,
b
)
(a,b)
(a,b)交叉，我们将这两条分别更换为
(
i
,
a
)
(i,a)
(i,a)和
(
j
,
b
)
(j,b)
(j,b)答案一定变小。
对于随意一条路径，我们使用调整法，每次随便选一组交叉的边调整至不交叉，一定可以调整到整条路径不交叉。因为每次调整都会使路径长度变短，所以调整次数有限并不会调整回之前的状态。
我们从最高点开始按顺时针给每个点重新编号，为了方便，
0
0
0号和
n
n
n号点都是最高点。由于路线不会交叉，所以时时刻刻没有被遍历过的结点的新编号都是一段连续的区间。
考虑设计 dp，令
f
l
,
r
,
0
/
1
f_{l,r,0/1}
fl,r,0/1表示
[
l
+
1
,
r
−
1
]
[l+1,r-1]
[l+1,r−1]还没有被遍历，上一个遍历的结点是
l
/
r
l/r
l/r时的最短路径。初始状态
f
0
,
n
,
0
=
f
0
,
n
,
1
=
0
，
f_{0,n,0}=f_{0,n,1}=0，
f0,n,0=f0,n,1=0，一次转移就是
f
l
,
r
,
1
=
min
(
f
l
,
r
+
1
,
0
+
dis
(
l
,
r
)
,
f
l
,
r
+
1
,
1
+
dis
(
r
,
r
+
1
)
)
f_{l,r,1}=\min(f_{l,r+1,0}+\text{dis}(l,r),f_{l,r+1,1}+\text{dis}(r,r+1))
fl,r,1=min(fl,r+1,0+dis(l,r),fl,r+1,1+dis(r,r+1))
要输出方案就记录一下决策就好了。
c
o
d
e
code
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
const int N = 1e3 + 10;
const ld INF = 1e18;
int n, k, g[N][N][2], p[N];
ld px[N], py[N], f[N][N][2];
inline ld sqr(ld x) {
return x * x;
}
inline ld dis(int x, int y) {
return sqrt(sqr(px[p[x]] - px[p[y]]) + sqr(py[p[x]] - py[p[y]]));
}
inline void answer(int l, int r, int t) {
if (l < 0 || r > n) return ;
if (t == 0) {
if (g[l][r][0]) answer(l - 1, r, 1);
else answer(l - 1, r, 0);
} else {
if (g[l][r][1]) answer(l, r + 1, 1);
else answer(l, r + 1, 0);
}
write(t ? p[r] : p[l]), putchar(' ');
}
int main() {
scanf("%d", &n);
ld tmp = -INF;
for (int i = 1; i <= n; i++) {
scanf("%Lf %Lf", px + i, py + i);
if (py[i] > tmp) tmp = py[i], k = i;
}
for (int i = k; i <= n; i++)
p[i - k] = i;
for (int i = 1; i <= k; i++)
p[i + n - k] = i;
for (int l = 0; l <= n; l++)
for (int r = l; r <= n; r++)
f[l][r][0] = f[l][r][1] = INF;
f[0][n][0] = f[0][n][1] = 0;
for (int l = 0; l <= n; l++)
for (int r = n; r > l + 1; r--) {
ld LL = f[l][r][0] + dis(l, l + 1), LR = f[l][r][1] + dis(r, l + 1);
if (LL < LR) f[l + 1][r][0] = LL;
else f[l + 1][r][0] = LR, g[l + 1][r][0] = 1;
ld RL = f[l][r][0] + dis(l, r - 1), RR = f[l][r][1] + dis(r, r - 1);
if (RL < RR) f[l][r - 1][1] = RL;
else f[l][r - 1][1] = RR, g[l][r - 1][1] = 1;
}
ld ans = INF;
int pos = 0, qwq = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j <= 1; j++) {
if (f[i][i + 1][j] < ans) {
ans = f[i][i + 1][j];
pos = i, qwq = j;
}
}
answer(pos, pos + 1, qwq);
return 0;
}
密码锁
这道题…还不会，看不太懂。
准备打打暴力。
重新看了遍题，发现
k
=
1
k=1
k=1是很好做出来的，直接用最大值减去最小值就可以了，这样可以通过#1，#2得到
10
p
t
s
10pts
10pts。
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], n, b[N];
const int mxn1=0,min1=0x3f3f3f3f;
int maxn1,main1;
int main() {
int t, k;
cin >> t >> k;
while (t--) {
maxn1=mxn1;
main1=min1;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for(int i=1;i<=n;i++){
maxn1=max(a[i],maxn1);
main1=min(a[i],main1);
}
cout<<maxn1-main1<<endl;
}
return 0;
}
现在来思考
k
=
2
k=2
k=2是什么怎么个事。
我们注意到我们所求答案的最大值为最大值减去最小值，如果想使答案低于这个最大值，就必须让最大值跟最小值不在同一行。
我们可以设最大值
m
a
x
n
maxn
maxn在第一行，最小值
m
i
n
n
minn
minn在第二行，二分极差的最大值为
m
i
d
mid
mid。对于第一行，判定条件为
m
a
x
n
−
a
i
≤
m
i
d
,
maxn-a_i≤mid,
maxn−ai≤mid,第二行则是
a
i
−
m
i
n
n
≤
m
i
d
。
a_i-minn≤mid。
ai−minn≤mid。
时间复杂度为
O
(
n
l
o
g
n
)
。
O(n log n)。
O(nlogn)。
40
p
t
s
40pts
40pts
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 50010, M = 10;
int a[M][N];
int maxx[M][N], minn[M][N];
int t, n, m;
int ans = 0x3f3f3f3f;
void dfs(int deep){
if(deep == n + 1){
int res = 0;
for(int i = 1; i <= m; i ++){
res = max(res, maxx[i][n] - minn[i][n]);
}
ans = min(ans, res);
return;
}
for(int j = 0; j < m; j ++){
for(int i = 1; i <= m; i ++){
int mid;
if(i + j > m)mid = i + j - m;
else mid = i + j;
maxx[i][deep] = max(maxx[mid][deep - 1], a[i][deep]);
minn[i][deep] = min(minn[mid][deep - 1], a[i][deep]);
}
dfs(deep + 1);
}
}
signed main(){
cin >> t >> m;
if(m == 1){
while(t --){
cin >> n;
int maxxx = 0, minnn = 0x3f3f3f3f;
for(int i = 1; i <= n; i ++){
int a;
cin >> a;
maxxx = max(maxxx, a);
minnn = min(minnn, a);
}
cout << maxxx - minnn << endl;;
}
return 0;
}
while(t --){
cin >> n;
ans = 0x3f3f3f3f;
for(int i = 1; i <= m; i ++){
for(int j = 1; j <= n; j ++){
cin >> a[i][j];
maxx[i][j] = 0;
minn[i][j] = 0x3f3f3f3f;
}
minn[i][0] = 0x3f3f3f3f;
maxx[i][0] = 0;
}
dfs(1);
cout << ans << endl;
}
return 0;
}
剩下的两种情况原谅在下能力有限，不能讲述完整。
但贴心的善良的我给大家找了看似好理解的博客点这里
c o d e code code
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 10, inf = INT_MAX;
int n, k, t;
int mx1, mn1;
int a[maxn + 10][6]/*a[n][k] n列n串*/;
int mx[maxn + 10], mn[maxn + 10];
int main() {
cin >> t >> k;
if (k == 1) {
while (t--) {
cin >> n;
int mx1 = 0, mn1 = INT_MAX, a1;
while (n--)cin >> a1, mn1 = min(mn1, a1), mx1 = max(mx1, a1);
cout << mx1 - mn1 << "\n";
}
return 0;
}
int cnt = (k == 4 ? 124 : 40);
while (t--) {
cin >> n;
int ans = inf;
for (int i = 0; i < k; ++i)for (int j = 1; j <= n; ++j)cin >> a[j][i];
for (int H = 1; H < cnt; ++H) {
random_shuffle(a + 1, a + 1 + n); //打乱n串顺序
memset(mx, -0x3f, sizeof mx);
memset(mn, 0x3f, sizeof mn); //每行极值
for (int i = n; i >= 1; --i) { //正在贪i列
int lst = inf, pos = 0;
for (int op = 1; op <= k; ++op) { //转op次
int res = 0;
for (int j = 0; j < k; ++j) {
int tmp = (op + j) % k;
res = max(res, max(mx[tmp], a[i][j]) - min(mn[tmp], a[i][j]));
}
if (lst > res)lst = res, pos = op;
}
for (int j = 0; j < k; ++j) {
int tmp = (pos + j) % k;
mx[tmp] = max(mx[tmp], a[i][j]);
mn[tmp] = min(mn[tmp], a[i][j]);
}
}
int res = 0;
for (int i = 0; i < k; ++i)res = max(res, mx[i] - mn[i]);
ans = min(ans, res);
}
cout << ans << "\n";
}
return 0;
}