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

CEXE的%你赛5-题解

T1

简单 dfs,记录数组 \(vis\) 表示一个点有没有被搜索过,从小到大遍历 \(vis\),如果 \(vis_i=0\) 则从 \(i\) 开始遍历图,遍历时记录答案即可。

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[30005];
vector<int> G[30005];
bool vis[30005];
long long ans=0,maxn=-1;
void dfs(int x){vis[x]=1;maxn=max(maxn,a[x]);for(auto to:G[x]){if(vis[to]) continue;dfs(to);}
}
int main(){cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1,u,v;i<=m;i++){cin>>u>>v;G[u].push_back(v);}for(int i=1;i<=n;i++){if(!vis[i]){maxn=-1;dfs(i);ans+=maxn;}}
//	cout<<"13"<<endl;cout<<ans<<endl;return 0;
}

T2

数学题,答案为 \(\left \lfloor \frac{n+1}{2} \right \rfloor\)。记得开 unsigned long long

void Main(int cases){ull x;cin>>x;cout<<(x+1>>1)<<endl;return;
}

T3

数据结构板子题。可以用树状数组、线段树、分块。这里讲最简单的分块做法。

把序列分成 \(\sqrt n\) 个长度均匀的块。对于每个位置,记录 \(id_i\),表示 \(i\) 这个位置属于哪个块。

对于每个块记录几个属性:

  • \(sum\),表示这个块的和
  • \(add\),懒标记
  • \(cnt\),这个块内包含了多少元素(接近 \(\sqrt n\)

两种操作如下:

  • 对于区间加,把范围内的整块的懒标记增加,整块两边的碎块暴力增加
  • 对于查询,整块的和为 \(sum+add\times cnt\),碎块直接暴力统计

总体复杂度 \(O(n \sqrt n)\)

分块写法:

ll n,m,len;
ll a[100005],id[100005],sum[100005],add[100005],cnt[100005];
ll op,x,y,k;
void op1(int l,int r,int x){if(id[l]==id[r]){for(int i=l;i<=r;i++){a[i]+=x;sum[id[i]]+=x;}}else{for(int i=l;id[i]==id[l];i++){a[i]+=x;sum[id[i]]+=x;}for(int i=r;id[i]==id[r];i--){a[i]+=x;sum[id[i]]+=x;}for(int i=id[l]+1;i<=id[r]-1;i++){add[i]+=x;}}
}
ll op2(int l,int r){ll ans=0;if(id[l]==id[r]){for(int i=l;i<=r;i++){ans+=a[i]+add[id[i]];}return ans;}else{for(int i=l;id[i]==id[l];i++){ans+=a[i]+add[id[i]];}for(int i=r;id[i]==id[r];i--){ans+=a[i]+add[id[i]];}for(int i=id[l]+1;i<=id[r]-1;i++){ans+=sum[i]+add[i]*cnt[i];}return ans;}
}
void Main(int cases){cin>>n;len=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];id[i]=i/len;//i属于第几个块 sum[i/len]+=a[i];//第i个块的和 cnt[i/len]++;//第i个块有多少个数 }cin>>m;while(m--){cin>>op;if(op==1){cin>>x>>y>>k;op1(x,y,k);}if(op==2){cin>>x>>y;cout<<op2(x,y)<<endl;}}return;
}

