本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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了。
$$ f(n,m)=\left\{ \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,ABC \leq N$
这样A的上界还可以缩小，最大为$\sqrt[3]{N}$ b的上界为$\sqrt{\frac {N}{A}}$， 总时间复制度约为 $$\displaystyle \sum_{a=1}^{\sqrt[3]{N}}*(\sqrt{\frac {N}{A}}-A+1) $$ 经过推导，时间复杂度大约为$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";
}
}
鲁ICP备2025150228号