当前位置: 首页 > news >正文

国庆集训模拟赛记录

2025.9.26

A 序列

OI 赛制收益者,挂了 70 分。

先考虑构造一个相邻逆序对最大的序列。

最佳的序列一定是从最大数扫到最小数,每个出现次数不为 \(0\) 的数依次放入数组末尾,并将出现次数减一,扫完最小数后重新扫最大数,一直重复即可。

构造出来后,若 \([1,j]\) 的相邻逆序对个数为 \(m\),将 \([j+1,m]\) 的部分从小到大排序,消去贡献。

具体实现用 vector,可以参考代码,复杂度为 \(O(Tn\log n)\)

点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n,m,ans[N];
vector<int>t[N];
map<int,int>H;
bool cmp(int a,int b){return a>b;
}
void work(){scanf("%d %d",&n,&m);int mx=0;for(int i=1,x;i<=n;i++){scanf("%d",&x);H[x]++,mx=max(mx,H[x]);t[H[x]].push_back(x);}int idx=0;for(int i=1;i<=mx;i++){sort(t[i].begin(),t[i].end(),cmp);for(auto v:t[i]){ans[++idx]=v;}}int now=0;bool flag=0;for(int i=1;i<=n;i++){if(now==m){sort(ans+i,ans+n+1);flag=1;break;}if(ans[i]>ans[i+1])now++;}if(!flag){printf("-1\n");}else{for(int i=1;i<=n;i++)printf("%d ",ans[i]);printf("\n");}H.clear();for(int i=1;i<=mx;i++)t[i].clear();for(int i=1;i<=n;i++)ans[i]=0;return;
}
int main(){freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);int T;scanf("%d",&T);while(T--)work();return 0;
}

B 平衡数列

容易发现若所有的 \(A_i>1\),则一个平衡数列不超过 \(20\)。因为 \(2^{20}>2\times 20\),所以一定不行。

这启发我们平衡数列个数很少,记录每个位置 \(i\) 前上一个 \(A_i>1\) 的位置。枚举区间右端点 \(r\),然后往左跳 \(nxt_l\),跳的次数一定不超过 \(20\),时间复杂度为 \(O(n\log n)\)

点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const ll V=5e11;
int n,a[N],pre[N],ans;
ll s[N];
int main(){freopen("bal.in","r",stdin);freopen("bal.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",a+i);s[i]=s[i-1]+a[i];}int x=0;for(int i=1;i<=n;i++){pre[i]=x;if(a[i]>1)x=i;}for(int i=1,l;i<=n;i++){ll prod=1,sum=0;int lst=i;for(int j=i;j&&prod<=V;j=pre[j]){prod*=a[j],sum+=s[lst]-s[j-1],l=pre[j];if(prod-sum>=0&&prod-sum<=j-1-l)ans++;lst=j-1;}}printf("%d\n",ans);return 0;
}

C 间谍部署

\(f_{i,j}\) 表示 \(i\) 子树内,距离 \(i\) 最近的选择的点距离 \(i\)\(j\),做一个树上背包状物即可,因为可以子树选空,所以要注意继承的情况。

时间复杂度为 \(O(n)\)

点击查看代码
#include <iostream> 
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const int mod=998244353;
int n,mk[N];
vector<int>G[N];
ll f[N][4],ans[4],sum;
void add(int x,int y){G[x].push_back(y); 
}
void dfs(int x,int fa){for(auto y:G[x]){if(y==fa)continue;dfs(y,x);for(int i=1;i<=3;i++)ans[i]=f[x][i];for(int i=0,s;i<=3;i++){s=min(3,i+1);ans[s]=(ans[s]+f[y][i])%mod;}for(int i=1,s;i<=3;i++){for(int j=0;j<=3;j++){if(i+j<2)continue;s=min(3,min(i,j+1));ans[s]+=f[x][i]*f[y][j]%mod;ans[s]%=mod;}}for(int i=1;i<=3;i++)f[x][i]=ans[i];}if(mk[x])f[x][0]=f[x][3]+1;return;
}
int main(){freopen("spy.in","r",stdin);freopen("spy.out","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",mk+i);for(int i=2,f;i<=n;i++){scanf("%d",&f);add(f,i),add(i,f);}dfs(1,0);for(int i=0;i<=3;i++)sum=(sum+f[1][i])%mod;printf("%d\n",sum);return 0;
}

D 小A与字符串

不难发现,字符串的循环节一定是最小循环节的倍数,所以可以求出区间最小循环节。

\(p\)\([l,r]\) 的循环节,需要满足 \([l+p,r]=[l,r-p]\),具体和 KMP 相关。可以预处理字符串 Hash 值,方便 \(O(1)\) 比较。

从小到大试倍数,直到试出第一个循环节为答案,复杂度 \(O(n\sqrt{n})\),慢。

反过来!若 \(p\) 是循环节,则一定是最小循环节的倍数,考虑逐个剔除其中质因子。

