2023潍坊一中第二届编程挑战赛题解

wflengxuenong · 2023-11-23 08:28:57 · 个人记录

T1 揽月湖

题目链接

本题考察基本表达式与数据类型。

int 4个字节 (-2^{31},2^{31}-1) ,(-2,147,483,648 到-2,147,483,647）
long long 8个字节 -2^{63},2^{63}-1（-9,223,372,036,854,775,808到9,223,372,036,854,775,807）
unsigned long long 8个字节 0,2^{64}（0到18,446,744,073,709,551,616）

本题中，用不同的数据类型，得到不同的分数

对于 50\% 的数据，r≤1×10^4。最大3*10^8在int范围内，预计得分50
对于 70\% 的数据，r≤1×10^9。最大3*10^{18}在long \space long 范围内，预计得分70.
对于 100\% 的数据，r≤2×10^9。最大1.2*10^{19}在unsigned \space long \space long 范围内。得分100。

参考满分代码：

#include<cstdio>
#include<iostream>
using namespace std;
unsigned long long a;
int main()
{
    cin>>a;
    cout<<a*a*3;
    return 0;
 }

T2 大写，小写？

题目链接

本题考察字符串的输入及ASCII码转换。

cin只能读入可见字符。用cin只能获得50分。

带空格的字符串读入用getline（）

参考代码：

#include<iostream>
#include<string>
#define int long long
using namespace std;

string s;

signed main()
{
    getline(cin, s);
    for(int i=0; i<s.length(); i++)
    {
        if(s[i] >= 'a' && s[i] <= 'z')
        {
            cout << (char)(s[i] - ('a' - 'A'));
        }
        else if(s[i] >= 'A' && s[i] <= 'Z')
        {
            cout << (char)(s[i] - ('A' - 'a'));
        }
        else
        {
            cout << s[i];
        }
    }
    return 0;
}

T3 200天纪念

题目链接

本题考察循环的应用与基本表达式。注意数据范围用long \space long

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 
int main(){
  ll  N;
  int K;
  cin >> N >> K;
  for (int i = 0; i < K; i++) {
    if (N % 200 == 0) N /= 200;
    else N = N * 1000 + 200;
  }
  cout << N << endl;
  return 0;
}

T4 走方格

题目链接

本题考察分类讨论。从数据来看，光标的移动只需要向下和向右。为了简化问题，我们把对称的(n,m)(m,n)归为同一类处理，强制n<m

如何走最优呢？尽量多利用Fn？如何最大化利用Fn？

先来看特殊数据n=1||m==1

1 2 3 4 5 6 7 8

0 1 2 3 3 4 4 5

可以通过打表找规律和计算得出结论

2+\lceil\frac {(m-1-2)}{2}\rceil \space \space \space m>=4

=\lceil\frac {(m-1-2+4)}{2}\rceil

=\lceil\frac {(m+1)}{2}\rceil

=\lfloor\frac {m}{2}+1\rfloor

=\frac {m}{2}+1

n>1的情况已经规定n<=m

如何尽可能多的运用Fn呢？

先下右走，然后Fn直到下移结束。再按一次右移，就又可以利用Fn了。

\begin{aligned} m,\space n>=m-1 \\ (2+(n-2)+1+\frac{(m-n-1)}{2} \space n<m-1,n>=2 \end{aligned} \right.

(2+(n-2)+1+\lceil\frac{(m-n-1)}{2}\rceil

=\lceil\frac{(2n+m-n-1)}{2}\rceil+1

=\lceil\frac{(m+n-1)}{2}\rceil+1

=\lfloor\frac{(m+n)}{2}\rfloor+1

=\frac{(m+n)}{2}+1

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll work() {
    ll n,m,ans=0;
    cin>>n>>m; 
    if(n>m)swap(n,m);//n<=m
    if(n==1){
        if(m<4)ans=m-1;
        else ans=m/2+1; 
    } 
    else {
        if(n>=m-1)ans=m ;//n=m-1 n=m 直接下右作为一组。 
        else ans=(n+m)/2+1;
    }
    return ans;

}
int main() {
    int t;
    cin>>t; 
    while(t--) {
        cout<<work()<<"\n";
    }
    return 0;
}

T5寻找三元组

本题考察枚举的优化。

部分分1

枚举ABC,三重循环，预计得分20.

#include<bits/stdc++.h>

using namespace std;
#define int long long
signed main()
{
    int n, ans = 0;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j*i<=n; j++)
        {
            for(int k=1; i*j*k<=n; k++)
            {
                if(i <= j && j <= k && i * j * k <= n)
                {
                    ans++;
                }
            }
        }
    }
    cout << ans;
    return 0;
}

优化1，枚举AB,计算C

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, ans = 0;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        for(int j=i; j*i<=n; j++)
        {

            ans+=max(0ll,n/(i*j) -(j-1) ); //a b,c  选出>=b的数 
        }
    }
    cout << ans;
    return 0;
}

