The 16th Harbin Engineering University Collegiate Programming Contest
A. stral Reflection
用右界覆盖左界为下标的数组 构成一个以i为左界,a[i]为右界的数组 以此表示区间
对于每一个陨石都尽可能找左界<=自己,右界尽可能大的一个区间,那么反映在上面的数组就是最大的一个前缀值
对于已选区间要去掉可以到达的数,学习官方解答利用vector的back() (我自己都从来没用过这个函数)
注:官方解答的线段树写的也比我漂亮很多,悲,拉过来当板子了
struct node{ int l,r, max; }tr[N*4]; void pushup(node &u,node &l,node &r){ u.max=max(l.max,r.max); } void pushup(int u){ pushup(tr[u],tr[u<<1],tr[u<<1|1]); } void build(int u,int l,int r){ if(l==r){ tr[u]={l,l,0}; } else { tr[u]={l,r}; int mid=l+r >>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); } } void modify(int u,int x,int w){ if (tr[u].l == x && tr[u].r == x) tr[u]= {x, x, max(tr[u].max,w)}; else{ int mid = tr[u].l + tr[u].r >> 1; if (x <= mid) modify(u << 1, x, w); else modify(u << 1 | 1, x, w); pushup(u); } } int ask(int u,int l,int r){ if (tr[u].l >= l && tr[u].r <= r) return tr[u].max; else{ int mid = tr[u].l + tr[u].r >> 1; if (r <= mid) return ask(u << 1, l, r); else if (l > mid) return ask(u << 1 | 1, l, r); else{ int lans = ask(u << 1, l, r); int rans = ask(u << 1 | 1, l, r); int res=max(lans,rans); return res; } } } void solve(){ int n=read(),m=read(); build(1,1,n); for(int i=1;i<=m;i++){ int x=read(); if(x==1){ int left=read(),right=read(); int w=read(); modify(1,left,right); }else { int k=read(); vector<int>a(k); for(int i=0;i<k;i++) a[i]=read(); sort(a.begin(),a.end(),greater<int>()); int ans=0; while(a.size()){ int x=ask(1,1,a.back()); if(x<a.back()){ ans=-1; break; } ans++; while(a.size()&&x>=a.back()) a.pop_back(); } cout<<ans<<'\n'; } } //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
map<char,int>mp; void solve(){ string s; cin>>s; int cnt=0; for(int i=0;i<s.size();i++){ if(mp[s[i]]==0)cnt++,mp[s[i]]=1; } puts(cnt>1?"2":"-1"); }
C. hivalric Blossom
int l[N],r[N],ans[N]; void solve(){ int n=read(),m=read(); stack<int>st; for(int i=n;i>=1;i--) st.push(i); for(int i=1;i<=m;i++){ int x=read(),y=read(); r[x]=y; l[y]=x; } for(int i=1;i<=n;i++){ if(l[i]){ ans[i]=ans[l[i]]; if(!r[i]) st.push(ans[i]); }else { ans[i]=st.top(); if(r[i]) st.pop(); } } for(int i=1;i<=n;i++) cout<<ans[i]<<' '; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
D. andelion Knight
对于两个a,b数组求前缀和
我们对记录b数组中i这个数字出现的左界l[i]和右界r[i]
对于a中每个前缀和x都有l[x]~r[x]可以满足要求,所以从x+l[x]~x+r[x]的f(i)都会多出一个方案,这里用差分实现区间加
int a[N],b[N],pra[N],prb[N],cntl[N],cntr[N],ans[N]; void solve(){ int n=read(); for(int i=1;i<=n;i++){ a[i]=read(); pra[i]=pra[i-1]+a[i]; } memset(cntl,-1,sizeof(cntl)); memset(cntr,-1,sizeof(cntr)); cntl[0]=0;cntr[0]=0; for(int i=1;i<=n;i++){ b[i]=read(); prb[i]=prb[i-1]+b[i]; if(cntl[prb[i]]==-1)cntl[prb[i]]=i; cntr[prb[i]]=i; } for(int i=0;i<=n;i++){ if(cntl[pra[i]]==-1)break; ans[i+cntl[pra[i]]]++; ans[i+cntr[pra[i]]+1]--; } int res=0; for(int i=0;i<=2*n;i++){ res+=ans[i]; cout<<res<<" "; } cout<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
E. clipsing Star
博弈论问题,首先正向思考无果,就反向思考
对于最后一轮,先手必全部拿走。那么倒数第二轮的先手必会衡量当前的a[n-1]和a[n],全部拿走大的一个。所以最后两轮的策略是确定的,那么可以向上推,已知最后两轮的策略,倒数第三轮的先手会衡量当前的a[n-2]和abs(a[n]-a[n-1]),拿走大的一种。倒数第四轮的先手会考虑a[n-3]和abs(abs(a[n]-a[n-1])-a[n-2]),所以我们只需一直反推就可以得到所谓的收益差
int a[N]; void solve(){ int n=read(),ans=0; for(int i=1;i<=n;i++){ a[i]=read(); } for(int i=n;i>=1;i--){ ans=abs(a[i]-ans); } cout<<abs(ans)<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
double l[N],r[N]; int n,m; bool check(double x) { double fin=0; for(int i=1;i<=n;i++){ if(x>r[i]) fin+=1; else if(x>l[i]){ fin+=(x-l[i])/(r[i]-l[i]); } } return fin>=m; } double bs3(double l, double r) { const double eps = 1e-6; while (r - l > eps) { double mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid; } return l; } void solve(){ n=read(),m=read(); for(int i=1;i<=n;i++){ cin>>l[i]>>r[i]; } cout<<bs3(0,1000000000)<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
void solve(){ int n=read(); cout<<n<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
int ans[N]; void yuchuli(){ ans[0]=1; ans[1]=0; ans[2]=1; ans[3]=2; ans[4]=1; for(int i=5;i<N;i++){ ans[i]=(ans[i-3]*2%mod+ans[i-2])%mod; } } void solve(){ int n=read(); cout<<ans[n-2]<<'\n'; //puts(ans>0?"YES":"NO"); //puts(ans>0?"Yes":"No"); }
void solve(){ puts("NO"); //puts(ans>0?"Yes":"No"); }
- Engineering Programming Collegiate University Contestengineering programming collegiate university programming collegiate provincial contest programming university contest jimei programming collegiate jiangsu contest programming university jiaotong contest international programming collegiate contest programming collegiate mianyang contest programming collegiate contest guilin programming collegiate shanghai contest programming collegiate shenzhen contest