#春节巅峰赛#17 部分题解
2025-02-04 22:29:15
发布于：四川
134阅读
7回复
3点赞
奶龙最后时候没了😂😂。 好像感觉大家都很重视。。
T1
分类讨论：
- ，显然有当 时，可以，否则不可以；
- ，显然可以。
- ，显然有当 时，可以，否则不可以；
#include<iostream>
using namespace std;
int a,b,c,d;
int main(){
cin>>a>>b>>c>>d;
if(c<a){
if(c+d>=a)cout<<"YES";
else cout<<"NO";
}
if(c>=a && c<=b) cout<<"YES";
if(c>b){
if(c-d<=b)cout<<"YES";
else cout<<"NO";
}
}
T2
由于只能从前往后扫，所以必然要扫一段前缀，因此要找到最后一个重复的元素，看见 并不大，用桶存就可以。
具体方法就是从后往前扫，找到第一个拥有重复元素的索引，输出就可以了。
#include<iostream>
using namespace std;
int t[105];
int a[105];
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int idx;
for(idx=n;idx>=1;idx--){
if(t[a[idx]])break;
t[a[idx]]++;
}
cout<<idx;
}
T3
好像写复杂了。。。
说实话就是做着题做崩溃的。
透析几何可以 处理出。
很有兴致和大家讲解。
首先将这个圆的运动过程分成 7 段，具体看代码。
设摩天轮的圆心为 ，从摩天轮的圆心向该时刻的目标点作一条线，记其与圆的交点为 ，再做一条线与经过出发点的一条直径交于点 。则显然有 ，记为 ，有 ，。因此处理好三角形位置对于 轴的影响就可以了 （就是这被卡了 3 次）。
接下来说确定两个点后如何计算角度。
首先先算出两点 轴意义下的距离，勾股就能计算，记为 。接下来设 的差为 ，设最终答案为 ，则首先有 ，所以 。
cmath 库自带三角函数。
#include<iostream>
#include<cmath>
using namespace std;
const double pi=3.141592653589;
double t,xa,xb,ya,yb,la,lb,s;
double x,y,z,xx,yy,zz;
int q;
double len(double x,double y,double xx,double yy){
return sqrt((x-xx)*(x-xx)+(y-yy)*(y-yy));
}
double cal(double x,double y,double z,double xx,double yy,double zz){
if(z==zz)return 0.000000000;
if(x==xx && y==yy) return 90.0000000;
double d=len(x,y,xx,yy);
return atan(abs(z-zz)/d);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
cin>>xa>>ya>>la;
cin>>xb>>yb>>lb;
cin>>q;
while(q--){
cin>>s;
x=xa;
xx=xb;
if(s==0){
y=ya;
z=0;
yy=yb;
zz=0;
}
else if(s<t/4.00){
y=ya-sin((360.00*s/t)*pi/180.00)*la/2;
z=la/2-cos((360.00*s/t)*pi/180.00)*la/2;
yy=yb-sin((360.00*s/t)*pi/180.00)*lb/2;
zz=lb/2-cos((360.00*s/t)*pi/180.00)*lb/2;
}
else if(s==t/4.00){
y=ya-la/2;
z=la/2;
yy=yb-lb/2;
zz=lb/2;
}
else if(s<t/2.00){
y=ya-sin((180.00-360.00*s/t)*pi/180.00)*la/2;
z=la/2+cos((180.00-360.00*s/t)*pi/180.00)*la/2;
yy=yb-sin((180.00-360.00*s/t)*pi/180.00)*lb/2;
zz=lb/2+cos((180.00-360.00*s/t)*pi/180.00)*lb/2;
}
else if(s==t/2.00){
y=ya;
z=la;
yy=yb;
zz=lb;
}
else if(s*4.00<t*3.00){
s=t-s;
y=ya+sin((180.00-360.00*s/t)*pi/180.00)*la/2;
z=la/2+cos((180.00-360.00*s/t)*pi/180.00)*la/2;
yy=yb+sin((180.00-360.00*s/t)*pi/180.00)*lb/2;
zz=lb/2+cos((180.00-360.00*s/t)*pi/180.00)*lb/2;
}
else if(s*4.00==t*3.00){
y=ya+la/2;
z=la/2;
yy=yb+lb/2;
zz=lb/2;
}
else{
s=t-s;
y=ya+sin((360.00*s/t)*pi/180.00)*la/2;
z=la/2-cos((360.00*s/t)*pi/180.00)*la/2;
yy=yb+sin((360.00*s/t)*pi/180.00)*lb/2;
zz=lb/2-cos((360.00*s/t)*pi/180.00)*lb/2;
}
//cout<<x<<" "<<y<<" "<<z<<" "<<xx<<" "<<yy<<" "<<zz<<endl;
printf("%.9lf\n",cal(x,y,z,xx,yy,zz)*180.00/pi);
}
}
T4
维护一个 unordered_map 来记录每个的出现位置，同时为了压缩路径，可以采用类似并查集的方法，记录最近一个可以到达的位置，就是这样了。
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
int n,q;
int fa[100005];
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
bool has[100005];
long long x;
unordered_map<long long,int> pos_map;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=0;i<n;i++) fa[i]=i;
for(int i=1;i<=q;i++){
cin>>x;
if(pos_map.count(x)==0){
int h=x%n;
int res=find(h);
pos_map[x]=res;
has[res]=1;
fa[res]=find((res+1)%n);
}
cout<<pos_map[x]<<'\n';
}
}
T5
并不算很难。
dp 记录状态下的 a，ac，acg 子串个数，类似的题很多。
更展开来讲，判断每一位是哪一个字符，然后进行一定操作：举例计算 acg 的方法：在每一个字符 g，将该状态的 acg 加上该状态下的 ac 子串个数。
答案计算的方法，就是对于每一个字符 o，把它前面的 acg 子串个数加入答案即可。
注意动态取模，开 long long。
担心空间不够，开了滚动数组。
#include<iostream>
using namespace std;
const int mod=998244353;
int n;
char s[1000005];
long long dp[5][5];
long long ans;
int main(){
cin>>n>>s;
for(int i=0;i<n;i++){
for(int j=0;j<3;j++)dp[i%2][j]=dp[(i-1)%2][j];
if(s[i]=='a')dp[i%2][0]=(dp[(i-1)%2][0]+1)%mod;
if(s[i]=='c')dp[i%2][1]=(dp[(i-1)%2][1]+dp[(i-1)%2][0])%mod;
if(s[i]=='g')dp[i%2][2]=(dp[(i-1)%2][2]+dp[(i-1)%2][1])%mod;
if(s[i]=='o') ans=(ans+dp[(i-1)%2][2])%mod;
}
cout<<ans;
}
T6
预处理线性筛出最大值范围内的质数，然后对每个查询做质因数分解就可以了，没什么技术含量。
#include<iostream>
using namespace std;
int n;
long long a;
long long vis[200005],prime[200005];
int cnt;
void os(int n){
for(int i=2;i<=n;i++){
if(!vis[i]) prime[++cnt]=i;
for(int j=1;j<=cnt && i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
bool check(long long x){
int ans=0;
for(int i=1;prime[i]*prime[i]<=x;i++){
while(x%prime[i]==0){
ans++;
x/=prime[i];
if(ans>3)return false;
}
}
if(x!=1)ans++;
return ans==3;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
vis[1]=1;
cin>>n;
os(200000);
for(int i=1;i<=n;i++){
cin>>a;
if(check(a))cout<<"Yes"<<'\n';
else cout<<"No"<<'\n';
}
}
T7
对于一个质数，显然无法操作。
对于一个非质数，显然有策略是先选最小的质因数，然后选该数 ，再选 ，就可以选择区间 的所有质数，然后进一步选择所有的合数。所以不能选的数就是 ，， 的所有质数，还是线性筛出最大值范围内的所有质数，用前缀和预处理出，设前缀数组为 ，每次查询的答案就是 。
#include<iostream>
using namespace std;
bool vis[3000005];
int prime[1000005];
int qz[3000005];
int cnt;
void os(int n){
for(int i=2;i<=n;i++){
if(!vis[i]) prime[++cnt]=i;
for(int j=1;j<=cnt && i*prime[j]<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int t;
int n;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>t;
vis[1]=1;
os(3000000);
int tmp=0;
for(int i=2;i<=3000000;i++){
if(vis[i]==0)tmp++;
qz[i]=tmp;
}
while(t--){
cin>>n;
if(vis[n]==0)cout<<0<<'\n';
else{
cout<<n-2-(qz[n-1]-qz[n/2])<<'\n';
}
}
}
T8
不会，问这位大佬或者官方。
有帮助，赞一个