优化2

这样发现还是超时。因为n<=10^{11},且A \leq B \leq C,A*B*C \leq N

这样A的上界还可以缩小，最大为\sqrt[3]{N} b的上界为\sqrt{\frac {N}{A}}，总时间复制度约为

经过推导，时间复杂度大约为o(N^{\frac {2}{3}})

参考代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans;
signed main()
{
    int n;
    cin >> n;
    for(int i=1; i*i*i<=n; i++)
    {
        for(int j=i; i*j*j<=n; j++)
        {
            ans += n / (i * j) - j + 1;
        }
    }
    cout << ans;
    return 0;
}

T6走方格2

本题考察搜索算法。我们从 (1,1) 开始更新每一个点。求最短距离，首选BFS,广度优先搜索。

由于我们要求走到距离其欧式距离为 \sqrt{M} 的点，设我们横坐标移动的距离为x，纵坐标移动距离为y。

则我们需要寻找这个方程的所有解：

x^2+y^2=M

我们可以只枚举正整数 x,y 其他负数的解也顺便出来了。

但是枚举 x,y 加上 BFS 时间复杂度为 O(n^4 )，需要优化。

优化方法一：可以提前预处理符号要求的变换位置，存储，后面直接使用即可。
优化方法二：枚举 x 即可找出对应的 y 或判断无解，所以只枚举x 即可。

优化后的时间复杂度 O(n^3)，足已通过本题。

参考代码：

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> > e;
int ans[410][410];
bool done[410][410];
signed main() {
    int n,m;
    cin>>n>>m;
    for(int i=-n;i<=n;i++)
        for(int j=-n;j<=n;j++)
            if(i*i+j*j==m) e.push_back({i,j});
    queue<pair<pair<int,int>,int> > q;
    q.push({{1,1},0});
    while(!q.empty()) {
        auto tmp=q.front();q.pop();
        int x=tmp.first.first,y=tmp.first.second,w=tmp.second;
        if(done[x][y]) continue;
        done[x][y]=1,ans[x][y]=w;
        for(auto d:e) {
            int tx=x+d.first,ty=y+d.second;
            if(tx<1||tx>n||ty<1||ty>n) continue;
            if(!done[tx][ty]) q.push({{tx,ty},w+1});
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(!done[i][j]) cout<<-1<<" ";
            else cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

T7 数字游戏

题目链接

有的同学用贪心，用最小的和最大的匹配，这是错误的。例如

1 8 9

9 8 1

最大值并不出现在左右端点，可能出现在中间。因此，正确的方法是将A_i从小到大排序，B_i从大到小排序，依次对应，使得最大值最小。

部分分1

每次sort排序，总时间复杂度o(n^2log ^n),预计得分50.

优化

注意到A_i,B_i的范围比较小。每次对应可以用桶排序，根据鸽巢原理，在n大的情况下，桶内数据可能是多个，可以多组数据一起对应。A桶从小到大，B桶从大到小，匹配求最大值即可。时间复杂度O(N*200)。预计得分100. 参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100009;
typedef long long ll;
int ma[209],mb[209],ta[209],tb[209];
int la,lb,ra,rb;
int n,x,y,ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        ma[x]++,mb[y]++;
        for(int i=1;i<=200;i++)ta[i]=ma[i],tb[i]=mb[i];
        int k=0,j=200,cnt=0;
        ans=0;
        while(cnt<i){//共匹配i个数
            while(j>0&&!tb[j])j--;//从小到大找bi
            if(j==0)break; 
            while(k<=200&&!ta[k])k++;//从大到小找ai
            if(k>200)break;
            int t=min(ta[k],tb[j]);//每次可以匹配t个数，加快了匹配进度
            cnt+=t;
            ans=max(ans,k+j);
            ta[k]-=t;tb[j]-=t;              
        }
        cout<<ans<<"\n";
    }   
}

2023潍坊一中第二届编程挑战赛题解

T1 揽月湖

T2 大写，小写？

T3 200天纪念

T4 走方格

先来看特殊数据n=1||m==1

n>1的情况 已经规定n<=m

T5寻找三元组

部分分1

优化1，枚举AB,计算C

优化2

T6走方格2

T7 数字游戏

部分分1

优化

n>1的情况已经规定n<=m