ABC400(a-d)

ABC400(a-d)

wlwhonest Lv1
  2025-04-06 00:11:28 2025-04-06 00:11:28 Created   2025-04-06 22:28 2025-04-06 22:28 Updated    1.1k Words  6 Mins  

A

输入x

输出400%x

B

直接累加，累加过程中res+=pow(n,i),如果res>1e9，则输出inf,否则最后输出答案。

C

在做题过程中打表发现了 当a=1和a=2的时候能够表示1-n的所有好数。

下面是打表关键部分

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
#include<bits/stdc++.h>

using namespace std;
// #define int __int128
#define int long long

const int N=1e9;
const int M=1e7;


typedef pair<int,int> pii;

signed main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  
  int n;
  cin>>n;

  for(int i=1;i<=log2(n);i++){
    int di=pow(2,i);
    int cnt=0;
    int res=0;
    for(int j=1;j<=sqrt(n);j++){
      int ans=di*pow(j,2);
      if(ans>n){
        cout<<i<<' '<<res<<' '<<cnt<<endl;
        break;
      }else{
        cnt++;
        if(!mp[ans]){
          cout<<ans<<endl;
          mp[ans]=1;
          res++;
        }
      }
    }
  }

  // cout<<res<<endl;

  return 0;
}

image-20250406001235129

暴力思路@kkkey11

由于2的幂次在之后会有重复的情况，那么就直接枚举不是2的倍数的b。

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
#include<bits/stdc++.h>

using namespace std;
#define int long long

typedef pair<int,int> pii;

const int mod=1e9;

signed main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

  int n,m;
  cin>>n;
  int res=0;
  for(int i=1;i*i*2<=n;i++){
    if(i%2==0) continue;
    for(int j=2;;j*=2){
      int ans=i*i*j;
      if(ans>n){
        break;
      }else{
        res++;
      }
    }
  }
  cout<<res<<endl;
  return 0;
}

赛时打表没有用sqrtl，被卡精度了。

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
#include<bits/stdc++.h>

using namespace std;
// #define int __int128
#define int long long

const int N=1e9;
const int M=1e7;


typedef pair<int,int> pii;

signed main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  
  int n;
  cin>>n;

  int res=0;
  int cnt2=sqrtl(n/2);
  int cnt4=sqrtl(n/4);
  res=cnt2+cnt4;

  cout<<res<<endl;

  return 0;
}

D

赛后看了蔡的代码。

发现是用了双端队列

一开始自己做了一下，发现还是和01bfs有点区别，因为可能在在bfs过程中出现更新的距离比在队列前面的距离要小的情况。

需要注意，只有产生更小距离才入队

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
const int N=1e3+10;
int d[N][N],vis[N][N];
char g[N][N];

signed main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

  int n,m;
  cin>>n>>m;

  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>g[i][j];
    }
  }
  memset(d,0x3f,sizeof d);

  deque<pair<int,pii>> dq;

  int sx,sy;
  int ex,ey;
  cin>>sx>>sy;
  cin>>ex>>ey;

  dq.push_back({0,{sx,sy}});
  d[sx][sy]=0;

  while(dq.size()){

    auto [dist,vex]=dq.front();
    auto [x,y] = vex;
    dq.pop_front();
    if(x==ex&&y==ey){
      cout<<d[ex][ey]<<endl;
      return 0;
    }
    if(dist>d[x][y]) continue;

    for(int i=0;i<4;i++){
      int xx=dx[i]+x;
      int yy=dy[i]+y;
      if(xx<1||xx>n||yy<1||yy>m) continue;
      if(g[xx][yy]=='.'){
        if(d[xx][yy]>dist){
          d[xx][yy]=d[x][y];
          dq.push_front({d[xx][yy],{xx,yy}});
        }
      }else{
        if(d[xx][yy]>dist+1){
          d[xx][yy]=dist+1;
          dq.push_back({d[xx][yy],{xx,yy}});
        }
        xx+=dx[i];
        yy+=dy[i];
        if(xx<1||xx>n||yy<1||yy>m) continue;
        if(d[xx][yy]>dist+1){
          d[xx][yy]=dist+1;
          dq.push_back({d[xx][yy],{xx,yy}});
        }
       
      }
      
    }
  }

  // cout<<-1<<endl;

  return 0;
}

用优先队列会慢一点。

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
const int N=1e3+10;
int d[N][N],vis[N][N];
char g[N][N];

signed main() {
  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

  int n,m;
  cin>>n>>m;

  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
      cin>>g[i][j];
    }
  }
  memset(d,0x3f,sizeof d);

  priority_queue<
    pair<int, pii>,
    vector<pair<int, pii>>,
    greater<pair<int, pii>>
> dq;

  int sx,sy;
  int ex,ey;
  cin>>sx>>sy;
  cin>>ex>>ey;

  dq.push({0,{sx,sy}});
  d[sx][sy]=0;

  while(dq.size()){

    auto [dist,vex]=dq.top();
    auto [x,y] = vex;
    dq.pop();
    if(x==ex&&y==ey){
      cout<<d[ex][ey]<<endl;
      return 0;
    }
    // if(dist>d[x][y]) continue;

    for(int i=0;i<4;i++){
      int xx=dx[i]+x;
      int yy=dy[i]+y;
      if(xx<1||xx>n||yy<1||yy>m) continue;
      if(g[xx][yy]=='.'){
        if(d[xx][yy]>dist){
          d[xx][yy]=d[x][y];
          dq.push({d[xx][yy],{xx,yy}});
        }
      }else{
        if(d[xx][yy]>dist+1){
          d[xx][yy]=dist+1;
          dq.push({d[xx][yy],{xx,yy}});
        }
        xx+=dx[i];
        yy+=dy[i];
        if(xx<1||xx>n||yy<1||yy>m) continue;
        if(d[xx][yy]>dist+1){
          d[xx][yy]=dist+1;
          dq.push({d[xx][yy],{xx,yy}});
        }
       
      }
      
    }
  }

  // cout<<-1<<endl;

  return 0;
}
  • Title: ABC400(a-d)
  • Author: wlwhonest
  • Created at : 2025-04-06 00:11:28
  • Updated at : 2025-04-06 22:00:28
  • Link: https://blog.wlwhonest.top/2025/04/06/ABC400-a-d/
  • License: This work is licensed under CC BY-NC-SA 4.0.
推荐阅读
星爷杯 星爷杯 ABC-376(a-e) ABC-376(a-e) ABC-399(a-f) ABC-399(a-f)
推荐阅读
星爷杯 星爷杯 ABC-376(a-e) ABC-376(a-e)
Comments
On this page
ABC400(a-d)
  1. A
  2. B
  3. C
  4. D