模拟赛一补题报告
日期：\(2023\)—\(10\)—\(2\) 学号：\(S11390\)
一、总分：
\(T1\) 数字降级:\(80\)分
\(T2\) 分组:\(0\)分
\(T3\) 抢夺地盘:\(10\)分
\(T4\) 闯关:\(10\)分
共：\(100\) 分
二、比赛过程
-
在第一题中，我考虑得较为麻烦，其实已经想到最优解了，但却没有相信自己用最简单的方法做。
-
在第二题中，做题思路确实想到了桶记录，但是想要去的最优解却没有进行暴力得分，导致最后也没有得出最优解，成功爆 \(0\)。
-
在第三题中，因为动态规划思路没有学，只能想到暴力枚举的思路，因此只能暴力枚举进行骗分，最终只得了 \(10\) 分。
-
在第四题中，我的题目理解出现了偏差，导致整个代码出现了错误，因此只对不用给神器的那一种情况，也是只得了 \(10\) 分。
三、题目分析
\(T1\) 数字降级
本题题意就是判断是否为素数，如果是素数，那么就输出 \(0\),否则输出 \(1\)。
但我在这道题目中想到了这种方法。但我觉得太简单了，却没有用，导致只对了 \(80\) 分。
正解
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=1e6+5;
bool su(int x)
{
for(int i=2;i<=sqrt(x);i++)
{
if(x%i==0)
return 0;
}
return 1;
}
int n;
signed main()
{ ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n;
if(su(n))
cout<<0<<endl;
else
cout<<1<<endl;
//fclose(stdin);
//fclose(stdout);
return 0;
}
但在判断素数时循环条件是 for(int i=2;i<=sqrt(x);i++)。
！！！但是，要注意不开 \(long long\) 见祖宗。
\(T2\) 分组
本题题意就是将数出现的进行桶记录，遍历前一个数的个数与当前数的个数。其中有两种情况。
-
\(mp_{i}<mp_{i-1}\) 这时将出现的次数乘上当前数，则 \((mp_{i-1}<mp_{i})\times i\)。
-
\(mp_{i}>=mp_{i-1}\) 这时就将多了的舍去，则 \(mp_{i}=mp_{i-1}\)。
正解
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int a;
int mp[N];
int n;
int sum;
signed main()
{
// freopen("group.in","r",stdin);
// freopen("group.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
mp[a]++;
}
for(int i=1;i<=1001;i++)
{
if(mp[i]<mp[i-1])
{
sum+=((mp[i-1]-mp[i])*i);
}
else
{
mp[i]=mp[i-1];
}
//cout<<mp[i]<<" ";
}
cout<<sum<<endl;
// fclose(stdin);
// fclose(stdout);
return 0;
}
\(T3\) 抢夺地盘
本题就是动态规划—最长上升，最长下降子序列的模板题，但是要注意本题数据范围大，需要运用二分查找，找最小值问题。在回答这道题之前，先给我这样的蒟蒻普及一下，什么是最长上升和最长下降子序列。
最长上升子序列 最长下降也同样如此—就是将符号变一变
普通做法 \(O(n*n)\)
signed main()
{ ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int maxx=0;
for(int i=1;i<=n;i++)
{
dp[i]=1;
for(int j=1;j<i;j++)
{
if(a[j]<a[i])
dp[i]=max(dp[i],dp[j]+1);
}
}
for(int i=1;i<=n;i++)
{
maxx=max(maxx,dp[i]);
}
cout<<maxx<<endl;
//fclose(stdin);
//fclose(stdout);
return 0;
}
二分优化 \(O(nlogn)\)
signed main()
{ ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
if(a[i]>dp[m])
{
dp[++m]=a[i];
}
else
{
int l=1,r=m;
while(l<r)
{
int mid=(l+r)>>1;
if(dp[mid]>=a[i])
r=mid;
else
l=mid+1;
}
dp[r]=a[i];
}
}
cout<<m<<endl;
//fclose(stdin);
//fclose(stdout);
return 0;
}
再说回这个题目中，我们就将这个数列从 \(q\) 分开，前半部分跑一边最长上升，后半部分跑一边最长下降，最后减去最长序列的长度，这就是本题的思路。
正解
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=1e6+5;
int n,p;
int dp1[N],dp2[N];
int m1=1,m2=1;
int a[N];
signed main()
{ ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>p;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
//dp1[1]=a[1];
for(int i=2;i<=p;i++)
{
if(a[i]>=dp1[m1])
{
dp1[++m1]=a[i];
}
else
{
int l1=1,r1=m1;
while(l1<r1)
{
int mid=(l1+r1)>>1;
if(dp1[mid]>=a[i])
r1=mid;
else
l1=mid+1;
}
dp1[r1]=a[i];
}
}
//dp2[1]=a[p];
for(int i=p+1;i<=n;i++)
{
if(a[i]<=dp2[m2])
{
dp2[++m2]=a[i];
}
else
{
int l2=1,r2=m2;
while(l2<r2)
{
int mid=(l2+r2)>>1;
if(dp2[mid]<=a[i])
r2=mid;
else
l2=mid+1;
}
dp2[r2]=a[i];
}
}
cout<<n-(m2+m1)<<endl;
//fclose(stdin);
//fclose(stdout);
return 0;
}
\(T4\) 闯关
本题在读明白题意后，就能够有很好的思路了，就是运用贪心思想来进行模拟。
在这之前，我们可以特判一下，如果达达能够不用神器就能够跑完全程的话，就可以直接输出 \(0\)。即不用进行神器转移。
在其中一人拿到神器中，另一个人就跑到他能够跑到的最远距离，其中有几个条件。
-
没拿到神器的人，跑的距离减去当前关卡的距离要小于规定的能够跳跃的最大距离。
-
拿到神器的人，跑的距离减去没拿到神器的人的距离要小于规定能够传递神器的最大距离。
这样说不好理解，来转化成代码来展示。
拿到神器的人是 \(b\)。
没拿到神器的人是 \(a\)。
拿到神器的人的位置为 \(pos2\)。
没拿到神器的人的位置为 \(pos1\)。
能够跳跃的最大距离为 \(m\)。
能够传递神器的最大距离为 \(q\)。
-
b[pos2+1]-b[pos2]<=m -
a[pos1+1]-b[pos2]<=q
这样这道题最主要的问题就能够解决了，接着就进行模拟了。
正解
#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=1e6+5;
int n,m,k,q;
int a[N],b[N];
int c[N];
bool flag;
int res;
signed main()
{ ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>m>>k>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
//s1+=a[i];
}
for(int i=1;i<=n;i++)
{
cin>>b[i];
c[i]=b[i]-b[i-1];
//s2+=b[i];
}
for(int i=1;i<=n;i++)
{
if(c[i]>=m)
{
flag=1;
}
}
if(!flag)
{
cout<<0<<endl;
return 0;
}
bool f=0;//小可
int h=1;
int pos1=0,pos2=0;
while(1)
{
if(f==0)
{
while((b[pos2+1]-b[pos2])<=m&&pos2+1<=n)
{
pos2++;
}
if(pos2==n)
{
break;
}
while((a[pos1+1]-b[pos2])<=q&&pos1+1<=n)
{
pos1++;
}
res++;
f=1;
}
else
{
while((a[pos1+1]-a[pos1])<=m&&pos1+1<=n)
{
pos1++;
}
if(pos1==n)
{
break;
}
while((b[pos2+1]-a[pos1])<=q&&pos2+1<=n)
{
pos2++;
}
res++;
f=0;
}
}
cout<<res<<endl;
//fclose(stdin);
//fclose(stdout);
return 0;
}