3.1
闲话
做题纪要
luogu B3908 异或构造题？
-
构造 \(x= \bigoplus\limits_{i=1}^{n}a_{i}\) 即可。
点击查看代码
int main() { ll n,a,x=0,i; cin>>n; for(i=1;i<=n;i++) { cin>>a; x^=a; } cout<<x<<" "<<0<<endl; return 0; }
luogu P4303 [AHOI2006] 基因匹配
-
不太清楚该做法是否能扩展到其他情况。
点击查看代码
int c[200000],f[200000],a[200000],b[200000]; vector<int>vis[200000]; int lowbit(int x) { return (x&(-x)); } void add(int n,int x,int key) { for(int i=x;i<=n;i+=lowbit(i)) { c[i]=max(c[i],key); } } int getsum(int x) { int ans=0; for(int i=x;i>=1;i-=lowbit(i)) { ans=max(ans,c[i]); } return ans; } int main() { int n,ans=0,i,j; cin>>n; for(i=1;i<=5*n;i++) { cin>>a[i]; vis[a[i]].push_back(i); } for(i=1;i<=5*n;i++) { cin>>b[i]; } for(i=1;i<=5*n;i++) { if(vis[b[i]].size()>=1) { for(j=vis[b[i]].size()-1;j>=0;j--) { f[vis[b[i]][j]]=getsum(vis[b[i]][j]-1)+1; add(5*n,vis[b[i]][j],f[vis[b[i]][j]]); } } } for(i=1;i<=5*n;i++) { ans=max(ans,f[i]); } cout<<ans<<endl; return 0; }
3.2
闲话
做题纪要
luogu P5142 区间方差
-
对方差的推导过程详见 2.20 做题纪要 luogu P1471 方差 。
点击查看代码
const ll p=1000000007; ll a[500000]; struct SegmentTree { ll l,r,sum1,sum2; }tree[500000]; ll lson(ll x) { return x*2; } ll rson(ll x) { return x*2+1; } void pushup(ll rt) { tree[rt].sum1=(tree[lson(rt)].sum1+tree[rson(rt)].sum1)%p; tree[rt].sum2=(tree[lson(rt)].sum2+tree[rson(rt)].sum2)%p; } void build(ll rt,ll l,ll r) { tree[rt].l=l; tree[rt].r=r; if(l==r) { tree[rt].sum1=a[l]; tree[rt].sum2=a[l]*a[l]%p; return; } ll mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } void update(ll rt,ll pos,ll val) { if(tree[rt].l==tree[rt].r) { tree[rt].sum1=val; tree[rt].sum2=val*val%p; return; } ll mid=(tree[rt].l+tree[rt].r)/2; if(pos<=mid) { update(lson(rt),pos,val); } else { update(rson(rt),pos,val); } pushup(rt); } ll query1(ll rt,ll l,ll r) { if(r<tree[rt].l||tree[rt].r<l) { return 0; } if(l<=tree[rt].l&&tree[rt].r<=r) { return tree[rt].sum1; } return (query1(lson(rt),l,r)+query1(rson(rt),l,r))%p; } ll query2(ll rt,ll l,ll r) { if(r<tree[rt].l||tree[rt].r<l) { return 0; } if(l<=tree[rt].l&&tree[rt].r<=r) { return tree[rt].sum2; } return (query2(lson(rt),l,r)+query2(rson(rt),l,r))%p; } ll qpow(ll a,ll b,ll p) { ll ans=1; while(b>0) { if(b&1) { ans=ans*a%p; } b>>=1; a=a*a%p; } return ans; } int main() { ll n,m,x,y,pd,sum1,sum2,i; cin>>n>>m; for(i=1;i<=n;i++) { cin>>a[i]; } build(1,1,n); for(i=1;i<=m;i++) { cin>>pd>>x>>y; if(pd==1) { update(1,x,y); } if(pd==2) { sum1=query1(1,x,y)*qpow(y-x+1,p-2,p)%p; sum2=query2(1,x,y)*qpow(y-x+1,p-2,p)%p; cout<<(sum2-sum1*sum1%p+p)%p<<endl; } } return 0; }
3.3
闲话
做题纪要
AT_joig2021_d 展覧会 2 (Exhibition 2)
3.4
闲话
- 上午上正课的时候，感觉讲的好快，有点跟不上了。
- 下午刚到机房的时候，有只鸽子飞进了 \(1\) 机房，找 \(miaomiao\) 说要把鸽子放出去了但没成功。后来 \(feifei\) 来了后联合机房众人把鸽子放出去了。
- \(miaomiao\) 又稍微解释了下直升的政策，包括但不限于分校区时因怕和 @5k_sync_closer ， @hh弟中弟 抢明年省队名额故不给分到 HZ 然后两个校区平分；若没考到衡中系自主招生线则必须学奥赛，学费看实际奥赛成绩。然后扯了些别的，包括但不限于因学校师资紧张，年级部不给安排上高一课程；初三下半年重心要放在奥赛上。
做题纪要
luogu P3451 [POI2007]ATR-Tourist Attractions
-
跑 \(d+1\) 遍 \(dijkstra\) ，分别预处理出从 \(1 \sim d+1\) 到 \(1 \sim d+1\) 和 \(n\) 的最短距离。
-
设 \(f_{i,j}\) 表示当前“停留状态”对应的二进制数为 \(i\) 时，且当前处于点 \(j\) 时的最短路长度。
-
接下来考虑优化空间。
- 将 \(2 \sim d+1\) 映射到 \(0 \sim d-1\) 。
- 因在转移过程中若 \(f_{i,j}\) 能进行转移则，则状态 \(i\) 中已经包含了 \(j\) ，故可以抹去这一位。
点击查看代码
struct node { int nxt,to,w; }e[400010]; int head[20010],dis[30][20010],viss[20010],f[(1<<19)+10][22],cnt=0; bool vis[20010]; void add(int u,int v,int w) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; e[cnt].w=w; head[u]=cnt; } void dijkstra(int s) { memset(dis[s],0x3f,sizeof(dis[s])); memset(vis,false,sizeof(vis)); priority_queue<pair<int,int> >q; int x,i; dis[s][s]=0; q.push(make_pair(0,-s)); while(q.empty()==0) { x=-q.top().second; q.pop(); if(vis[x]==false) { vis[x]=true; for(i=head[x];i!=0;i=e[i].nxt) { if(dis[s][e[i].to]>dis[s][x]+e[i].w) { dis[s][e[i].to]=dis[s][x]+e[i].w; q.push(make_pair(-dis[s][e[i].to],-e[i].to)); } } } } } int del(int x,int y) { return ((x>>(y+1))<<y)+x-((x>>y)<<y); } int main() { int n,m,d,q,u,v,w,r,s,ans=0x7f7f7f7f,i,j,k; cin>>n>>m>>d; for(i=1;i<=m;i++) { cin>>u>>v>>w; add(u,v,w); add(v,u,w); } cin>>q; for(i=1;i<=d+1;i++) { dijkstra(i); } if(d==0) { cout<<dis[1][n]<<endl; } else { memset(f,0x3f,sizeof(f)); for(i=1;i<=q;i++) { cin>>r>>s; viss[s]|=1<<(r-2); } for(i=1;i<=d+1;i++) { if(viss[i]==0) { f[0][i]=dis[1][i]; } } for(i=0;i<=(1<<d)-1;i++) { for(j=2;j<=d+1;j++) { if((i>>(j-2))&1) { for(k=2;k<=d+1;k++) { if(((i>>(k-2))&1)==0&&(i&viss[k])==viss[k]) { f[del(i,k-2)][k]=min(f[del(i,k-2)][k],f[del(i,j-2)][j]+dis[j][k]); } } } } } for(i=2;i<=d+1;i++) { ans=min(ans,f[del((1<<d)-1,i-2)][i]+dis[i][n]); } cout<<ans<<endl; } return 0; }
3.5
闲话
做题纪要
luogu P2831 [NOIP2016 提高组] 愤怒的小鸟
luogu P3622 [APIO2007]动物园
luogu P4163 [SCOI2007]排列
- 多倍经验： CF401D Roman and Numbers