1.1
闲话
- 以为下午 \(2:30\) 开始进校，遂从家里出发已经比较晚了。到学校后发现是 \(2：30\) 在机房做好，遂直接拉着行李来机房了。
- 晚上 \(miaomiao\) 说今明两天把字符串和动态规划专题收收尾。
做题纪要
CF601E A Museum Robbery
-
线段树分治。
点击查看代码
const ll mod=1000000007,base=10000019; ll st[15010],ed[15010],v[30010],w[30010],f[18][1010],jc[1010],ans[30010],k; struct SMT { struct SegmentTree { vector<ll>info; }tree[120010]; #define lson(rt) (rt<<1) #define rson(rt) (rt<<1|1) void update(ll rt,ll l,ll r,ll x,ll y,ll id) { if(x<=l&&r<=y) { tree[rt].info.push_back(id); return; } ll mid=(l+r)/2; if(x<=mid) { update(lson(rt),l,mid,x,y,id); } if(y>mid) { update(rson(rt),mid+1,r,x,y,id); } } void solve(ll rt,ll l,ll r,ll dep) { for(ll i=1;i<=k;i++) { f[dep][i]=f[dep-1][i]; } for(ll i=0;i<tree[rt].info.size();i++) { for(ll j=k;j>=w[tree[rt].info[i]];j--) { f[dep][j]=max(f[dep][j],f[dep][j-w[tree[rt].info[i]]]+v[tree[rt].info[i]]); } } if(l==r) { for(ll i=1;i<=k;i++) { ans[l]=(ans[l]+f[dep][i]*jc[i-1]%mod)%mod; } } else { ll mid=(l+r)/2; solve(lson(rt),l,mid,dep+1); solve(rson(rt),mid+1,r,dep+1); } } }T; int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif ll n,m,pd,x,tim=0,i; cin>>n>>k; for(i=1;i<=n;i++) { cin>>v[i]>>w[i]; st[i]=1; ed[i]=-1; } cin>>m; for(i=1;i<=m;i++) { cin>>pd; if(pd==1) { n++; cin>>v[n]>>w[n]; st[n]=tim+1; ed[n]=-1; } if(pd==2) { cin>>x; ed[x]=tim; } if(pd==3) { tim++; } } for(i=1;i<=n;i++) { ed[i]=(ed[i]==-1)?tim:ed[i]; if(st[i]<=ed[i]) { T.update(1,1,tim,st[i],ed[i],i); } } for(i=0;i<=k-1;i++) { jc[i]=(i==0)?1:jc[i-1]*base%mod; } T.solve(1,1,tim,1); for(i=1;i<=tim;i++) { cout<<ans[i]<<endl; } return 0; }
HZOJ 368. 稳稳的参天大树
-
观察到深度为 \(dep\) 的点 \(i\) 在 \(n\) 时刻它的初始权值对 \(1\) 的异或次数为 \(\dbinom{n+dep-1}{n-1}\) 。
- 对于长度为 \(dep\) 的数组 \(\{ a \}\) ，初始时有 \(a_{1}=1,a_{2 \sim dep}=0\) ,对其做 \(n\) 阶前缀和后有 \(a_{n,dep}\) 即为异或次数。
- 将前缀和转化成二维平面的格路计数问题后，有 \(\dbinom{n+dep-1}{n-1}\) 即为所求。
-
由 \(Lucas\) 定理可知 \(\dbinom{n+dep-1}{n-1} \bmod 2=1\) 当且仅当 \((n+dep-1)\And(n-1)=n-1\) ，即 \(n-1\) 在二进制表示下是 \(n+i-1\) 的二进制表示下的子集，等价于 \(i\) 二进制表示是 \(n-1\) 二进制表示的子集。
-
此时只需要快速地做到对于每个数 \(i\) 求出它二进制表示下所有子集的异或和。
-
考虑对子集按位 \(DP\) ，设 \(f_{i,j}\) 表示只有前 \(j\) 位和 \(i\) 不同的 \(i\) 的所有子集的异或和。状态转移方程为 \(\begin{cases} f_{i,j}=f_{i,j-1} & i 的第 j 位为 0 \\ f_{i,j}=f_{i,j-1} \bigoplus f_{i \bigoplus 2^{j},j-1} & i 的第 j 位为 1 \end{cases}\) 。
-
做前缀和后注意更新顺序。
点击查看代码
struct node { int nxt,to; }e[2000010]; int head[2000010],dep[2000010],a[2000010],f[2000010],cnt=0,tot=0,base=(1<<20)-1; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void dfs(int x,int fa) { dep[x]=dep[fa]+1; for(int i=head[x];i!=0;i=e[i].nxt) { if(e[i].to!=fa) { dfs(e[i].to,x); } } } int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int n,u,v,i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i]); } for(i=1;i<=n-1;i++) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1,0); for(i=1;i<=n;i++) { f[dep[i]-1]^=a[i]; } for(j=0;j<20;j++) { for(i=0;i<=base;i++) { if((i>>j)&1) { f[i]^=f[i^(1<<j)]; } } } for(i=1;i<=n;i++) { printf("%d ",f[(i-1)^base]); } return 0; }
luogu P5058 [ZJOI2004] 嗅探器
-
找到割点后判断是否将 \(a,b\) 分到了两个连通块内。
-
建出圆方树后从 \(a\) 开始遍历，用栈记录下路径上的点即可。注意嗅探器不能安装在中心服务器上。
点击查看代码
struct node { int nxt,to; }e[1000010]; int head[200010],dfn[200010],low[200010],a,b,ans=0x7f7f7f7f,v_dcc=0,cnt=0,tot=0; stack<int>s,t; vector<int>g[400010]; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void tarjan(int x) { tot++; dfn[x]=low[x]=tot; s.push(x); for(int i=head[x];i!=0;i=e[i].nxt) { if(dfn[e[i].to]==0) { tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); if(dfn[x]==low[e[i].to]) { v_dcc++; g[v_dcc].push_back(x); g[x].push_back(v_dcc); int tmp=0; while(e[i].to!=tmp) { tmp=s.top(); s.pop(); g[v_dcc].push_back(tmp); g[tmp].push_back(v_dcc); } } } else { low[x]=min(low[x],dfn[e[i].to]); } } } void dfs(int x,int fa) { s.push(x); if(x==b) { t=s; t.pop(); while(t.size()>=3) { ans=min(ans,t.top()); t.pop(); } } for(int i=0;i<g[x].size();i++) { if(g[x][i]!=fa) { dfs(g[x][i],x); } } s.pop(); } int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int n,u,v,i; cin>>n; while(cin>>u>>v) { if(u==0&&v==0) { break; } else { add(u,v); add(v,u); } } v_dcc=n; for(i=1;i<=n;i++) { if(dfn[i]==0) { tarjan(i); } } cin>>a>>b; while(s.empty()==0) { s.pop(); } dfs(a,0); if(ans>n) { cout<<"No solution"<<endl; } else { cout<<ans<<endl; } return 0; }
CF487E Tourists
-
对于每个方点开一个
multiset存储所在点双连通分量内圆点的最小值，修改时若遇到菊花则会被卡成暴力。 -
不妨让每个方点只存储圆方树上儿子节点的最小值，同样使用
multiset维护。查询时注意细节。点击查看代码
struct node { int nxt,to; }e[200010]; int head[100010],w[200010],dfn[200010],low[100010],fa[200010],siz[200010],dep[200010],son[200010],top[200010],pos[200010],v_dcc=0,cnt=0,tot=0,n; stack<int>s; vector<int>g[200010]; multiset<int>t[200010]; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } void tarjan(int x) { tot++; dfn[x]=low[x]=tot; s.push(x); for(int i=head[x];i!=0;i=e[i].nxt) { if(dfn[e[i].to]==0) { tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); if(dfn[x]==low[e[i].to]) { v_dcc++; g[x].push_back(v_dcc); g[v_dcc].push_back(x); int tmp=0; while(e[i].to!=tmp) { tmp=s.top(); s.pop(); g[tmp].push_back(v_dcc); g[v_dcc].push_back(tmp); } } } else { low[x]=min(low[x],dfn[e[i].to]); } } } void dfs1(int x,int father) { siz[x]=1; fa[x]=father; dep[x]=dep[father]+1; if(x<=n) { t[x].insert(w[x]); } for(int i=0;i<g[x].size();i++) { if(g[x][i]!=father) { dfs1(g[x][i],x); siz[x]+=siz[g[x][i]]; son[x]=(siz[g[x][i]]>siz[son[x]])?g[x][i]:son[x]; if(x>n) { t[x].insert(w[g[x][i]]); } } } } void dfs2(int x,int id) { top[x]=id; tot++; dfn[x]=tot; pos[tot]=x; if(son[x]!=0) { dfs2(son[x],id); for(int i=0;i<g[x].size();i++) { if(g[x][i]!=fa[x]&&g[x][i]!=son[x]) { dfs2(g[x][i],g[x][i]); } } } } struct SMT { struct SegmentTree { int minn; }tree[800010]; #define lson(rt) (rt<<1) #define rson(rt) (rt<<1|1) void pushup(int rt) { tree[rt].minn=min(tree[lson(rt)].minn,tree[rson(rt)].minn); } void build(int rt,int l,int r) { if(l==r) { tree[rt].minn=*t[pos[l]].begin(); return; } int mid=(l+r)/2; build(lson(rt),l,mid); build(rson(rt),mid+1,r); pushup(rt); } void update(int rt,int l,int r,int pos,int val) { if(l==r) { tree[rt].minn=val; return; } int mid=(l+r)/2; if(pos<=mid) { update(lson(rt),l,mid,pos,val); } else { update(rson(rt),mid+1,r,pos,val); } pushup(rt); } int query(int rt,int l,int r,int x,int y) { if(x<=l&&r<=y) { return tree[rt].minn; } int mid=(l+r)/2; if(y<=mid) { return query(lson(rt),l,mid,x,y); } if(x>mid) { return query(rson(rt),mid+1,r,x,y); } return min(query(lson(rt),l,mid,x,y),query(rson(rt),mid+1,r,x,y)); } }T; void update(int x,int y) { t[x].erase(t[x].find(w[x])); t[x].insert(y); T.update(1,1,v_dcc,dfn[x],*t[x].begin()); if(fa[x]!=0) { t[fa[x]].erase(t[fa[x]].find(w[x])); t[fa[x]].insert(y); T.update(1,1,v_dcc,dfn[fa[x]],*t[fa[x]].begin()); } w[x]=y; } int query(int u,int v) { int ans=0x7f7f7f7f; while(top[u]!=top[v]) { if(dep[top[u]]>dep[top[v]]) { ans=min(ans,T.query(1,1,v_dcc,dfn[top[u]],dfn[u])); u=fa[top[u]]; } else { ans=min(ans,T.query(1,1,v_dcc,dfn[top[v]],dfn[v])); v=fa[top[v]]; } } if(dep[u]<dep[v]) { ans=min(ans,T.query(1,1,v_dcc,dfn[u],dfn[v])); if(u>n) { ans=min(ans,*t[fa[u]].begin()); } } else { ans=min(ans,T.query(1,1,v_dcc,dfn[v],dfn[u])); if(v>n) { ans=min(ans,*t[fa[v]].begin()); } } return ans; } int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int m,q,u,v,i; char pd; cin>>n>>m>>q; for(i=1;i<=n;i++) { cin>>w[i]; } for(i=1;i<=m;i++) { cin>>u>>v; add(u,v); add(v,u); } v_dcc=n; tarjan(1); dfs1(1,0); tot=0; dfs2(1,1); T.build(1,1,v_dcc); for(i=1;i<=q;i++) { cin>>pd>>u>>v; if(pd=='C') { update(u,v); } else { cout<<query(u,v)<<endl; } } return 0; }
SP2878 KNIGHTS - Knights of the Round Table
-
若 \(u,v\) 两人之间不相互作用憎恨，则在它们中间连一条边，此时能召开圆桌会议的条件是参加会议的骑士构成了奇环。
-
观察到若两个骑士分属不同的点双连通分量，则他们不可能一起出席会议，故可以只考虑点双连通分量内部的点。
-
进一步挖掘性质，发现若一个点双连通分量内存在奇环，则这个点双连通分量中的所有点都可以被至少一个奇环包含。
- 考虑奇环从某两处断开后得到的两部分长度奇偶性不同即可证明。
点击查看代码
struct node { int nxt,to; }e[2000010]; int head[1010],f[1010][1010],dfn[1010],low[1010],vis[1010],v_dcc=0,cnt=0,tot=0,siz,n; stack<int>s; bitset<1010>ans,ins; void add(int u,int v) { cnt++; e[cnt].nxt=head[u]; e[cnt].to=v; head[u]=cnt; } bool dfs(int x,int col) { vis[x]=col; for(int i=head[x];i!=0;i=e[i].nxt) { if(ins[e[i].to]==1) { if(vis[e[i].to]==0&&dfs(e[i].to,3-col)==false) { return false; } if(vis[e[i].to]==col) { return false; } } } return true; } void tarjan(int x) { tot++; dfn[x]=low[x]=tot; s.push(x); for(int i=head[x];i!=0;i=e[i].nxt) { if(dfn[e[i].to]==0) { tarjan(e[i].to); low[x]=min(low[x],low[e[i].to]); if(dfn[x]==low[e[i].to]) { siz=1; ins.reset(); fill(vis+1,vis+1+n,0); ins[x]=1; int tmp=0; while(e[i].to!=tmp) { tmp=s.top(); s.pop(); ins[tmp]=1; siz++; } if(siz>=3&&dfs(x,0)==false) { ans|=ins; } } } else { low[x]=min(low[x],dfn[e[i].to]); } } } int main() { // #define Isaac #ifdef Isaac freopen("in.in","r",stdin); freopen("out.out","w",stdout); #endif int m,u,v,i,j; while(cin>>n>>m) { if(n==0&&m==0) { break; } else { ans.reset(); fill(e+1,e+1+cnt,(node){0,0}); fill(head+1,head+1+n,0); fill(dfn+1,dfn+1+n,0); fill(low+1,low+1+n,0); for(i=1;i<=n;i++) { fill(f[i]+1,f[i]+1+n,0); } cnt=tot=v_dcc=0; for(i=1;i<=m;i++) { cin>>u>>v; f[u][v]=f[v][u]=1; } for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { if(f[i][j]==0) { add(i,j); add(j,i); } } } for(i=1;i<=n;i++) { if(dfn[i]==0) { tarjan(i); } } cout<<n-ans.count()<<endl; } } return 0; }