线段树写法:

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define int long long
using namespace std;
const int N=100005;
int a[N];
int n,m,op,x,y,k;
struct node{int l,r,sum,lazy;
}tr[N<<2];
void pushup(int u){tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){if(tr[u].lazy){//有懒标记才pushdown tr[u<<1].sum+=(tr[u<<1].r-tr[u<<1].l+1)*tr[u].lazy;//区间和增加(区间元素个数)个懒标记 tr[u<<1|1].sum+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*tr[u].lazy;tr[u<<1].lazy+=tr[u].lazy;//把懒标记传递给左右孩子 tr[u<<1|1].lazy+=tr[u].lazy;tr[u].lazy=0;//清空懒标记 }
}
void build(int u,int l,int r){tr[u].l=l,tr[u].r=r;if(l==r){tr[u].sum=a[l];tr[u].lazy=0;//懒标记初始化 return;}int mid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);
}
void modify(int u,int l,int r,int val){if(tr[u].l>=l&&tr[u].r<=r){tr[u].sum+=val*(tr[u].r-tr[u].l+1);//需要加很多个val tr[u].lazy+=val;//懒标记一下,标记加上过valreturn; }pushdown(u);//懒标记下传int mid=(tr[u].l+tr[u].r)>>1;if(mid>=l) modify(u<<1,l,r,val);if(mid<r) modify(u<<1|1,l,r,val);pushup(u); 
}
int ask(int u,int l,int r){if(tr[u].l>=l&&tr[u].r<=r){return tr[u].sum;}pushdown(u);int mid=(tr[u].l+tr[u].r)>>1,sum=0;if(mid>=l) sum+=ask(u<<1,l,r);if(mid<r) sum+=ask(u<<1|1,l,r);return sum;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}cin>>m;build(1,1,n);
//	cout << tr[1].sum<<endl;while(m--){cin>>op;if(op==1){cin>>x>>y>>k;modify(1,x,y,k);}else{cin>>x>>y;cout<<ask(1,x,y)<<endl;}} return 0;
}

T4

诈骗题。

注意到结尾的动图小标题为“小彩蛋”,而其他题目都为“小踩蛋”,显然答案与这个动图有关。

不难猜到题中所说的游戏是荒野乱斗(BrawlStars),查找荒野乱斗中的所有人物,可以发现动图中人物名为阿尔提,英文名为 R-T。小写的 rt 在锣鼓中恰好为“如题”的意思,所以答案为 rt

下次模拟赛还有类似这样的题目!

T5

可爱动态规划。

第一问很好求,状态转移方程为 \(dp_i=\max\{dp_j\}+1\)

第二问,根据 Dilworth 定理,最小链覆盖等于最长反链长度(模拟即可理解),故答案与第一问答案完全相同。输出两次即可。

不知道 Dilworth 定理的去看 P1020 导弹拦截。

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,a[5005],dp[5005],ans=-1e9;
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){for(int j=0;j<i;j++){if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);}}for(int i=1;i<=n;i++) ans=max(dp[i],ans);cout<<ans<<' '<<ans<<endl;return 0;
}

T6

可爱动态规划。

第一问简单 dp,定义 \(dp_{i,j}\) 表示从起点到 \((i,j)\) 的最大得分,显然有 \(dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})\)

第二问需要在第一问转移时进行。定义 \(sum_{i,j}\) 表示从起点走到 \((i,j)\) 能得到最大价值的方案数,转移方程为:

  • 如果 \(dp_{i-1,j}>dp_{i,j-1}\),则 \(sum_{i,j}=sum_{i-1,j}\)
  • 如果 \(dp_{i-1,j}<dp_{i,j-1}\),则 \(sum_{i,j}=sum_{i,j-1}\)
  • 如果 \(dp_{i-1,j}=dp_{i,j-1}\),则 \(sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}\)

别忘了取模。

第三问直接再次 dp,从 \((x,y)\) 点开始递推直到 \((n,m)\) 即可。

int n,m,x,y;
ll a[N][N];
ll dp1[N][N],dp2[N][N];
ll sum[N][N];void Main(int cases){n=read(),m=read(),x=read(),y=read();up(i,1,n){up(j,1,m){a[i][j]=read();}}sum[1][1]=1;up(i,1,n) dp1[i][1]=dp1[i-1][1]+a[i][1],sum[i][1]=1;up(j,1,m) dp1[1][j]=dp1[1][j-1]+a[1][j],sum[1][j]=1;up(i,2,n){up(j,2,m){if(dp1[i-1][j]>dp1[i][j-1]) dp1[i][j]=dp1[i-1][j]+a[i][j],sum[i][j]=sum[i-1][j]%1000000000;if(dp1[i-1][j]<dp1[i][j-1]) dp1[i][j]=dp1[i][j-1]+a[i][j],sum[i][j]=sum[i][j-1]%1000000000;if(dp1[i-1][j]==dp1[i][j-1]) dp1[i][j]=dp1[i][j-1]+a[i][j],sum[i][j]=(sum[i][j-1]+sum[i-1][j])%1000000000;}}
//	up(i,1,n){
//		up(j,1,m){
//			cout<<sum[i][j]<<' ';
//		}cout<<endl;
//	}cout<<dp1[n][m]<<' '<<sum[n][m]<<' ';up(i,x,n) dp2[i][y]=dp2[i-1][y]+a[i][y];up(j,y,m) dp2[x][j]=dp2[x][j-1]+a[x][j];up(i,x+1,n){up(j,y+1,m){if(i==x&&y==j) continue;dp2[i][j]=max(dp2[i-1][j],dp2[i][j-1])+a[i][j];}}cout<<dp1[x][y]+dp2[n][m]-a[x][y]<<endl;return;
}

