2022HDU多校第五场
2022/8/4 6:22:58
本文主要是介绍2022HDU多校第五场,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2022HDU多校第五场
过程
开场12读了个假题,以为是找一个时间最短的跟后面排队,wa了两发反应过了是找一个人数最少的跟在后面排队,然后wa了一发没清空就过了,寄,开始演队友了。10智慧题,明牌的话先手应该赢面很大,那什么时候会输呢,发现叫的骰子数必须大于等于1,那么就只有一种会输的情况了,没玩过吹牛,题面看了好久才看懂,这下又在签到上浪费了时间。同时队友过了03签到再看06,于是我跟榜看07,推出了暴力的DP式子有卷积形式,于是叫自己的想法告诉队友让他去搓NTT去,自己将暴力打好准备对拍,期间队友06WA了,帮他看了看,没有发现什么问题,于是转向01,发现是珂朵莉树,于是迅速开码,码完已经快结束了交完T了一发,已经没有时间在改了。这期间队友码完07T了,于是我交他动态数组创建将从小到大合并改为启发式合并通过07,(队友好强,这下成辅助了)。快结束的时候队友发现06题读假了,增删改都算一次操作,而他只考虑了增删,这波我跟着他给的题意想确实没找出bug,原来是题读错了,不过原文描述着实有点抽象, “Now you can modify, add or delete one letter in 1 unit of time.”,这里modify 我们理解是跟前面,现在你可以修改了,增加或删除消耗一单位时间,但实际上是 现在你可以 修改,增加,删除,均消耗一单位时间,这下顶级理解了。
赛后发现自己01假了,区间和只能再开一个线段树维护,不能在珂朵莉树上维护,否则珂朵莉树复杂度就假了。
这次比赛启发式合并NTT已经算是第4道签到题了,已经人均NTT了,自己应更加扩充自己的知识库了。02需要使用非线性筛,甚至要更高级的,(学的杜教筛已经不配了),04听人说是暴力可做,可惜没时间看了。总结下来就是题一定要读对,题读错了会浪费巨大时间,这次12浪费了一些时间,10阅读理解智慧题思考时间尚可,01假了属实是人菜了,唔,签到一定要更快更好,要倒在难题上。
题解
01
区间赋属性很容易联想到珂朵莉树,同时单点需要维护权值,此处必须再开线段树来记录,不能在珂朵莉树上维护权值,否则珂朵莉树退化为暴力。
那么在珂朵莉树上维护属性,每当属性更改时,对相应属性进行按时间差分来获得修改前后得到的权值,最后在线段树上单点求值再加上属性对应权值即可。需注意n为1e8,而q为1e5,故此处需要动态开点线段树。
int n,q; int attr=0; vector<ll>sum; struct SEG{ ll sum[maxm],tag[maxm]; int lson[maxm],rson[maxm]; int root,cnt; void clear(int &o){ if(!o) return; sum[o]=tag[o]=0; clear(lson[o]);clear(rson[o]); o=0; } inline void up(int o){sum[o]=sum[lson[o]]+sum[rson[o]];} void down(int o,int l,int r){ int mid=(l+r)>>1; ll tmp=tag[o];tag[o]=0; if(!lson[o]) lson[o]=++cnt; if(!rson[o]) rson[o]=++cnt; sum[lson[o]]+=1LL*tmp*(mid-l+1); sum[rson[o]]+=1LL*tmp*(r-mid); tag[lson[o]]+=tmp;tag[rson[o]]+=tmp; } void update(int &o,int l,int r,int L,int R,ll val){ if(!o) o=++cnt; if(L<=l&&r<=R){sum[o]+=val;tag[o]+=val;return;} if(tag[o])down(o,l,r); int mid=(l+r)>>1; if(L<=mid) update(lson[o],l,mid,L,R,val); if(mid<R) update(rson[o],mid+1,r,L,R,val); up(o); } ll query(int &o,int l,int r,int pos){ if(!o) o=++cnt; if(l==r) {return sum[o];} if(tag[o]) down(o,l,r); int mid=(l+r)>>1; if(pos<=mid) return query(lson[o],l,mid,pos); else return query(rson[o],mid+1,r,pos); } }; struct KDLTree{ struct node{ int l,r;mutable int c; bool operator < (const node x)const { return l<x.l; } }; set<node>s;SEG T; void clear(){ s.clear(); T.clear(T.root); T.root=T.cnt=0; } void split(int x){ auto it = s.lower_bound({x,0,0}); if(it!=s.end()&&it->l==x) return; it--; int L=it->l,R=it->r; int C=it->c; s.erase(it); s.insert({L,x-1,C}); s.insert({x,R,C}); } set<node>::iterator find(int x){ auto it=s.upper_bound({x,0,0}); it--;return it; } void assign(int l,int r,int x){ split(l);split(r+1); auto itl = s.lower_bound({l,0,0}); auto itr = s.lower_bound({r+1,0,0}); for(auto it=itl;it!=itr;it++){ T.update(T.root,1,n,it->l,it->r,sum[it->c]); } s.erase(itl,itr); s.insert({l,r,x}); T.update(T.root,1,n,l,r,-sum[x]); } void assign1(int pos,int x){ auto it=find(pos); auto tmp=it; int l=inf,r=-1,y=it->c; while(it->c==y) { r=it->r; it++; if(it==s.end()) break; } it=tmp; while(it->c==y){ l=it->l; if(it==s.begin()) break; it--; } assign(l,r,x); } ll query(int x){ auto it=find(x); return sum[it->c]+T.query(T.root,1,n,x); } }kdl; void solve(){ n=read();q=read(); sum.clear();sum.resize(q+1); kdl.clear();attr=0; kdl.s.insert({1,n,0}); ll last=0,ans=0; int n2=(n-1)/2; while(q--){ int opt=read(); int x,y,c,v; if(opt==1){ x=read(),c=read(); x=((x-1)^last)%n+1; c=((c-1)^last)%n2+1; ++attr; if(x>c && x+c<=n) kdl.assign(x-c,x+c,attr); else if(x<=c){ int tmp=c-x+1; kdl.assign(1,x+c+tmp,attr); }else { int tmp=x+c-n; kdl.assign(x-c-tmp,n,attr); } } else if(opt==2){ x=read(),y=read(); x=((x-1)^last)%n+1; y=((y-1)^last)%n+1; auto tmp=kdl.find(x); kdl.assign1(y,tmp->c); } else if(opt==3){ x=read(),v=read(); x=((x-1)^last)%n+1; auto tmp=kdl.find(x); sum[tmp->c]+=v; } else{ x=read();x=((x-1)^last)%n+1; ans=kdl.query(x); printf("%lld\n",ans); last=ans&1073741823; } } }
02
只会杜教筛,要被时代淘汰力
03
对每一层建一个入点和出点,该层所有点连向出点,入点连向该层所有点,然后出点向+-k层的入点相连,直接跑dijk最短路即可。
struct Dijkstra{ bool vis[maxn]; ll dis[maxn]; struct node{ ll dis;int id; bool operator < (const node &a)const{ return dis>a.dis; } }; priority_queue<node>q; vector<P>G[maxn]; void add(int u,int v,int w){ G[u].pb({v,w}); } inline void clear(int n){rep(i,1,n) G[i].clear();} void Dijk(int st,int n){ while(!q.empty()) q.pop(); rep(i,1,n) vis[i]=0,dis[i]=linf; dis[st]=0; q.push((node){0,st}); while(!q.empty()){ int u=q.top().id;q.pop(); if(vis[u]) continue; vis[u]=1; for(auto x:G[u]){ int w=x.second,v=x.first; if(dis[v]>dis[u]+w){ dis[v]=dis[u]+w; q.push((node){dis[v],v}); } } } } }D1; int n,k,p,st,ed; int dp[maxn]; void dfs(int now,int fa,int dep){ dp[now]=dep; for(auto x:D1.G[now]){ if(x.first==fa) continue; dfs(x.first,now,dep+1); } } void solve(){ cin>>n; rep(i,1,n-1){ int u,v,w; scanf("%d %d %d",&u,&v,&w); D1.add(u,v,w); D1.add(v,u,w); } scanf("%d %d",&k,&p); scanf("%d %d",&st,&ed); dfs(1,0,1); rep(j,1,n){ int i=dp[j]; int t1=(i<<1)+n,t2=(i<<1)-1+n; D1.add(t2,j,0); D1.add(j,t1,0); if(i>k) D1.add(t1,((i-k)<<1)-1+n,p); if(i+k<=n) D1.add(t1,((i+k)<<1)-1+n,p); } D1.Dijk(st,3*n); printf("%lld\n",D1.dis[ed]); D1.clear(n*3); }
04
待补
06
待补
07
各个数相连形成若干个环,环间任意取,环内取套公式,
一个相关博客,由此将若干个环用NTT合并,合并时进行启发式合并,每次选两个长度最小的合并,最后可保证复杂度\(O(nlog^2n)\)
10
注意到双方明牌,且说话时骰子数必须大于等于1,那么在两个人都满足第三种特殊状态时,骰子数为0,此时先手必输,否则均为先后必胜。
int n; set<int>s; void solve(){ cin>>n;int tmp;bool flag1=0,flag2=0; s.clear(); rep(i,1,n) scanf("%d",&tmp),s.insert(tmp); if(s.size()==n) flag1=1; s.clear(); rep(i,1,n) scanf("%d",&tmp),s.insert(tmp); if(s.size()==n) flag2=1; if(flag1&flag2) puts("Just a game of chance."); else puts("Win!"); }
12
新来的人回去到人数最少且标号最小的队伍去,那么一个set维护正在排队的人,每次根据当前的时间,来判断哪些排队的人排完了,以此来更新各个队列的人数,S[i]表示队伍中有i人的队伍,动态维护这些STL即可。
int n,m; struct node{ ll ddl;int id; }; bool operator < (node a,node b){ if(a.ddl==b.ddl) return a.id<b.id; else return a.ddl<b.ddl; } set<node>s; set<int>S[maxn]; int cnt[maxn]; struct Peo{ ll a,s; }p[maxn]; ll len[maxn]; bool cmp(Peo a,Peo b){ return a.a<b.a; } void solve(){ cin>>n>>m; rep(i,1,n) scanf("%lld %lld",&p[i].a,&p[i].s); sort(p+1,p+1+n,cmp); rep(i,1,m) S[0].insert(i); ll ans=0;int now=0; rep(i,1,n){ if(s.size()>0){ auto it=s.upper_bound((node){p[i].a,inf}); while(it!=s.begin()){ auto x=*s.begin(); s.erase(s.begin()); S[cnt[x.id]].erase(S[cnt[x.id]].find(x.id)); cnt[x.id]--; S[cnt[x.id]].insert(x.id); now=min(now,cnt[x.id]); } } int x=*S[now].begin(); S[now].erase(x); cnt[x]++; S[now+1].insert(x); if(!S[now].size()) now++; len[x]=max(len[x],p[i].a)+p[i].s; s.insert((node){len[x],x}); } rep(i,1,m) ans=max(ans,len[i]); s.clear(); rep(i,1,m) cnt[i]=0,len[i]=0; rep(i,0,n) S[i].clear(); printf("%lld\n",ans); }
这篇关于2022HDU多校第五场的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?