最后预处理每个数因数个数,质因子的东西,时间复杂度为 \(O(n\log n)\)

点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ull;
const int N=5e5+10;
int n,m,ys[N],mk[N];
char s[N];
vector<int>pr[N];
struct Hash{ull p,pw[N],hs[N];void prework(ull Ciallo,char *s,int n){p=Ciallo,pw[0]=1,hs[0]=0;for(int i=1;i<=n;i++){pw[i]=pw[i-1]*p;hs[i]=hs[i-1]*p+s[i]-'a';}return;}ull qry(int l,int r){return hs[r]-hs[l-1]*pw[r-l+1];}
}T1,T2;
bool check(int l1,int r1,int l2,int r2){if(l1>r1)return 1;if(T1.qry(l1,r1)!=T1.qry(l2,r2))return 0;if(T2.qry(l1,r1)!=T2.qry(l2,r2))return 0;return 1;
}
void init(){T1.prework(131,s,n);T2.prework(13331,s,n);for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=i)ys[j]++;for(int i=2;i<=n;i++){if(mk[i])continue;for(int j=i;j<=n;j+=i){pr[j].push_back(i);mk[j]=1;	 }}return;
}
int main(){freopen("str.in","r",stdin);freopen("str.out","w",stdout);scanf("%d %d",&n,&m);scanf("%s",s+1);init();for(int i=1,l,r;i<=m;i++){scanf("%d %d",&l,&r);int x=1,y=r-l+1;for(auto v:pr[r-l+1]){while(1){if(y%v!=0)break;if(!check(l,r-y/v,l+y/v,r))break;x*=v,y/=v;}}printf("%d\n",ys[x]);}return 0;
}
http://www.hskmm.com/?act=detail&tid=22407

相关文章:

  • 2025 年集装袋厂家 TOP 企业品牌推荐排行榜,深度剖析优质厂家优势集装袋推荐这十家公司!
  • oppoR9m刷Linux系统: 工具、软件下载
  • 实用指南:HTTP(web缓存与历史迭代)
  • 2025.10.1——1橙2黄
  • virtualbox新版安装指定路径--7.2版本之后
  • 2025 年隔音门厂家 TOP 企业品牌推荐排行榜,剧院,ktv,防火 ,软包 ,录音棚 ,静音 ,钢质 ,实验室 ,直播间隔音门推荐这十家公司!
  • 2025年算法备案咨询服务公司TOP最新推荐排行榜单,互联网信息服务,深度合成服务,ai算法备案,互联网算法备案,国家生成式人工智能服务备案咨询公司
  • AT_agc048_b [AGC048B] Bracket Score
  • 2025 年热浸塑钢管工厂 TOP 企业品牌推荐排行榜 ,nhap/NHAP/ 电力 / N-HAP/200 / 新型防腐热浸塑钢管 / 热浸塑穿线钢管 / 电力钢管 / 电力涂塑钢管推荐!
  • 信创PC收藏网址
  • 线程同步实战指南:从 bug 根源到锁优化的终极之路 - 教程
  • 2025 年数据恢复系统推荐转转大师数据恢复,深度剖析各款系统平台核心优势与适用场景数据恢复系统推荐指南
  • 2025 年离心泵厂家 TOP 企业品牌推荐排行榜!化工,卧式多级,不锈钢,立式,氟塑料,管道,衬氟,耐腐蚀离心泵推荐这十家公司!
  • 在线PS的强大功能一览:从基础修图到高级合成,还有这3款免费软件推荐!
  • 详细介绍:抽丝剥茧的Transformer详解
  • 2025 年高压氧舱厂家 TOP 推荐榜单揭晓,家用,高原,小型,单人,民用,专业,医用,家庭,智能,进口高压氧舱公司推荐!
  • oppoR9m刷Linux系统:开启开发者模式
  • macOS 上手记录
  • Google Drive批量转存他人分享的链接的文件
  • 异常检测
  • 2025 年物流公司服务 TOP 企业品牌推荐推荐榜,无锡到西安、无锡到太原、无锡到宁波、无锡到郑州、无锡到上海物流公司推荐!
  • 2025 年曝气器制造厂家 TOP 企业品牌推荐排行榜,微孔 / 平板 / 管式 / 拱形 / 可提升式曝气器公司推荐这 10 家
  • 2025 年石灰料仓厂家 TOP 企业品牌推荐榜单,深度剖析行业优秀企业优势!
  • 完整教程:MYSQL —— 约束和多表查询
  • 排序算法汇总,堆排序,归并排序,冒泡排序,插入排序 - 详解
  • AI元人文:于价值表征困境中试探
  • 解决ubuntu因自动挂起导致电脑卡死
  • 2025板材厂家 TOP 企业品牌推荐排行榜,环保 / 密度 / 净化 / 零醛添加 / 装修 / 生态板 / 指接板 / 直拼板 / PET 实木板材公司推荐!
  • 2线性规划模型建模实战
  • 网络技术:基本结构与协议