2023年多校联训NOIP层测试3
T1 数列变换 \(10pts\)
- 考虑暴力，发现 \(f\) 数列进行一次变换 \(A\) ，再进行一次变换 \(B\) 后，恢复成了原数列； \(f\) 数列进行一次变换 \(B\) ，再进行一次变换 \(A\) 后，也恢复成了原数列。即变换 \(A\) 可以和变换 \(B\) 相互抵消。
- 本质是差分是前缀和的逆运算（讲树状数组的时候顺带讲了，没认真听，现在才想起来，祭）。
- 直接暴力，数据有点弱，时间复杂度 \(O(n×|sumA-sumB|)\) 。
- 这个数据卡负数的取模也真是醉了，在这里挂了 \(30pts\) ,这里推荐两篇讲解负数取模的博客。link1 link2
- 赛场上前缀和打错了，挂了 \(60pts\) 。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sort stable_sort
#define endl '\n'
ll f[1000],sum[1000];
int main()
{
ll n,m,i,j,k,num=0;
char pd;
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>f[i];
sum[i]=(sum[i-1]+f[i])%998244353;
}
for(i=1;i<=m;i++)
{
cin>>pd>>k;
if(pd=='A')
{
num+=k;
}
if(pd=='B')
{
num-=k;
}
}
if(num>0)
{
for(i=1;i<=num;i++)//直接暴力
{
for(j=2;j<=n;j++)
{
f[j]=(f[j]+f[j-1]+998244353)%998244353;
}
}
for(i=1;i<=n;i++)
{
cout<<f[i]%998244353<<" ";
}
}
if(num==0)
{
for(i=1;i<=n;i++)
{
cout<<f[i]%998244353<<" ";
}
}
if(num<0)
{
for(i=1;i<=-num;i++)//直接暴力
{
for(j=n;j>=2;j--)
{
f[j]=(f[j]-f[j-1]+998244353)%998244353;
}
}
for(i=1;i<=n;i++)
{
cout<<f[i]%998244353<<" ";
}
}
return 0;
}
T2 超级质数 \(0pts\)
-
部分分( \(40pts\) ):筛法求素数+暴力枚举
-
这题卡空间 \(64MB\) ,结果赛场上把筛素数数组大小改成了 \(5e7\) ，但筛的范围是 \(7e7\) ，挂了40pts。
-
考虑打表，打表发现太大了，压缩不下，但是得到从 \(1\) ~ \(4×10^7\)的超级质数个数为 \(76488\) 。- 隔壁 wkh分段打表貌似没我暴力多。
-
正解：线性筛出所有超级质数，二分查找回答答案，复杂度主要在线性筛上，略带卡常，请使用 \(scanf,printf\) or关闭 \(cin,cout\) 同步流。
#include<bits/stdc++.h> using namespace std; #define ll long long #define sort stable_sort #define endl '\n' int prime[4000001],cjprime[80001],sum[10],len=0,cjlen=0; bool vis[40000100];//某人（我）写成char，但没有报错 bool check(int x) { sum[0]=sum[1]=sum[1]=sum[2]=sum[3]=sum[4]=sum[5]=sum[6]=sum[7]=sum[8]=sum[9]=0; while(x>0) { sum[x%10]++; if(sum[x%10]>=2) { return false; } x/=10; } return true; } void isprime(int n) { int i,j; memset(vis,false,sizeof(vis)); for(i=2;i<=n;i++) { if(vis[i]==false) { len++; prime[len]=i; if(check(i)==true) { cjlen++; cjprime[cjlen]=i; } } for(j=1;j<=len&&i*prime[j]<=n;j++) { vis[i*prime[j]]=true; if(i%prime[j]==0) { break; } } } } int main() { int n,i,l,r,fl,fr; scanf("%d",&n); isprime(40000000); for(i=1;i<=n;i++) { scanf("%d%d",&l,&r); fl=upper_bound(cjprime+1,cjprime+1+cjlen,l-1)-cjprime-1;//记得是l-1 fr=upper_bound(cjprime+1,cjprime+1+cjlen,r)-cjprime-1;//第一个大于r的数字的下标减一就是第一个小于等于r的数字的下标 printf("%d\n",fr-fl); } return 0; } -
花絮：请从下往上阅读，\(Accoders\) 的测评机太老了，“运行错误”不一定是 \(RE\) ，还可能是空间炸了（出题人为什么要卡空间啊，喂）。
T3 区间加和 \(45pts\)
- 部分分( \(45pts\) )：\(O(n×max(k))\)的离线暴力即可
T4 距离序列 \(6pts\)
- 部分分( \(6pts\) )：输出 \(1\)
「SFCOI-3」Sadness Fan Club Round 3
这场比赛和luogu上的比赛时间重了，然后就 \(4h\) 打两场比赛，两场比赛都挂分了
T1 P9492 「SFCOI-3」进行一个拆的解 \(30pts\)
- 部分分( \(30pts\) ):
- Subtask \(0\) ( \(15pts\) )：序列内全部相等公共时输出
No。 - Subtask \(1\) ( \(15pts\) )：输出
YES。不，可以，总司令
- Subtask \(0\) ( \(15pts\) )：序列内全部相等公共时输出
- 正解：
- 考虑一个贪心的思想（不会证明）:
- 当 \(n\) 为偶数时，将序列 \(a_1...a_n\) 分成\(a_1...a_{\frac{n}{2}}\) 和\(a_{\frac{n}{2}+1}...a_n\) 一定是最优方案。
- 当 \(n\) 为奇数时，将序列分成如下两种情况一定是最优方案。
- \(a_1...a_{\frac{n-1}{2}}\) 和\(a_{\frac{n-1}{2}+1}...a_n\)
- \(a_1...a_{\frac{n+1}{2}}\) 和\(a_{\frac{n+1}{2}+1}...a_n\)
- 分别处理，进行模拟即可。
- 考虑一个贪心的思想（不会证明）:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sort stable_sort
#define endl '\n'
int a[1000010];
int main()
{
int t,n,i,j,flag,mid;
cin>>t;
for(i=1;i<=t;i++)
{
cin>>n;
flag=0;//多测不请客，爆零两行泪
for(j=1;j<=n;j++)
{
cin>>a[j];
}
for(j=1;j<=n-1;j++)
{
if(a[j]!=a[j+1])//特判全部相等的情况
{
flag=1;
break;
}
}
if(flag==0)
{
cout<<"NO"<<endl;
}
else
{
flag=0;
if(n%2==0)
{
for(j=1;j<=n/2;j++)
{
if(a[j]!=a[j+n/2])//若前后两个序列有不同的数字，则一定可以满足题意
{
flag=1;
break;
}
}
if(flag==1)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
else
{
mid=n/2+1;
for(j=1;j<=n/2;j++)//1~(n-1)/2和(n-1)/2+1~n
{
while(a[j]!=a[mid]&&mid<=n)
{
mid++;
}
mid++;
}
if(mid>=n+2)
{
cout<<"YES"<<endl;
}
else
{
mid=1;
for(j=n/2+2;j<=n;j++)//1~(n+1)/2和(n+1)/2+1~n
{
while(a[j]!=a[mid]&&mid<=n)
{
mid++;
}
mid++;
}
if(mid>=n/2+3)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
}
}
}
return 0;
}