311 字
1 分钟
ACK 2026 暑假第一次集训
AK,总体比较容易,最后一题想了很久
补题链接
前三题
前两题都是基础语法,没有要讲的
第三题稍微提一下,其实只用到了去重,c++的话用set和unordered_set都可以
unordered_set<string> st;string s;
void solve() { while(cin>>s&&s!="0"){ if(st.find(s)==st.end()){ st.insert(s); cout<<s; } }}第四题 前缀和+质数筛
朴素解法是一个一个核对,复杂度O(),但是注意到范围的最大值达到,那么最坏结果计算量达到,朴素解法是过不了的,因此可以思考一下,是否可以简化计算量,对于l1,r1的范围的每个数x,要查询x+l2,x+r2之间是否存在质数即可,合数更普遍,Burnside更容易获胜,只要存在一个数在Edisnrub所选的范围里面没有质数解即可,因此可以用质数筛记录最大区间中的所有质数,通过前缀和记录区间中的质数个数之和,这样,区间查询的结果就能反映出该区间有没有质数每轮的查询花销就可以被优化:O(n)->O(1)
const ll N = 2e5+5;
vector<int> pr;bool vis[N];
void eulers(){ vis[0]=vis[1]=true; for(int i=2;i<N;i++){ if(!vis[i]){ pr.push_back(i); } for(int j=0;j<pr.size();j++){ if(i*pr[j]>=N){ break; } vis[i*pr[j]]=true; if(i%pr[j]==0){ break; } } }}
int l1,r1,l2,r2;
void solve() { cin>>l1>>r1>>l2>>r2; vector<int> pre(r2+r1+1,0); for(int i=1;i<=r2+r1;i++){ if(!vis[i]) pre[i]=1; pre[i]+=pre[i-1]; } for(int i=l1;i<=r1;i++){ if(pre[i+r2]-pre[i+l2-1]==0){ cout<<"Burnside\n"; return; } } cout<<"Edisnrub\n";}第五题 单调栈
第六题 滑动窗口
第七题 博弈论 dp
分享
如果这篇文章对你有帮助,欢迎分享给更多人!
ACK 2026 暑假第一次集训
https://blog.hydrodyio.xyz/posts/ack-2026-暑假第一次集训/ 部分信息可能已经过时
相关文章 智能推荐