T7

双指针。为了快速求出区间和,先预处理前缀和。

维护两个指针 \(p_1,p_2\),从一开始往后扫。

注意到正整数序列,所以对于一个区间 \([l,r]\) 的和 \(sum_{l,r}\),一定有 \(sum_{l+1,r} < sum_{l,r} < sum_{l,r+1}\)。即区间和是递增的。

接着,我们会发现,对于一个给定的区间右端点 \(r\),满足条件的左端点 \(l\) 的取值一定是连续的。我们只需要找出这个连续区间的长度,那么这个 \(r\) 对答案的贡献就是这个区间的长度。

所以,我们用开头提到的两个指针从 \(1\) 开始,枚举区间右端点 \(right\),对于每个右端点分别找到第一个满足和小于等于 \(r\) 的地方 \(p_1\),以及第一个满足和小于 \(l\) 的地方 \(p_2\),则这个右端点对答案的贡献为 \(\max\{0,p_1-p_2\}\)

答案很大,记得开 long long

int a[3000005],sum[3000005];
int p1=1,p2=1;
ll ans=0;
void Main(int cases){n=read(),l=read(),r=read();up(i,1,n){a[i]=read();sum[i]=sum[i-1]+a[i];}up(right,1,n){int p=sum[right];while(p1<=right&&p-sum[p1-1]>r) p1++;while(p2<=right&&p-sum[p2-1]>=l) p2++;ans+=max(0,p2-p1);}cout<<ans<<endl;return;
}

关注 CEXE!

http://www.hskmm.com/?act=detail&tid=20950

相关文章:

  • C++语言(1)
  • Windows多人共享文件夹全流程,附2025新共享文件快90%
  • 第11章 day11-day12关于json请求体/逆向爬虫实战
  • 容斥与二项式反演
  • react useCallback Hook详解
  • 从Docker构建失败到CRA被淘汰:一个React项目的ES模块探索记录
  • 充气泵PCBA方案中数字传感器和模拟传感器的差异
  • 实用指南:小米17手机的上市公司供应商
  • CDN + WAF + CLB + Higress 架构下的 TLS 加解密详细解析(适用阿里云)
  • react useMemo Hook详解
  • react useContext 详解
  • Python技能大赛-备赛建议
  • 【软件系统架构】系列七:系统性能——操作系统性能深入解析 - 实践
  • 你的下一款定位神器,何必是GPS?Nordic带你解锁Wi-Fi SSID的隐藏潜能
  • CF407E k-d-sequence 题目分析(0929模拟赛最后一题)
  • Linux 生成随机端口
  • MATLAB 中 dsp.FFT 系统对象:从原理到实践的完整指南
  • 并发编程可见性
  • C# Devexpress GridControl实现全选功能(转载,记录)
  • github Connection reset by 20.205.243.160 port 443 fatal: Could not read from remote repository.
  • VsCode Ai插件
  • 完整教程:基于完全分布式模式部署Hadoop(喂饭教程)
  • Vue 3.6 引入 Vapor Mode,虚拟DOM已死?
  • part 10
  • Nordic发布用于nRF54L系列的nRF Connect SDK裸机选项
  • 微软SSO集成中的顺序用户ID身份验证绕过漏洞剖析
  • content和text方法的区别
  • shell脚本动态域名解析阿里云
  • 聪明的wyk
  • Windows下进程和账户权限