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

【做题记录】贪心--提高组

A. Monotone Subsequence

有点 Ad-hoc。

\(i\) 次查询,直接询问当前未被删去的所有点。如果回答 \(\ge n+1\),那么直接输出;否则将回答的这些点标一个级别 \(i\)。最后一次询问之后还剩下的标为 \(n+1\)。根据鸽笼原理,如果最后没剩下,那么中间必然有一次回答 \(\ge n+1\)

可以发现,对于每个级别为 \(i\) 的位置,在其之前必然有一个级别为 \(i-1\) 的位置 \(j\),且 \(p_j\) 是必然比 \(p_i\) 大的。于是我们连边,跑一个 DAG 上 DP 即可。

Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define pb push_back
using namespace std;
namespace asbt{
const int maxn=1e4+5;
int T,n,a[maxn],f[maxn],g[maxn];
set<int> st;
vector<int> e[maxn];
queue<int> q;
il void print(int u){if(!u){printf("! ");return ;}print(g[u]);printf("%d ",u);
}
int main(){scanf("%d",&T);while(T--){scanf("%d",&n);st.clear();for(int i=1;i<=n*n+1;i++){st.insert(i),e[i].clear();}for(int i=1;i<=n;i++){printf("? %d ",(int)st.size());for(int j:st){printf("%d ",j);}puts(""),fflush(stdout);int c;scanf("%d",&c);if(c>=n+1){printf("! ");for(int j=1,x;j<=c;j++){scanf("%d",&x);if(j<=n+1){printf("%d ",x);}}puts(""),fflush(stdout);goto togo;}for(int j=1,x;j<=c;j++){scanf("%d",&x);a[x]=i,st.erase(x);}}for(int i:st){a[i]=n+1;}for(int i=1;i<=n*n+1;i++){if(a[i]==1){q.push(i),f[i]=1,g[i]=0;}else{for(int j=i-1;j;j--){if(a[j]==a[i]-1){e[j].pb(i);break;}}}}while(q.size()){int u=q.front();q.pop();for(int v:e[u]){q.push(v);f[v]=f[u]+1,g[v]=u;}}for(int i=1;i<=n*n+1;i++){if(f[i]==n+1){print(i);puts(""),fflush(stdout);break;}}togo:;}return 0;
}
}
int main(){return asbt::main();}

B. Yet Another MEX Problem

重要结论\(\sum[a_i>\operatorname{mex}(a)]=\max\limits_{x\notin a}\sum[a_i>x]\)。证明显然。

于是我们考虑在移动 \(r\) 时对每个 \(x\) 维护右面那个式子。设最后出现 \(x\) 的位置为 \(p_x\),我们维护的就是 \([p_x+1,r]\) 中大于 \(x\) 的数的个数,这是方便用线段树维护的。

Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define lid id<<1
#define rid id<<1|1
using namespace std;
namespace asbt{
const int maxn=3e5+5;
int T,n,a[maxn],tr[maxn<<2],tag[maxn<<2];
il void pushup(int id){tr[id]=max(tr[lid],tr[rid]);
}
il void pushtag(int id,int v){tr[id]+=v,tag[id]+=v;
}
il void pushdown(int id){if(tag[id]){pushtag(lid,tag[id]);pushtag(rid,tag[id]);tag[id]=0;}
}
il void build(int id,int l,int r){tr[id]=tag[id]=0;if(l==r){return ;}int mid=(l+r)>>1;build(lid,l,mid);build(rid,mid+1,r);
}
il void upd(int id,int l,int r,int p){if(l==r){tr[id]=0;return ;}pushdown(id);int mid=(l+r)>>1;if(p<=mid){upd(lid,l,mid,p);}else{pushtag(lid,1);upd(rid,mid+1,r,p);}pushup(id);
}
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>T;while(T--){cin>>n;build(1,0,n);for(int i=1;i<=n;i++){cin>>a[i];upd(1,0,n,a[i]);cout<<tr[1]<<' ';}cout<<'\n';}return 0;
}
}
int main(){return asbt::main();}

C. Make Good

Ad-hoc。

先把 \(n\) 为奇数判掉。然后开始对脑电波寻找性质:

首先,所有的 (()) 都是可以随意移动的。比如 ((

  • (()\(\to\))))\(\to\))((
  • )((\(\to\))))\(\to\)(()
  • (((\(\to\)((((没变但等于是动了)

所以我们先用栈把所有的 (()) 找出来,设有 \(cnt\) 个。剩下的字符串有以下三种可能:

  1. ()()()...()
  2. )()()()...()(
  3. 空串

那么如果 \(cnt\) 为奇数则必然无解,如果为偶数那么可以在这个串左右各加 \(\frac{cnt}{2}\)(())。当然如果 \(cnt=0\) 那么第二种情况就不成立。

Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=2e5+5;
int T,n,top,cnt;
char stk[maxn];
string s;
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>T;while(T--){cin>>n>>s;if(n&1){cout<<-1<<'\n';continue;}cnt=top=0;for(int i=0;i<n;i++){if(!top){stk[++top]=s[i];}else if(stk[top]==s[i]){cnt++,top--;}else{stk[++top]=s[i];}}if(cnt&1){cout<<-1<<'\n';}else if(!cnt&&stk[1]==')'){cout<<-1<<'\n';}else{for(int i=1;i<=cnt>>1;i++){cout<<"((";}for(int i=1;i<=top;i++){cout<<stk[i];}for(int i=1;i<=cnt>>1;i++){cout<<"))";}cout<<'\n';}}return 0;
}
}
int main(){return asbt::main();}

D. Long Journey

\(len=\operatorname{lcm}(a)\)。显然 \(len\le2520\)。称走 \(len\) 格为走了一个周期。

考虑整个过程,就是走 \(\lfloor\frac{m}{len}\rfloor\) 个周期,然后再走 \(m\bmod len\) 步。考虑压缩前面那些周期的过程。枚举进入这个周期前的时刻模 \(n\) 的值 \(i\),我们希望求出此状态下走一个周期的用时。模拟一遍这个周期的过程即可。

模拟的过程是一个贪心:如果下一格在下一秒是陷阱,那就等一秒,否则就走过去。如果在一格等待了 \(n\) 秒还是没走,那么无解。贪心的正确性在于不会出现两个相邻的格子同时是陷阱的情况。在每个格子都最多等待 \(n\) 次,所以单次模拟的时间复杂度是 \(O(n\times len)\) 的。这个预处理的总时间是 \(O(n^2\times len)\)

于是我们就可以快速计算了。走周期这个过程显然可合并,于是我们对走周期这个过程做快速幂。合并两个过程是 \(O(n)\) 的,这一部分时间复杂度 \(O(n\log\lfloor\frac{m}{len}\rfloor)\)。然后再类似上面的方式模拟最后一小段即可。

Code
#include<bits/stdc++.h>
#define int long long
#define il inline
#define gcd __gcd
using namespace std;
namespace asbt{
const int inf=1e18;
int T,n,m,a[12],b[12];
struct juz{int a[12];il int&operator[](int x){return a[x];}il juz operator*(juz b)const{juz c;for(int i=0;i<n;i++){c[i]=min(a[i]+b[(i+a[i])%n],inf);}return c;}
}bas;
il int calc(int t,int len){int p=0,res=0;while(p<len){p++;int cnt=0;t=t%n+1,res++;while(p%a[t]==b[t]){if(cnt==n){return inf;}t=t%n+1,cnt++,res++;}}return res;
}
il juz qpow(juz x,int y){juz res;for(int i=0;i<n;i++){res[i]=0;}while(y){if(y&1){res=res*x;}x=x*x,y>>=1;}return res;
}
int main(){ios::sync_with_stdio(0),cin.tie(0);cin>>T;while(T--){cin>>n>>m;int len=1;for(int i=1;i<=n;i++){cin>>a[i];len=len/gcd(len,a[i])*a[i];}for(int i=1;i<=n;i++){cin>>b[i];}if(m<len){int ans=calc(0,m);cout<<(ans>=inf?-1:ans)<<'\n';continue;}for(int i=0;i<n;i++){bas[i]=calc(i,len);
//			cout<<bas[i]<<' ';}
//		cout<<'\n';int ans=qpow(bas,m/len)[0];ans=ans+calc(ans%n,m%len);cout<<(ans>=inf?-1:ans)<<'\n';}return 0;
}
}
signed main(){return asbt::main();}
http://www.hskmm.com/?act=detail&tid=37664

相关文章:

  • 如何炫酷地使用集合划分容斥
  • 简单云计算算法--20251023
  • 处理空输入踩的坑
  • latex输入公式
  • 【为美好CTF献上祝福】 New Star 2025 逆向笔记
  • XXL-JOB(5)
  • 蛋白表达原理与关键要素解析
  • Ramanujan Master Theorem
  • 顾雅南的声音美化课堂
  • C++案例 自定义数组
  • 【周记】2025.10.13~2025.10.19
  • 背包
  • 10.23《程序员修炼之道 从小工到专家》第二章 注重实效的途径 - GENGAR
  • 玩转单片机之智能车小露——LED闪烁实战
  • ord() 函数
  • 2025.10.23总结 - A
  • 大模型 | VLA 初识及在自动驾驶场景中的应用
  • ExPRT.AI如何预测下一个将被利用的漏洞
  • Redis中的分布式锁之SETNX底层实现
  • 攻击模拟
  • 2025家纺摄影公司推荐,南通鼎尚摄影专注产品视觉呈现
  • AI元人文构想的跨学科研究:技术实现与人文影响分析——对自由与责任的再框架化(DeepSeek基于Ai元人文系列文章研究)
  • Python---简易编程解决工作问题
  • 日总结 16
  • 比赛题解 总结
  • DM8 安装包 for linux_x86
  • MPK(Mirage Persistent Kernel)源码笔记(1)--- 基础原理
  • 模拟can通信
  • 解题报告-拯救计划(概率 DP)
  • 日志分析-IIS日志分析